Optimale Wegstreckenführung in Netzwerken unter variablen Verkehrsflüssen

Inhaltsverzeichnis

1 Einleitung
1.1 Hintergründe zur optimalen Wegstreckenführung
1.2 Deutschlands Verkehrsnetze als Graphen
1.3 GPS-Navigation bei Routenplanungen (Problematik)

2 Hauptteil
2.1 Dijkstra-Verfahren zur Bestimmung kürzester Wege
2.2 Dijkstra-Verfahren im Verkehrsnetzwerk (Beispiel) .
2.3 Das Modell zur Optimierung der globalen Fahrzeit .
2.4 Constrained System Optimum
2.5 Problemformulierung zum Modell
2.6 Die Idee des Modells am Beispiel
2.7 Anwendung auf ein Verkehrsnetz
2.8 Diskussion bei Veränderung der Daten

3 Fazit
3.1 Interpretation des mathematischen Modells
3.2 Kritikäußerungen und Potentiale

4 Tabellenverzeichnis

5 Abbildungsverzeichnis

6 Abkürzungsverzeichnis

7 Literaturverzeichnis

8 Anhang

1 Einleitung

1.1 Hintergründe zur optimalen Wegstreckenführung

Das Verkehrsaufkommen auf Autobahnen, Landstraßen und auch im Stadtverkehr steigt seit 2002 stetig. Der Deutsche Automobilclub ermittelte in seiner Staubilanz 2011 eine Erhöhung der Kfz-Fahrleistungen um 2,4 Prozentpunkte im Vergleich zum Vorjahr. Die Länge aller Staus 2011 betrug dabei insgesamt ca. 450.000 km und insgesamt wurden rund 185.000 Staustunden gemeldet. Allein auf das Bundesland Nordrhein-Westfalen entfiel eine Staulänge von ca. 139.000 km, was einer mehr als vierzehnfachen Distanz von Berlin nach Kapstadt entspricht, gemessen an Luftliniendistanzen.¹

Prof. Dr. Rolf Möhring, Wissenschaftler an der Technischen Universität in Berlin und Spezialist für Netzwerkoptimierung im Straßenverkehr, geht davon aus, dass Straßennetze 2015 ein knappes Gut sein werden und eine entgeltliche Nutzung nicht ausgeschlossen werden kann.²

Im aktuellen Investitionsrahmenplan für Verkehrsprojekte hat Bundesverkehrsminister Peter Ramsauer die Investitionsplanungen an tatsächlich vorhandenen Finanzierungsmöglichkeiten ausgerichtet und diese, für alle Projekte die von 2011 bis 2015 abgeschlossen sein sollen, bzw. weitergeführt oder neu begonnen werden, vorgestellt. Für den Zeitraum 2011 bis zum Jahr 2015 entfällt von dem gesamten Projektvolumen, in Höhe von rund 41 Milliarden Euro, ein Anteil von insgesamt 24,8 Milliarden Euro auf den Bereich Straßenverkehr.

Jedoch wurde 2011 von der Bundesregierung beschlossen, dass ab dem Jahr 2012 mehrjährig eine Milliarde Euro zusätzlich als Investitionsmittel für Infrastrukturprojekte zur Verfügung gestellt wird. Ramsauer erklärte, dass bei dieser Mittelverwendung klare Prioritäten gesetzt werden und dort investiert wird, wo der Bedarf am größten und der Nutzen für die Menschen und die Wirtschaft am effektivsten sei.

Schwerpunkt hierbei ist mit 600 Millionen Euro - verteilt auf zwei Jahre - die Straße als Verkehrsträger Nummer eins. Dies macht deutlich, welche zentrale Rolle der Straßenverkehr spielt und wie wichtig die Instandhaltung, vor allem aber der Ausbau dieser Infrastruktur ist.³

Die Optimierung von Wegführungen ist somit ein wichtiger Bestandteil, nicht nur um die Abnutzung der Verkehrswege so gering wie möglich zu halten, sondern auch im Bereich Gütertransporte dem Trend des Wachstums entgegen zu wirken. Gerade im letztgenannten Bereich hat das Bundesministerium für Umwelt, Naturschutz und Reaktorsicherheit alarmierende Statistiken veröffentlicht. So ist der Zuwachs auf den Straßen 2006 im Güterverkehrstransport um 77% gestiegen. Bereits im Vorjahr wurde ein Anstieg um 65% verzeichnet.⁴ (s. Grafik)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Gütertransporte innerhalb Deutschlands von 1991 - 2006

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Gütertransportleistung in Mrd. tKm

Im Jahre 2007 wurde ein neues Rekordhoch der Fahrleistungen von knapp 650 Mrd. tkm erreicht. Das Umweltbundesamt prognostiziert einen Anstieg von 59% zwischen den Jahren 2005 und 2025 im Güterverkehrsbereich.⁵

Einer der wichtigsten Punkte für die Untersuchung zur Optimalen Wegstreckenführung ist der Personenverkehrstransport mittels Kraftwagen. Dieser Anteil liegt aktuell innerhalb Deutschlands bei über[45] allerPersonenverkehrsleistungenund ist innerhalb der letzten vier Jahre stetig gestiegen.⁶

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Personenverkehrsleistung in Deutschland von 2007 - 2010

Insofern ist deshalb gerade die Optimierung kürzester Wege im Straßenverkehr eine zentrale Aufgabe, die nicht nur von politischem Interesse ist. Jeder private Nutzer ist natürlich daran interessiert in möglichst kurzer Zeit sein Ziel zu erreichen. Aus diesem Grund wird in der vorliegenden Arbeit insbesondere die Navigationswegführung in den Fokus der Betrachtung genommen. Diese wird häufig zur Bestimmung der kürzesten Routenführung eingesetzt.

1.2 Deutschlands Verkehrsnetze als Graphen

Die Länge der überörtlichen Straßen innerhalb Deutschlands lag im Jahr 2010 bei insgesamt ca. 232.000 km. Darunter befinden sich Bundesstraßen mit 41.400 km, Bundesautobahnen mit 12.600 km, 86.600 km Landesstraßen, sowie Kreisstraßen mit 91.700 km. Gemeindestraßen wurden bei dieser Aufstellung der Verkehrswegearten in Deutschland nicht mit erhoben.⁷

Bei dieser Darstellung wird deutlich, dass es viele Möglichkeiten gibt ein Ziel zu erreichen. Die optimale Wegführung in Form kürzester Entfernungen bei unbekannten Strecken zu bestimmen, stellt sich als äußerst komplexes Anliegen dar. Aus diesem Grund greifen viele Verkehrsteilnehmer auf die Wegführung durch Navigationssoftware zurück. Dies wird in Abschnitt 1.3 genauer erläutert. Im weiteren Untersuchungsverlauf soll mit Graphen gearbeitet werden, die dabei wie folgt definiert werden:⁸

Abbildung in dieser Leseprobe nicht enthalten

G: bezeichnet einen Graph,

V: besteht aus einer endlichen Menge von Knoten,

E: aus einer Menge 2-elementiger Teilmengen von V, den Kanten.

Knoten stellen bei der im Rahmen dieser Untersuchung vorgenommenen Routenplanung die Orte dar, zwischen denen wir eine optimale Verbindung finden möchten. Bei einer Fahrt von München nach Hamburg können die Knoten beispielsweise als Autobahnabfahrten und -kreuze angesehen werden. Lässt man bei dieser Fahrt in der Routenplanung noch Bundes -und Landesstraßen zu, ergeben sich viele weitere Kreuzungen und Abfahrten, die ebenfalls als Knoten aufgefasst werden. Als Kanten (E) werden die Straßenverbindungen zweier Orte miteinander definiert.

Beispiel:⁹

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Basisstruktur

Ein solcher Graph wie in Abbildung 4 soll als ungerichteter Graph, welcher zusammenhängend ist, bezeichnet werden. Er ist deshalb zusammenhängend, weil die Möglichkeit besteht, über die vorhandenen Kanten von einem beliebigen Knoten zu jedem anderen zu gelangen. Für ein späteres Untersuchungsmodell sind die Graphen als Voraussetzung immer zusammenhängend.

