Improving the Approximation Ratio for Capacitated Vehicle Routing

2020/11/10 by Jannis Blauth, Blauth, Jannis, Vera Traub +3 · 4 citations
Engineering · Social Sciences · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Transportation Planning and Optimization #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.2011.05235

openalex publication_date 2020/11/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We devise a new approximation algorithm for capacitated vehicle routing. Our algorithm yields a better approximation ratio for general capacitated vehicle routing as well as for the unit-demand case and the splittable variant. Our results hold in arbitrary metric spaces. This is the first improvement upon the classical tour partitioning algorithm by Haimovich and Rinnooy Kan and Altinkemer and Gavish.

Cited by

• Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
• An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
• An n^{O(loglog n)} time approximation scheme for capacitated VRP in the Euclidean plane
• Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands

Related

• A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees
• Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
• Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees
• Capacitated Vehicle Routing in Graphic Metrics
• A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing