2026-08-18T17:44:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24200 2025-11-12T13:34:33Z ddc:004 open_access

Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity Zhao, Jingyang Xiao, Mingyu Combinatorial Optimization Capacitated Vehicle Routing Approximation Algorithms Graph Algorithms The Capacitated Vehicle Routing Problem (CVRP) is one of the most extensively studied problems in combinatorial optimization. Based on customer demand, we distinguish three variants of CVRP: unit-demand, splittable, and unsplittable. In this paper, we consider k-CVRP in general metrics and on general graphs, where k is the vehicle capacity. All three versions are APX-hard for any fixed k ≥ 3. Assume that the approximation ratio of metric TSP is 3/2. We present a (5/2 - Θ(√{1/k}))-approximation algorithm for the splittable and unit-demand cases, and a (5/2 + ln 2 - Θ(√{1/k}))-approximation algorithm for the unsplittable case. Our approximation ratio is better than the previous results when k is less than a sufficiently large value, approximately 1.7 x 10⁷. For small values of k, we design independent and elegant algorithms with further improvements. For the splittable and unit-demand cases, we improve the approximation ratio from 1.792 to 1.500 for k = 3, and from 1.750 to 1.500 for k = 4. For the unsplittable case, we improve the approximation ratio from 1.792 to 1.500 for k = 3, from 2.051 to 1.750 for k = 4, and from 2.249 to 2.157 for k = 5. The approximation ratio for k = 3 surprisingly achieves the same value as in the splittable case. Our techniques, such as EX-ITP - an extension of the classic ITP method, have the potential to improve algorithms for other routing problems as well. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jingyang Zhao and Mingyu Xiao 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.93 urn:nbn:de:0030-drops-242008 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.93 eng https://creativecommons.org/licenses/by/4.0/legalcode