Es gibt aber auch Fälle, in denen Graphen nicht zusammenhängend sind. Dies ist beispielsweise der Fall, wenn man kürzeste Straßenverbindungen zwischen Orten auf einer Inselgruppe betrachtet. Dann ist eine Unterbrechung durch einen Umstieg auf ein anderes Verkehrsmittel (in diesem Falle eine Fähre) nötig.

Ungerichtet ist der Graph deshalb, weil keine Fahrtrichtungen berücksichtigt wurden. Das bedeutet im konkreten Fall, dass davon ausgegangen werden kann, dass die Straßenverbindungen in beide Richtungen befahren werden können. Ist dies nicht möglich, muss die Fahrtrichtung durch Pfeile an den Kanten gekennzeichnet werden. In dieser Situation nennt sich der Graph gerichtet und ein Durchfahren ist nur in Pfeilrichtung möglich.

Für spätere Beispiele und deren Umsetzungen sollen nur gerichtete Graphen betrachtet werden, da der Verkehrsfluss in entgegengesetzer Richtung keine Auswirkungen auf die Kapazität der Kante hat.

Beispiel:¹⁰

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: Gerichteter Graph

Abschließend werden für die Umsetzung der Graphen noch sogenannte Gewichte benötigt. Gemeinverständlich ist klar, dass die Strecke von Berlin nach Hamburg um einige Kilometer kürzer ist, als die Strecke von München nach Hamburg. Deshalb sollen die Kanten der Graphen mit Gewichten versehen werden, die entweder als Länge der Kanten in Kilometer oder als Zeitstunden für die Überfahrt interpretiert werden können. Im weiteren Verlauf wird dies situationsbedingt spezifiziert.

Digraph bezeichnet einen gerichteten Graphen, bei dem die Kanten mit entsprechenden Gewichten versehen sind. Für Wegoptimierungen sind die Kantenbewertungen von enormer Wichtigkeit, um Fahrwege oder Fahrzeiten zu optimieren. Aus den genannten Gründen werden für die weitere Vorgehensweise Digraphen verwendet (s. Abbildung 6).¹¹

Beispiel:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6: Beispiel eines Digraphen

Betrachtet man die Graphentheorie nun im Zusammenhang mit Deutschlands Straßenverbindungen, ist intuitiv unverkennbar, dass eine Darstellung als Graph von größter Komplexität ist. Der Deutschland-Graph setzt sich aus 4,8 Millionen Knoten und 11,9 Millionen Kanten zusammen. Allein die Hauptstadt Berlin hat insgesamt 10.000 Knoten und 30.000 Kanten. Ein Ausschnitt eines StadtStraßennetzes in Berlin zeigt folgende Abbildung.¹²

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 7: Stadt-Straßennetz Lietzenburger/Joachimstaler Straße, Berlin - gerichteter Graph

1.3 GPS-Navigation bei Routenplanungen (Problematik)

Global Positioning System, kurz GPS, ist ein satellitengesteuertes System, das zur Standortbestimmung dient. Das Verfahren basiert auf Messungen von Laufzeitunterschieden der von den verschiedenen Satelliten synchron gesendeten Signale. Systembedingt kann mit einer Wahrscheinlichkeit von 95 Prozent eine Genauigkeit von unter 20 Metern erwartet werden.¹³

Navigationssysteme arbeiten mit den GPS-Signalen und digitalen Straßenkarten. Diese digitalen Karten geben Straßen und ihre Verzweigungen in vektorisierter Form von Kanten und Knoten wieder (s. dazu 1.2).

Mit Hilfe der Kantenlänge und standardisierten Geschwindigkeiten, die je nach Straßentyp variieren, ermitteln Navigationssysteme Fahrzeiten, Entfernungen in Kilometern und kürzeste Wege, die herstellerspezifisch abweichen können. Oft wird dabei die Route über Autobahnen präferiert, da dort die zulässige Höchstgeschwindigkeit unbeschränkt oder höher beschränkt ist, als auf Bundesstraßen.

