Document Open Access Logo

A Tight (1.5+ε)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees

Authors Claire Mathieu, Hang Zhou

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.91.pdf
  • Filesize: 0.93 MB
  • 16 pages

Document Identifiers

Author Details

Claire Mathieu
  • CNRS Paris, France
Hang Zhou
  • École Polytechnique, Institut Polytechnique de Paris, France

Funding

This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR).

Cite As Get BibTex

Claire Mathieu and Hang Zhou. A Tight (1.5+ε)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 91:1-91:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.91

Abstract

In the unsplittable capacitated vehicle routing problem (UCVRP) on trees, we are given a rooted tree with edge weights and a subset of vertices of the tree called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the root of the tree such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1.
For the special case when all terminals have equal demands, a long line of research culminated in a quasi-polynomial time approximation scheme [Jayaprakash and Salavatipour, TALG 2023] and a polynomial time approximation scheme [Mathieu and Zhou, TALG 2023].
In this work, we study the general case when the terminals have arbitrary demands. Our main contribution is a polynomial time (1.5+ε)-approximation algorithm for the UCVRP on trees. This is the first improvement upon the 2-approximation algorithm more than 30 years ago. Our approximation ratio is essentially best possible, since it is NP-hard to approximate the UCVRP on trees to better than a 1.5 factor.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
Keywords
  • approximation algorithms
  • capacitated vehicle routing
  • graph algorithms
  • combinatorial optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Muhammad Al-Salamah. Constrained binary artificial bee colony to minimize the makespan for single machine batch processing with non-identical job sizes. Applied Soft Computing, 29:379-385, 2015. Google Scholar
  2. Kemal Altinkemer and Bezalel Gavish. Heuristics for unequal weight delivery problems with a fixed error guarantee. Operations Research Letters, 6(4):149-158, 1987. Google Scholar
  3. Tetsuo Asano, Naoki Katoh, and Kazuhiro Kawashima. A new approximation algorithm for the capacitated vehicle routing problem on a tree. Journal of Combinatorial Optimization, 5(2):213-231, 2001. Google Scholar
  4. Amariah Becker. A tight 4/3 approximation for capacitated vehicle routing in trees. In International Conference on Approximation Algorithms for Combinatorial Optimization Problems, volume 116, pages 3:1-3:15, 2018. Google Scholar
  5. Amariah Becker and Alice Paul. A framework for vehicle routing approximation schemes in trees. In Workshop on Algorithms and Data Structures, pages 112-125. Springer, 2019. Google Scholar
  6. Jannis Blauth, Vera Traub, and Jens Vygen. Improving the approximation ratio for capacitated vehicle routing. Mathematical Programming, pages 1-47, 2022. Google Scholar
  7. Huaping Chen, Bing Du, and George Q. Huang. Scheduling a batch processing machine with non-identical job sizes: a clustering perspective. International Journal of Production Research, 49(19):5755-5778, 2011. Google Scholar
  8. Jing Chen, He Guo, Xin Han, and Kazuo Iwama. The train delivery problem revisited. In International Symposium on Algorithms and Computation, pages 601-611. Springer, 2013. Google Scholar
  9. Purushothaman Damodaran, Praveen Kumar Manjeshwar, and Krishnaswami Srihari. Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms. International Journal of Production Economics, 103(2):882-891, 2006. Google Scholar
  10. George B. Dantzig and John H. Ramser. The truck dispatching problem. Management Science, 6(1):80-91, 1959. Google Scholar
  11. Aparna Das, Claire Mathieu, and Shay Mozes. The train delivery problem-vehicle routing meets bin packing. In International Workshop on Approximation and Online Algorithms, pages 94-105. Springer, 2010. Google Scholar
  12. Lionel Dupont and Clarisse Dhaenens-Flipo. Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure. Computers & Operations Research, 29(7):807-819, 2002. Google Scholar
  13. Zachary Friggstad, Ramin Mousavi, Mirmahdi Rahgoshay, and Mohammad R. Salavatipour. Improved approximations for capacitated vehicle routing with unsplittable client demands. In International Conference on Integer Programming and Combinatorial Optimization, pages 251-261. Springer, 2022. Google Scholar
  14. Bruce L. Golden and Richard T. Wong. Capacitated arc routing problems. Networks, 11(3):305-315, 1981. Google Scholar
  15. Fabrizio Grandoni, Claire Mathieu, and Hang Zhou. Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm. In Innovations in Theoretical Computer Science (ITCS), volume 251 of LIPIcs, pages 63:1-63:13, 2023. Google Scholar
  16. Mordecai Haimovich and Alexander H. G. Rinnooy Kan. Bounds and heuristics for capacitated routing problems. Mathematics of Operations Research, 10(4):527-542, 1985. Google Scholar
  17. Shin-ya Hamaguchi and Naoki Katoh. A capacitated vehicle routing problem on a tree. In International Symposium on Algorithms and Computation, pages 399-407. Springer, 1998. Google Scholar
  18. Aditya Jayaprakash and Mohammad R. Salavatipour. Approximation schemes for capacitated vehicle routing on graphs of bounded treewidth, bounded doubling, or highway dimension. ACM Transactions on Algorithms (TALG), 19(2), 2023. Google Scholar
  19. Ali Husseinzadeh Kashan, Behrooz Karimi, and Fariborz Jolai. Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes. International Journal of Production Research, 44(12):2337-2360, 2006. Google Scholar
  20. Martine Labbé, Gilbert Laporte, and Hélene Mercure. Capacitated vehicle routing on trees. Operations Research, 39(4):616-622, 1991. Google Scholar
  21. Claire Mathieu and Hang Zhou. A PTAS for capacitated vehicle routing on trees. ACM Transactions on Algorithms (TALG), 19(2), 2023. Google Scholar
  22. Sharif Melouk, Purushothaman Damodaran, and Ping-Yu Chang. Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. International Journal of Production Economics, 87(2):141-147, 2004. Google Scholar
  23. İbrahim Muter. Exact algorithms to minimize makespan on single and parallel batch processing machines. European Journal of Operational Research, 285(2):470-483, 2020. Google Scholar
  24. N. Rafiee Parsa, Behrooz Karimi, and Ali Husseinzadeh Kashan. A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes. Computers & Operations Research, 37(10):1720-1730, 2010. Google Scholar
  25. Thomas Rothvoß. The entropy rounding method in approximation algorithms. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 356-372. SIAM, 2012. Google Scholar
  26. Reha Uzsoy. Scheduling a single batch processing machine with non-identical job sizes. The International Journal of Production Research, 32(7):1615-1635, 1994. Google Scholar
  27. Yuanxiao Wu and Xiwen Lu. Capacitated vehicle routing problem on line with unsplittable demands. Journal of Combinatorial Optimization, pages 1-11, 2020. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact