Tech Report CS-03-10

Dynamic Vehicle Routing with Stochastic Requests

Russell Bent and Pascal Van Hentenryck

June 2003


This paper considers vehicle routing problems (VRP) where customer locations and service times are random variables which are realized dynamically during plan execution. It studies a multiple scenario approach (MSA) which continuously generates plans consistent with past decisions and anticipating future requests, and compares it with the best available heuristics on dynamic VRP problems that model long-distance courier mail services. In addition, it proposes a least-commitment refinement of MSA (MSA-LC), which also uses stochastic information to delay vehicle departures opportunistically. Experimental results shows that MSA, and MSA-LC in particular, may significantly decrease travel times (while not degrading service) and is robust with respect to reasonably noisy distributions.

(complete text in pdf or gzipped postscript)