Metaheuristics Network



	Vehicle Routing with Stochastic Demand Vehicle Routing with Stochastic Demand edited by Leonora Bianchi, IDSIA Contents About the Vehicle Routing Problem with Stochastic Demand Readings Links About the Vehicle Routing Problem with Stochastic Demand Introduction The vehicle routing problem is a classical problem in operation research and it is one of the most challenging combinatorial optimization tasks. Many variations of this problem have been formulated, the main task of the problem being the same: designing the optimal set of routes for a fleet of vehicles in order to serve a given set of customers. The most elementary version of the vehicle routing problem is the capacitated vehicle routing problem (CVRP). The CVRP is described as follows: n customers must be served from a unique depot. Each customer asks for a quantity q_i of goods (i = 1,..., n) and a vehicle of capacity Q is available to deliver goods. Since the vehicle capacity is limited, the vehicle has to periodically return to the depot for reloading. In the CVRP, it is not possible to split customer delivery. Therefore, a CVRP solution is a collection of tours where each customer is visited only once and the total tour demand is at most Q. From a graph theoretical point of view the CVRP may be stated as follows: Let G = (C,L) be a complete graph with node set C = (c_o , c₁, c₂,..., c_n) and arc set L = { (c_i , c_j) : c_i, c_j Î C, i ¹ j}. In this graph model, c_o is the depot and the other nodes are the customers to be served. Each node is associated with a fixed quantity q_i of goods to be delivered (a quantity q_o = 0 is associated to the depot c_o). To each arc (c_i, c_j) is associated a value d_ij representing the distance between c_i and c_j. The goal is to find a set of tours of minimum total distance traveled. Each tour starts from and terminates at the depot c_o , each node c_i (i = 1,..., n) must be visited exactly once, and the quantity of goods to be delivered on a route should never exceed the vehicle capacity Q. The vehicle routing problem with stochastic demand The vehicle routing problem with stochastic demand (VRPSD) is a variation of the CVRP where each customer demand is uncertain, instead of being exactly known a priori. The VRPSD arises in practice whenever a company faces the problem of deliveries to a set of customers, whose demands are uncertain. In this formulation, it is assumed that the demand q_i of customer i is a discrete random variable whose probability distribution is specified by p_{i k} , i.e., the probability that customer i asks for a quantity q_i= k of goods, with k = 0,1,..., K, and K<=Q . In the VRPSD it is also assumed that the actual customer demand is known only when the vehicle arrives at the customer's location. In the deterministic VRP routes are planned in such a way that the vehicle always has enough capacity to satisfy all customers' demands on one of its pre-planned routes. When demands are stochastic, the situation is different. In fact, suppose a vehicle visits customers in a certain pre-planned order. It is possible that at some customer location, where the actual demand is revealed, the vehicle capacity becomes attained or exceeded, and a route failure is said to occur. In such a situation, the vehicle must return to the depot to replenish. The action taken by the vehicle after a route failure depends on the routing strategy that the planner decides to adopt. For example, the simplest strategy is to go back to the customer where demand has not been fully satisfied, and than to proceed visiting other customers in the pre-planned order. In general, also the planning of vehicle routes depends on the strategy that the planner wants to adopt. Whatever strategy is adopted for planning the vehicle routes for the VRPSD, the distance traveled by the vehicle is a random quantity, since the number and location of recurse actions is not known in advance. Indeed, the actual route followed by the vehicle might be in general different from the pre-planned one. The goal, in the VRPSD, is to determine a routing policy such that demand at each customer is met, and the expected distance traveled is minimized. Readings P. Toth and D.Vigo, eds., 2002, The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications. D. Bertsimas. A vehicle routing problem with stochastic demand. Operations Research, 40(3):574--585, 1992. D. Bertsimas, P. Chervi and M. Peterson. Computational approaches to stochastic vehicle routing problems. Transportation Sciences, 29(4):342--352, 1995. D. Bertsimas, P. Jaillet and A. Odoni. A priori optimization. Operations Research, 38:1019--1033, 1990. D. Bertsimas and D. Simchi-Levi. A new generation of vehicle routing research: robust algorithms, addressing uncertainty. Operations Research, 44(2):216--304, 1996. L. Bianchi, L. M. Gambardella and M. Dorigo. An ant colony optimization approach to the probabilistic traveling salesman problem. In Proceedings of PPSN-VII, Seventh International Conference on Parallel Problem Solving from Nature, volume 2439 of Lecture Notes in Computer Science. Springer, Berlin, Germany, 2002. L. Bianchi, L. M. Gambardella and M. Dorigo. Solving the homogeneous probabilistic traveling salesman problem by the ACO metaheuristic. In M. Dorigo, G. Di Caro and M. Sampels, editors, Proceedings of ANTS 2002 -- From Ant Colonies to Artificial Ants: Third International Workshop on Ant Algorithms, volume 2463 of Lecture Notes in Computer Science, pages 176--187. Springer, Berlin, Germany, 2002. J. Bramel and D. Simchi-Levi. The Logic of Logistics. Springer, Berlin, Germany, 1997. T. G. Crainic and G. Laporte. Planning models for freight transportation. European Journal of Operational Research, 97:409--438, 1997. M.Fisher. In O. M. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, editors, Network Routing, chapter Vehicle Routing, pages 1--33. Elsevier, Amsterdam, Holland, 1995. M. Gendreau, G. Laporte, and R. Séguin. An exact algorithm for the vehicle routing problem with stochastic demands and customers. Transportation Sciences, 29(2):143--155, 1995. M. Gendreau, G. Laporte, and R.Séguin. A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Operations Research, 44(3), 1996. B. L. Golden and A.A. Assad, editors. Vehicle Routing: Methods and Studies. Elsevier, Amsterdam, Holland, 1988. M. Haimovitch and A. Rinnooy Kan. Bounds and heuristics for capacitated routing problems. Mathematics of Operations Research, 10:527--542, 1985. P. Jaillet. Probabilistic Traveling Salesman Problems. PhD thesis, MIT, Cambridge, MA, 1985. P. Jaillet. A priori solution of a travelling salesman problem in which a random subset of the customers are visited. Operations Research, 36(6), 1988. P. Jaillet and A. Odoni. In B. L. Golden and A. A. Assad, editors, Vehicle Routing: Methods and Studies, chapter The probabilistic vehicle routing problems. Elsevier, Amsterdam, Holland, 1988. G. Laporte and F. Louveaux. The integer l-shaped method for stochastic integer programs with complete recourse. Operations Research Letters , 33:133--142, 1993. I. Or. Traveling salesman-type combinatorial problems and their relation to the logistics of blood banking . PhD thesis, Department of Industrial Engineering and Management Sciences, Nortwestern University, Evanston, IL, 1976. N. Secomandi. Exact and heuristic dynamic programming algorithms for the vehicle routing problem with stochastic demands . PhD thesis, University of Houston, Texas, 1998. N. Secomandi. A rollout policy for the vehicle routing problem with stochastic demands. Operations Research , 49(5):796--802, 2001. W. Yang, K. Mathur, and R. H. Ballou. Stochastic vehicle routing problem with restocking. Transportation Science , 34(1):99--112, 2000. Links IDSIA introduction to the VRP . Website about the deterministic VRP with VRP variants, instances, solution techniques, best known results, and more.