Document Open Access Logo

Framing Algorithms for Approximate Multicriteria Shortest Paths

Authors Nicolas Hanusse, David Ilcinkas, Antonin Lentz

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2020.11.pdf
  • Filesize: 0.83 MB
  • 19 pages

Document Identifiers

Author Details

Nicolas Hanusse
  • LaBRI, CNRS & Université Bordeaux, France
David Ilcinkas
  • LaBRI, CNRS & Université Bordeaux, France
Antonin Lentz
  • LaBRI, Université Bordeaux, France

Cite As Get BibTex

Nicolas Hanusse, David Ilcinkas, and Antonin Lentz. Framing Algorithms for Approximate Multicriteria Shortest Paths. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/OASIcs.ATMOS.2020.11

Abstract

This paper deals with the computation of d-dimensional multicriteria shortest paths. In a weighted graph with arc weights represented by vectors, the cost of a path is the vector sum of the weights of its arcs. For a given pair consisting of a source s and a destination t, a path P dominates a path Q if and only if P’s cost is component-wise smaller than or equal to Q’s cost. The set of Pareto paths, or Pareto set, from s to t is the set of paths that are not dominated. The computation time of the Pareto paths can be prohibitive whenever the set of Pareto paths is large.
We propose in this article new algorithms to compute approximated Pareto paths in any dimension. For d = 2, we exhibit the first approximation algorithm, called Frame, whose output is guaranteed to be always a subset of the Pareto set. Finally, we provide a small experimental study in order to confirm the relevance of our Frame algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Applied computing → Multi-criterion optimization and decision-making
Keywords
  • Pareto set
  • multicriteria
  • shortest paths
  • approximation

Metrics

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

