Volltextdatei(en) vorhanden
Titel: Self-Organizing Transport Networks : Decentralized Optimization based on Genetic Programming
Sonstige Titel: Selbstorganisierende Transport-Netzwerke : Dezentrale Optimierung auf Basis genetischer Programmierung
Sprache: Englisch
Autor*in: Göbel, Johannes
Schlagwörter: Dezentrale Steuerung; Genetische Programmierung; Java; Decentralized Control; Genetic Programming; Java
GND-Schlagwörter: Evolution; Netzwerk; Programmierung; Organisation; Optimierung; Transport; Verkehr; Wartezeit
Erscheinungsdatum: 2012
Tag der mündlichen Prüfung: 2013-06-14
Zusammenfassung: 
The goal of this thesis is transport network optimization. Transport networks are defined as network topologies in which entities are processed by nodes and successively forwarded to the next node on a link. Capacity restrictions on both nodes and links may apply. Examples include urban traffic (vehicles/signalized intersections), IP networks (packets/routers), and automated production systems (items/workstations). The control and optimization of such networks, e.g. minimizing entity waiting times, particularly requires determining which of potentially multiple entities waiting at a node should be processed next. Such decisions or general rules to base such decisions on can be imposed and altered if need be by a central authority based on global knowledge of the network state. In such centralized solutions, entity processing as conducted by the nodes typically is subject to constraints such as fixed signal plans, which are periodically applied in urban traffic; without implementing such constraints, dynamically determining node behaviour would be computationally infeasible.
In contrast, a self-organizing transport network as proposed in this thesis relies on decision rules that require local data like traffic densities and current queue lengths as their only input. Genetic programming is used to evolve such rules, which – once deployed – can be autonomously applied by the nodes to dynamically prioritize waiting entities without contacting a central server. Such a decentralized network control is scalable and robust. Furthermore, empirical results indicate that the performance is similar to or even better than centrally controlled systems: among multiple nodes, the synchronization of entity processing is achieved implicitly. The nodes may be unable to base entity prioritization on global traffic data; this, however, is compensated for by the absence of processing constraints such as fixed signal plans.

Das Ziel dieser Arbeit ist die Optimierung so genannter Transport-Netzwerke, also von Netzwerk-Topologien, in denen Knoten Entitäten „bearbeiten“ und anschließend zum nächsten Knoten weiterleiten, wobei sowohl für das „Bearbeiten“ der Entitäten an den Knoten als auch für das Durchqueren der Kanten Kapazitätsbeschränkungen gelten können. Beispiele für solche Netzwerke sind Stadtverkehr (Autos, ampelgesteuerte Kreuzungen), IP-Netzwerke (IP-Pakete, Router) und automatische Produktionssysteme (Werkstücke, Maschinen). Als Teil von Steuerung und ggf. Optimierung solcher Netzwerke, also z.B. der Minimierung der Wartezeiten der Entitäten, muss insbesondere definiert werden, welche von potenziell mehreren zu einem Zeitpunkt an einem Knoten wartenden Entitäten als nächste „bearbeitet“ und weitergeleitet werden sollen. Diese Entscheidung kann von einem zentralen Server bzw. auf Basis von allgemeinen Regeln getroffen werden, die von einem zentralen Server festgesetzt und bei Bedarf geändert werden; hierfür muss der Server den Zustand des Netzwerkes (z.B. mittlere Flüsse, Verteilung der Entitäten) kennen. Bei Anwendung einer Zentralsteuerung erfolgt die Bearbeitung der Entitäten durch die Knoten typischerweise nicht beliebig flexibel: Für das Handeln der Knoten gelten Einschränkungen, z.B. in Form von sich zyklisch wiederholenden festen Ampelphasen im Stadtverkehr. Dies ist ein notwendiges Zugeständnis, um den Rechenaufwand der zentralen Instanz zu beschränken – andernfalls wäre eine dynamische, zentrale Steuerung nicht möglich.
Im Gegensatz dazu erfolgt die Priorisierung der „Bearbeitung“ der Entitäten in den Knoten eines in dieser Arbeit vorgeschlagenen „selbstorganisierenden Transport-Netzwerks“ vollständig autonom und dezentral, also ohne Kommunikation mit einer zentralen Instanz. Im Rahmen seiner Programmlogik zur Priorisierung der Entitäten kann der Knoten somit ausschließlich auf lokal verfügbare Daten zurückgreifen, z.B. auf die Längen seiner Warteschlangen. Eine solche Netzwerksteuerung ist skalierbar und robust. Hinsichtlich der Wartezeiten der Entitäten lassen sich vergleichbare oder sogar bessere Ergebnisse als bei typischen zentralen Steuerungsansätzen erzielen: Die Synchronisation der Knoten erfolgt implizit und das Fehlen globaler Netzwerkzustandsdaten wird durch die zusätzliche Flexibilität der Knoten, die nicht z.B. an feste Schaltpläne gebunden sind, kompensiert.
URL: https://ediss.sub.uni-hamburg.de/handle/ediss/4970
URN: urn:nbn:de:gbv:18-62435
Dokumenttyp: Dissertation
Betreuer*in: Page, Bernd (Prof. Dr.-Ing.)
Enthalten in den Sammlungen:Elektronische Dissertationen und Habilitationen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat  
Dissertation.pdf4.77 MBAdobe PDFÖffnen/Anzeigen
Zur Langanzeige

Diese Publikation steht in elektronischer Form im Internet bereit und kann gelesen werden. Über den freien Zugang hinaus wurden durch die Urheberin / den Urheber keine weiteren Rechte eingeräumt. Nutzungshandlungen (wie zum Beispiel der Download, das Bearbeiten, das Weiterverbreiten) sind daher nur im Rahmen der gesetzlichen Erlaubnisse des Urheberrechtsgesetzes (UrhG) erlaubt. Dies gilt für die Publikation sowie für ihre einzelnen Bestandteile, soweit nichts Anderes ausgewiesen ist.

Info

Seitenansichten

90
Letzte Woche
Letzten Monat
geprüft am 18.04.2021

Download(s)

20
Letzte Woche
Letzten Monat
geprüft am 18.04.2021
Werkzeuge

Google ScholarTM

Prüfe