Document Open Access Logo

Exact and Approximation Algorithms for Routing a Convoy Through a Graph

Authors Martijn van Ee, Tim Oosterwijk, René Sitters, Andreas Wiese

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2023.86.pdf
  • Filesize: 0.6 MB
  • 15 pages

Document Identifiers

Author Details

Martijn van Ee
  • Netherlands Defence Academy, Den Helder, The Netherlands
Tim Oosterwijk
  • Vrije Universiteit Amsterdam, The Netherlands
René Sitters
  • Vrije Universiteit Amsterdam, The Netherlands
Andreas Wiese
  • Technische Universität München, Germany

Cite As Get BibTex

Martijn van Ee, Tim Oosterwijk, René Sitters, and Andreas Wiese. Exact and Approximation Algorithms for Routing a Convoy Through a Graph. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 86:1-86:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.MFCS.2023.86

Abstract

We study routing problems of a convoy in a graph, generalizing the shortest path problem (SPP), the travelling salesperson problem (TSP), and the Chinese postman problem (CPP) which are all well-studied in the classical (non-convoy) setting. We assume that each edge in the graph has a length and a speed at which it can be traversed and that our convoy has a given length. While the convoy moves through the graph, parts of it can be located on different edges. For safety requirements, at all time the whole convoy needs to travel at the same speed which is dictated by the slowest edge on which currently a part of the convoy is located. For Convoy-SPP, we give a strongly polynomial time exact algorithm. For Convoy-TSP, we provide an O(log n)-approximation algorithm and an O(1)-approximation algorithm for trees. Both results carry over to Convoy-CPP which - maybe surprisingly - we prove to be NP-hard in the convoy setting. This contrasts the non-convoy setting in which the problem is polynomial time solvable.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • approximation algorithms
  • convoy routing
  • shortest path problem
  • traveling salesperson problem

Metrics

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

References

  1. Pierre Chardaire, Geoff P. McKeown, S.A. Verity-Harrison, and S.B. Richardson. Solving a time-space network formulation for the convoy movement problem. Operations research, 53(2):219-230, 2005. Google Scholar
  2. Jack Edmonds. The Chinese postman problem. Operations Research, 13:73-77, 1965. Google Scholar
  3. Jack Edmonds and Ellis L. Johnson. Matching, Euler tours and the Chinese postman. Mathematical programming, 5(1):88-124, 1973. Google Scholar
  4. Michael R. Garey and David S. Johnson. Computers and intractability, volume 174. Freeman San Francisco, 1979. Google Scholar
  5. Michael Held and Richard M. Karp. The traveling-salesman problem and minimum spanning trees. Operations Research, 18(6):1138-1162, 1970. Google Scholar
  6. Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric TSP. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 32-45, 2021. Google Scholar
  7. Michael Hart Moore. On the fastest route for convoy-type traffic in flowrate-constrained networks. Transportation Science, 10(2):113-124, 1976. Google Scholar
  8. Dong Hwan Oh, R. Kevin Wood, and Young Hoon Lee. Optimal interdiction of a ground convoy. Military Operations Research, 23(2):5-18, 2018. Google Scholar
  9. Christos H. Papadimitriou. On the complexity of edge traversing. Journal of the ACM, 23:544-554, 1976. Google Scholar
  10. Marta Pascoal, M. Eugénia V. Captivo, and João C.N. Clímaco. A comprehensive survey on the quickest path problem. Annals of Operations Research, 147(1):5-21, 2006. Google Scholar
  11. P.N. Ram Kumar and T.T. Narendran. A mathematical approach for variable speed convoy movement problem (CMP). Defense & Security Analysis, 25(2):137-155, 2009. Google Scholar
  12. Martin Skutella. An introduction to network flows over time. In William Cook, László Lovász, and Jens Vygen, editors, Research Trends in Combinatorial Optimization: Bonn 2008, pages 451-482. Springer, Berlin, Heidelberg, 2009. Google Scholar
  13. Petr Slavík. The errand scheduling problem, 1997. Technical report. Google Scholar
  14. Ola Svensson, Jakub Tarnawski, and László A Végh. A constant-factor approximation algorithm for the asymmetric traveling salesman problem. Journal of the ACM (JACM), 67(6):1-53, 2020. Google Scholar
  15. Vera Traub and Jens Vygen. An improved approximation algorithm for the asymmetric traveling salesman problem. SIAM Journal on Computing, 51(1):139-173, 2022. 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