Daher weicht die durch Zielführungssysteme berechnete Route oftmals von der Routenwahl eines ortskundigen Verkehrsteilnehmers ab, da dieser über Straßenverläufe, fahrbare Geschwindigkeiten, auch in Abhängigkeit von Wochentagen und verschiedenen Tageszeiten, genau informiert ist.

Das zentrale Problem, mit dem wir uns beschäftigen wollen, ist die Mehrbelastung von Verkehrsstrecken durch den Einsatz von GPS-Routenführung. Angenommen viele Verkehrsteilnehmer möchten gleichzeitig mit Hilfe der Navigation eine Fahrt von Berlin nach Hamburg bestreiten. Das System sendet somit alle Verkehrsteilnehmer auf den kürzesten Weg.

Graphisch:¹⁴

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 8: Verkehrsteilnehmer mit gleichem Start -und Zielort

In Abbildung 9 wird deutlich, dass die Navigationshilfe zwar auf den kürzesten Weg navigiert, aber Simulationen zeigen, dass die Belastung steigt, sobald viele Autofahrer das System benutzen. Folglich kommt es zu keiner optimalen Verkehrsführung, da ein zu hohes Verkehrsaufkommen lange Staus verursachen kann.

Die gewünschten Effekte von GPS-Navigationen sollten zu einer verbesserten Netz-Nutzung führen, gekoppelt mit einer Entlastung des Straßennetzes und so zu minimalen Fahrzeiten beitragen. Die ideale Verkehrssituation zum betrachteten Ziel Hamburg sollte demnach wie folgt aussehen:¹⁵

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 9: Effiziente Verkehrsführung bei gleichem Start -und Zielort

Um dieses Ziel zu erreichen befinden sich die PKW auf verschiedenen Verkehrswegen. Die Belastungen der Straßen sind durch diese Streuung ausgeglichener, allerdings geht damit einher, dass nicht alle Verkehrsteilnehmer den kürzesten Weg nutzen können. Das bedeutet wiederum, dass einige dieser alternativen Routen länger sind als der kürzeste Weg. Demnach wird die Länge der zurückgelegten Strecke bei den betroffenen Autofahrern steigen. Doch was passiert mit den Fahrzeiten?

Auf diese Frage soll in Kapitel zwei der vorliegenden Arbeit näher eingegangen werden. Hätten auch die Verkehrsteilnehmer auf den Alternativrouten den kürzesten Weg befahren, so hätte die Verkehrsbelastung auf dem selbigen erheblich zugenommen (siehe Abbildung 8). Vermutet wird, dass dadurch die globale Fahrzeit, d.h. die Gesamtfahrzeit aller PKW auf der Route von Berlin nach Hamburg, gestiegen wäre. Ob und in wieweit dies der Fall ist, gilt es am Beispiel zu untersuchen.

2 Hauptteil

2.1 Dijkstra-Verfahren zur Bestimmung kürzester Wege

Das Dijkstra-Verfahren liefert in Bezug auf die bisher erarbeiteten Voraussetzungen eine gute Möglichkeit, um kürzeste Wege in Graphen zu bestimmen, die sich aus Straßennetzen ergeben. Weiterhin wird der Dijkstra-Algorithmus als Lable-Setting-Verfahren im späteren Modellbeispiel vorausgesetzt. Daher ist es sinnvoll, das Verfahren zu betrachten und an einem Beispiel eines Verkehrsnetzes anzuwenden.¹⁶

Voraussetzung für das Verfahren ist, dass keine negativen Kantenbewertungen auftreten und es sich um einen zusammenhängenden Graphen handelt. Beides ist in unserem Fall erfüllt, weil Kantenbewertungen kleiner Null negativen Weglängen oder Fahrzeiten entsprächen, was bereits ausgeschlossen wurde.

Die Länge eines Weges soll als Summe der Bewertungen der Kanten in der Folge definiert werden. Somit ist der kürzeste Weg gegeben durch die Kantenfolge, in der die Summe der Gewichte zum Zielknoten, unter allen Wegen von unserem Startknoten aus, minimal wird.

