1. the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result; Evolutionary Minimization of Traffic Congestion 2. the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper(s); Maximilian Böther Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany maximilian.boether@student.hpi.de +49 331 5509-414 Leon Schiller Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany leon.schiller@student.hpi.de +49 331 5509-414 Philipp Fischbeck Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany philipp.fischbeck@hpi.de +49 331 5509-413 Louise Molitor Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany louise.molitor@hpi.de +49 331 5509-414 Martin S. Krejca LIP6, CNRS Sorbonne University 4 place Jussieu 75252 Paris France martin.krejca@lip6.fr +33 1 44 27 87 96 Tobias Friedrich Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany tobias.friedrich@hpi.de +49 331 5509-410 3. the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition); Martin Krejca 4. the abstract of the paper(s); 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. 5. a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies; (B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal. (E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions. (G) The result solves a problem of indisputable difficulty in its field. 6. a statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission); (B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal. Our paper extends the results of a recent paper by Bläsius et al., published at the prestigious workshop ATMOS (2020). The previous paper considered re-routing traffic by suggesting a single alternative to an established route. Besides the NP-hard nature of this problem, Bläsius et. al propose a highly problem-specific optimal algorithm in the sense of solution quality. We extend this setting to proposing arbitrarily many routes, without necessarily being bound to an established route. In direct comparison to the algorithm of Bläsius et al., our general evolutionary algorithm gets very close in terms of solution quality (up to 99.69 % in median) while only requiring about 40 % of the time. In addition of our algorithm being faster than the competitor, it is also more general in the sense that it does not need to address the flow of traffic – in contrast, the algorithm by Bläsius et al. requires this. Our algorithm can be used for arbitrary objectives (such as CO2 emissions) as long as more drivers yield a higher value of the objective to be minimized. (E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions. Human drivers are bad at avoiding traffic congestions. The main reason is that congestion is a global phenomenon, whereas each driver only has access to very local information. Making greedy choices is not sufficient in such a context. Traffic lights, as an early man-made tool assist to a certain extent in managing traffic, especially when the lights are adjusted with respect to the current traffic situation. However, they do not provide alternatives to the drivers. They only manage a fair flow of traffic at crossings. Our approach is not bound to this limitation, and it makes use of information about the network, which is global. While this drastically increases the complexity of the problem, our operators are engineered (and tested) to provide a good trade-off between efficiency and solution quality. Further, our algorithm incorporates a model of the drivers’ willingness to take alternative routes, thus making sure to make the results still attractive to actual humans. (G) The result solves a problem of indisputable difficulty in its field. As we prove, the problem we solve heuristically is NP-hard. However, even without such a proof, it is clear that avoiding traffic congestion is a hard task, as major streets of large cities are typically packed during rush hours. Even with the help of traffic lights and navigation systems that manage the flow of traffic (sometimes using live data), the general problem of traffic congestion in cities remains. Our approach helps in solving this problem, as it can be used by drivers and city planners alike. By adjusting the degrees of alternative routes to consider, the user has direct control over the complexity of the solution. Further, our algorithm can also optimize for other objectives than traffic load. Thus, it provides more flexibility than current approaches. 7. a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable); Author names: Maximilian Böther, Leon Schiller, Philipp Fischbeck, Louise Molitor, Martin S. Krejca, Tobias Friedrich Name of the conference: The Genetic and Evolutionary Computation Conference 2021 8. a statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors; Any prize money, if any, is to be divided equally among the two undergraduate students of this paper, who worked on the algorithm as part of their bachelor theses. The students' names are: – Maximilian Böther – Leon Schiller 9. a statement stating why the authors expect that their entry would be the "best," and Reducing traffic congestion is a long-standing hard problem with a huge relevance. Nowadays, additional factors, such as CO2 emissions or different roads only accessible for certain types of cars, make the problem even harder. We believe that our solution tackles this highly important problem elegantly, due to the following properties: – It is customizable. The objective function can be any value associated with a road that is monotone in the number of drivers. This includes the travel time, the CO2 emissions, or also noise levels. Further, we propose different operators, and we highlight their benefits. The algorithm makes use of a pool of these operators in a general manner. Thus, it is easy to add or remove operators at will. – It is fast. Compared to the tailored solution of Bläsius et al. for a special case of our problem, our approach only requires about 40 % of the run time while basically reaching the same solution quality. While the wall clock time depends on the complexity of the specific instance, this is a huge gain. In general, for our test scenarios described in the paper, each run took at most an hour. – It allows for warm restarts. Since our approach is an evolutionary algorithm, the initial population can be chosen arbitrarily. Although we make sure to initialize it with good solutions, the user can choose their own distribution. Especially, if a desirable solution was found and the road network changes, the algorithm can be started from the already known good solution, if wanted. – It provides multiple solutions. First, since we make use of a population, the user is presented a set of solutions, from which they can choose the one they prefer best. We make sure that duplicate solutions only occur if alternative solutions are far worse. Second, since our approach is randomized, different seeds can lead to different solutions, most likely with similar quality. 10. An indication of the general type of genetic or evolutionary computation used, such as GA (genetic algorithms), GP (genetic programming), ES (evolution strategies), EP (evolutionary programming), LCS (learning classifier systems), GE (grammatical evolution), GEP (gene expression programming), DE (differential evolution), etc. genetic algorithm 11. The date of publication of each paper. If the date of publication is not on or before the deadline for submission, but instead, the paper has been unconditionally accepted for publication and is “in press” by the deadline for this competition, the entry must include a copy of the documentation establishing that the paper meets the “in press” requirement. Copy of the paper attached to the e-mail.