Improved Approximations for a CVRP with Unsplittable Demands

References

• [1] Adamaszek A, Czumaj A, Lingas A (2009) PTAS for k-tour cover problem on the plane for moderately large values of k. Dong Y, Du DZ, Ibarra O, eds. Algorithms Comput. ISAAC 2009, Lecture Notes in Computer Science, vol. 5878 (Springer, Berlin, Heidelberg), 994–1003.Google Scholar
• [2] Altinkemer K, Gavish B (1987) Heuristics for unequal weight delivery problems with a fixed error guarantee. Oper. Res. Lett. 6(4):149–158.Crossref, Google Scholar
• [3] Arora S (1998) Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5):753–782.Crossref, Google Scholar
• [4] Asano T, Katoh N, Tamaki H, Tokuyama T (1997) Covering points in the plane by k-tours: Towards a polynomial time approximation scheme for general k. Proc. 29th ACM Sympos. Theory Comput (STOC) (Association for Computing Machinery, New York), 275–283.Google Scholar
• [5] Becker A (2018) A tight 4/3 approximation for capacitated vehicle routing in trees. Approximation Randomization Combin. Optim. Algorithms Tech. (APPROX/RANDOM 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 116 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 3:1–3:15.Google Scholar
• [6] Becker A, Paul A (2019) A framework for vehicle routing approximation schemes in trees. Friggstad Z, Sack JR, Salavatipour M, eds. Algorithms Data Structures. WADS 2019, Lecture Notes in Computer Science, vol. 11646 (Springer, Cham, Switzerland), 112–125.Google Scholar
• [7] Becker A, Klein PN, Saulpic D (2017) A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs. 25th Annual Eur. Sympos. Algorithms (ESA), Leibniz International Proceedings in Informatics (LIPIcs), vol. 87 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 12:1–12:15.Google Scholar
• [8] Becker A, Klein PN, Saulpic D (2018) Polynomial-time approximation schemes for k-center, k-median, and capacitated vehicle routing in bounded highway dimension. 26th Annual Eur. Sympos. Algorithms (ESA 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 112 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 8:1–8:15.Google Scholar
• [9] Becker A, Klein PN, Schild A (2019) A PTAS for bounded-capacity vehicle routing in planar graphs. Friggstad Z, Sack J-R, Salavatipour MR, eds. Algorithms Data Structures: 16th Internat. Sympos. (WADS) (Springer-Verlag, Berlin, Heidelberg), 99–111.Google Scholar
• [10] Blauth J, Traub V, Vygen J (2023) Improving the approximation ratio for capacitated vehicle routing. Math. Programming 197(2):451–497.Crossref, Google Scholar
• [11] Bompadre A, Dror M, Orlin JB (2006) Improved bounds for vehicle routing solutions. Discrete Optim. 3(4):299–316.Crossref, Google Scholar
• [12] Cohen-Addad V, Filtser A, Klein PN, Le H (2020) On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs. 61st IEEE Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 589–600.Google Scholar
• [13] Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management Sci. 6(1):80–91.Link, Google Scholar
• [14] Das A, Mathieu C (2015) A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica 73(1):115–142.Crossref, Google Scholar
• [15] Gabow HN (1976) An efficient implementation of Edmonds’ algorithm for maximum matching on graphs. J. ACM 23(2):221–234.Crossref, Google Scholar
• [16] Golden BL, Wong RT (1981) Capacitated arc routing problems. Networks 11(3):305–315.Crossref, Google Scholar
• [17] Haimovich M, Kan AHGR (1985) Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4):527–542.Link, Google Scholar
• [18] Hamaguchi S, Katoh N (1998) A capacitated vehicle routing problem on a tree. Chwa KY, Ibarra OH, eds. Algorithms and Comput. ISAAC 2009, Lecture Notes in Computer Science, vol. 1533 (Springer, Berlin, Heidelberg), 399–407.Google Scholar
• [19] Jayaprakash A, Salavatipour MR (2022) Approximation schemes for capacitated vehicle routing on graphs of bounded treewidth, bounded doubling, or highway dimension. Naor J, Buchbinder N, eds. Proc. 2022 ACM-SIAM Sympos. Discrete Algorithms (SODA 2022) (Society for Industrial and Applied Mathematics, Philadelphia), 877–893.Google Scholar
• [20] Khachay M, Dubinin R (2016) PTAS for the Euclidean capacitated vehicle routing problem in Rd. Kochetov Y, Khachay M, Beresnev V, Nurminski E, Pardalos P, eds. Discrete Optim. Oper. Res. DOOR 2016, Lecture Notes in Computer Science, vol. 9869 (Springer, Cham, Switzerland), 193–205.Google Scholar
• [21] Khachay M, Ogorodnikov Y (2020) QPTAS for the CVRP with a moderate number of routes in a metric space of any fixed doubling dimension. Kotsireas I, Pardalos P, eds. Learn. Intelligent Optim. LION 2020, Lecture Notes in Computer Science, vol. 12096 (Springer, Cham, Switzerland), 27–32.Google Scholar
• [22] Khachay M, Ogorodnikov Y, Khachay D (2020) An extension of the Das and Mathieu QPTAS to the case of polylog capacity constrained CVRP in metric spaces of a fixed doubling dimension. Kononov A, Khachay M, Kalyagin V, Pardalos P, eds. Math. Optim. Theory Oper. Res. MOTOR 2020, Lecture Notes in Computer Science, vol. 12095 (Springer, Cham, Switzerland), 49–68.Google Scholar
• [23] Labbé M, Laporte G, Mercure H (1991) Capacitated vehicle routing on trees. Oper. Res. 39(4):616–622.Link, Google Scholar
• [24] Mathiue C, Zhou H (2023) A PTAS for capacitated vehicle routing on trees. ACM Transactions on Algorithms, vol. 19(2) (Association for Computing Machinery, New York), 1–28.Google Scholar
• [25] Papadimitriou CH, Yannakakis M (1993) The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1):1–11.Link, Google Scholar
• [26] Tröbst T (2019) Capacitated vehicle routing and cycle covering problems. Unpublished master’s thesis, University of Bonn, Bonn, Germany.Google Scholar