pith. sign in

arxiv: 2306.01826 · v5 · submitted 2023-06-02 · 💻 cs.DS · cs.DM

Approximation Algorithms for Capacitated Vehicle Routing Problems: A Comprehensive Survey

Yongyu Chen This is my paper

Pith reviewed 2026-05-24 08:14 UTC · model grok-4.3

classification 💻 cs.DS cs.DM
keywords capacitated vehicle routingapproximation algorithmssurveyiterated tour partitioningPTASmetric spacescombinatorial optimizationNP-hard problems
0
0 comments X

The pith

This survey organizes the main approximation frameworks for the capacitated vehicle routing problem and records the best known performance ratios.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper first defines the CVRP and its variants, then traces the sources of its computational hardness. It examines three main lines of work: the iterated tour partitioning framework and its refinements, polynomial-time approximation schemes that apply in Euclidean and other geometric spaces, and specialized algorithms that exploit structure in trees, planar graphs, and graphs of bounded highway dimension. A reader would care because the problem appears in logistics planning where exact solutions are intractable and provable guarantees are needed to judge practical methods. The survey closes by listing the strongest ratios achieved to date and the main open questions that remain.

Core claim

The paper provides a systematic overview of CVRP approximation algorithms by defining the problem and its variants, analyzing the iterated tour partitioning framework together with its later improvements, describing the development of PTAS and QPTAS for geometric instances, and presenting algorithms for structured graphs that rely on metric embeddings and linear-programming relaxations, while collecting the current best approximation ratios across settings and enumerating the principal open problems.

What carries the argument

The Iterated Tour Partitioning (ITP) framework, which begins with a traveling-salesman tour and divides it into capacity-respecting vehicle routes.

If this is right

  • The iterated tour partitioning framework yields a constant-factor approximation for general metric CVRP.
  • Polynomial-time approximation schemes exist for CVRP when the underlying space is Euclidean of fixed dimension.
  • Better ratios are obtainable when the input graph is a tree, planar, or has bounded highway dimension.
  • Several gaps between known upper and lower bounds on approximability remain unresolved.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The survey indicates that progress has moved from uniform guarantees in arbitrary metrics toward exploiting geometric and topological structure.
  • New work could test whether the listed ratios remain competitive when demands or capacities are drawn from real-world distributions rather than worst-case instances.
  • The open problems identified suggest that closing the gap for general metrics may require new embedding or partitioning techniques.

Load-bearing premise

The collection of results on iterated tour partitioning, geometric approximation schemes, and algorithms for structured graphs accurately and exhaustively represents the state of CVRP approximation research.

What would settle it

Publication of a CVRP approximation algorithm with a ratio strictly better than any ratio listed in the survey, or discovery of a major framework omitted from the review.

read the original abstract

The Capacitated Vehicle Routing Problem (CVRP) is a core NP-hard problem in the field of combinatorial optimization. It aims to plan optimal routes for a fleet of vehicles with uniform capacity, serving a set of customers with specific demands from a single depot, while minimizing the total travel distance. Due to its extensive applications in logistics, distribution, and supply chain management, CVRP has attracted significant research attention. Theoretically, the problem has been proven to be APX-hard, and in general metric spaces, approximate solutions of arbitrary precision cannot be obtained unless P=NP. These inherent complexities highlight the importance of developing approximation algorithms-finding solutions with provable performance guarantees in polynomial time. This paper aims to provide a systematic and comprehensive survey of the research progress on CVRP approximation algorithms. The paper first strictly defines CVRP and its key variants, and elucidates the sources of its fundamental computational complexity. Subsequently, the article deeply analyzes the core algorithmic frameworks and technical schools of thought in this field, including: the Iterated Tour Partitioning (ITP) framework that laid the foundation of the field and its latest improvements; the evolution of approximation schemes (PTAS/QPTAS) for geometric spaces such as Euclidean space; and modern algorithms for structured graphs like trees, planar graphs, and graphs with bounded highway dimension, with a particular focus on techniques based on metric embedding and linear programming relaxation. Finally, this paper summarizes the current best approximation ratios for various problem settings and systematically outlines the core unresolved open problems in the field, pointing out directions for future research.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper claims to deliver a systematic and comprehensive survey of approximation algorithms for the Capacitated Vehicle Routing Problem (CVRP) and its variants. It defines the problem, establishes its APX-hardness in general metrics, reviews the Iterated Tour Partitioning (ITP) framework and subsequent improvements, traces the development of PTAS/QPTAS results in Euclidean and geometric settings, presents algorithms for structured graphs (trees, planar graphs, bounded highway dimension) via metric embeddings and LP relaxations, tabulates current best approximation ratios, and enumerates open problems.

