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

TLDR

The multiple vehicle routing problem with time windows (VRPTW) is a hard and extensively studied combinatorial optimization problem. This paper considers a dynamic VRPTW with stochastic customers, aiming to maximize the number of serviced customers. The authors propose a multiple scenario approach that continuously generates routing plans for scenarios with known and future requests, selecting a distinguished plan at each decision point via a consensus function, and evaluate it on Solomon benchmark instances with 30–80% dynamism. Results show that the multiple scenario approach yields dramatic improvements over non‑stochastic methods, that the consensus function significantly enhances solution quality, and that benefits grow with the degree of dynamism.

Abstract

The multiple vehicle routing problem 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) that continuously generates routing plans for scenarios including known and future requests. Decisions during execution use 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 increase with the (effective) degree of dynamism.