Games, Heuristics, and Risk Averseness in Vehicle Routing Problems
Publication: Journal of Urban Planning and Development
Volume 130, Issue 1
Abstract
For many freight carriers, uncertainty about travel times (or more generally, about travel costs) is a pervasive aspect of routing and scheduling. As the impact of an unforeseen delay on costs can be substantial, freight carriers will often wish to know which links are critical and what routes and schedules are less risky in cost terms. This paper concentrates on low probability, high consequence incidents whose probabilities are in practice unknown. The dispatcher therefore seeks a risk-averse routing and scheduling strategy. A game theoretic approach developed for transport network reliability is applied to the vehicle routing problem. Underlying this approach is the formulation of a maximin problem, whereby expected cost is minimized with respect to link use frequencies and maximized with respect to failure probabilities. A method of successive averages scheme allows the use of industry standard routing and scheduling software.
Get full access to this article
View all available purchase options and get full access to this article.
References
Boffey, T. B. (1982). Graph theory in operations research, MacMillan, Basingstoke, U.K.
Clarke, G., and Wright, J.(1963). “Scheduling of vehicles from a central depot to a number of delivery points.” Oper. Res., 11, 568–581.
Dror, M., Laporte, G., and Trudeau, P.(1989). “Vehicle routing with stochastic demands: Properties and solution frameworks.” Transp. Sci., 23, 166–176.
Gendreau, M., Laporte, G., and Potvin, J.-Y. (1997). “Vehicle routing: Modern heurisitics.” Local search in combinatorial optimisation, E. Aarts and J. K. Lenstra, eds., Wiley New York, 311–336.
Gendreau, M., Laporte, G., and Seguin, R.(1996). “Stochastic vehicle routing.” Eur. J. Oper. Res., 88, 3–12.
Hillier, F. S., and Lieberman, G. J. (1990). Introduction to operations research, McGraw-Hill, New York.
Jaillet, P., and Odoni, A. R. (1988). “The probabilistic vehicle routing problem.” Vehicle routing: Methods and studies, B. L. Golden and A. A. Assad, eds., North-Holland, Amsterdam, 293–318.
Laporte, G., Louveaux, F. V., and Mercure, H.(1992). “The vehicle routing problem with stochastic travel times.” Transp. Sci., 26, 161–170.
Powell, W. B., Jailllet, P., and Odoni, A. R. (1995). “Stochastic and dynamic network and routing.” Network routing, M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, eds., North-Holland, Amsterdam, 141–295.
Taniguchi, E., Yamada, T., and Tamagawa, D. (2000). “Probabilistic routing and scheduling of urban pickup/delivery trucks with variable travel times.” Reliability of transport networks, M. G. H. Bell and C. Cassir, eds., Research Studies Press, Hertfordshire, U.K.
Information & Authors
Information
Published In
Copyright
Copyright © 2004 American Society of Civil Engineers.
History
Received: Apr 24, 2002
Accepted: Nov 20, 2002
Published online: Feb 19, 2004
Published in print: Mar 2004
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.