Universität zu Köln

Ullrich, Oliver (2014). Modellbasierte Parallelisierung von Anwendungen zur Verkehrssimulation - Ein dynamischer und adaptiver Ansatz. PhD thesis, Universität zu Köln.

Preview

PDF Dissertation_Oliver_Ullrich.pdf Download (4MB)

Abstract

Im Rahmen des Projekts Computer Aided Tram Scheduling (CATS) werden Methoden und Werkzeuge zum Generieren, Simulieren und Bewerten von Stadtbahnfahrplänen entwickelt, die von den Verkehrsplanern vor Ort auf Desktop-PCs oder Notebooks genutzt werden können. Das wissenschaftliche Interesse liegt dabei in der Erforschung und Entwicklung der benötigten Konzepte und Verfahren, diese liegen hauptsächlich in den Bereichen mathematische Optimierung und diskrete Simulation. In diesem Zusammenhang entstand der Wunsch nach einer parallelen Simulationsanwendung, die deutlich genauer und schneller als das bestehende sequentielle Modul arbeitet. Im Rahmen dieser Arbeit werden Ziele aus drei Bereichen bearbeitet: Zunächst soll ein Verfahren zur modellbasierten Parallelisierung diskreter Simulationsanwendungen entworfen werden. Dabei sollen eine Reihe von Eigenschaften genutzt werden, die u.a. viele Verkehrsmodelle aufweisen. Um die von der Zielplattform zur Verfügung gestellten Ressourcen auszunutzen, soll der Ansatz ein dynamisches und adaptives Lastausgleichsverfahren beinhalten. Das Verfahren soll als Framework zur Entwicklung von Simulationsanwendungen implementiert werden, sein dynamisches Verhalten soll anhand von Beispielanwendungen untersucht werden. Weiterhin sollen die im Rahmen des Projekts CATS erstellten Werkzeuge vorgestellt werden. Im Vordergrund soll dabei das auf das beschriebene Framework aufsetzende, parallele Simulationsmodul stehen, mit dessen Hilfe die dynamischen Eigenschaften von Stadtbahnfahrplänen untersucht werden können. Um hierzu Kandidaten zu haben, soll eine Optimierungsanwendung genutzt werden, die Fahrpläne hinsichtlich ihrer Robustheit optimiert und gleichzeitig planerische Ansprüche an einsatztaugliche Fahrpläne berücksichtigt. Um die Nutzung mit verschiedenen Stadtbahnnetzen zu ermöglichen, sollen die Anwendungen einen von vielen Verkehrsunternehmen genutzten Datenstandard verwenden. Zuletzt sollen die erstellten Werkzeuge noch praktisch erprobt werden. Hierzu werden die Stadtbahnnetze der Städte Köln und Montpellier modelliert, und sowohl robuste als auch bewusst nicht robuste Fahrpläne für sie generiert. Diese Fahrpläne werden gemeinsam mit den von den Verkehrsunternehmen real verwendeten Fahrplänen simuliert unddie dabei resultierenden Verspätungsdaten verglichen. Die Arbeit beginnt mit einer Einführung in Kontext, Motivation und Ziele (Kapitel 1), gefolgt von einigen Hintergründen zu Verfahren der parallelen Berechnung von diskreten Simulationsmodellen. Dabei werden eine Reihe von allgemeinen und anwendungsbezogenen Parallelisierungsverfahren betrachtet (Kapitel 2). Danach wird ein Verfahren entwickelt, das insbesondere für die parallele Simulation von diskreten Verkehrsmodellen geeignet ist. Zuerst wird die Idee des Verfahrens beschrieben und auf die Umsetzung eingegangen, dann werden einige Überlegungen zu Skalierbarkeit und Effizienz des Verfahrens angestellt (Kapitel 3). Darauf folgt die Beschreibung einer Implementierung des Verfahrens als Framework für Simulationsanwendungen (Kapitel 4). Die Überlegungen zum Verhalten des Verfahrens werden nun ergänzt um eine Reihe von Beobachtungen, die bei Experimenten mit der Simulation von Tokenbewegungen auf zufällig erzeugten Graphen gemacht werden (Kapitel 5). Danach folgt die eigentliche Anwendung des Verfahrens: Hintergründe und Architektur des Projekts CATS werden erläutert, dazu die eingesetzten Optimierungs- und Simulationsmodelle beschrieben. Das Optimierungsmodul und die auf das vorgestellte Framework aufsetzende Simulationsanwendung werden genutzt, um Fahrpläne für die Stadtbahnnetze von Köln und Montpellier zu generieren und auszuwerten. Darauf folgen einige Beobachtungen zum Laufzeitverhalten der Simulationsanwendung (Kapitel 6). Die Arbeit endet mit einer kurzen Zusammenfassung des Erreichten und einem Ausblick auf weitere Forschungsmöglichkeiten (Kapitel 7).