Significance. If the coverage is accurate and exhaustive, the survey would consolidate a fragmented literature on CVRP approximation, providing a single reference for best-known ratios across settings and highlighting research gaps. This could accelerate progress in combinatorial optimization by clarifying the state of ITP-based methods, geometric schemes, and embedding techniques for structured instances.

major comments (1)
  1. [Abstract] Abstract: the central claim that the survey is 'systematic and comprehensive' and that it covers 'the latest improvements' to ITP, 'the evolution of approximation schemes for geometric spaces', and 'modern algorithms for structured graphs' is load-bearing but unsupported by any stated methodology (search strategy, databases, inclusion criteria, or cutoff date). Without such details, material omissions of high-impact results cannot be ruled out, undermining the exhaustiveness assertion.
minor comments (1)
  1. [Abstract] Abstract: the phrase 'strictly defines CVRP and its key variants' would benefit from an explicit list of the variants treated (e.g., whether split deliveries, time windows, or heterogeneous fleets are included).

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed review and for highlighting this important point regarding the presentation of our survey methodology. We address the comment below and will make the requested clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the survey is 'systematic and comprehensive' and that it covers 'the latest improvements' to ITP, 'the evolution of approximation schemes for geometric spaces', and 'modern algorithms for structured graphs' is load-bearing but unsupported by any stated methodology (search strategy, databases, inclusion criteria, or cutoff date). Without such details, material omissions of high-impact results cannot be ruled out, undermining the exhaustiveness assertion.

    Authors: We agree that the abstract and introduction do not explicitly describe the literature review process. The survey was compiled by systematically tracing the development of the field through the key papers that established the ITP framework, subsequent ratio improvements, PTAS/QPTAS results in Euclidean and geometric settings, and embedding/LP-based methods for structured graphs (trees, planar graphs, bounded highway dimension), drawing on the authors' expertise and cross-referencing citations from foundational works up to the paper's submission date. However, to strengthen the claim of being systematic, we will revise the manuscript by adding a short subsection (likely in Section 1 or a new preliminary section) that states the scope, primary sources (arXiv, conference proceedings in STOC/FOCS/SODA/ICALP, and key journals), search approach via citation chaining from seminal results, and the effective cutoff date of early 2023. This addition will make the coverage criteria transparent without altering the technical content. revision: yes

Circularity Check

0 steps flagged

Survey paper with no internal derivations or self-referential reductions

full rationale

This is a literature survey summarizing external results on CVRP approximation algorithms (ITP frameworks, PTAS/QPTAS for geometric spaces, algorithms for trees/planar/bounded-highway-dimension graphs). The abstract and described structure contain no equations, predictions, fitted parameters, or new claims that could reduce to self-definition, self-citation chains, or renaming of known results. All technical content is attributed to prior literature; the 'systematic and comprehensive' phrasing is a scope statement about coverage rather than a derived quantity. No load-bearing step matches any enumerated circularity pattern.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is a survey paper that introduces no new mathematical claims, so it adds no free parameters, axioms, or invented entities.

