Document Open Access Logo

A Strategic Routing Framework and Algorithms for Computing Alternative Paths

Authors Thomas Bläsius, Maximilian Böther , Philipp Fischbeck , Tobias Friedrich , Alina Gries , Falk Hüffner, Otto Kißig , Pascal Lenzner , Louise Molitor , Leon Schiller , Armin Wells , Simon Wietheger

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2020.10.pdf
  • Filesize: 1.4 MB
  • 14 pages

Document Identifiers

Author Details

Thomas Bläsius
  • Hasso Plattner Institute, University of Potsdam, Germany
Maximilian Böther
  • Hasso Plattner Institute, University of Potsdam, Germany
Philipp Fischbeck
  • Hasso Plattner Institute, University of Potsdam, Germany
Tobias Friedrich
  • Hasso Plattner Institute, University of Potsdam, Germany
Alina Gries
  • Hasso Plattner Institute, University of Potsdam, Germany
Falk Hüffner
  • TomTom Location Technology Germany GmbH, Berlin, Germany
Otto Kißig
  • Hasso Plattner Institute, University of Potsdam, Germany
Pascal Lenzner
  • Hasso Plattner Institute, University of Potsdam, Germany
Louise Molitor
  • Hasso Plattner Institute, University of Potsdam, Germany
Leon Schiller
  • Hasso Plattner Institute, University of Potsdam, Germany
Armin Wells
  • Hasso Plattner Institute, University of Potsdam, Germany
Simon Wietheger
  • Hasso Plattner Institute, University of Potsdam, Germany

Acknowledgements

We want to thank TomTom Location Technology Germany GmbH for supplying us with the data necessary for our experiments.

Cite As Get BibTex

Thomas Bläsius, Maximilian Böther, Philipp Fischbeck, Tobias Friedrich, Alina Gries, Falk Hüffner, Otto Kißig, Pascal Lenzner, Louise Molitor, Leon Schiller, Armin Wells, and Simon Wietheger. A Strategic Routing Framework and Algorithms for Computing Alternative Paths. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/OASIcs.ATMOS.2020.10

Abstract

Traditional navigation services find the fastest route for a single driver. Though always using the fastest route seems desirable for every individual, selfish behavior can have undesirable effects such as higher energy consumption and avoidable congestion, even leading to higher overall and individual travel times. In contrast, strategic routing aims at optimizing the traffic for all agents regarding a global optimization goal. We introduce a framework to formalize real-world strategic routing scenarios as algorithmic problems and study one of them, which we call Single Alternative Path (SAP), in detail. There, we are given an original route between a single origin-destination pair. The goal is to suggest an alternative route to all agents that optimizes the overall travel time under the assumption that the agents distribute among both routes according to a psychological model, for which we introduce the concept of Pareto-conformity. We show that the SAP problem is NP-complete, even for such models. Nonetheless, assuming Pareto-conformity, we give multiple algorithms for different variants of SAP, using multi-criteria shortest path algorithms as subroutines. Moreover, we prove that several natural models are in fact Pareto-conform. The implementation and evaluation of our algorithms serve as a proof of concept, showing that SAP can be solved in reasonable time even though the algorithms have exponential running time in the worst case.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
Keywords
  • Routing
  • Strategic Routing
  • Selfish Routing
  • Route Planning
  • Network Flow
  • Algorithm Design

Metrics

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

Related Versions

Supplementary Materials

