[Back]


Diploma and Master Theses (authored and supervised):

A. Partusch:
"Monte Carlo Simulation for the evaluation of routing results concerning their spatial variation and distribution";
Supervisor: G. Navratil, H. Fiby; FH Technikum Wien, Studiengang Intelligent Transportation Systems, 2013; final examination: 2013-10-22.



English abstract:
Various route planners and routing applications for all transport modes are available nowadays that calculate the optimal path for origin destination relations. For the motorised individual transport the calculation process of this optimal route is mostly based on the estimated total travel time. At state of the art routing algorithms the travel times and travel speeds, respectively, on the network are assumed to be deterministic. While this assumption increases the efficiency and performance of the calculation process it neglects uncertainties concerning these parameters that results for instance from current traffic volumes, incidents or weather conditions on which the travel speed heavily depend.
This thesis aims to evaluate the effects of uncertainties at estimated actual travel speeds on results of route calculations with regard to the spatial distribution and variation. The question is whether more than one reasonable path exists for a specific origin destination relation that has a certain probability of presenting the route with the least travel time if travel speeds for the calculation process are modelled as stochastic variables according to correspondent speed distributions.
To answer this question a Monte Carlo Simulation was implemented on shortest path calculation. This simulation belongs to the quantitative analyses methods and executes the underlying process thousands of times. The results of the implemented simulation within this thesis are route bundles that contain thousands of shortest paths for the same origin destination relation while the travel speeds for all route calculation iterations are changed and selected randomly as indicated above. These route bundles demonstrate the spatial distribution of the returned results.
In addition a process was developed to extract plausible route representatives out of the resulted route bundles that provide different alternatives for each other. Furthermore, different indicators are introduced to assess the spatial separation of the extracted route alternatives as well as the distribution of the overall route bundle.

German abstract:
In der heutigen Zeit gibt es eine Vielzahl von unterschiedlichen Routenplanern und -Applikationen für alle Verkehrsmodi, welche die Berechnung des optimalen Weges für Quell- Ziel Relationen ermöglichen. Für den Motorisierten Individualverkehr basiert die Berechnung dieser optimalen Route meist auf der kürzesten angenommenen Reisezeit. Bei klassischen Routing-Algorithmen werden hierbei die Reisegeschwindigkeiten bzw. -zeiten als deterministisch angenommen. Diese deterministische Herangehensweise ermöglicht eine effiziente und performante Routenberechnung, vernachlässigt jedoch den Umstand, dass die tatsächlichen Reisegeschwindigkeiten nicht mit Sicherheit vorhergesagt werden können, da diese von unterschiedlichen Faktoren wie beispielsweise der aktuellen Verkehrsstärke, Wetterbedingung oder sonstigen Ereignissen abhängig sind.
Ziel dieser Arbeit ist es, die Auswirkungen auf die räumliche Verteilung und Variation von Routen-Ergebnissen zu untersuchen, wenn bei den angenommenen Reisegeschwindig-keiten, für die Berechnung der Route, Varianzen berücksichtigt und die Geschwindigkeiten somit als Zufallsvariablen modelliert werden, wobei der Randomisierung eine bestimmte Geschwindigkeitsverteilung zugrunde liegt. Dieser Ansatz kann dazu führen, dass das Ergebnis der Routen-Berechnung nicht mehr eindeutig ist, sondern mehrere Routen zurückgegeben werden, welche den optimalen Weg mit einer bestimmten Wahrscheinlichkeit repräsentieren.
Für die Analyse der erwähnten Aspekte wurde eine Monte Carlo Simulation auf Basis eines Kürzeste-Wege-Algorithmus implementiert. Bei dieser Simulation, welche zu den quantitativen Analysemethoden zu zählen ist, wird der zugrundeliegende Prozess mehrere tausend Mal ausgeführt. Das Ergebnis der Simulation in dieser Arbeit ist ein Routenbündel, das aus tausenden von "optimalen" Wegen für eine bestimmte Quell-Ziel Relation besteht, wobei die Reisegeschwindigkeiten für jede Iteration der Routenberechnung neu und zufällig gewählt werden. Dieses Routenbündel zeigt die räumliche Verteilung der zurückgegebenen Routenergebnisse.
Des Weiteren wurde im Rahmen dieser Arbeit ein Prozess entwickelt, der es ermöglicht Repräsentanten aus diesem Routenbündel zu extrahieren, die somit unterschiedliche Routenalternativen darstellen. Außerdem werden mehrere Indikatoren präsentiert, die eine Bewertung der räumlichen Verteilung sowohl von den extrahierten Routenvarianten als auch vom gesamten Routenbündel ermöglichen und die Ergebnisse somit vergleichbar machen.

Keywords:
Routenbündel, räumliche Verteilung, stochastische Reisegeschwindig-keiten, Monte Carlo Simulation, Floating Car Data

Created from the Publication Database of the Vienna University of Technology.