A Vehicle Routing Problem with Stochastic Demand

TLDR

The study addresses a stochastic‑demand variant of the classical vehicle routing problem. The goal is to design a priori customer sequences that minimize expected total length using only probabilistic demand information, and to develop heuristics for this task. The authors analyze the stochastic VRP with theoretical methods and develop heuristics, evaluating their worst‑case and average performance via probabilistic analysis. Closed‑form expressions, algorithms, and bounds for expected sequence length were derived, and the proposed approach outperforms re‑optimization strategies in capacitated routing problems.

Abstract

We consider a natural probabilistic variation of the classical vehicle routing problem (VRP), in which demands are stochastic. Given only a probabilistic description of the demand we need to design routes for the VRP. Motivated by applications in strategic planning and distribution systems, rather than resolving the problem when the demand becomes known, we propose to construct an a priori sequence among all customers of minimal expected total length. We analyze the problem using a variety of theoretical approaches. We find closed-form expressions and algorithms to compute the expected length of an a priori sequence under general probabilistic assumptions. Based on these expressions we find upper and lower bounds for the probabilistic VRP and the VRP re-optimization strategy, in which we find the optimal route at every instance. We propose heuristics and analyze their worst case performance as well as their average behavior using techniques from probabilistic analysis. Our results suggest that our approach is a strong and useful alternative to the strategy of re-optimization in capacitated routing problems.