G = (V,E) sei ein Graph, V ist die Menge der Knoten und E ⊆ V ×V die Menge der Kanten. Eine Kante eij verbinde die zwei Knoten i und j. Die Markierungen der Kanten erfolgt über die Gewichtsfunktion c: V ×V → R+, wobei cij ≥ 0.

N = (V,E,c) sei das Netzwerk und mit Q = {i 1 ,...,ik} wird die Menge bezeichnet, die die zu untersuchenden Knoten enthält, wobei i ∈ { 1 , ..., n}. Es wird dabei jeder Knoten nur einmal in Q aufgenommen und entfernt.

Betrachtet werden von dem zu untersuchenden Knoten alle erreichbaren Nachfolgerknoten. Diese werden mit einer sogenannten Marke versehen, welche dabei die Gesamtentfernung zu dem entsprechenden Knoten sowie den Vorgängerknoten enthält. Nur wenn sich eine minimalere Gesamtentfernung von einem anderen Knoten aus ergibt, wird diese Marke verbessert. Gelabelt wird der Knoten, wo die Gesamtentfernung unter allen noch nicht gelabelten aber markierten Knoten minimal ist.

Die Auswahlregel für Q: i = arg min dk, k ∈ Q, wobei dk die Gesamtlänge von Knoten i nach j ist.

2.2 Dijkstra-Verfahren im Verkehrsnetzwerk (Beispiel)

Im Folgenden soll ein Beispiel zur Bestimmung eines kürzesten Weges in einem Verkehrsnetzwerk betrachtet werden. In Abbildung 10 sind die Orte markiert, die für das zu untersuchende Beispiel von Bedeutung sind.

Wir befinden uns mit unserem PKW in Dortmund (Do) und möchten auf kürzestem Wege unser Ziel Köln (K) erreichen. Es gibt einige Verbindungsstraßen in unserer Umgebung, über die wir unser Ziel erreichen können. Im Verkehrsnetzwerk seien folgende Orte im näheren Umfeld erreichbar: Hagen (Ha), Wuppertal (W), Duisburg (Du) und Düsseldorf (D). Alle genannten Orte stellen für den Graphen somit die Knoten dar.

Um das Dijkstra-Verfahren anzuwenden, seien die eingezeichneten Kanten sowie die Kantenbewertungen gegeben. Da dieses Beispiel zur Überzeugung der Berechnung kürzester Wege beitragen soll, wie sie auch bei Navigationssoftware Anwendung findet, werden die Gewichte als entsprechende Entfernung in Kilometer von Knoten i nach j definiert, wobei hier

i, j ∈ {Do, Du, Ha, W, D, K}.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 10: Digraph mit Knoten, Kanten und Gewichten für unser Beispiel¹⁷

[...]

---

¹ vgl. [ADAC], Staubilanz 2011

² vgl. [Möhring], Optimierung von Netzwerken, September 2003³ vgl. [BMVBS], Investitionsrahmenplan 2011-2015

⁴ vgl. [BMU 06], Gütertransporte 2006

⁵ vgl. [BMU 07], Gütertransporte 2007

⁶ vgl. [StBA], Personenbeförderung

⁷ vgl. [BMVBS 10], Im Profil , Mai 2010.⁸ vgl. [Gritzmann]

⁹ vgl. [Möhring], Optimierung von Netzwerken, September 2003

¹⁰ vgl. [Möhring], Optimierung von Netzwerken, September 2003

¹¹ vgl. [Möhring], Optimierung von Netzwerken, September 2003

¹² vgl. [Möhring], Optimierung von Netzwerken, September 2003

¹³ vgl. [Mansfeld] (1998)

¹⁴ vgl. [Möhring], Optimierung von Netzwerken, September 2003

¹⁵ vgl. [Möhring], Optimierung von Netzwerken, September 2003 8

¹⁶ vgl. [Gritzmann]

¹⁷ vgl. [Uni Bonn], Lutz Plümer, Diskrete Mathematik II