References

  1. Florian Barth, Stefan Funke, and Sabine Storandt. Alternative multicriteria routes. In 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX), pages 66-80. SIAM, 2019. Google Scholar
  2. Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route Planning in Transportation Networks. In Algorithm Engineering, volume 9220 of Lecture Notes in Computer Science, pages 19-80. Springer, Cham, 2016. URL: https://doi.org/10.1007/978-3-319-49487-6_2.
  3. Thomas Breugem, Twan Dollevoet, and Wilco van den Heuvel. Analysis of FPTASes for the multi-objective shortest path problem. Computers & Operations Research, 78(Supplement C):44-58, February 2017. URL: https://doi.org/10.1016/j.cor.2016.06.022.
  4. Fritz Bökler and Markus Chimani. Approximating Multiobjective Shortest Path in Practice. In 2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), Proceedings, pages 120-133. Society for Industrial and Applied Mathematics, December 2019. URL: https://doi.org/10.1137/1.9781611976007.10.
  5. Daniel Delling, Julian Dibbelt, and Thomas Pajor. Fast and exact public transit routing with restricted pareto sets. In 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX), pages 54-65. SIAM, 2019. Google Scholar
  6. Daniel Delling, Thomas Pajor, and Renato F. Werneck. Round-Based Public Transit Routing. Transportation Science, 49(3):591-604, October 2014. URL: https://doi.org/10.1287/trsc.2014.0534.
  7. Camil Demetrescu, Andrew Goldberg, and David Johnson. 9th DIMACS Implementation Challenge: Shortest Paths. URL: http://users.diag.uniroma1.it/challenge9/.
  8. Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Intriguingly Simple and Fast Transit Routing. In Experimental Algorithms, Lecture Notes in Computer Science, pages 43-54. Springer, Berlin, Heidelberg, June 2013. URL: https://doi.org/10.1007/978-3-642-38527-8_6.
  9. Matthias Ehrgott. Multicriteria optimization. Springer, Berlin ; New York, 2nd ed edition, 2005. Google Scholar
  10. Pierre Hansen. Bicriterion Path Problems. In Günter Fandel and Tomas Gal, editors, Multiple Criteria Decision Making Theory and Application, Lecture Notes in Economics and Mathematical Systems, pages 109-127. Springer Berlin Heidelberg, 1980. Google Scholar
  11. J. Hrnčíř, P. Žilecký, Q. Song, and M. Jakob. Practical Multicriteria Urban Bicycle Routing. IEEE Transactions on Intelligent Transportation Systems, 18(3):493-504, March 2017. URL: https://doi.org/10.1109/TITS.2016.2577047.
  12. H. T. Kung, F. Luccio, and F. P. Preparata. On Finding the Maxima of a Set of Vectors. Journal of the ACM, 22(4):469-476, October 1975. URL: https://doi.org/10.1145/321906.321910.
  13. E. Machuca and L. Mandow. Multiobjective heuristic search in road maps. Expert Systems with Applications, 39(7):6435-6445, June 2012. URL: https://doi.org/10.1016/j.eswa.2011.12.022.
  14. Lawrence Mandow and José. Luis Pérez De La Cruz. Multiobjective A* search with consistent heuristics. Journal of the ACM, 57(5):1-25, June 2010. URL: https://doi.org/10.1145/1754399.1754400.
  15. Ernesto Queirós Vieira Martins. On a multicriteria shortest path problem. European Journal of Operational Research, 16(2):236-245, May 1984. URL: https://doi.org/10.1016/0377-2217(84)90077-8.
  16. Christian Worm Mortensen. Fully Dynamic Orthogonal Range Reporting on RAM. SIAM Journal on Computing, 35(6):1494-1525, January 2006. Publisher: Society for Industrial and Applied Mathematics. URL: https://doi.org/10.1137/S0097539703436722.
  17. Matthias Müller-Hannemann and Karsten Weihe. On the cardinality of the Pareto set in bicriteria shortest path problems. Annals of Operations Research, 147(1):269-286, October 2006. URL: https://doi.org/10.1007/s10479-006-0072-1.
  18. C. H. Papadimitriou and M. Yannakakis. On the approximability of trade-offs and optimal access of Web sources. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 86-92, 2000. URL: https://doi.org/10.1109/SFCS.2000.892068.
  19. Andrea Raith and Matthias Ehrgott. A comparison of solution strategies for biobjective shortest path problems. Computers & Operations Research, 36(4):1299-1331, April 2009. URL: https://doi.org/10.1016/j.cor.2008.02.002.
  20. Michael Shekelyan, Gregor Josse, and Matthias Schubert. Linear path skylines in multicriteria networks. In 2015 IEEE 31st International Conference on Data Engineering, pages 459-470, Seoul, South Korea, April 2015. IEEE. URL: https://doi.org/10.1109/ICDE.2015.7113306.
  21. George Tsaggouris and Christos Zaroliagis. Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with Applications. Theory of Computing Systems, 45(1):162-186, June 2009. URL: https://doi.org/10.1007/s00224-007-9096-4.
  22. Chi Tung Tung and Kim Lin Chew. A multicriteria Pareto-optimal path algorithm. European Journal of Operational Research, 62(2):203-209, October 1992. URL: https://doi.org/10.1016/0377-2217(92)90248-8.
  23. Sibo Wang, Xiaokui Xiao, Yin Yang, and Wenqing Lin. Effective indexing for approximate constrained shortest path queries on large road networks. Proceedings of the VLDB Endowment, 10(2):61-72, October 2016. URL: https://doi.org/10.14778/3015274.3015277.
  24. Arthur Warburton. Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems. Operations Research, 35(1):70-79, February 1987. URL: https://doi.org/10.1287/opre.35.1.70.
  25. Huanhuan Wu, James Cheng, Silu Huang, Yiping Ke, Yi Lu, and Yanyan Xu. Path Problems in Temporal Graphs. Proc. VLDB Endow., 7(9):721-732, May 2014. URL: https://doi.org/10.14778/2732939.2732945.
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