Verkehrsnetze als mathematische Graphen
Die Graphentheorie bildet das mathematische Fundament der Verkehrsplanung. Jedes Verkehrsnetz – ob Busnetz, Schienennetz oder multimodales Transportnetzwerk – lässt sich als gerichteter Graph G = (V, E) modellieren, wobei die Knoten V Haltestellen, Bahnhöfe oder Kreuzungen repräsentieren und die Kanten E die Verbindungen zwischen ihnen darstellen. Kantengewichte kodieren Fahrzeiten, Distanzen, Kosten oder Kapazitäten.
Diese Abstraktion ermöglicht den Einsatz einer breiten Palette effizienter Algorithmen, die in Jahrzehnten mathematischer Forschung entwickelt und optimiert wurden. Im Gegensatz zu allgemeinen Optimierungsverfahren nutzen graphentheoretische Algorithmen die spezifische Netzwerkstruktur des Problems aus und erreichen dadurch oft polynomielle Laufzeiten – selbst bei Instanzen mit Millionen von Knoten und Kanten.
Für die Verkehrsplanung besonders relevant sind zeitexpandierte Graphen, in denen jeder Knoten nicht nur einen Ort, sondern auch einen Zeitpunkt repräsentiert. Diese Modellierung ermöglicht die exakte Abbildung von Fahrplänen, Umsteigezeiten und zeitabhängigen Reisezeiten und bildet die Grundlage für Fahrplanauskunftssysteme wie HAFAS und EFA.
Graph G = (V, E)
V = {(station, time)} // Raum-Zeit-Knoten
E = Etravel ∪ Ewait ∪ Etransfer
// Shortest Path: Dijkstra
for each v ∈ V:
dist[v] = ∞
dist[s] = 0
while Q ≠ ∅:
u = extractMin(Q)
for each (u,v) ∈ E:
relax(u, v, w(u,v))
Graphenalgorithmen für den Verkehr
Von der Routenberechnung bis zur Netzwerkoptimierung – unsere Implementierungen nutzen die neuesten algorithmischen Fortschritte.
Shortest Path
Dijkstra, A*, Contraction Hierarchies und Transit Node Routing für ultraschnelle Routenberechnung. Vorberechnung ermöglicht Antwortzeiten im Mikrosekundenbereich für Fahrplanauskunft und Echtzeit-Routing in der ÖPNV-Disposition.
Netzwerkfluss
Min-Cost-Flow-Algorithmen für die Fahrzeugumlaufplanung. Das Vehicle Scheduling Problem lässt sich als Minimum-Cost-Flow-Problem in einem Verbindungsgraphen formulieren, was polynomielle Lösungszeiten ermöglicht.
Matching
Maximum-Weight-Matching für die optimale Zuordnung von Fahrzeugen zu Fahrten, Fahrern zu Diensten oder Passagieren zu Fahrzeugen im Ride-Sharing. Der Ungarische Algorithmus liefert beweisbar optimale Zuordnungen in polynomieller Zeit.
Spanning Trees
Minimum-Spanning-Tree-Algorithmen für das Design von Verkehrsnetzen und die Planung von Infrastrukturprojekten. Steiner-Tree-Probleme modellieren die kostenoptimale Verbindung von Haltestellen.
Topologische Sortierung
Erkennung und Auflösung von Abhängigkeiten in Fahrplänen und Betriebsabläufen. Kritische-Pfad-Analyse für die Identifikation von Engpässen im Verkehrsnetz und die Priorisierung von Infrastrukturmaßnahmen.
Graph Partitioning
Zerlegung großer Verkehrsnetze in handhabbare Teilprobleme für die parallele Optimierung. Balanced Graph Partitioning minimiert die Schnittmenge und ermöglicht effiziente Dekompositionsverfahren.
Netzwerkfluss-basierte Umlaufplanung
Die Fahrzeugumlaufplanung im ÖPNV lässt sich elegant als Netzwerkflussproblem formulieren. In einem Verbindungsgraphen repräsentiert jeder Knoten eine Fahrplanfahrt, und eine gerichtete Kante von Fahrt i zu Fahrt j existiert genau dann, wenn ein Fahrzeug nach Beendigung von Fahrt i rechtzeitig Fahrt j beginnen kann. Zusätzliche Quell- und Senkenknoten modellieren die Depots.
Das Minimum-Cost-Flow-Problem auf diesem Graphen findet die kostenoptimale Zuordnung von Fahrten zu Fahrzeugumläufen. Die Kosten der Kanten kodieren Leerfahrtkosten, Standzeiten und Depotkosten. Diese Formulierung hat den entscheidenden Vorteil, dass sie in polynomieller Zeit lösbar ist – im Gegensatz zur allgemeinen MILP-Formulierung, die NP-schwer ist.
Für komplexere Varianten des Problems – etwa mit Fahrzeugtyp-Restriktionen, E-Bus-Ladeanforderungen oder Multi-Depot-Szenarien – erweitern wir die Netzwerkfluss-Formulierung um zusätzliche Nebenbedingungen und lösen das resultierende Problem mit MILP-Solvern, wobei die Netzwerkstruktur weiterhin für effiziente LP-Relaxationen genutzt wird.
"Die graphentheoretische Modellierung unseres Busnetzes hat uns ein tiefes Verständnis der Netzwerkstruktur gegeben. Die darauf aufbauende Optimierung hat Leerfahrten signifikant reduziert und die Pünktlichkeit unserer Anschlüsse deutlich verbessert."
Echtzeit-Routing mit zeitabhängigen Graphen
In der Praxis sind Verkehrsnetze nicht statisch: Reisezeiten variieren je nach Tageszeit, Wochentag und aktueller Verkehrslage. Störungen, Baustellen und Verspätungen erfordern eine dynamische Anpassung der Routenberechnung. Unsere zeitabhängigen Graphmodelle bilden diese Dynamik exakt ab.
Durch die Integration von Echtzeitdaten – SIRI-Feeds, VDV 453/454, GTFS-RT – aktualisieren wir die Kantengewichte unserer Graphen kontinuierlich. Effiziente Update-Algorithmen stellen sicher, dass Änderungen in Millisekunden propagiert werden, ohne den gesamten Graphen neu berechnen zu müssen.
Für die Fahrgastinformation nutzen wir Contraction Hierarchies mit zeitabhängigen Kantengewichten, die Routenanfragen in Mikrosekundenbereich beantworten. Diese Technologie bildet die Grundlage für moderne Fahrplanauskunftssysteme und multimodale Routenplaner, die verschiedene Verkehrsträger nahtlos kombinieren.
Echtzeit-Feed
Transit-Daten
453/454
EU-Standard