Bittihn, Stefan Alexander (2018). Stochastic Transport Models on Simple Networks: Phase Diagrams and Braess Paradox. PhD thesis, Universität zu Köln.

[img]
Preview
PDF
dr_arbeit_rahmen.pdf - Accepted Version
Bereitstellung unter der CC-Lizenz: Creative Commons Attribution Non-commercial No Derivatives.

Download (8MB) | Preview

Abstract

The Braess paradox is a counterintuitive phenomenon that can occur in traffic networks, which are used by selfish users. It states that under certain circumstances the addition of a new road to a traffic network can result in increased travel times for all network users. This can have important consequences for the design of new traffic networks and for the extension of existing ones, since the naive assumption that the traffic situation in a road network always improves when adding new roads does not always hold. A detailed understanding of this paradox is needed, since possible negative externalities resulting from the construction of new roads have to be understood in order to be avoided. This is especially true, since the capacity of the road networks of many cities has long been reached and space for the construction of new roads is limited. Even though there have been numerous real world examples that indicate that the Braess paradox might occur in real world traffic networks, a deep understanding based on realistic traffic models is still missing. This thesis provides important stepping stones towards this much needed understanding. Most previous research on the topic focused on analysing deterministic mathematical models, the results of which are not directly transferable to real traffic networks. Often many oversimplifying assumptions were made: the description of traffic flow is reduced to unrealistic road travel time functions that increase linearly with the numbers of cars using the roads. Furthermore, perfect traffic information and perfectly rational decision makings of the network users were assumed. This thesis is dedicated to the study of the Braess paradox in networks of totally asymmetric exclusion processes (TASEPs). The TASEP models drivers as particles hopping on a one dimensional lattice. It is a simple stochastic transport model that includes microscopic interactions and exhibits a nonlinear current-density relation. The travel time functions of TASEPs have close-to-realistic shapes: they increase monotonically and diverge when approaching the maximum possible density. TASEPs do not reproduce all phenomena of real road traffic, but many basic features which are not included in most previous research on the Braess paradox, can be described. The network originally used by Braess is studied in several variants, but with the traffic flow described by TASEPs: various boundary conditions, route choice mechanisms and update types are considered. In a first step, it is shown that states realizing the paradox exist in TASEP networks. For this the decisions of the road users are tuned externally, i.e. users do not decide individually in an intelligent way, but are set to choose certain routes in the network. The user optimum states of the networks without and with the new roads are identified and their travel times are compared. It is shown that Braess’ paradox occurs in large regions of the phase space in the networks with added periodic boundary conditions and random-sequential dynamics. With fixed amounts of drivers assigned to individual routes, gridlock states are found in large parts of phase space. Assigning drivers to their routes according to turning probabilities results instates with strong fluctuations in travel times that dominate large regions of the phase space. Unexpected phases in which the system is prone to oscillations between several unstable states are observed in the system with open boundary conditions and random-sequential dynamics: the Braess paradox is observed in an indirect way, since an increase of travel times is expected if this system was used by ‘intelligent’ particles. If parallel dynamics are employed instead of random-sequential dynamics, the treatment becomes more complicated. Traffic lights are implemented to avoid potential conflicts at junction sites. Braess’ paradox is also observed in this case. Beyond confirming that Braess’ paradox can be observed in TASEP networks, phase diagrams which characterize the influences of the new road in more detail are presented for all analysed variants of the network. Braess’ paradox is also realized if intelligent particles, which individually choose their routes, use the network. In the second part of the thesis, a route choice algorithm is implemented and results of a performance test in the Braess network with periodic boundary conditions are presented. All particles choose their routes individually based on this algorithm. Several types of traffic information are used as input for the algorithm. The Braess paradox occurs if particles decide based on their own memories from previous travel experiences. It is also realized if all particles base their decisions on publicly available approximations of future travel times. These approximations are calculated based on the current positions of all particles in the system and are a type of information similar to that provided by smartphone apps in real traffic networks. It is also shown that the paradox occurs if some particles base their decisions on personal information and the others on public information. This situation is very similar to that of real commuters’ scenarios. These results further stress the importance of Braess’ paradox for real road networks.

