2026-08-02T17:37:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13146 2024-03-06T10:31:07Z ddc:004 open_access

A Strategic Routing Framework and Algorithms for Computing Alternative Paths Bläsius, Thomas Böther, Maximilian Fischbeck, Philipp Friedrich, Tobias Gries, Alina Hüffner, Falk Kißig, Otto Lenzner, Pascal Molitor, Louise Schiller, Leon Wells, Armin Wietheger, Simon Routing Strategic Routing Selfish Routing Route Planning Network Flow Algorithm Design 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Bläsius and Maximilian Böther and Philipp Fischbeck and Tobias Friedrich and Alina Gries and Falk Hüffner and Otto Kißig and Pascal Lenzner and Louise Molitor and Leon Schiller and Armin Wells and Simon Wietheger 2020 Is Part Of OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2020.10 urn:nbn:de:0030-drops-131469 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.10 eng https://creativecommons.org/licenses/by/3.0/legalcode