Tech Report CS-02-08

Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers

Russell W. Bent and Pascal Van Hentenryck

July 2002

Abstract:

Multiple vehicle routing with time windows (VRPTW) is a hard and extensively studied combinatorial optimization problem. This paper considers a dynamic VRPTW with stochastic customers, where the goal is to maximize the number of serviced customers. It presents a multiple scenario approach (MSA) which continuously generates routing plans for scenarios including known and future requests. Decisions during execution uses a distinguished plan chosen, at each decision, by a consensus function. The approach was evaluated on vehicle routing problems adapted from the Solomon benchmarks with a degree of dynamism varying between 30% and 80%. They indicate that MSA exhibits dramatic improvements over approaches not exploiting stochastic information, that the use of consensus function improves the quality of the solutions significantly, and that the benefits of MSA increases with the (effective) degree of dynamism.