Mathematical modelling, simulation and optimisation of dynamic transportation networks : with applications in production and traffic

Ziegler, Ute; Herty, Michael

doi:urn:nbn:de:hbz:82-opus-44522

Mathematical modelling, simulation and optimisation of dynamic transportation networks : with applications in production and traffic = Mathematische Modellierung, Simulation und Optimierung dynamischer Transportnetzwerke mit Anwendung in Produktion und Verkehr

Ziegler, Ute (Author)

2012 & 2013

Verantwortlichkeitsangabevorgelegt von Ute Ziegler

ImpressumAachen : Publikationsserver der RWTH Aachen University 2012

UmfangIV, 172 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2012

Prüfungsjahr: 2012. - Publikationsjahr: 2013

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Herty, Michael (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2012-11-27

Online
URN: urn:nbn:de:hbz:82-opus-44522
URL: https://publications.rwth-aachen.de/record/210495/files/4452.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Gemischt-ganzzahlige Optimierung (Genormte SW) ; Netzwerk (Genormte SW) ; Dynamik (Genormte SW) ; Mathematische Modellierung (Genormte SW) ; Heuristik (Genormte SW) ; Mathematik (frei) ; Transportgleichung (frei) ; Verkehrssimulation (frei) ; Produktionsnetzwerk (frei) ; Differentialgleichungen (frei) ; mixed-integer optimization (frei) ; branch and bound algorithm (frei) ; differential equations (frei) ; dynamic networks (frei) ; heuristics (frei) ; traffic network model (frei) ; production network model (frei)

Thematische Einordnung (Klassifikation)
DDC: 510
msc: 35R02 * 90B20 * 90B30 * 35Q93 * 90C57

Kurzfassung
Die Dissertation befasst sich mit einer allgemeinen Klassifizierung dynamischer Transportnetzwerke. Ihnen liegen Netzwerkflussprobleme zugrunde, die in makroskopischen Modellen mit Hilfe von Differentialgleichungen formuliert werden. Vielfältige Versionen ermöglichen die Anpassung an verschiedenste Anwendungen. So ist es zum Beispiel möglich, Puffer zu modellieren, in denen Partikel zwischengelagert werden können. Außerdem kann man die Entwicklung der Partikeldichte über Erhaltungsgleichungen beschreiben und verschiedene Kopplungesbedingungen an den Verzweigungspunkten modellieren. Als Nächstes werden Optimierungstechniken betrachtet. Die Vorteile von gemischt ganzzahliger Optimierung werden diskutiert und eine allgemeine Strategie vorgestellt, wie dynamische Transportnetzwerke in gemischt-ganzzahlige Optimierungsprobleme umgewandelt werden können. Außerdem wird gezeigt, wie das Wissen über die Problemstruktur ausgenutzt werden kann, um Abschätzungsheuristiken zu entwickeln, mit deren Hilfe man den Optimierungsprozess in höchst effizienter Weise beschleunigen kann. In diesem Zusammenhang werden spezielle Modelle für die Anwendung in Produktion und Verkehr vorgestellt. Das erste ist ein Produktionsmodell mit zeitlich veränderlicher Arbeiteraufteilung. Die Hauptidee ist es, die Systemleistung optimal zu halten, unter der Annahme, dass Machinen ausfallen und repariert werden müssen. Im Allgemeinen ist die Anzahl der Reparaturarbeiter begrenzt, so dass eine Entscheidung getroffen werden muss, welche Machine zuerst repariert wird. Dies führt zu der Optimierungsfrage, wie eine optimale Arbeiteraufteilung aussehen muss, um den Produktionsfluss zu maximieren. Diese Fragestellung wird intensiv analysiert und numerische Fallstudien, die fest und zeitlich veränderliche Aufteilungen vergleichen, werden vorgestellt. Die numerischen Ergebnisse zeigen die verschiedenen Möglichkeiten dieses Modellansatzes. Die zweite Anwendung bezieht sich auf ein Verkehrsflussmodell, dass auf Gleichungen von Lighthill, Witham und Richards basiert. Es wird gezeigt, wie verschiedene Kreuzungstypen in leicht linearisierbare Minimum-Ausdrücke umformuliert werden können. Wir entwickeln einen numerischen Rahmen für eine Verkehrsflussmodellierung über Hamilton-Jacobi Gleichungen und zeigen, wie die korrekte Dynamik an den Kopplungsstellen erfasst werden kann. Simulationen für einen Verkehrskreisel werden vorgestellt und mit schon bekannten Ergebnissen verglichen. Desweiteren werden Reisezeiten für bestimmte Strecken durch Netzwerke abhängig von der Startzeit der Reise berechnet. Ein Ampelmodell wird vorgestellt, das leicht an beliebige Kreuzungstypen und Netzwerktopologien angepasst werden kann, und Bedingungen für sichere Ampelschaltungen werden diskutiert. Wir zeigen die Notwendigkeit zusätzlicher Bedingungen an die Ampelschaltung um zu hohe Fluktuationen zu vermeiden, die auftreten können, wenn gemischt-ganzzahlige Optimierungstechniken verwendet werden, und lösen diese Problem mit den zuvor vorgestellten Techniken. Das Wissen um die Modellstruktur ermöglicht die Entwicklung von speziellen Heuristiken die zur Beschleunigung des Optimierungsprozesses eingesetzt werden können, indem sie während des Branch&Bound-Verfahrens zulässige Lösungen für die einzelnen Unterprobleme berechnen. Die resultierenden Verbesserungen des Optimierungsprozesses sind bemerkenswert und weisen auf das Potential hin, das in der Kombination von Simulationen und Branch&Bound Methoden liegt.

In this work we provide a general classification of dynamic transportation networks (DTNs), which represent macroscopic PDE/ODE-based descriptions of network flow problems. There is a broad variety of versions depending on the application; for example it is possible to model buffers, where particles can be stored. Furthermore, we can describe the evolution of density by conservation laws and model different kinds of coupling conditions. Afterwards we consider optimisation techniques. We discuss the advantages of mixed integer optimisation and presented a general strategy how DTNs can be transformed into linear mixed-integer optimization Problems (short MIPs). Furthermore, we show how the knowledge of the problem structure can be used to introduce bounding heuristics which are extremely efficient to speed up the optimisation procedure. Within this frame, we present specific models with application in production and traffic. The first is a novel production model for the time-changing repair worker assignment. The main idea is to keep the system performance optimal whenever machines have failed and must be repaired. In general, available workers are limited and therefore a decision has to be made on which machines are repaired first. The resulting optimisation question is how the optimal worker schedule looks like to maximise the production flow. This issue is intensively analysed and numerical case studies comparing fixed and time-changing schedules are presented. The numerical results show the different opportunities of our modelling approach. With respect to the second application, we consider the LWR-based traffic flow network model. We show how coupling conditions of several junction types can be transformed into easily linearisable min-terms. We introduce a numerical framework for the Hamilton-Jacobi formulation of traffic flow and show how this correctly resolves the dynamics at the junction. We present simulations for a roundabout and compare them with existing results and computed travel times for certain routes through the network depending on the starting time of the travel. Moreover, we model traffic light settings for LWR-based traffic flow networks that can easily be adapted to arbitrary junction types and network topologies and discuss requirements for secure traffic light settings. We show the necessity of additional requirements on the switching time rate to avoid inapplicably frequent fluctuations which appear when mixed integer optimisation techniques are used, and solve this problem with previously derived techniques. Furthermore, we use the knowledge of the problem structure to develop bounding heuristics to speed up the optimisation process by providing feasible solutions for the subproblems within the Branch&Bound procedure. The resulting improvements for the optimisation procedure are remarkable and indicate the potential of combining simulation techniques with Branch & Bound procedures.

Fulltext:
PDF