References

  1. Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Alternative routes in road networks. Journal of Experimental Algorithmics, 18, 2013. URL: https://doi.org/10.1145/2444016.2444019.
  2. Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route planning in transportation networks. Algorithm Engineering, 2016. URL: https://doi.org/10.1007/978-3-319-49487-6_2.
  3. Umang Bhaskar, Lisa Fleischer, and Elliot Anshelevich. A Stackelberg strategy for routing flow over time. Games and Economic Behavior, 92:232-247, 2015. Google Scholar
  4. Thomas Bläsius, Maximilian Böther, Philipp Fischbeck, Tobias Friedrich, Alina Gries, Falk Hüffner, Otto Kißig, Pascal Lenzner, Louise Molitor, Leon Schiller, Armin Wells, and Simon Wietheger. A strategic routing framework and algorithms for computing alternative paths, 2020. URL: https://arxiv.org/abs/2008.10316.
  5. Vincenzo Bonifaci, Tobias Harks, and Guido Schäfer. Stackelberg routing in arbitrary networks. Mathematics of Operations Research, 35(2):330-346, 2010. Google Scholar
  6. Daniel Delling. Time-dependent SHARC-routing. Algorithmica, 60(1):60-94, 2009. URL: https://doi.org/10.1007/s00453-009-9341-0.
  7. Daniel Delling and Dorothea Wagner. Pareto paths with SHARC. In Experimental Algorithms, Lecture Notes in Computer Science, page 125–136. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02011-7_13.
  8. Daniel Delling and Dorothea Wagner. Time-dependent route planning. In Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems, pages 207-230. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-05465-5_8.
  9. Ugur Demiryurek, Farnoush Banaei-Kashani, and Cyrus Shahabi. A case for time-dependent shortest path computation in spatial networks. In Proceedings of SIGSPATIAL 2010, page 474–477. ACM, 2010. URL: https://doi.org/10.1145/1869790.1869865.
  10. Pierre Hansen. Bicriterion path problems. In Multiple Criteria Decision Making Theory and Application, page 109–127. Springer, 1980. URL: https://doi.org/10.1007/978-3-642-48782-8_9.
  11. INRIX, Inc. INRIX Verkehrsstudie: Stau verursacht Kosten in Milliardenhöhe. INRIX Press Releases, 2020. URL: https://inrix.com/press-releases/2019%2Dtraffic%2Dscorecard%2Dgerman/.
  12. George Karakostas and Stavros G Kolliopoulos. Stackelberg strategies for selfish routing in general multicommodity networks. Algorithmica, 53(1):132-153, 2009. Google Scholar
  13. Yannis A. Korilis, Aurel A. Lazar, and Ariel Orda. Achieving network optima using Stackelberg routing strategies. IEEE/ACM Transactions on Networking, 5(1):161-173, 1997. URL: https://doi.org/10.1109/90.554730.
  14. Alexander Kröller, Falk Hüffner, Lukasz Kosma, Katja Kröller, and Mattia Zeni. Driver expectations towards strategic routing. Unpublished Manuscript, 13 Pages. Google Scholar
  15. Ekkehard Köhler, Rolf H. Möhring, and Martin Skutella. Traffic networks and flows over time. In Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation, volume 5515 of Lecture Notes in Computer Science, page 166–196. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02094-0_9.
  16. Lawrence Mandow and José. Luis Pérez De La Cruz. Multiobjective A* search with consistent heuristics. Journal of the ACM, 57(5):27:1–27:25, 2008. URL: https://doi.org/10.1145/1754399.1754400.
  17. Ernesto Queirós Vieira Martins. On a multicriteria shortest path problem. European Journal of Operational Research, 16(2):236–245, 1984. URL: https://doi.org/10.1016/0377-2217(84)90077-8.
  18. Matthias Müller-Hannemann and Karsten Weihe. Pareto shortest paths is often feasible in practice. In Algorithm Engineering, page 185–197. Springer, 2001. Google Scholar
  19. Giacomo Nannicini, Daniel Delling, Dominik Schultes, and Leo Liberti. Bidirectional A* search on time-dependent road networks. Networks, 59(2):240-251, 2011. URL: https://doi.org/10.1002/net.20438.
  20. US Bureau of Public Roads. Office of Planning. Urban Planning Division. Traffic Assignment Manual for Application with a Large, High Speed Computer. US Department of Commerce, 1964. Google Scholar
  21. Andreas Paraskevopoulos and Christos D. Zaroliagis. Improved alternative route planning. In Proceedings of ATMOS 2013, pages 108-122. Schloss Dagstuhl, 2013. URL: https://doi.org/10.4230/OASIcs.ATMOS.2013.108.
  22. Tim Roughgarden. Selfish routing and the price of anarchy. MIT Press, 2005. Google Scholar
  23. Tim Roughgarden and Éva Tardos. How bad is selfish routing? Journal of the ACM, 49(2):236–259, March 2002. URL: https://doi.org/10.1145/506147.506153.
  24. Leon Sering and Martin Skutella. Multi-source multi-sink Nash flows over time. In Proceedings of ATMOS 2018, pages 12:1-12:20, 2018. URL: https://doi.org/10.4230/OASIcs.ATMOS.2018.12.
  25. Socrates2.0. Amsterdam pilot site launched with improved navigation service. Website, December 2019. URL: https://socrates2.org/news-agenda/amsterdam-pilot-launched-improved-navigation-service-testers-sought.
  26. Ben Strasser. Dynamic time-dependent routing in road networks through sampling. In Proceedings of ATMOS 2017, pages 3:1-3:17. Schloss Dagstuhl, 2017. URL: https://doi.org/10.4230/OASIcs.ATMOS.2017.3.
  27. Mariska Alice van Essen. The potential of social routing advice. PhD thesis, University of Twente, 2018. URL: https://doi.org/10.3990/1.9789055842377.
  28. John Glen Wardrop. Some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers, 1(3):325-362, 1952. URL: https://doi.org/10.1680/ipeds.1952.11259.
  29. Michael A. Yukish. Algorithms to Identify Pareto Points in Multi-Dimensional Data Sets. PhD thesis, Mechanical Engineering Dept., The Pennsylvania State University, State College, 2004. Google Scholar
  30. Shanjiang Zhu and David Levinson. Do people use the shortest path? An empirical test of Wardrop’s first principle. PLOS ONE, 10(8):1-18, 2015. URL: https://doi.org/10.1371/journal.pone.0134322.
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