Games, Heuristics, and Risk Averseness in Vehicle Routing Problems

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.