License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2020.10
URN: urn:nbn:de:0030-drops-131469
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13146/
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
A Strategic Routing Framework and Algorithms for Computing Alternative Paths
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.
BibTeX - Entry
@InProceedings{blsius_et_al:OASIcs:2020:13146,
author = {Thomas Bl{\"a}sius and Maximilian B{\"o}ther and Philipp Fischbeck and Tobias Friedrich and Alina Gries and Falk H{\"u}ffner and Otto Ki{\ss}ig and Pascal Lenzner and Louise Molitor and Leon Schiller and Armin Wells and Simon Wietheger},
title = {{A Strategic Routing Framework and Algorithms for Computing Alternative Paths}},
booktitle = {20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
pages = {10:1--10:14},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-95977-170-2},
ISSN = {2190-6807},
year = {2020},
volume = {85},
editor = {Dennis Huisman and Christos D. Zaroliagis},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13146},
URN = {urn:nbn:de:0030-drops-131469},
doi = {10.4230/OASIcs.ATMOS.2020.10},
annote = {Keywords: Routing, Strategic Routing, Selfish Routing, Route Planning, Network Flow, Algorithm Design}
}
|
Keywords: |
|
Routing, Strategic Routing, Selfish Routing, Route Planning, Network Flow, Algorithm Design |
|
Collection: |
|
20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
10.11.2020 |
|
Supplementary Material: |
|
Source code: https://github.com/MaxiBoether/strategic-routing |
