Inhaltszusammenfassung:
Ein effizienter Ressourcentransport ist für die Funktionalität von Netzen auf allen Ebenen von entscheidender Bedeutung. Während sich natürliche Systeme im Laufe der Zeit anpassen, um optimale Strukturen für den Transport zu erreichen, werden vom Menschen geschaffene Infrastrukturen nicht mit einem vergleichbaren Evolutionsmechanismus gebaut. Infolgedessen erfüllen diese Strukturen häufig nicht die ihnen zugedachten Gestaltungskriterien.
In dieser Arbeit werden Anpassungsregeln vorgestellt, die in biologischen Systemen verwurzelt sind und den Entwurf plausibler vom Menschen geschaffener Infrastrukturen ermöglichen. Konkret werden mathematische Modelle, die klassischerweise zur Untersuchung des Nährstofftransports in Pflanzen oder im menschlichen Körper verwendet werden, extrapoliert und durch einen Paradigmenwechsel zur Modellierung verschiedener Szenarien erweitert: Wir nutzen solche Gleichungen, um instrumentelle Erkenntnisse über den Aufbau künstlicher Netzwerke zu gewinnen.
Wir ziehen eine Verbindung zwischen Anpassungsregeln und Optimalität mit der Optimal Transport (OT) Theorie. Zunächst formulieren wir Anpassungsgleichungen, die auf das jeweilige Problem zugeschnitten sind. Dann versuchen wir, ein wohldefiniertes Lyapunov-Funktional für diese Gleichungen zu finden, das als die Kosten für den Transport von Masse entlang der Kanten eines Netzwerks interpretiert werden kann. Dies sind die Kosten, die in OT minimiert werden. Diese Verbindung ermöglicht es uns, Erkenntnisse und Methoden der Optimierung zu nutzen, um die Leistung zu verbessern und unsere Anpassungsschemata zu validieren.
Während dieser Mechanismus für gierige Routing-Probleme etabliert ist, erweitern wir ihn auf komplexere Szenarien.
Zunächst betrachten wir ein Multicommodity-Problem, bei dem sich verschiedene nicht mischbare Massenarten in einem gemeinsamen Netz bewegen. Indem sie in einer Infrastruktur interagieren, tragen die Massentypen dazu bei, die einmaligen Kosten zu minimieren. Wir stellen fest, dass eine durchdachte Kopplung der Massentypen für die Schaffung optimaler Netze von zentraler Bedeutung ist. Wir untersuchen auch Verkehrsüberlastungsregime, die durch einen kritischen Exponenten in den Anpassungsregeln kontrolliert werden, sowie die entsprechende Optimierungsformulierung. Die Multicommodity-Anpassungsgleichungen werden verwendet, um die Beförderung von Fahrgästen in der Pariser Métro und in den Straßen von Bordeaux zu untersuchen. Diese Anwendungen zeigen, welche Stationen entscheidend sind, um den Verkehr bei gezielten Knotenausfällen zu entlasten, und dass Straßenbahnen eine wertvolle Alternative sind, um die Überlastung der Busse zu verringern. Außerdem setzen wir diese Methode zur Verbesserung der überwachten Bildklassifizierung mit OT ein. In diesem Fall sind die Massentypen RGB-Farbverteilungen von Bildern, und die OT-Kosten werden als Proxy für die Bewertung ihrer Ähnlichkeit verwendet.
Zweitens untersuchen wir die optimale Gestaltung von Transportnetzen, in welche Massen zeitabhängig eingeführt werden. Unsere Hauptannahme ist die Modellierung der langsamen Entwicklung der Netzinfrastruktur, die durch periodische und schnell schwankende Massen, die in die Knoten eintreten, bestimmt wird. Indem wir die Existenz dieser beiden unterschiedlichen Zeitskalen postulieren, leiten wir Anpassungsregeln in geschlossener Form ab, die die Transportkosten bei Konvergenz reduzieren. Außerdem ermöglichen sie es, analytische Eigenschaften der Massen---ihre Fourier-Koeffizienten---mit der Topologie optimaler Netze zu verbinden. Wir verwenden diese Methode, um die Robustheit des Busnetzes von Bordeaux zu untersuchen.
Drittens stellen wir den Wettbewerb zwischen einem Netzmanager und gierigen Fahrgästen dar, die in einem zweistufigen Optimierungsproblem konkurrieren. Der erste versucht, das Verkehrsaufkommen durch die Erhebung von Straßenbenutzungsgebühren zu minimieren, während der zweite versucht, seine Reisekosten zu senken. Zur Lösung des Problems entwickeln wir ein Schema, bei dem sich Anpassungsregeln für gieriges Routing mit einem in geschlossener Form projizierten stochastischen Gradientenabstieg zur Abstimmung der Kantengewichte abwechseln. Unsere Studie über das internationale E-Road-Netz zeigt, dass eine informierte Mauterhebung für Straßen einen wirksamen Ausgleich zwischen Reisezeit und Staus schafft und dazu beitragen kann, den CO2-Fußabdruck von Straßen zu verringern.
Um unsere Ergebnisse reproduzierbar zu machen, ergänzen wir unsere Methoden mit Open-Source-Codes.
Zusammenfassend lässt sich sagen, dass unsere Modelle einen systematischen Ansatz für die Gestaltung von Verkehrsnetzen bieten, die für verschiedene Aufgaben optimal sind. Diese Werkzeuge sind wertvoll für Personen, die sich für diese Probleme interessieren, z.B. für politische Entscheidungsträger, die beurteilen wollen, ob eine Verkehrsinfrastruktur die Nachfrage der Nutzer effektiv erfüllt.
Abstract:
Efficient transportation of resources is critical for network functionality at all scales. However, while natural systems adapt over time to achieve optimal structures for transportation, man-made networks are not built with a comparable evolutionary mechanism. Consequently, these structures frequently fall short of meeting their intended design criteria.
This thesis presents adaptation rules rooted in biological systems that enable the design of plausible man-made infrastructures. Specifically, we extrapolate mathematical models classically used to study, for instance, the transport of nutrients in plants or the human body and extend them to model different problems with a paradigm shift: Use such equations to get instrumental insight on how to build artificial networks.
We connect adaptation rules and optimality with Optimal Transport (OT) theory. Initially, we formulate adaptation equations tailored to the problem at hand. Then, we aim to find a well-defined Lyapunov functional for these equations, which is interpretable as the cost to transport mass along the edges of a network. This is the cost minimized in OT. This link allows us to leverage optimization insights and methods to enhance performance and validate our adaptation schemes.
While this mechanism is established for greedy routing problems, we extend it to more complex scenarios.
First, we consider a multicommodity problem where different immiscible mass types move in a shared network. By interacting in one infrastructure, the mass types contribute to minimizing a unique cost. We observe that thoughtfully devising the coupling of mass types is pivotal to producing optimal networks. We also explore traffic congestion regimes controlled through a critical exponent entering the adaptation rules and its corresponding optimization formulation. The multicommodity adaptation equations are used to study the routing of passengers in the Paris Métro and the streets of Bordeaux. These applications showcase which stations are crucial to alleviating traffic under targeted node failures and that trams are a valuable alternative to reduce bus congestion. Furthermore, we employ this method for ameliorating supervised image classification with OT. Here, mass types are RGB color distributions of images, and the OT cost is used as a proxy to assess their similarity.
Second, we study optimal designs of transportation networks with time-dependent input mass loads. Our fundamental assumption is to model the slow evolution of the network infrastructure, which is governed by periodic and fast-fluctuating mass entering its nodes. By postulating the existence of these two different time scales, we derive closed-form adaptation rules that reduce the transport cost upon convergence. Additionally, they enable connecting analytical properties of the mass loads---their Fourier coefficients---with the topology of optimal networks. We use this method to study the robustness of Bordeaux's bus network.
Third, we frame the competition of a network manager and greedy passengers competing in a bilevel optimization problem. The first aims to minimize traffic by tolling roads, while the second move to reduce their travel costs. To solve the problem, we devise a scheme where adaptation rules for greedy routing are alternated with closed-form Projected Stochastic Gradient Descent for tuning edge weights. Our study on the international E-road network demonstrates that an informed tolling of roads effectively trades off travel time against congestion and can help reduce the carbon footprint of roads.
To make our results reproducible, we complement our methods with open-source codes.
In summary, our models provide a systematic approach to designing optimal transportation networks for different tasks. These tools are valuable for practitioners interested in these problems, for example, policymakers aiming to assess whether a transport infrastructure effectively meets user demand.
network science