Chapter 7

Robust Vehicle Routing

Fernando Ordóñez
Industrial and Systems Engineering Department, University of Southern California, Los Angeles, California 90089, and Industrial Engineering Department, University of Chile, Santiago, Chile, fordon@usc.edu

Abstract
Vehicle routing problems in many industrial applications must take into account uncertain demand, traffic conditions, and/orservice times. In this tutorial we present recent work on the use of the robust optimization methodology for the vehicle routing problem (VRP) under uncertainty. We outline different robust VRP models, depending on the source of the uncertainty (costs, demand, time, customers), VRP formulation, and correlation between uncertain coefficients. Furthermore, we discuss previous computational results that illustrate when such a robust model is convenient and when it is not. We then focus on using robust optimization to find a routing plan for a stochastic VRP that takes into account that routes will be adapted to the outcome of the uncertainty. We report that the use of robust optimization to find routing plans for two applications (routing in large scale emergencies and a courier delivery problem) leads to encouraging solutions.

Key words: vehicle routing problem; uncertainty; robust optimization

Download Chapter 7 - Password-protected content.

The 2010 volume of the TutORials in Operations Research series will be available to people who have registered for the 2010 INFORMS Annual Meeting. All INFORMS members will be able to access TutORials after January 1, 2011. Printed TutORials books from this and previous years can also be ordered here, along with CDs from 2005 to 2009.

For login instructions click here.

________________________________________________

Citation Information:

Ordóñez, F. 2010. Robust Vehicle Routing. J. J. Hasenbein, ed. INFORMS TutORials in Operations Research, Vol. 7. INFORMS, Hanover, MD, pp. 153–178.