Item Type: Thesis (PhD thesis)
Translated title:
TitleLanguage
Stochastische Transportprozesse auf einfachen Netzwerken: Phasendiagramme und Braess ParadoxonGerman
Translated abstract:
AbstractLanguage
Das Braess-Paradoxon ist ein kontraintuitives Phänomen, welches in Verkehrsnetzen mit egoistischen Nutzern auftreten kann. Es besagt, dass das Hinzufügen einer neuen Straße zu einem Verkehrsnetzwerk unter bestimmten Umständen zu längeren Reisezeiten für alle Nutzer führen kann. Dies kann wichtige Konsequenzen für die Planung neuer und den Ausbau bestehender Verkehrsnetzwerke haben, da die naive Annahme, dass zusätzliche Straßen immer zu einer besseren Verkehrssituation führen, nicht immer zutrifft. Um negative Folgen vom Bau neuer Straßen zu verhindern, ist ein detailliertes Verständnis des Paradoxons essenziell. Dies ist insbesondere wichtig, da die Kapazitäten der Straßennetzwerke vieler großer Städte schon lange erreicht und der Platz für den Bau neuer Straßen begrenzt ist. Trotz vieler Beispiele, welche darauf hindeuten, dass das Paradoxon in echten Straßennetzwerken auftritt, fehlt ein fundiertes Verständnis dieses Effekts. Die meisten bisherigen Arbeiten zu diesem Thema basierten auf deterministischen mathematischen Modellen, deren Ergebnisse sich nicht direkt auf reale Verkehrsnetze übertragen lassen. Darin wurden einige stark vereinfachende Annahmen getroffen. Die Beschreibung des Verkehrsflusses wurde auf Reisezeitfunktionen beschränkt, welche linear mit der Anzahl der Autos auf den Straßen zunehmen. Weiterhin wurde angenommen, dass allen Nutzern fehlerfreie Verkehrsinformationen zur Verfügung stehen und dass sie ihre Routen auf dieser Basis komplett rational wählen. In dieser Arbeit wird das Verständnis des Paradoxons auf eine realistischere Basis gehoben. Dazu werden Netzwerke aus total asymmetrischen Exklusionsprozessen ("totally asymmetric exclusion process", TASEP) in Bezug auf das Braess-Paradoxon untersucht. Der TASEP beschreibt Autos als Teilchen, welche auf einem eindimensionalen Gitter springen. Er ist ein einfaches stochastisches Transportmodell, welches mikroskopische Wechselwirkungen beinhaltet und eine nichtlineare Fluss-Dichte Relation aufweist. Auch Reisezeitfunktionen von TASEPs haben eine annähernd realistische Form, sie sind monoton wachsend und divergieren bei maximalen Dichten. Der TASEP kann nicht alle Phänomene von echtem Straßenverkehr beschreiben, bildet jedoch viele Effekte ab, welche in vorheriger Forschung oft vernachlässigt wurden. Die Netzwerkstruktur, welche in Braess ursprünglicher Veröffentlichung benutzt wurde, wird in verschiedenen Varianten analysiert, wobei der Verkehrsfluss im Netzwerk durch TASEPs beschrieben wird. Verschiedene Randbedingungen, Routenwahlverfahren und Dynamiken werden betrachtet. Zunächst werden die Entscheidungen der Nutzer extern festgelegt. Dies bedeutet, dass die Nutzer nicht intelligent entscheiden, welche Routen sie wählen, sondern dass diese extern vorgegeben werden. Durch Vergleiche der Nutzeroptimumszustände ("user optimum states") der Netzwerke mit und ohne neue Straße wird gezeigt, dass das Paradoxon in solchen Netzwerken grundsätzlich auftreten kann. Es wird gezeigt, dass das Braess-Paradoxon in großen Bereichen des Phasenraumes des Braess-Netzwerkes mit periodischen Randbedingungen und zufällig-sequentieller Dynamik auftritt. Verkehrsstillstände können in großen Bereichen des Phasenraumes gefunden werden, falls fixe Anzahlen von Nutzern bestimmte Routen wählen. Wenn Nutzer hingegen mit festgelegten Wahrscheinlichkeiten auf die Routen verteilt werden, sind in großen Bereichen des Phasenraumes starke Fluktuationen in den Reisezeiten zu beobachten. Unerwartete Phasen, in welchen das System potentiell zwischen nicht-stabilen Zuständen oszilliert können bei offenen Randbedingungen und zufällig-sequentieller Dynamik festgestellt werden. Das Braess-Paradoxon wird hier indirekt beobachtet, da eine resultierende Zunahme der Reisezeiten erwartet wird, falls dieses System von "intelligenten" Teilchen genutzt wird. Die Untersuchung der Netzwerke wird komplizierter, wenn parallele statt zufällig-sequentieller Dynamik verwendet wird. In diesem Fall werden Ampeln eingesetzt um potentielle Konflikte an Kreuzungen zu vermeiden. Das Braess-Paradoxon tritt auch in diesem Fall auf. Zusätzlich zu der Erkenntnis, dass das Braess-Paradoxon in TASEP Netzwerken beobachtet werden kann, werden Phasendiagramme für alle untersuchten Varianten des Netzwerkes präsentiert, welche die Auswirkungen des Hinzufügens einer neuen Straße detaillierter beschreiben. Das Braess-Paradoxon tritt auch auf, wenn Teilchen ihre Routen individuell intelligent wählen. Im zweiten Teil der Arbeit wird ein Routenwahlalgorithmus implementiert und am Beispiel des Braess-Netzwerkes mit periodischen Randbedingungen getestet. Verschiedene Arten von Verkehrsinformationen werden als Grundlage des Algorithmus genutzt und alle Teilchen wählen ihre Route individuell darauf basierend. Das Paradoxon tritt auf, wenn Teilchen Entscheidungen basierend auf ihren eigenen Erfahrungen treffen. Es tritt ebenfalls auf, wenn die Entscheidungen auf Abschätzungen zukünftiger Reisezeiten basieren, welche für alle Teilchen zugänglich sind. Diese Abschätzungen werden auf Basis der aktuellen Positionen aller Teilchen im System berechnet. Dies kann als Näherung von Verkehrsinformationen, wie sie von Smartphone-Apps zur Verfügung gestellt werden, verstanden werden. Es wird weiterhin gezeigt, dass das Paradoxon auftritt, wenn einige Nutzer ihre Entscheidungen auf Basis von persönlichen Erfahrungen und der Rest basierend auf ̈offentlich zur Verfügung stehenden Informationen treffen. Dies beschreibt die Situation von Pendlern im Berufsverkehr. Die erzielten Ergebnisse unterstreichen die Bedeutung des Braess-Paradoxons für reale Verkehrsnetzwerke.German
Creators:
CreatorsEmailORCID
Bittihn, Stefan Alexanderbittihn@thp.uni-koeln.deUNSPECIFIED
URN: urn:nbn:de:hbz:38-91666
Subjects: Physics
Uncontrolled Keywords:
KeywordsLanguage
Braess; Braess paradox; network; TASEP; totally asymmetric exclusion process; transport process; nonequilibrium; non-equilibrium; traffic; road network; road-networkEnglish
Braess; Braess Paradoxon; Netzwerk; TASEP; totally asymmetric exclusion process; Trasportprozess; Nichtgleichgewicht; Verkehr; StraßennetzwerkGerman
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Institute for Theoretical Physics
Language: English
Date: December 2018
Date of oral exam: 30 November 2018
Referee:
NameAcademic Title
Schadschneider, AndreasProf. Dr.
Krug, JoachimProf. Dr.
Refereed: Yes
URI: http://kups.ub.uni-koeln.de/id/eprint/9166

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item