## Vehicle Routing with Stochastic Demandedited by Leonora Bianchi, IDSIA ## Contents## About the Vehicle Routing Problem with Stochastic Demand## IntroductionThe 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 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 ## The vehicle routing problem with stochastic demandThe 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 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 ## 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.
| |

Network Coordinator: Marco Dorigo e-mail: mdorigo@ulb.ac.be Web site responsibles: Christian Blum and Max Manfrin |