90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Year of publication
- 2017 (2) (remove)
Document Type
- Master's Thesis (2) (remove)
Is part of the Bibliography
- no (2)
Keywords
Institute
In dieser Arbeit betrachten wir das Problem, für den Fahrplan eines (Nah-) Verkehrsnetzes schnellste Wege zu berechnen. Da die Verkehrsmittel zu unterschiedlichen Zeiten von den einzelnen Haltestellen/Bahnhöfen abfahren, kann das Problem nicht ohne Weiteres mit einem „statischen“ Graphen modelliert werden. Es gibt zwei unterschiedliche Ansätze für dieses zeitabhängige Problem: Erstens können die verschiedenen An-/Abfahrtereignisse an einem Halt durch „Kopien“ dargestellt werden, das ist das zeit-expandierte Modell. Zweitens können die Gewichte der Kanten zeitabhängig sein, das ist
das zeitabhängige Modell. Wir untersuchen in dieser Arbeit, wie der „klassische“ Dijkstra-Algorithmus und der A* Algorithmus mit einer geeigneten Heuristik im Vergleich abschneiden. Die gewählte Heuristik ist der Abstand zum Zielknoten, wenn die Abfahrtszeiten ignoriert werden. Nach unseren Untersuchungen zeigt sich, dass der A* Algorithmus dem Dijkstra-Algorithmus weit überlegen ist für genügend große Nahverkehrsnetze. Wir testen anhand der echten Verkehrsnetze von Berlin und Aachen. Unsere Berechnungen zeigen, dass die gewählte Heuristik besonders gut ist für Start- und Zielknoten, welche unabhängig von ihrer Distanz nur 1–2 verschiedene mögliche kürzeste Pfade für alle Zeitschritte haben. Dort ist der A* Algorithmus bis zu 20-mal schneller. Dies kommt aber nicht häufig in unseren Testinstanzen vor. Die einzelnen Laufzeitvergleich zeigen, dass
der A* Algorithmus durchschnittlich 7-mal so schnell ist wie der Dikstra-Algorithmus.
The topic of this thesis is the examination of an optimization model
which stems from the clustering process of non-reversible markov processes.
We introduce the cycle clustering problem und formulate it as a mixed
integer program (MIP).
We prove that this problem is N P-hard and discuss polytopal aspects
such as facets and dimension. The focus of this thesis is the development of
solving methods for this clustering problem. We develop problem specific
primal heuristics, as well as separation methods and an approximation
algorithm. These techniques are implemented in practice as an application
for the MIP solver SCIP.
Our computational experiments show that these solving methods result
in an average speedup of ×4 compared to generic solvers and that our
application is able to solve more instances to optimality within the given
time limit of one hour.