Universität zu Köln

Genc, Zülfükar (2003). Ein neuer Ansatz zur Fahrplanoptimierung im ÖPNV: Maximierung von zeitlichen Sicherheitabständen. PhD thesis, Universität zu Köln.

Preview

PDF diss.pdf Download (4MB)

Abstract

Der Fahrplan bildet ein wichtiges Element der Verkehrsplanung. Er legt die Ankunfts- und Abfahrtszeiten der einzelnen Linien im Streckennetz fest. Die bislang verwendete Software hilft bei der manuellen Erstellung am Bildschirm und ermöglicht die Visualisierung und Simulation von Fahrplänen. Zur besseren Unterstützung des Planers fehlen jedoch Systeme zur automatischen Generierung zulässiger und in Hinblick auf die Zielvorstellung optimierter Fahrpläne. Die vorliegende Arbeit beschäftigt sich mit einem neuen Ansatz zur Optimierung von Fahrplänen. Das der Fahrplangestaltung zu Grunde liegende Streckennetzwerk besteht aus einer Menge von Stationen und Linien, denen Takte zugeordnet sind. Den Streckenabschnitten zwischen den Stationen sind Fahrzeiten zugeordnet. Das Ziel der Fahrplanoptimierung, die in dieser Arbeit betrachtet wird, besteht darin, die Abfahrtszeiten der Linien an den Anfangsstationen so festzulegen, dass die Ankunftszeiten an den einzelnen Stationen möglichst gleichmässig verteilt sind. Damit soll erreicht werden, dass kleine Störungen, wie sie häufig bei Nahverkehrssytemen auftreten, nur geringe, zeitlich begrenzte Auswirkungen auf den Linienverkehr haben. Im ersten Kapitel werden die einzelnen Planungsprozesse im öffentlichen Personennahverkehr (ÖPNV) erläutert und es wird ein überblick über einige aus der Literatur bekannte Ansätze zur Fahrplanoptimierung gegeben. Kapitel 2 stellt die Modellierung zur Fahrplanoptimierung, die in dieser Arbeit untersucht wird, dar. In Kapitel 3 werden Reduktionen des Streckennetzwerks präsentiert, mit deren Hilfe die Zielfunktion und obere Schranken schneller ermittelt werden können. Die Reduktionen nutzen Relationen, die auf der Menge der Stationen und auf der Menge der Kanten eines speziellen noch zu definierenden Multi-Linienkonflikt-Graphen, der aus dem Streckennetzwerk gebildet wird, definiert sind. Darüber hinaus enthält Kapitel 3 Ergebnisse zur Zeitkomplexität des hier untersuchten Fahrplanoptimierungsproblems. Ein Branch-and-Bound-Algorithmus zur Lösung des Fahrplanoptimierungsproblems wird in Kapitel 4 vorstellt. Es werden Heuristiken präsentiert, um mit deren Hilfe gute Anfangslösungen für den Branch-and-Bound-Algorithmus zu erhalten. Kapitel 4 enthält noch einen Ansatz zur Zerlegung des Streckennetzwerks in Teilnetze, so dass es ausreicht, optimale Fahrpläne für die Teilnetze zu berechnen, um daraus einen optimalen Fahrplan für das gesamte Streckennetzwerk zu erhalten. Dazu werden die zweifachen Zusammenhangskomponenten des Linienkonflikt-Graphen, der aus dem Streckennetzwerk gebildet wird, betrachtet. In Kapitel 5 wird das Fahrplanoptimierungsproblem als ganzzahliges lineares Programm dargestellt, um dann mittels CPLEX, einem Programmpaket zur Lösung linearer und gemischtganzzahliger Variablen, gelöst zu werden. Mit Hilfe von Reduktionen lässt sich die Zahl der Variablen und Gleichungen so verringern, dass CPLEX in vertretbarer Zeit gute Lösungen liefert. Kapitel 6 präsentiert experimentelle Ergebnisse zur Lösung des Fahrplanoptimierungsproblems, die mit einem Branch-and-Bound-Verfahren und mit CPLEX auf Basis der ganzzahligen LP-Formulierung anhand der Daten des Streckennetzwerks der Kölner Verkehrs-Betriebe (KVB) einerseits und auf künstlich erzeugten Streckennetzwerken andererseits, erzielt worden sind. Die Arbeit schliesst mit einer Zusammenfassung und einem Ausblick auf mögliche zukünftige Entwicklungen dieses Ansatzes.

Item Type:	Thesis (PhD thesis)
Translated title:	Title Language A new approach for the optimization of timetables in public transport networks: Maximization of safe distances English
Translated abstract:	Abstract Language An important element of train scheduling is the timetable. It determines the arrival and departure times for the different train lines in a public transportation network. The software which has been hitherto employed features the manual creation, visualisation and simulation of timetables on the screen. There is, however, a lack of systems which allow the automatic generation of valid and teleologically optimized timetables. This thesis deals with a new method of timetable optimization. The network which forms the basis of timetable creation consists of a set of stations and lines, to which certain time periods are assigned. The connections between stations correspond to travelling times. The goal of timetable optimization, as analyzed in this thesis, is to set the departure time of the respective lines at the first station in order to evenly distribute the arrival times. The intention behind that is to limit the temporal effect of small disturbances, as they happen quite often in public transport networks. In the first chapter, we discuss the different planning processes in public transport systems and give an overview of existing models of timetable optimization. Chapter 2 presents the models of timetable optimization that will form the basis of our further work. In chapter 3, we introduce reductions of the network leading to faster calculation of the optimization function and upper bounds. The reductions make use of relations that are defined on the set of stations and on the set of the edges of a special yet-to-be-defined multi-line-conflict-graph formed out of the network. Moreover, chapter 3 consists of results explaining the time-complexity of the central timetable optimization problem of this thesis. A branch and bound algorithm to solve the timetable optimization problem is presented in chapter 4. Heuristics will be employed to get feasible solutions that can be used with the branch and bound algorithm. Chapter 4 contains a method to split the network into sub-networks, making it possible to calculate optimal timetables of the sub-networks and to combine them into an optimal timetable for the whole network. This is archieved by focusing on the bi-connected components of the line-conflict-graph that was formed out of the network. In chapter 5, the timetable optimization problem is described as an integer linear program, before solving it with the help of CPLEX, a program package to solve linear and mixed integer variables. As a result of the described reductions of the number of variables and equations, CPLEX can give good solutions in a considerably short amount of time. Chapter 6 discusses experimental results for solving the timetable optimization problem. These were produced by the branch and bound algorithm and CPLEX on the basis of integer LP-formulation of data of the cologne tram network on the one hand and through artificially created networks on the other hand. The thesis concludes with a summary and a suggestion for further research in this area. English
Creators:	Creators Email ORCID ORCID Put Code Genc, Zülfükar genc@informatik.uni-koeln.de UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-9505
Date:	2003
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
Uncontrolled Keywords:	Keywords Language Fahrplanoptimierung, Branch-and-Bound, kombinatorische Optimierung German timetable optimization, scheduling, combinatorial optimization, branch and bound English
Date of oral exam:	5 June 2003
Referee:	Name Academic Title Speckenmeyer, Ewald Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/950