6,159 research outputs found
The multi-path Traveling Salesman Problem with stochastic travel costs
No full textGiven a set of nodes, where each pair of nodes is connected by several paths and each path shows a stochastic travel cost with unknown distribution, the multipath Traveling Salesman Problem with stochastic travel costs aims at finding an
expected minimum Hamiltonian tour connecting all nodes. Under a mild assumption on the unknown probability distribution a deterministic approximation of the
stochastic problem is given. The comparison of such approximation with a Montecarlo simulation shows both the accuracy and the eciency of the deterministic approximation, with a mean percentage gap around 2% and a reduction of the computational times of two orders of magnitude
The two-echelon capacitated vehicle routing problem: models and math-based heuristics
No full text Multiechelon distribution systems are quite common in supply-chain and logistics. They are used by public administrations in their transportation and traffic planning strategies, as well as by companies, to model own distribution systems. In the literature, most of the studies address issues relating to the movement of flows throughout the system from their origins to their final destinations. Another recent trend is to focus on the management of the vehicle fleets required to provide transportation among different echelons. The aim of this paper is twofold. First, it introduces the family of two-echelon vehicle routing problems (VRPs), a term that broadly covers such settings, where the delivery from one or more depots to customers is managed by routing and consolidating freight through intermediate depots. Second, it considers in detail the basic version of two-echelon VRPs, the two-echelon capacitated VRP, which is an extension of the classical VRP in which the delivery is compulsorily delivered through intermediate depots, named satellites. A mathematical model for two-echelon capacitated VRP, some valid inequalities, and two math-heuristics based on the model are presented. Computational results of up to 50 customers and four satellites show the effectiveness of the methods developed. </jats:p
A model for the location and sizing of many interlinked health care specialities and some empirical results
No full textThis paper describes in non technical terms a new model, recently developed by the authors, which generalizes in several ways the traditional health care facility location models (Clarke,Wilson,1983; Mayhew,Taket,1980; Tadei, Gallino, Salomone, 1983; Wilson, Clarke, 1982). First, a multi-specialty structure is explicitly introduced,so that bundles of specialties, rather than aggregate hospital beds,are allocated over space. Secondly, patients are introduced in terms of their patient history, that is, each patient is associated with a sequence of stays in and transitions among different specialties and locations. This introduces interactions among all specialties and locations. Third, the evaluation and choice process associated with each patient history is treated as a stochastic multistage decision process, based on nested random utility theory (Bertuglia, Leonardi, Tadei, 1983; De Palma, Ben-Akiva, 1981; Domencich, McFadden, 1975; Leonardi, 1983; Leonardi, Campisi, 1981; Leonardi, Tadei, 1981; McFadden, 1978)
The capacitated transshipment location problem with stochastic handling utilities at the facilities
No full textThe problem consists in finding a transshipment facilities location that maximizes the total net utility when the handling utilities at the facilities are stochastic variables, under supply, demand, and lower and upper capacity constraints. The total net utility is given by the expected total shipping utility minus the total fixed cost of the located facilities. Shipping utilities are given by a deterministic utility for shipping freight from origins to destinations via transshipment facilities plus a stochastic handling utility at the facilities, whose probability distribution is unknown. After giving the stochastic model, by means of some results of the extreme values theory, the probability distribution of the maximum stochastic utilities is derived and the expected value of the optimum of the stochastic model is found. An efficient heuristics for solving real-life instances is also given. Computational results show a very good performance of the proposed methods both in terms of accuracy and efficienc
Modeling the retail system competition
No full textThe retail system is a competitive environment and its transformations have a relevant socio-economic impact. In this context, it is important to represent customer-store interactions, and, to this end, literature mostly proposes logit models. It is well-known that these models present some behavioral and structural anomalies (e.g., the Independence-from-Irrelevant-Alternatives) making them hardly applicable to retail system analysis. In this paper, we show that even some alternative approaches (e.g. Nested-logit or Paired-Combinatorial logit models) do not suitably represent the competition between retail stores, and we present a new modeling framework. It aims at overcoming the above limits by two cooperating logit-based models: the first one analyzes customer-store interactions; the second model uses the interaction information to evaluate the impact of some major transformations. The framework has been integrated in a decision support system and used in real-life cases to determine the impact of new stores in some Italian region
Worst-case analysis for new online bin packing problems
No full textWe consider two new online bin packing problems, the online Variable Cost and Size Bin Packing Problem (o-VCSBPP) and the online Generalized Bin Packing Problem (o-GBPP). We take two well-known bin packing algorithms to address them, the First Fit (FF) and the Best Fit (BF). We show that both algorithms have an asymptotic worst-case ratio bound equal to 2 for the o-VCSBPP and this bound is tight. When there are enough bins of a particular type to load all items, FF and BF also have an absolute worst-case ratio bound equal to 2 for the o-VCSBPP, and this bound is also tight. In addition, we prove that no worst-case ratio bound of FF and BF can be computed for the o-GBPP. Therefore, we consider a natural evolution of these algorithms, the First Fit with Rejection and the Best Fit with Rejection, able to reject inconvenient bins at the end of the process. Similarly, we prove that no worst-case ratio of these algorithms can be computed for the o-GBPP. Finally, we give sucient conditions under which algorithms do not admit any performance ratio, and conclude that the worst-case results obtained for the o-VCSBPP and the o-GBPP also hold for the oine variant of these two problem
The three-dimensional knapsack problem with balancing constraints
No full textTech. Rep. CIRRELT 2011-51, CIRRELT, Montreal, Canad
- …
