Improved algorithm for vehicle route planning cuts costs by better client coverage
Improved Approximation for Unsplittable CVRP via a Greedy Approach
Data Structures and Algorithms
Summary
The paper addresses the problem of planning routes for vehicles that must deliver goods to customers without splitting their deliveries. The authors propose a new method that carefully balances the cost of each delivery route with how well high-demand customers are served. Building on previous approaches, their technique makes smarter choices about routing and grouping customers, leading to routes that are less costly overall. This helps companies organize delivery trips more efficiently when vehicles have limited capacity.
What this means in practice
- •For logistics planners: Generate delivery routes that better handle customers with large orders while controlling overall transport cost.
- •For supply chain managers: Optimize vehicle loads and routes for fixed-capacity fleets to reduce transportation expense and improve service reliability.
Authors
Daniel Ebert, Leonard Weismantel
Abstract
We devise a polynomial-time $3.159$-approximation algorithm for the metric unsplittable Capacitated Vehicle Routing Problem. We build on the Relative Greedy Algorithm suggested by Traub (2025), which can be considered as a variant of the LP rounding algorithm of Friggstad, Mousavi, Rahgoshay, and Salavatipour (2025). Our main ingredient is the Average Greedy Algorithm, a new algorithm that controls both tour costs and the coverage of clients with high demand. This additional control enables a sharper averaging argument for the cost of subsequent greedy choices. Similarly to Zhao and Xiao (2026), combining the Average Greedy with variants of tour partitioning and a matching algorithm yields the final approximation guarantee.