research-article

Open access

Evolutionary minimization of traffic congestion

Authors:

Maximilian Böther,

Philipp Fischbeck,

Louise Molitor,

Martin S. Krejca,

Tobias FriedrichAuthors Info & Claims

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 937 - 945

https://doi.org/10.1145/3449639.3459307

Published: 26 June 2021 Publication History

Abstract

Traffic 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.

Supplementary Material

PDF File (p937-bother_suppl.pdf)

p937-bother_suppl.pdf

Download
592.62 KB

References

[1]

Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2013. Alternative Routes in Road Networks. Journal of Experimental Algorithmics 18, Article 1.3 (2013), 17 pages.

Digital Library

[2]

Enrique Alba, Gabriel Luque, and Sergio Nesmachnow. 2013. Parallel meta-heuristics: recent advances and new trends. International Transactions in Operational Research 20, 1 (2013), 1--48.

[3]

Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. 2016. Route Planning in Transportation Networks. In Algorithm Engineering: Selected Results and Surveys. Springer International Publishing.

[4]

Martin J. Beckmann, Charles B. MacGuire, and Christopher B. Winsten. 1956. Studies in the Economics of Transportation. Yale University Press.

[5]

Jean Berger and Mohamed Barkaoui. 2003. A Hybrid Genetic Algorithm for the Capacitated Vehicle Routing Problem. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2003. 646--656.

[6]

Thomas Bläsius, Maximilian Böther, Philipp Fischbeck, Tobias Friedrich, Alina Gries, Falk Hüffner, Otto Kißig, Martin S. Krejca, Pascal Lenzner, Louise Molitor, Leon Schiller, Armin Wells, and Simon Wietheger. 2021. Strategic Routing GitHub Repository. Retrieved April 03, 2021 from https://github.com/MaxiBoether/strategic-routing

[7]

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. 2020. A Strategic Routing Framework and Algorithms for Computing Alternative Paths. In Proceedings of the 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2020. 10:1--10:14.

[8]

Nick Cohn. 2019. The Tom Tom Traffic Index: An Objective Measure of Urban Traffic Congestion. Retrieved January 27, 2021 from https://www.tomtom.com/blog/road-traffic/urban-traffic-congestion/

[9]

James Patrick Cohoon, Shailesh U. Hegde, Worthy N. Martin, and Dana S. Richards. 1987. Punctuated Equilibria: A Parallel Genetic Algorithm. In Proceedings of the Second International Conference on Genetic Algorithms and Their Application. 148--154.

[10]

Stella Dafermos. 1980. Traffic Equilibrium and Variational Inequalities. Transportation Science 14, 1 (1980), 42--54.

Digital Library

[11]

Leonardo Dagum and Ramesh Menon. 1998. OpenMP: An Industry Standard API for Shared Memory Programming. IEEE Computational Science and Engineering 5, 1 (1998), 46--55.

Digital Library

[12]

Kalyanmoy Deb and Christie Myburgh. 2016. Breaking the Billion-Variable Barrier in Real-World Optimization Using a Customized Evolutionary Algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2016. 653--660.

Digital Library

[13]

Daniel Delling. 2009. Time-Dependent SHARC-Routing. Algorithmica 60, 1 (2009), 60--94.

[14]

Daniel Delling and Dorothea Wagner. 2009. Time-Dependent Route Planning. In Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems. Springer, 207--230.

Digital Library

[15]

Ugur Demiryurek, Farnoush Banaei-Kashani, and Cyrus Shahabi. 2010. A Case for Time-Dependent Shortest Path Computation in Spatial Networks. In Proceedings of SIGSPATIAL 2010. ACM, 474--477.

Digital Library

[16]

Edsger Wybe Dijkstra. 1959. A Note on Two Problems in Connexion with Graphs. Numer. Math. 1, 1 (1959), 269--271.

Digital Library

[17]

Marguerite Frank and Philip Wolfe. 1956. An Algorithm for Quadratic Programming. Naval Research Logistics Quarterly 3, 1-2 (1956), 95--110.

[18]

Mark Galassi, Jim Davies, James Theiler, Brian Gough, Gerard Jungman, Patrick Alken, Michael Booth, Fabrice Rossi, and Rhys Ulerich. 2019. GNU Scientific Library Reference Manual. Network Theory Ltd.

[19]

Alexander Kröller, Falk Hüffner, Łukasz Kosma, Katja Kröller, and Mattia Zeni. 2021. Driver Expectations towards Strategic Routing. Transportation Research Record (2021). To appear.

[20]

Ekkehard Köhler, Rolf H. Möhring, and Martin Skutella. 2009. Traffic Networks and Flows over Time. In Algorithmics of Large and Complex Networks. Springer, 166--196.

Digital Library

[21]

Henry B. Mann and Donald R. Whitney. 1947. On a Test of Whether one of Two Random Variables is Stochastically Larger than the Other. The Annals of Mathematical Statistics 18, 1 (1947), 50--60.

