German Title: Lösung von Zuordnungs- und Routenproblemen in Gemischten Verkehrssystemen

Preview

PDF, English Download (6MB) | Terms of use

Abstract

This doctoral thesis presents not only a new traffic assignment model for mixed traffic systems but also new heuristics for multi-paths routing problems, a case study in Hanoi Vietnam, and a new software, named TranOpt Plus, supporting three major features: map editing, dynamic routing, and traffic assignment modeling.

We investigate three routing problems: k shortest loop-less paths (KSLP), dissimilar shortest loop-less paths (DSLP), and multi-objective shortest paths (MOSP). By developing loop filters and a similarity filter, we create two new heuristics based on Eppstein's algorithm: one using loop filters for the KSLP problem (HELF), the other using loop-and-similarity filters for the DSLP problem (HELSF). The computational results on real street maps indicate that the new heuristics dominate the other algorithms considered in terms of either running time or the average length of the found paths.

In traffic assignment modeling, we propose a new User Equilibrium (UE) model, named GUEM, for mixed traffic systems where 2- and 4-wheel vehicles travel together without any separate lanes for each kind of vehicle. At the optimal solution to the model, a user equilibrium for each kind of vehicle is obtained. The model is applied to the traffic system in Hanoi, Vietnam, where the traffic system is mixed traffic dominated by motorcycles. The predicted assignment by the GUEM model using real collected data in Hanoi is in high agreement with the real traffic situation in Hanoi.

Finally, we present the TranOpt Plus software, containing the implementation of all the routing algorithms mentioned in the thesis, as well as the GUEM model and a number of popular traffic assignment models for both standard traffic systems and mixed traffic systems. With its intuitive graphical user interface (GUI) and its strong visualization tools, TranOpt Plus also enables users without any mathematical or computer science background to use conveniently. Nevertheless, TranOpt Plus can be easily extended by further map-related problems, e.g., transportation network design, facility location, and the traveling salesman problem.

Keywords: mixed traffic assignment modeling, routing algorithms, shortest paths, dissimilar paths, Hanoi, TranOpt Plus, map visualization

Translation of abstract (German)

Diese Dissertation präsentiert nicht nur ein neues Verkehrszuordnungs-Modell für gemischte Verkehrssysteme, sondern auch neue Heuristiken für Mehrwege-Routing-Probleme, sowie eine Fallstudie in Hanoi und eine neu entwickelte Software namens TranOpt Plus mit drei Hauptanwendungen: Kartenbearbeitung, dynamisches Routing und Modellierung der Verkehrszuordnung.

Wir untersuchen drei Routing-Probleme: k kürzeste schleifenfreie Wege (KSLP), ungleiche kürzeste schleifenfreie Wege (DSLP) und Pareto optimale kürzeste Wege (MOSP). Durch die Entwicklung von Schleifenfiltern und eines Ähnlichkeitsfilters, ergeben sich zwei neue Heuristiken auf Basis des Eppstein-Algorithmus: Eine mit Schleifenfilter für das KSLP-Problem (HELF) und eine mit Schleifen- und Ähnlichkeitsfiltern für das DSLP-Problem (HELSF). Die Rechenexperimente mit realen Straßenkarten einiger Städte zeigen, dass die neuen Heuristiken die bisherigen in Bezug auf Laufzeit oder durchschnittliche Pfadlänge dominieren. Im neuen Verkehrszuordnungs-Modell (TAM) schlagen wir eine neues User-Equilibrium Modell (UE) für gemischte Verkehrssysteme vor, in denen sich 2- und 4-rädrige Fahrzeuge gemeinsam bewegen, ohne gesonderte Spuren für jede Fahrzeugart zu verwenden. Bei der optimalen Lösung für das Modell bleibt das Gleichgewicht für jede Fahrzeugart erhalten. Das Modell wird auf das Verkehrssystem in Hanoi, wo der gemischte Verkehr von Motorrädern dominiert wird, angewendet. Die vom Modell produzierten Ergebnisse stimmen mit der realen Verkehrssituation in Hanoi deutlich überein.

Schließlich präsentieren wir die Software TranOpt Plus, welche alle in der Arbeit erwähnten Routing-Algorithmen sowie die Verkehrszuordnungs-Modelle sowohl für Standard als auch gemischten Verkehr umfasst. Durch die grafische Benutzeroberfläche (GUI) und die umfangreichen Visualisierungstools, kann die Software auch von Benutzern ohne weiterführende Informatik- oder Mathematik-Kenntnisse verwendet werden. Dennoch kann TranOpt Plus leicht um zusätzliche Graphenprobleme, wie beispielsweise Netzwerkdesign, das Facility-Location und das Traveling-Salesman-Problem, erweitert werden.

Stichwörter: Verkehrszuordnungs-Modelle für gemischte Verkehrssysteme, Routing-Probleme, kürzeste Wege, ungleiche kürzeste Wege, Hanoi, TranOpt Plus, Kartenvisualisierung