Improved approximation methods for vehicle routing with uncertain deliveries
Tight Approximations for Fixed-Order Vehicle Routing with Stochastic Demands
Data Structures and Algorithms
Summary
This paper looks at the problem of planning routes for delivery vehicles when customer demands are uncertain and only revealed upon visiting. The authors improve previous methods for deciding the order of deliveries and how to replenish supplies by using a special mathematical approach, achieving better accuracy and guaranteed near-optimal performance. They also show these new results are the best possible under general conditions. Their approach works not only for uncertain demands but also improves routes when demands are known in advance.
What this means in practice
- •For logistics planners: Generate delivery routes that efficiently handle uncertain customer demands while minimizing restocking trips and cost.
- •For supply chain managers: Improve inventory restocking decisions by predicting demand distributions and incorporating them into fixed delivery schedules.
Authors
Jingyang Zhao, Mingyu Xiao
Abstract
We study the vehicle routing problem (VRP) with stochastic demands, where each client has an independent demand with a known distribution, and its realized demand is observed only on the first visit. We consider a priori and restocking policies that fix the client order before observing demands and serve each client's entire demand before first visiting the next. Gupta, Nagarajan, and Ravi (Oper. Res., 2012) developed randomized a priori $(α+1)$-approximation and $(α+2)$-approximation algorithms for splittable and unsplittable deliveries, respectively, where $α$ is the approximation ratio of a metric traveling salesman problem (TSP) algorithm. We improve these approximation ratios to $2$ and $3$ by using their replenishment rules with a TSP tour constructed via matroid parity. We also obtain deterministic a priori $(2+\varepsilon)$-approximation and $(3+\varepsilon)$-approximation algorithms by compressing the distributions of cumulative demands to select an initial stock in polynomial time. All guarantees are relative to the general adaptive optimum. We then establish matching lower bounds of $2$ and $3$ that hold even for the more general class of randomized restocking policies. Finally, we apply our matroid-parity construction to improve approximation ratios for several VRP variants with deterministic demands.