Document Open Access Logo

Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm

Authors Fabrizio Grandoni, Claire Mathieu, Hang Zhou

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.63.pdf
  • Filesize: 0.69 MB
  • 13 pages

Document Identifiers

Author Details

Fabrizio Grandoni
  • IDSIA, USI-SUPSI, Lugano, Switzerland
Claire Mathieu
  • CNRS, IRIF, Université de Paris, France
Hang Zhou
  • École Polytechnique, Institut Polytechnique de Paris, France

Funding

This work was partially funded by the SNSF Grant 200021 200731 / 1, the Grant ANR-19-CE48-0016 from the French National Research Agency (ANR), and the Hi!PARIS Grant "Efficiency in Algorithms".

Acknowledgements

We thank Vincent Cohen-Addad for helpful preliminary discussions. We thank the anonymous reviewers for their valuable comments.

Cite AsGet BibTex

Fabrizio Grandoni, Claire Mathieu, and Hang Zhou. Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 63:1-63:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.63

Abstract

In the unsplittable capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices 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 depot 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. Our main result is a polynomial-time (2+ε)-approximation algorithm for this problem in the two-dimensional Euclidean plane, i.e., for the special case where the terminals and the depot are associated with points in the Euclidean plane and their distances are defined accordingly. This improves on recent work by Blauth, Traub, and Vygen [IPCO'21] and Friggstad, Mousavi, Rahgoshay, and Salavatipour [IPCO'22].

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • capacitated vehicle routing
  • approximation algorithms
  • Euclidean plane

Metrics

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

References

  1. Anna Adamaszek, Artur Czumaj, and Andrzej Lingas. PTAS for k-tour cover problem on the plane for moderately large values of k. International Journal of Foundations of Computer Science, 21(06):893-904, 2010. 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. Kemal Altinkemer and Bezalel Gavish. Heuristics for delivery problems with constant error guarantees. Transportation Science, 24(4):294-297, 1990. Google Scholar
  4. Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM (JACM), 45(5):753-782, 1998. Google Scholar
  5. Tetsuo Asano, Naoki Katoh, Hisao Tamaki, and Takeshi Tokuyama. 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, pages 275-283, 1997. Google Scholar
  6. 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
  7. Jannis Blauth, Vera Traub, and Jens Vygen. Improving the approximation ratio for capacitated vehicle routing. In International Conference on Integer Programming and Combinatorial Optimization, pages 1-14. Springer, 2021. Google Scholar
  8. Jean-François Cordeau, Gilbert Laporte, Martin W.P. Savelsbergh, and Daniele Vigo. Vehicle routing. Handbooks in operations research and management science, 14:367-428, 2007. Google Scholar
  9. George B. Dantzig and John H. Ramser. The truck dispatching problem. Management Science, 6(1):80-91, 1959. Google Scholar
  10. 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
  11. 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
  12. Narendra Karmarkar and Richard M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In 23rd Annual Symposium on Foundations of Computer Science, pages 312-320. IEEE, 1982. Google Scholar
  13. Richard M. Karp. Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. Mathematics of operations research, 2(3):209-224, 1977. Google Scholar
  14. Michael Khachay and Roman Dubinin. PTAS for the Euclidean capacitated vehicle routing problem in ℝ^d. In International Conference on Discrete Optimization and Operations Research, pages 193-205. Springer, 2016. Google Scholar
  15. Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on computing, 28(4):1298-1309, 1999. Google Scholar
  16. Laurent Perron and Vincent Furnon. OR-Tools, Google, version 9.3, 2022. URL: https://developers.google.com/optimization/.
  17. David P. Williamson and David B. Shmoys. The design of approximation algorithms. Cambridge university press, 2011. 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 Imprint Privacy Contact