OASIcs.ATMOS.2021.7.pdf
- Filesize: 0.78 MB
- 15 pages
Document
Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data
Authors
Niels Lindner 
,
Pedro Maristany de las Casas ,
Philine Schiewe
-
Part of:
Volume:
21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-09-27
File
Document Identifiers
Author Details
Acknowledgements
We thank Lufthansa Systems GmbH & Co. KG. and in particular Marco Blanco for the data required to build the instance representing the airway network over Germany.
Cite As Get BibTex
Niels Lindner, Pedro Maristany de las Casas, and Philine Schiewe. Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/OASIcs.ATMOS.2021.7
Abstract
We investigate preprocessing for single-source shortest path queries in digraphs, where arc costs are only known to lie in an interval. More precisely, we want to decide for each arc whether it is part of some shortest path tree for some realization of costs. We show that this problem is solvable in polynomial time by giving a combinatorial algorithm, using optimal structures that we call forks. Our algorithm turns out to be very efficient in practice, and is sometimes even superior in quality to a heuristic developed for the one-to-one shortest path problem in the context of passenger routing in public transport.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Paths and connectivity problems
- Theory of computation → Shortest paths
- Mathematics of computing → Graph algorithms
Keywords
- Preprocessing Shortest Path Problems
- Interval Data
- Graph Algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
Supplementary Materials
-
Software (Source Code)
https://github.com/tfePedro/optimal-forks
browse
archived version
References
- H. Bast, D. Delling, A. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner, and R. F. Werneck. Route Planning in Transportation Networks. In Algorithm Engineering, 2016. URL: https://doi.org/10.1007/978-3-319-49487-6_2.
- D. Catanzaro, M. Labbé, and M. Salazar-Neumann. Reduction approaches for robust shortest path problems. Computers & Operations Research, 38(11):1610-1619, 2011. URL: https://doi.org/10.1016/j.cor.2011.01.022.
- S. Chanas and P. Zieliński. The computational complexity of the criticality problems in a network with interval activity times. European Journal of Operational Research, 136(3):541-550, February 2002. URL: https://doi.org/10.1016/s0377-2217(01)00048-0.
- S. Chanas and P. Zieliński. On the hardness of evaluating criticality of activities in a planar network with duration intervals. Operations Research Letters, 31(1):53-59, 2003. URL: https://doi.org/10.1016/S0167-6377(02)00174-8.
- D. B. Johnson. Efficient algorithms for shortest paths in sparse networks. J. ACM, 24(1):1-13, January 1977. URL: https://doi.org/10.1145/321992.321993.
-
O. E. Karasan, M. Pinar, and H. Yaman. The Robust Shortest Path Problem with Interval Data. Technical report, Bilkent University, 2001.
-
F. Krellner. Shortest Paths with Interval Data and their Application in Timetabling. Master’s thesis, Freie Universität Berlin, 2018.
- R. Montemanni and L. M. Gambardella. An exact algorithm for the robust shortest path problem with interval data. Computers & Operations Research, 31(10):1667-1680, 2004. URL: https://doi.org/10.1016/S0305-0548(03)00114-X.
- A. Schienle, P. Maristany, and M. Blanco. A Priori Search Space Pruning in the Flight Planning Problem. In Valentina Cacchiani and Alberto Marchetti-Spaccamela, editors, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019), volume 75 of OpenAccess Series in Informatics (OASIcs), pages 8:1-8:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISSN: 2190-6807. URL: https://doi.org/10.4230/OASIcs.ATMOS.2019.8.
- A. Schiewe, S. Albert, P. Schiewe, A. Schöbel, and F. Spühler. LinTim - Integrated Optimization in Public Transportation. Homepage. https://lintim.net, 2020.
- A. Schiewe, S. Albert, P. Schiewe, A. Schöbel, and F. Spühler. LinTim: An integrated environment for mathematical public transport optimization. Documentation for version 2020.12. Technical report, TU Kaiserslautern, 2020. URL: https://nbn-resolving.org/urn:nbn:de:hbz:386-kluedo-62025.
- P. Schiewe. Integrated Optimization in Public Transport Planning, volume 160 of Optimization and Its Applications. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-46270-3.
- P. Schiewe and A. Schöbel. Periodic Timetabling with Integrated Routing: Toward Applicable Approaches. Transportation Science, 54(6):1714-1731, 2020. URL: https://doi.org/10.1287/trsc.2019.0965.
- H. Yaman, O. E. Karaşan, and M. Ç. Pınar. The robust spanning tree problem with interval data. Operations Research Letters, 29(1):31-40, 2001. URL: https://doi.org/10.1016/S0167-6377(01)00078-5.