pith-pipeline@v0.9.0 · 5804 in / 961 out tokens · 36505 ms · 2026-05-24T08:14:33.655364+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages · 2 internal anchors

  1. [1]

    Arora, S. (2003). Approximation schemes for NP-hard geometric optimization problems: A survey. Mathematical Programming, 97(1), 43- 69

    work page 2003

  2. [2]

    Bern, M., & Eppstein, D. (1997). Approximation algo rithms for geometric problems. Approximation algorithms for NP -hard problems, 296-345

    work page 1997

  3. [3]

    B., & Ramser, J

    Dantzig, G. B., & Ramser, J. H. (1959). The truck d ispatching problem. Management science, 6(1), 80-91

    work page 1959

  4. [4]

    Christofides, N. (1976). Worst-case analysis of a n ew heuristic for the travelling salesman problem. Carnegie-Mellon Univ P ittsburgh Pa Management Sciences Research Group

    work page 1976

  5. [5]

    van Bevern, R., & Slugina, V. A. (2020). A historic al note on the 3/2- approximation algorithm for the metric traveling sa lesman problem. Historia Mathematica, 53, 118-127

    work page 2020

  6. [6]

    R., Klein, N., & Gharan, S

    Karlin, A. R., Klein, N., & Gharan, S. O. (2021, Ju ne). A (slightly) improved approximation algorithm for metric TSP. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Compu ting (pp. 32-45)

    work page 2021

  7. [7]

    Haimovich, M., & Rinnooy Kan, A. H. (1985). Bounds and heuristics for capacitated routing problems. Mathematics of operations Research, 10(4), 527-542

    work page 1985

  8. [8]

    Arora, S., Lund, C., Motwani, R., Sudan, M., & Szeg edy, M. (1992). Proof verification and intractability of approximat ion algorithms. In Proceedings of the IEEE Symposium on the Foundation s of Computer Science (Vol. 10)

    work page 1992

  9. [9]

    Arora, S. (1998). Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Jo urnal of the ACM (JACM), 45(5), 753-782

    work page 1998

  10. [10]

    Asano, T., Katoh, N., & Kawashima, K. (2001). A new approximation algorithm for the capacitated vehicle routing probl em on a tree. Journal of Combinatorial Optimization, 5(2), 213-231

    work page 2001

  11. [11]

    (1 997, May)

    Asano, T., Katoh, N., Tamaki, H., & Tokuyama, T. (1 997, May). Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (pp. 275-283)

    work page

  12. [12]

    Becker, A. (2018). A tight 4/3 approximation for ca pacitated vehicle routing in trees. arXiv preprint arXiv:1804.08791, unpublished

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  13. [13]

    Hassin, R., & Rubinstein, S. (2005). On the complexity of the k-customer vehicle routing problem. Operations Research Letters, 33(1), 71-76

    work page 2005

  14. [14]

    Hu, Y. (2009). Approximation algorithms for the cap acitated vehicle routing problem

    work page 2009

  15. [15]

    (2010, January)

    Das, A., & Mathieu, C. (2010, January). A quasi-pol ynomial time approximation scheme for Euclidean capacitated vehi cle routing. In Proceedings of the twenty-first annual ACM-SIAM sym posium on Discrete Algorithms (pp. 390-403). Society for Indu strial and Applied Mathematics

    work page 2010

  16. [16]

    Adamaszek, A., Czumaj, A., & Lingas, A. (2010). PTAS for k-tour cover problem on the plane for moderately large values of k. International Journal of Foundations of Computer Science, 21(06), 893-904

    work page 2010

  17. [17]

    Khachay, M., & Zaytseva, H. (2015). Polynomial Time Approximation Scheme for the Euclidean Capacitated Vehicle Routin g Problem. In International Conference on Control, Automation and Artificial Intelligence (CAAI) (pp. 43-47). DEStech Publications, Inc

    work page 2015

  18. [18]

    Polynomial-Time Approximation Schemes for k-Center and Bounded-Capacity Vehicle Routing in Graphs with Bounded Highway Dimension

    Becker, A., Klein, P. N., & Saulpic, D. (2017). Pol ynomial-Time Approximation Schemes for k-Center and Bounded-Capa city Vehicle Routing in Graphs with Bounded Highway Dimension. a rXiv preprint arXiv:1707.08270, in press

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  19. [19]

    (2019, June)

    Khachay, M., & Ogorodnikov, Y. (2019, June). Approx imation scheme for the capacitated vehicle routing problem with time windows and non- uniform demand. In Mathematical Optimization Theory and Operations Research: 18th International Conference, MOTOR 2019 , Ekaterinburg, Russia, July 8-12, 2019, Proceedings (pp. 309-327). Cham: Springer International Publishing

    work page 2019

  20. [20]

    (2019, January)

    Khachay, M., & Ogorodnikov, Y. (2019, January). Improved polynomial time approximation scheme for capacitated vehicle routing problem with time windows. In Optimization and Applications: 9th International Conference, OPTIMA 2018, Petrovac, Montenegro, October 1–5, 2018, Revised Selected Papers (pp. 155-169). Cham: Spring er International Publishing

    work page 2019

  21. [21]

    Y., & Ogorodnikov, Y

    Khachai, M. Y., & Ogorodnikov, Y. Y. (2019). Polyno mial-time approximation scheme for the capacitated vehicle ro uting problem with time windows. Proceedings of the Steklov Institute of Mathematics, 307(Suppl 1), 51-63

    work page 2019

  22. [22]

    N., & Schild, A

    Becker, A., Klein, P. N., & Schild, A. (2019). A PT AS for bounded- capacity vehicle routing in planar graphs. In Algor ithms and Data Structures: 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings 16 (pp. 99-11 1). Springer International Publishing

    work page 2019

  23. [23]

    Becker, A., & Paul, A. (2019). A framework for vehi cle routing approximation schemes in trees. In Algorithms and Data Structures: 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings 16 (pp. 112-125). Springer I nternational Publishing

    work page 2019

  24. [24]

    Y., & Ogorodnikov, Y

    Khachay, M. Y., & Ogorodnikov, Y. Y. (2020, July). Efficient approximation of the capacitated vehicle routing pr oblem in a metric space of an arbitrary fixed doubling dimension. In Doklady Mathematics (Vol. 102, pp. 324-329). Pleiades Publishing

    work page 2020

  25. [25]

    Svensson, O., Tarnawski, J., & Végh, L. A. (2020). A constant-factor approximation algorithm for the asymmetric traveling salesman problem. Journal of the ACM (JACM), 67(6), 1-53

    work page 2020

  26. [26]

    Y., & Khachay, M

    Ogorodnikov, Y. Y., & Khachay, M. Y. (2021). Approx imation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension. Computat ional Mathematics and Mathematical Physics, 61, 1194-1206

    work page 2021

  27. [27]

    Friggstad, Z., Mousavi, R., Rahgoshay, M., & Salavatipour, M. R. (2021). Improved approximations for CVRP with unsplittable demands. arXiv preprint arXiv:2111.08138, unpublished

    work page arXiv 2021

  28. [28]

    Mathieu, C., & Zhou, H. (2021). Probabilistic analy sis of Euclidean capacitated vehicle routing. arXiv preprint arXiv:2 109.06958, unpublished

    work page 2021

  29. [29]

    Zhao, J., & Xiao, M. (2022). Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity. ar Xiv preprint arXiv:2210.16534, unpublished

    work page arXiv 2022

  30. [30]

    Grandoni, F., Mathieu, C., & Zhou, H. (2022). Unspl ittable Euclidean Capacitated Vehicle Routing: A $(2+\epsilon) $-Appr oximation Algorithm. arXiv preprint arXiv:2209.05520, in press

    work page arXiv 2022

  31. [31]

    Mathieu, C., & Zhou, H. (2022). A tight (1. 5+ ϵ)-a pproximation for unsplittable capacitated vehicle routing on trees. arXiv preprint arXiv:2202.05691, in press

    work page arXiv 2022

  32. [32]

    Mathieu, C., & Zhou, H. (2023). A PTAS for capacitated vehicle routing on trees. ACM Transactions on Algorithms, 19(2), 1-28

    work page 2023

  33. [33]

    Heine, O. F. C., Demleitner, A., & Matuschke, J. (2 023). Bifactor approximation for location routing with vehicle and facility capacities. European Journal of Operational Research, 304(2), 429-442

    work page

  34. [34]

    Jayaprakash, A., & Salavatipour, M. R. (2023). Appr oximation schemes for capacitated vehicle routing on graphs of bounded treewidth, bounded doubling, or highway dimension. ACM Transactions on Algorithms, 19(2), 1-36

    work page 2023

  35. [35]

    Blauth, J., Traub, V., & Vygen, J. (2023). Improvin g the approximation ratio for capacitated vehicle routing. Mathematical Programming, 197(2), 451-497

    work page 2023

  36. [36]

    Nie, Z., & Zhou, H. (2023). Euclidean Capacitated V ehicle Routing in Random Setting: A $1.55 $-Approximation Algorithm. arXiv preprint arXiv:2304.11281, unpublished

    work page arXiv 2023

  37. [37]

    Mömke, T., & Zhou, H. (2023). Capacitated Vehicle Routing in Graphic Metrics. In Symposium on Simplicity in Algorithms ( SOSA) (pp. 114- 123). Society for Industrial and Applied Mathematics

    work page 2023

  38. [38]

    N., & Le, H

    Cohen-Addad, V., Filtser, A., Klein, P. N., & Le, H . (2020, November). On light spanners, low-treewidth embeddings and eff icient traversing in minor-free graphs. In 2020 IEEE 61st Annual Symposi um on Foundations of Computer Science (FOCS) (pp. 589-600). IEEE

    work page 2020

  39. [39]

    Cohen-Addad, V., Le, H., Pilipczuk, M., & Pilipczuk, M. (2023). Planar and Minor-Free Metrics Embed into Metrics of Polylo garithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1. arXiv preprint arXiv:2304.07268, unpublished

    work page arXiv 2023

  40. [40]

    (2023, May 22)

    Wikimedia Foundation. (2023, May 22). Christofides algorithm. Wikipedia. https://en.wikipedia.org/wiki/Christofid es algorithm, unpublished

    work page 2023

  41. [41]

    Michael, K. (n.d.). Approximability of the D-dimens ional euclidean capacitated vehicle… https://nnov.hse.ru/data/2017/05/12/1171275833/Lecture-2.pdf, unpublished

    work page 2017