Stochastic Vehicle Routing Problems

There are many examples of problems in transportation where some elements are uncertain. In the distribution of goods as well as systems responding to calls for emergency, demands typically occur in a random fashion. Transportation systems have thus to be created in face of uncertainty about future levels of demands, making strategic decisions difficult to take. Similarly, traffic conditions vary randomly over time and travel routes are usually designed in face of uncertainty about traffic conditions, hence about effective travel times. Stochastic models, i.e. models that take uncertainty explicitly into account, have thus a central role to play in transportation. In this paper, we first present a number of examples of transportation models and discuss the impact of uncertainty. We then discuss some of the algorithmic approaches, including the Integer L-shaped and the sample Average Approximation method.

François V.Louveaux is director and professor at the Business department of the Business and Economics school in University of Namur, Belgium. He holds a engineering degree both in Electrical and in Industrial Engineering. He also holds a Ph.D. in Industrial Engineering, all from the Catholic University of Louvain, Belgium. He has been associate editor of Operations Research, Mathematical Programming and Operations Research Letters. His research has mainly be devoted to various aspects of stochastic programming. He is the coauthor with John Birge of the book Introduction to Stochastic Programming (Springer-Verlag, 1997).