Dynamic Vehicle Routing with Stochastic Requests

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 [13]. In addition, it proposes a least-commitment refinement of MSA (MSA-LC), which also uses stochastic information to delay vehicle departures opportunistically