Item Type:	Thesis (PhD thesis)
Translated title:	Title Language Model-based parallelization of traffic simulation systems - A dynamic and adaptive approach English
Translated abstract:	Abstract Language The project Computer Aided Tram Scheduling (CATS) is concerned with the design and implementation of methods and software tools that enable transport providers to generate, simulate, and evaluate tram schedules on their own notebook or desktop computers. The scientific interest lies in the research and development of the required concepts and methods, these are mainly based in the areas of mathematical optimization and discrete simulation. In this context originated the desire for a parallel simulation software, which would be more accurate and also faster than the existing sequential model. This thesis attends to three main goals: At first a method for the parallel execution of discrete simulation models will be devised, which should utilize properties of (amongst others) traffic simulation models. To use the resources of the target platforms to the full extend, the approach should include a dynamic and adaptive load balancing scheme. The method will be implemented as a software framework, its dynamic behavior will be examined by conducting experiments on example applications. Furthermore, the software tools designed and implemented for project CATS will be presented. The thesis concentrates on a simulation module based on the described framework, which can be utilized to examine dynamic properties of tram schedules. To find candidates for this, an optimization module should be applied which generates robust tram schedules that also adhere to given sets of transport planning requirements. At last, the presented software tools should be applied to the tram networks of the cities of Cologne, Germany, and Montpellier, France. The optimizer should be applied to generate both robust and non-robust schedules for these networks, which will be simulated, evaluated, and compared to the schedules applied by the tram network providers. The thesis begins with an introduction of context, motivation and aims (chapter 1), followed by some background on methods of the parallel execution of discrete simulation models (chapter 2). After this a method is proposed which is especially suitable for the parallel execution of discrete traffic simulation models. The section begins by outlining the ideas of the method and its realization, followed by some thoughts on its scalability and efficiency (chapter 3). The thesis then continues by showing an implementation of the method as a software framework for simulation applications (chapter 4), followed by the description of some experiments conducted on a model of token movements on randomly generated graphs, based on the presented framework (chapter 5). This is followed by an application of method and framework in the simulation of tram schedules. Background and architecture of project CATS are described, the applied simulation and optimization models presented. These modules are utilized to generate and evaluate tram schedules for the networks of the cities of Cologne and Montpellier. This is followed by some observations on the run time behavior of the simulation module (chapter 6). The thesis concludes with a short summary and some thoughts on further research (chapter 7). English
Creators:	Creators Email ORCID ORCID Put Code Ullrich, Oliver mail@oullr.de UNSPECIFIED UNSPECIFIED
Corporate Creators:	Universität zu Köln
URN:	urn:nbn:de:hbz:38-54781
Date:	22 January 2014
Language:	German
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science Technology (Applied sciences)
Uncontrolled Keywords:	Keywords Language Diskrete Simulation, Parallele Simulation, Verkehrssimulation, Fahrplansimulation German Discrete simulation, parallel simulation, traffic simulation, time table simulation English
Date of oral exam:	22 January 2014
Referee:	Name Academic Title Speckenmeyer, Ewald Prof. Dr. Lang, Ulrich Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/5478