Name
Abstract | ||
|---|---|---|
ABSTRACTTraffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. We extend this formalization and introduce the Multiple-Routes problem, which is given a start and destination and aims at finding up to n different routes that the drivers strategically disperse over, minimizing the overall travel time of the system. Due to the NP-hard nature of the problem, we introduce the Multiple-Routes evolutionary algorithm (MREA) as a heuristic solver. We study several mutation and crossover operators and evaluate them on real-world data of Berlin, Germany. We find that a combination of all operators yields the best result, improving the overall travel time by a factor between 1.8 and 3, in the median, compared to all drivers taking the fastest route. For the base case n = 2, we compare our MREA to the highly tailored optimal solver by Bläsius et al. [ATMOS 2020] and show that, in the median, our approach finds solutions of quality at least 99.69% of an optimal solution while only requiring 40 % of the time. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1145/3449639.3459307 | Genetic and Evolutionary Computation Conference |
Keywords | DocType | Citations |
Strategic routing, traffic congestion, optimization, evolutionary algorithm | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maximilian Böther | 1 | 0 | 1.01 |
| Leon Schiller | 2 | 0 | 1.35 |
| Philipp Fischbeck | 3 | 0 | 0.68 |
| Louise Molitor | 4 | 1 | 4.08 |
| Martin S. Krejca | 5 | 0 | 0.34 |
| Tobias Friedrich | 6 | 1 | 3.06 |