1
Einleitung
1.1
Hintergründe zur optimalen Wegstreckenführung
Das Verkehrsaufkommen auf Autobahnen, Landstraßen und auch im Stadtver-
kehr 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 ent-
spricht, gemessen an Luftliniendistanzen.
1
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.
2
Im aktuellen Investitionsrahmenplan für Verkehrsprojekte hat Bundesverkehrs-
minister 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 Infrastruk-
turprojekte zur Verfügung gestellt wird. Ramsauer erklärte, dass bei dieser Mit-
telverwendung 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.
3
1
vgl. [ADAC], Staubilanz 2011
2
vgl. [Möhring], Optimierung von Netzwerken, September 2003
3
vgl. [BMVBS], Investitionsrahmenplan 2011-2015
1
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 wir-
ken. 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.
4
(s. Grafik)
Abbildung 1: Gütertransporte innerhalb Deutschlands von 1991 - 2006
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.
5
4
vgl. [BMU 06], Gütertransporte 2006
5
vgl. [BMU 07], Gütertransporte 2007
2
Einer der wichtigsten Punkte für die Untersuchung zur Optimalen Wegstrecken-
führung ist der Personenverkehrstransport mittels Kraftwagen. Dieser Anteil liegt
aktuell innerhalb Deutschlands bei über
4
5
aller Personenverkehrsleistungen und
ist innerhalb der letzten vier Jahre stetig gestiegen.
6
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 priva-
te 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.
6
vgl. [StBA], Personenbeförderung
3
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 Verkehrswe-
gearten in Deutschland nicht mit erhoben.
7
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 unbe-
kannten 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:
8
G
= (V, E)
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 Rou-
tenplanung die Orte dar, zwischen denen wir eine optimale Verbindung finden
möchten. Bei einer Fahrt von München nach Hamburg können die Knoten bei-
spielsweise 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 miteinan-
der definiert.
Beispiel:
9
Abbildung 4: Basisstruktur
7
vgl. [BMVBS 10], Im Profil , Mai 2010.
8
vgl. [Gritzmann]
9
vgl. [Möhring], Optimierung von Netzwerken, September 2003
4
Ein solcher Graph wie in Abbildung 4 soll als ungerichteter Graph, welcher zu-
sammenhängend ist, bezeichnet werden. Er ist deshalb zusammenhängend, weil
die Möglichkeit besteht, über die vorhandenen Kanten von einem beliebigen Kno-
ten 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 Or-
ten 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 gekenn-
zeichnet 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 Aus-
wirkungen auf die Kapazität der Kante hat.
Beispiel:
10
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 ent-
weder 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.
10
vgl. [Möhring], Optimierung von Netzwerken, September 2003
5
Digraph bezeichnet einen gerichteten Graphen, bei dem die Kanten mit entspre-
chenden Gewichten versehen sind. Für Wegoptimierungen sind die Kantenbewer-
tungen 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).
11
Beispiel:
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 Millio-
nen Knoten und 11,9 Millionen Kanten zusammen. Allein die Hauptstadt Berlin
hat insgesamt 10.000 Knoten und 30.000 Kanten. Ein Ausschnitt eines Stadt-
Straßennetzes in Berlin zeigt folgende Abbildung.
12
Abbildung 7: Stadt-Straßennetz Lietzenburger/Joachimstaler Straße, Berlin - gerichteter Graph
11
vgl. [Möhring], Optimierung von Netzwerken, September 2003
12
vgl. [Möhring], Optimierung von Netzwerken, September 2003
6
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.
13
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öchstge-
schwindigkeit 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ßen-
verlä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 Mehrbelas-
tung von Verkehrsstrecken durch den Einsatz von GPS-Routenführung. Ange-
nommen 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:
14
Abbildung 8: Verkehrsteilnehmer mit gleichem Start -und Zielort
13
vgl. [Mansfeld] (1998)
14
vgl. [Möhring], Optimierung von Netzwerken, September 2003
7
In Abbildung 9 wird deutlich, dass die Navigationshilfe zwar auf den kürzes-
ten 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 betrachte-
ten Ziel Hamburg sollte demnach wie folgt aussehen:
15
Abbildung 9: Effiziente Verkehrsführung bei gleichem Start -und Zielort
Um dieses Ziel zu erreichen befinden sich die PKW auf verschiedenen Verkehrs-
wegen. 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 Rou-
ten 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 Fahr-
zeiten?
Auf diese Frage soll in Kapitel zwei der vorliegenden Arbeit näher eingegan-
gen werden. Hätten auch die Verkehrsteilnehmer auf den Alternativrouten den
kürzesten Weg befahren, so hätte die Verkehrsbelastung auf dem selbigen erheb-
lich zugenommen (siehe Abbildung 8). Vermutet wird, dass dadurch die globale
Fahrzeit, d.h. die Gesamtfahrzeit aller PKW auf der Route von Berlin nach Ham-
burg, gestiegen wäre. Ob und in wieweit dies der Fall ist, gilt es am Beispiel zu
untersuchen.
15
vgl. [Möhring], Optimierung von Netzwerken, September 2003
8
2
Hauptteil
2.1
Dijkstra-Verfahren zur Bestimmung kürzester Wege
Das Dijkstra-Verfahren liefert in Bezug auf die bisher erarbeiteten Vorausset-
zungen 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.
16
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 Weg-
lä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 e
ij
verbinde die zwei Knoten i und j. Die Markierun-
gen der Kanten erfolgt über die Gewichtsfunktion c
: V ×V R
+
, wobei c
ij
0.
N
= (V, E, c) sei das Netzwerk und mit Q = {i
1
, ..., i
k
} wird die Menge be-
zeichnet, 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 Nachfol-
gerknoten. 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 d
k
, k
Q, wobei
d
k
die Gesamtlänge von Knoten i nach j ist.
16
vgl. [Gritzmann]
9
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ür-
zestem Wege unser Ziel Köln (K) erreichen. Es gibt einige Verbindungsstraßen in
unserer Umgebung, über die wir unser Ziel erreichen können. Im Verkehrsnetz-
werk 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 so-
wie 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 Kilo-
meter von Knoten i nach j definiert, wobei hier
i, j
{Do, Du, Ha, W, D, K}.
Abbildung 10: Digraph mit Knoten, Kanten und Gewichten für unser Beispiel
17
17
vgl. [Uni Bonn], Lutz Plümer, Diskrete Mathematik II
10