{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:14:39Z","timestamp":1781345679895,"version":"3.54.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,6,14]],"date-time":"2022-06-14T00:00:00Z","timestamp":1655164800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,14]],"date-time":"2022-06-14T00:00:00Z","timestamp":1655164800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"crossref","award":["200021_184622"],"award-info":[{"award-number":["200021_184622"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 (Math Oper Res 10:527\u2013542, 1985) and Altinkemer and Gavish (Oper Res Lett 6:149\u2013158, 1987).\n\n<\/jats:p>","DOI":"10.1007\/s10107-022-01841-4","type":"journal-article","created":{"date-parts":[[2022,6,14]],"date-time":"2022-06-14T14:10:50Z","timestamp":1655215850000},"page":"451-497","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Improving the approximation ratio for capacitated vehicle routing"],"prefix":"10.1007","volume":"197","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5181-802X","authenticated-orcid":false,"given":"Jannis","family":"Blauth","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vera","family":"Traub","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,6,14]]},"reference":[{"key":"1841_CR1","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1142\/S0129054110007623","volume":"21","author":"A Adamaszek","year":"2010","unstructured":"Adamaszek, A., Czumaj, A., Lingas, A.: PTAS for $$k$$-tour cover problem on the plane for moderately large values of $$k$$. Int. J. Found. Comput Sci. 21, 893\u2013904 (2010)","journal-title":"Int. J. Found. Comput Sci."},{"key":"1841_CR2","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0167-6377(87)90012-5","volume":"6","author":"K Altinkemer","year":"1987","unstructured":"Altinkemer, K., Gavish, B.: Heuristics for unequal weight delivery problems with a fixed error guarantee. Oper. Res. Lett. 6, 149\u2013158 (1987)","journal-title":"Oper. Res. Lett."},{"key":"1841_CR3","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1023\/A:1011461300596","volume":"5","author":"T Asano","year":"2001","unstructured":"Asano, T., Katoh, N., Kawashima, K.: A new approximation algorithm for the capacitated vehicle routing problem on a tree. J. Comb. Optim. 5, 213\u2013231 (2001)","journal-title":"J. Comb. Optim."},{"key":"1841_CR4","doi-asserted-by":"crossref","unstructured":"Asano, T., Katoh, N., Tamaki, H., Tokuyama, T.: Covering points in the plane by $$k$$-tours: towards a polynomial time approximation scheme for general $$k$$. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC) (1997), pp.\u00a0275\u2013283","DOI":"10.1145\/258533.258602"},{"key":"1841_CR5","unstructured":"Becker, A.: A tight 4\/3 approximation for capacitated vehicle routing in trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM), 3:1\u20133:15, (2018)"},{"key":"1841_CR6","unstructured":"Becker, A., Klein, P.\u00a0N., Saulpic, D.: Polynomial-time approximation schemes for $$k$$-center, $$k$$-median, and capacitated vehicle routing in bounded highway dimension. In 26th Annual European Symposium on Algorithms (ESA), pp.\u00a08:1\u20138:15, (2018)"},{"key":"1841_CR7","doi-asserted-by":"crossref","unstructured":"Becker, A., Klein, P.\u00a0N., Schild, A.: A PTAS for bounded-capacity vehicle routing in planar graphs. In Algorithms and Data Structures (WADS), pp.\u00a099\u2013111, (2019)","DOI":"10.1007\/978-3-030-24766-9_8"},{"key":"1841_CR8","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1137\/050645464","volume":"37","author":"A Blum","year":"2007","unstructured":"Blum, A., Chawla, S., Karger, D.R., Lane, T., Meyerson, A., Minkoff, M.: Approximation algorithms for orienteering and discounted-reward TSP. SIAM J. Comput. 37, 653\u2013670 (2007)","journal-title":"SIAM J. Comput."},{"key":"1841_CR9","first-page":"10","volume":"67","author":"A Bock","year":"2011","unstructured":"Bock, A., Grant, E., K\u00f6nemann, J., Sanit\u00e0, L.: The school bus problem on trees. Algorithmica 67, 10\u201319 (2011)","journal-title":"Algorithmica"},{"key":"1841_CR10","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.disopt.2006.04.002","volume":"3","author":"A Bompadre","year":"2006","unstructured":"Bompadre, A., Dror, M., Orlin, J.B.: Improved bounds for vehicle routing solutions. Discrete Optim. 3, 299\u2013316 (2006)","journal-title":"Discrete Optim."},{"key":"1841_CR11","volume-title":"Worst-case analysis of a new heuristic for the traveling salesman problem","author":"N Christofides","year":"1976","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Carnegie-Mellon University, Tech. rep. (1976)"},{"key":"1841_CR12","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s00453-014-9906-4","volume":"73","author":"A Das","year":"2015","unstructured":"Das, A., Mathieu, C.: A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica 73, 115\u2013142 (2015)","journal-title":"Algorithmica"},{"key":"1841_CR13","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.disopt.2017.02.003","volume":"25","author":"I Diarrassouba","year":"2017","unstructured":"Diarrassouba, I.: On the complexity of the separation problem for rounded capacity inequalities. Discrete Optim. 25, 86\u2013104 (2017)","journal-title":"Discrete Optim."},{"key":"1841_CR14","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 248\u2013264 (1972)","journal-title":"J. ACM"},{"key":"1841_CR15","unstructured":"Friggstad, Z., Mousavi, R., Rahgoshay, M., Salavatipour, M.\u00a0R.: Improved approximations for CVRP with unsplittable demands. arXiv:2111.08138 (2021)"},{"key":"1841_CR16","doi-asserted-by":"crossref","unstructured":"Friggstad, Z., Swamy, C.: Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), 744\u2013753, (2014)","DOI":"10.1145\/2591796.2591840"},{"key":"1841_CR17","doi-asserted-by":"crossref","unstructured":"Friggstad, Z., Swamy, C.: Compact, provably-good LPs for orienteering and regret-bounded vehicle routing. In International Conference on Integer Programming and Combinatorial Optimization (IPCO), 199\u2013211, (2017)","DOI":"10.1007\/978-3-319-59250-3_17"},{"key":"1841_CR18","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0167-6377(94)90067-1","volume":"16","author":"MX Goemans","year":"1994","unstructured":"Goemans, M.X., Williamson, D.P.: Approximating minimum-cost graph problems with spanning tree edges. Oper. Res. Lett. 16, 183\u2013189 (1994)","journal-title":"Oper. Res. Lett."},{"key":"1841_CR19","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1287\/moor.10.4.527","volume":"10","author":"M Haimovich","year":"1985","unstructured":"Haimovich, M., Rinnooy Kan, A.H.G.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10, 527\u2013542 (1985)","journal-title":"Math. Oper. Res."},{"key":"1841_CR20","doi-asserted-by":"crossref","unstructured":"Hamaguchi, S., Katoh, N.: A capacitated vehicle routing problem on a tree. In: Algorithms and Computation (ISAAC), pp. 399\u2013407. Springer, Berlin (1998)","DOI":"10.1007\/3-540-49381-6_42"},{"key":"1841_CR21","doi-asserted-by":"crossref","unstructured":"Karlin, A.\u00a0R., Klein, N., Oveis Gharan, S.: A (slightly) improved approximation algorithm for metric TSP. In: Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pp. 32\u201345 (2021)","DOI":"10.1145\/3406325.3451009"},{"key":"1841_CR22","doi-asserted-by":"crossref","unstructured":"Khachay, M., Dubinin, R.: PTAS for the Euclidean capacitated vehicle routing problem in $${\\mathbb{R}}^d$$. In: 9th International Conference on Discrete Optimization and Operations Research (DOOR),193\u2013205, (2016), Springer, Cham","DOI":"10.1007\/978-3-319-44914-2_16"},{"key":"1841_CR23","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1287\/opre.39.4.616","volume":"39","author":"M Labb\u00e9","year":"1991","unstructured":"Labb\u00e9, M., Laporte, G., Mercure, H.: Capacitated vehicle routing on trees. Oper. Res. 39, 616\u2013622 (1991)","journal-title":"Oper. Res."},{"key":"1841_CR24","doi-asserted-by":"crossref","unstructured":"Mathieu, C., Zhou, H.: A PTAS for capacitated vehicle routing on trees. arXiv:2111.03735 (2021)","DOI":"10.1145\/3575799"},{"key":"1841_CR25","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1137\/S0895480194271323","volume":"10","author":"H Nagamochi","year":"1997","unstructured":"Nagamochi, H., Nishimura, K., Ibaraki, T.: Computing all small cuts in an undirected network. SIAM J. Discrete Math. 10, 469\u2013481 (1997)","journal-title":"SIAM J. Discrete Math."},{"key":"1841_CR26","first-page":"76","volume":"17","author":"A Serdjukov","year":"1978","unstructured":"Serdjukov, A.: Some extremal bypasses in graphs [in Russian]. Upravlyaemye Sistemy 17, 76\u201379 (1978)","journal-title":"Upravlyaemye Sistemy"},{"key":"1841_CR27","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1002\/net.3230010206","volume":"1","author":"N Tomizawa","year":"1971","unstructured":"Tomizawa, N.: On some techniques useful for solution of transportation network problems. Networks 1, 173\u2013194 (1971)","journal-title":"Networks"},{"key":"1841_CR28","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BFb0120913","volume":"13","author":"L Wolsey","year":"1980","unstructured":"Wolsey, L.: Heuristic analysis, linear programming and branch and bound. Math. Program. Study 13, 121\u2013134 (1980)","journal-title":"Math. Program. Study"},{"key":"1841_CR29","doi-asserted-by":"crossref","unstructured":"Wu, Y., Lu, X.: Capacitated vehicle routing problem on line with unsplittable demands. Journal of Combinatorial Optimization, to appear (2020)","DOI":"10.1007\/s10878-020-00565-5"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01841-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01841-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01841-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T17:20:48Z","timestamp":1675704048000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01841-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,14]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1841"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01841-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,14]]},"assertion":[{"value":"28 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}