Abstract
We develop a general framework for designing polynomial-time approximation schemes (PTASs) for various vehicle routing problems in trees. In these problems, the goal is to optimally route a fleet of vehicles, originating at a depot, to serve a set of clients, subject to various constraints. For example, in Minimum Makespan Vehicle Routing, the number of vehicles is fixed, and the objective is to minimize the longest distance traveled by a single vehicle. Our main insight is that we can often greatly restrict the set of potential solutions without adding too much to the optimal solution cost. This simplification relies on partitioning the tree into clusters such that there exists a near-optimal solution in which every vehicle that visits a given cluster takes on one of a few forms. In particular, only a small number of vehicles serve clients in any given cluster. By using these coarser building blocks, a dynamic programming algorithm can find a near-optimal solution in polynomial time. We show that the framework is flexible enough to give PTASs for many problems, including Minimum Makespan Vehicle Routing, Distance-Constrained Vehicle Routing, Capacitated Vehicle Routing, and School Bus Routing, and can be extended to the multiple depot setting.
Research funded by NSF grant CCF-14-09520.
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., Kawashima, K.: A new approximation algorithm for the capacitated vehicle routing problem on a tree. J. Comb. Optim. 5(2), 213–231 (2001). https://doi.org/10.1023/A:1011461300596
Becker, A.: A tight 4/3 approximation for capacitated vehicle routing in trees. CoRR abs/1804.08791 (2018). http://arxiv.org/abs/1804.08791
Bock, A., Grant, E., Könemann, J., Sanità, L.: The school bus problem on trees. Algorithmica 67(1), 49–64 (2013). https://doi.org/10.1007/s00453-012-9711-x
Chen, L., Marx, D.: Covering a tree with rooted subtrees-parameterized and approximation algorithms. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2801–2820. SIAM (2018)
Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Carnegie-Mellon University Pittsburgh, PA, Management Sciences Research Group (1976)
Even, G., Garg, N., Könemann, J., Ravi, R., Sinha, A.: Min-max tree covers of graphs. Oper. Res. Lett. 32(4), 309–315 (2004). https://doi.org/10.1016/j.orl.2003.11.010
Friggstad, Z., Swamy, C.: Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC 2014, pp. 744–753. ACM, New York (2014). https://doi.org/10.1145/2591796.2591840, http://doi.acm.org/10.1145/2591796.2591840
Friggstad, Z., Swamy, C.: Compact, provably-good LPs for orienteering and regret-bounded vehicle routing. In: Eisenbrand, F., Koenemann, J. (eds.) IPCO 2017. LNCS, vol. 10328, pp. 199–211. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59250-3_17
Haimovich, M., Rinnooy Kan, A.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527–542 (1985)
Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM (JACM) 34(1), 144–162 (1987)
Karuno, Y., Nagamochi, H., Ibaraki, T.: Vehicle scheduling on a tree with release and handling times. Ann. Oper. Res. 69, 193–207 (1997)
Labbé, M., Laporte, G., Mercure, H.: Capacitated vehicle routing on trees. Oper. Res. 39(4), 616–622 (1991)
Nagamochi, H., Okada, K.: Approximating the minmax rooted-tree cover in a tree. Inf. Process. Lett. 104(5), 173–178 (2007)
Nagarajan, V., Ravi, R.: Approximation algorithms for distance constrained vehicle routing problems. Networks 59(2), 209–214 (2012)
Sahni, S.K.: Algorithms for scheduling independent tasks. J. ACM (JACM) 23(1), 116–127 (1976)
Xu, L., Xu, Z., Xu, D.: Exact and approximation algorithms for the min-max k-traveling salesmen problem on a tree. Eur. J. Oper. Res. 227(2), 284–292 (2013)
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., Paul, A. (2019). A Framework for Vehicle Routing Approximation Schemes in Trees. 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_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-24766-9_9
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)