Tech Report CS-03-10
Dynamic Vehicle Routing with Stochastic Requests
Russell Bent and Pascal Van Hentenryck
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.