Grundlagen

Wie schon in der Einleitung dargestellt, geht es in dieser Arbeit um das Routing innerhalb eines Verkehrsnetzes. Der Begriff „Routing“ kommt ursprünglich aus der Informations- und Kommunikationstechnik. Routing bezeichnet dabei „das Ermitteln eines geeigneten [besonders günstigen] Wegs für die übertragung von Daten in einem Netzwerk“ (Duden). Heute wird „Routing“ ebenfalls im Zusammenhang mit der Routenplanung in Straßennetzen benutzt. Auch wenn die Datenübermittlung in einem Kommunikationsnetz und die Berrechnung einer bestimmten Route in einem Verkehrsnetz, auf den ersten Blick zwei völlig unterschiedliche Sachverhalte darstellen, stecken dahinter die gleichen überlegungen. Nämlich das Auffinden des „optimalen“ Weges. Für die Lösung dieser Probleme bedient man sich der Graphentheorie, einem Teilbereich der Mathematik. Dabei werden komplizierte Sachverhalte vereinfacht und auf Gebilde aus Punkten, Linien und Flächen abstrahiert, dem sogenannten Graphen.

Graphentheorie

Als Begründer der Graphentheorie gilt der Mathematiker Leonhard Euler. Dieser löste 1736 das Königsberger Brückenproblem. Dabei ging es um die Frage, ob es möglich sei, bei einem Spaziergang durch Königsberg alle sieben Brücken der Stadt genau einmal zu überqueren und dabei zum Aus- gangspunkt zurückzukehren. Die Grundidee zur Lösung des Problems war es, den Stadtplan auf Punkte (Stadtteile) und Linien (Brücken) zu reduzieren. Abbildung 1 zeigt die Abstraktion des Königsberger Brückenproblems auf einen Graphen (c). Euler zeigte und bewies, dass das Problem unlösbar ist. Detailierte Ausführungen zu Eulers Lösung finden sich in verschiedenen Schriften und können bei Bedarf dort nachgelesen werden.

Der Graph

Ein Graph besteht also aus Punkten, die Knoten genannt werden, und Linien, die Kanten genannt werden. Graphen haben eine Reihe von Eigenschaften. Auf einige, die speziell für die Modellierung eines Graphen für Straßennetze nützlich sind, wird an dieser Stelle eingegangen.

Ein Graph lässt sich als ein Quadrupel G = (V, E, α, ω) darstellen. Dabei ist V (lat. Vertex = Punkt) die Menge aller Knoten und E (engl. edge = Kante) die Menge aller Kanten. α: E → V und ω: E → V sind Abbildungen. Wobei α(e) der Anfangsknoten und ω(e) der Endknoten ist. Dadurch ergeben sich Richtungen für die Kanten, der Graph wird zu einem gerichteten Graph oder auch Digraph (engl. „directed graph“). ¹⁾

Man bezeichnet den Graphen als gewichtet, wenn es zusätzlich eine Abbildung β: E → R gibt. Dabei ist β das Gewicht bzw. die Länge einer Kante. Der Graph heißt positiv, wenn gilt β(e) ≥ 0 für alle e ≥ E. ²⁾

Algorithmen

„Algorithmen sind Verfahren zur Lösung von Problemen.“ ³⁾ Diese Probleme können aus bis zu unendlich vielen Einzelproblemen bestehen. Vorrausgesetzt sie weisen die gleichen Strukturen auf, ist es dem Algorithmus möglich die Gesamtheit der Probleme zu lösen. Der Algorithmus beschreibt die einzelnen Handlungsschritte, die zur Lösung führen. ⁴⁾

Für diese Arbeit wurden vor allem Algorithmen benötigt, die die optimale Route finden. Was als optimale Route ausgelegt wird, kann sehr unterschiedlich sein. Das kann zum Beispiel die schnellste oder auch die kürzeste Route sein. Da es eine Vielzahl an potentiellen Routen in einem Straßennetz gibt, müssen diese Algorithmen sehr effizient arbeiten. In ⁵⁾ lässt sich dazu ein passender Vergleich finden: Im deutschen Straßennetz gibt es zirka 5.022.028 Kreuzungen und 6.169.904 Straßen (aus Lauther, U.: Persönliche Kommunikation, 2005). Das ergibt bei der Bestimmung eines Weges von Berlin nach München, eine Anzahl von 10¹⁰⁰ Möglichkeiten. Im Vergleich dazu, beläuft sich die Anzahl der Atome im Universum nach heutigen Schätzungen auf ca. 10⁸⁰ . Für die Berechnung aller Wege wird eine enorme Rechenleistung notwendig, die selbst mit heutigen Computern nicht erreicht wird. Daher ist es notwendig, dass der gewählte Algorithmus nicht nur zum gewünschten Ergebnis führt, sondern dies auch in einer akzeptablen Zeit schafft. In der heutigen Zeit kann man in diesem Zusammenhang von Sekundenbruchteilen ausgehen.

Die wohl prominentesten Algorithmen in diesem Zusammenhang sind der Dijkstra- und der A*-Algorithmus. Auf der Homepage der Technischen Universität München finden sich eine Reihe von Java-Applets, die verschiedene Algorithmen veranschaulichen (Link). Unter anderem werden auch der Dijkstra- und A*-Algorithmus dargestellt. Die Applets geben die Möglichkeit die Algorithmen anhand von Beispielgraphen nachzuvollziehen. Darüber hinaus ist es möglich eigene Graphen zu konstruieren. Die Algorithmen können zudem als Pseudocode betrachtet werden. Die Applets sind daher besonders gut geeignet um ein besseres Verständnis über die Algorithmen zu erlangen.

 

(Quellen: 1) Manfred Nitzsche. Graphen für Einsteiger. Rund um das Haus vom Nikolaus. 3. Aufl. Vieweg + Teubner Verl., 2009. 2) Hartmut Noltemeier. Graphentheorie. Berlin: de Gruytner Lehrbuch, 1976. 3) Dieter Jungnickel. Graphen, Netzwerke und Algorithmen. Mannheim, Leipzig, Wien, Zürich: BI-Wiss.-Verl., 1994., S. 56 f. 4) Firoz Kaderali und Werner Poguntke. Graphen Algorithmen Netze. Grundlagen und Anwendungen in der Nachrichtentechnik. Vieweg Verl., 1995. 5) S. O. Krumke und H. Noltemeier. Graphentheoretische Konzepte und Algorithmen. 1. Aufl. Teubner Verl., 2005.)