Abstract
The Capacitated Vehicle Routing problem is to find a minimum-cost set of tours that collectively cover clients in a graph, such that each tour starts and ends at a specified depot and is subject to a capacity bound on the number of clients it can serve. In this paper, we present a polynomial-time approximation scheme (PTAS) for instances in which the input graph is planar and the capacity is bounded. Previously, only a quasipolynomial-time approximation scheme was known for these instances. To obtain this result, we show how to embed planar graphs into bounded-treewidth graphs while preserving, in expectation, the client-to-client distances up to a small additive error proportional to client distances to the depot.
Research supported by NSF grant CCF-1409520.
Research supported by NSF Grant CCF-1816861.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
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 Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 275–283. ACM (1997)
Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: 37th Annual Symposium on Foundations of Computer Science, FOCS 1996, Burlington, Vermont, USA, 14–16 October 1996, pp. 184–193 (1996)
Becker, A.: A tight 4/3 approximation for capacitated vehicle routing in trees. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
Becker, A., Klein, P.N., Saulpic, D.: Polynomial-time approximation schemes for k-center and bounded-capacity vehicle routing in metrics with bounded highway dimension. CoRR abs/1707.08270 (2017). http://arxiv.org/abs/1707.08270
Becker, A., Klein, P.N., Saulpic, D.: A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 87. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)
Becker, A., Klein, P.N., 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 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
Becker, A., Paul, A.: A PTAS for minimum makespan vehicle routing in trees. arXiv preprint arXiv:1807.04308 (2018)
Chakrabarti, A., Jaffe, A., Lee, J.R., Vincent, J.: Embeddings of topological graphs: lossy invariants, linearization, and 2-sums. In: 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 761–770 (2008)
Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report , Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group (1976)
Das, A., Mathieu, C.: A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing. In: Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 390–403. SIAM (2010)
Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3), 485–497 (2004)
Feldmann, A.E., Fung, W.S., Könemann, J., Post, I.: A (1+\(\varepsilon \))-embedding of low highway dimension graphs into bounded treewidth graphs. In: 42nd International Colloquium on Automata, Languages, and Programming, pp. 469–480 (2015)
Fox-Epstein, E., Klein, P.N., Schild, A.: Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1069–1088. SIAM (2019)
Haimovich, M., Rinnooy Kan, A.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527–542 (1985)
Khachay, M., Dubinin, R.: PTAS for the Euclidean capacitated vehicle routing problem in \(R^d\). In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 193–205. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44914-2_16
Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1), 1–11 (1993)
Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: 36th Annual ACM Symposium on Theory of Computing, pp. 281–290 (2004)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Becker, A., Klein, P.N., Schild, A. (2019). A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs. In: Friggstad, Z., Sack, JR., Salavatipour, M. (eds) Algorithms and Data Structures. WADS 2019. Lecture Notes in Computer Science(), vol 11646. Springer, Cham. https://doi.org/10.1007/978-3-030-24766-9_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-24766-9_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-24765-2
Online ISBN: 978-3-030-24766-9
eBook Packages: Computer ScienceComputer Science (R0)