[22]

Giacomo Nannicini, Daniel Delling, Dominik Schultes, and Leo Liberti. 2011. Bidirectional A* search on time-dependent road networks. Networks 59, 2 (2011), 240--251.

Digital Library

[23]

John F. Nash. 1950. Equilibrium Points in n-Person Games. Proceedings of the National Academy of Sciences 36, 1 (1950), 48--49.

[24]

Andreas Paraskevopoulos and Christos D. Zaroliagis. 2013. Improved Alternative Route Planning. In Proceedings of ATMOS 2013. Schloss Dagstuhl, 108--122.

[25]

Jean-Yves Potvin. 2009. State-of-the Art Review---Evolutionary Algorithms for Vehicle Routing. INFORMS Journal on Computing 21, 4 (2009), 518--548.

[26]

Tim Roughgarden and Eva Tardos. 2002. How Bad is Selfish Routing? J. ACM 49, 2 (2002), 236--259.

Digital Library

[27]

Dan Simon. 2013. Evolutionary Optimization Algorithms. Wiley-Blackwell.

[28]

United States Bureau of Public Roads, Office of Planning, Urban Planning Division. 1964. Traffic Assignment Manual for Application with a Large, High Speed Computer.

[29]

Mariska Alice van Essen. 2018. The Potential of Social Routing Advice. Ph.D. Dissertation. University of Twente.

[30]

John Glen Wardrop. 1952. Some Theoretical Aspects of Road Traffic Research. Proceedings of the Institution of Civil Engineers 1, 3 (1952), 325--362.

[31]

Tian Zhang, Raghu Ramakrishnan, and Miron Livny. 1996. BIRCH: An Efficient Data Clustering Method for Very Large Databases. ACM SIGMOD Record 25, 2 (1996), 103--114.

Digital Library

[32]

Shanjiang Zhu and David Levinson. 2015. Do People Use the Shortest Path? An Empirical Test of Wardrop's First Principle. PLOS ONE 10, 8 (2015), 1--18.

Cited By

Antipov DNeumann ANeumann FLi XHandl J(2024)A Detailed Experimental Analysis of Evolutionary Diversity Optimization for OneMinMaxProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654082(467-475)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654082
Böther MSchiller LFischbeck PMolitor LKrejca MFriedrich T(2022)Evolutionary Minimization of Traffic CongestionIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.322875027:6(1809-1821)Online publication date: 13-Dec-2022
https://dl.acm.org/doi/10.1109/TEVC.2022.3228750
Yarkoni SRaponi EBäck TSchmitt S(2022)Quantum annealing for industry applications: introduction and reviewReports on Progress in Physics10.1088/1361-6633/ac8c5485:10(104001)Online publication date: 21-Sep-2022
https://doi.org/10.1088/1361-6633/ac8c54

Index Terms

Evolutionary minimization of traffic congestion
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
      2. Randomized search

Recommendations

Evolutionary Minimization of Traffic Congestion
Traffic 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. ...
Comparing evolutionary algorithms to the (1+1) -EA

In this paper, we study the conditions in which the random hill-climbing algorithm (1 + 1)-EA compares favorably to other evolutionary algorithms (EAs) in terms of fitness function distribution at a given iteration and with respect to the average ...
A novel differential evolution using a mixed mutation strategy
ICIMCS '10: Proceedings of the Second International Conference on Internet Multimedia Computing and Service

Differential Evolution (DE) is well-known as a simple and efficient evolutionary algorithm for global optimization problems. However, the mutation strategies used in DE greatly affect its performance. Although many mutation operators have been proposed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference

June 2021

1219 pages

ISBN:9781450383509

DOI:10.1145/3449639

Editor:
Francisco Chicano
University of Malaga
,
General Chair:
Krzysztof Krawiec
Poznan University of Technology

Copyright © 2021 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '21

Sponsor:

SIGEVO

GECCO '21: Genetic and Evolutionary Computation Conference

July 10 - 14, 2021

Lille, France

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
791
Total Downloads

Downloads (Last 12 months)163
Downloads (Last 6 weeks)18

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Antipov DNeumann ANeumann FLi XHandl J(2024)A Detailed Experimental Analysis of Evolutionary Diversity Optimization for OneMinMaxProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654082(467-475)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654082
Böther MSchiller LFischbeck PMolitor LKrejca MFriedrich T(2022)Evolutionary Minimization of Traffic CongestionIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.322875027:6(1809-1821)Online publication date: 13-Dec-2022
https://dl.acm.org/doi/10.1109/TEVC.2022.3228750
Yarkoni SRaponi EBäck TSchmitt S(2022)Quantum annealing for industry applications: introduction and reviewReports on Progress in Physics10.1088/1361-6633/ac8c5485:10(104001)Online publication date: 21-Sep-2022
https://doi.org/10.1088/1361-6633/ac8c54

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents