Entwurf und Implementierung eines
Routing-Algorithmus und eines
zugrundeliegenden Datenmodells
am Beispiel des Straßennetzes

Diplomarbeit von Michael Hülsmann

Hochschule Bochum
Fachbereich Vermessung und Geoinformatik
Bochum, Februar 2008

Inhaltsverzeichnis

Inhaltsverzeichnis ... 2

Aufgabenstellung ... 4

Danksagung ... 5

1 Einleitung ... 7

1.1 Zielsetzung der Arbeit ... 7

1.2 Aufbau der Arbeit ... 8

2 Erläuterung von Bezeichnungen und Begriffen ... 9

2.1 Graphentheorie ... 9
2.1.1 Euler und Hamilton ... 11
2.1.2 Bäume ... 12
2.1.2.1 Minimaler Spannbaum ... 12
2.1.2.2 1-Baum ... 14

2.2 Komplexitätstheorie ... 15
2.2.1 Komplexität von Algorithmen ... 15
2.2.2 NP-Probleme ... 16

3 Einführung in Routing-Probleme ... 18

3.1 Kürzeste-Wege-Problem ... 18
3.1.1 Dijkstra-Algorithmus ... 19
3.1.2 A*-Algorithmus ... 22
3.1.3 Floyd-Warshall-Algorithmus ... 25
3.1.4 Abbiegeverbote ... 26
3.1.4.1 Kantenaufnahme ... 27
3.1.4.2 Mehrfache Knotenaufnahme ... 28
3.1.4.3 Ziehen neuer Kanten ... 29
3.1.4.4 Verbotsorientiertes Knotensplitting ... 30
3.1.4.5 Knotenorientierte Netzwerke ... 31
3.1.5 Wegeverbote ... 32
3.1.6 Kürzeste Wege in modifizierten Graphen ... 34

3.2 Chinesisches-Postboten-Problem ... 37

3.3 Traveling-Salesman-Problem ... 42
3.3.1 Bestimmung einer oberen Schranke ... 43
3.3.2 Bestimmung einer unteren Schranke ... 44
3.3.3 Branch-and-Bound-Verfahren ... 46

4 Implementierung eines Systems zur Routenplanung ... 51

4.1 Datenmodell ... 51

4.2 Demonstrator ... 59

5 Zusammenfassung und Ausblick ... 68

Literaturverzeichnis ... 71

Abbildungsverzeichnis ... 73

1 Einleitung

Mobilität und Wirtschaftlichkeit haben in unserer Gesellschaft einen hohen Stellenwert. Hierzu gehört unter anderem, möglichst zeit- oder kostengünstig ein geografisches Ziel zu erreichen. Dabei spielt der Einsatz von Systemen zur Routenplanung und -führung eine sehr große Rolle. Der technische Fortschritt der letzten Jahre hat dazu geführt, dass nicht nur in vielen Kraftfahrzeugen Navigationssysteme zur Standardausstattung gehören, sondern dass es auch leistungsstarke Lösungen zur Zielführung gibt, die in mobilen Geräten wie etwa in Personal Digital Assistant’s (PDA’s) integriert sind. Auch im Internet sind Routenplaner verfügbar, die für jeden Benutzer kostenfrei den optimalen Weg zu einem beliebigen Ziel in ganz Europa ermitteln.

Die Grundlage für derartige Systeme, die effizient einen optimalen Weg bestimmen, liegt in der möglichst präzisen Abbildung der Wirklichkeit in einem Datenmodell, ohne jedoch überflüssige Daten zu erheben. Anschließend muss auf diese Daten ein der Problemstellung angepasster Algorithmus angewendet werden, der in annehmbarer Zeit ein Ergebnis liefert.

Das Gebiet der Routenplanung umfasst aber noch mehr Fragestellungen, als nur Die nach dem kürzesten Weg zu einem gegebenen Ziel. Weitere Problemstellungen sind beispielsweise die Suche nach einer möglichst günstigen Verbindung mehrerer Orte, wie etwa für eine Geschäftsreise, oder auch die Suche nach einer effizienten Tour für die Müllabfuhr, also einer Route, auf der jede Straße eines Bezirks mindestens einmal, aber möglichst wenige Straßen doppelt befahren werden.

1.1 Zielsetzung der Arbeit

Im Fachbereich Vermessung und Geoinformatik der Hochschule Bochum, in dem diese Arbeit entstanden ist, sind bisher keine Forschungen zu dem Thema Routenplanung gelaufen. Aus diesem Grund ist dieses Werk in gewisser Weise als Pionierarbeit zu sehen. Ziel dieser Arbeit ist es somit, zunächst eine Einführung in diese vielfältige Problematik der Bestimmung optimaler Wege in den verschiedenen Anwendungsbereichen zu geben und die hierzu bestehenden Lösungsansätze vorzustellen. Des Weiteren soll auf der Grundlage einer selbst entworfenen Datenstruktur ein Programm implementiert werden, das das Kürzeste-Wege-Problem löst. Dieses Programm soll in der Lage sein, unter Berücksichtigung von speziellen Bedingungen, wie z.B. Abbiegeverboten, einen optimalen Weg von einem Start- zu einem Zielpunkt anzugeben. Auch die Auswahl eines Zwischenpunktes soll optional möglich sein. Die Suche eines optimalen Weges meint an dieser Stelle wahlweise den kürzesten oder den schnellsten Weg. Die Entwicklung eines komplexen und komfortablen Programms mit grafischer Ausgabe der Wegbeschreibung und vielen gängigen Extrafunktionen ist nicht vorgesehen.

1.2 Aufbau der Arbeit

Zunächst sollen die zum Verständnis dieser Arbeit notwendigen Begriffe aus der Graphentheorie und die verwendeten Bezeichnungen erläutert werden. Es wird in diesem Zusammenhang auch kurz auf die Bewertung der Zeitkomplexität von Algorithmen eingegangen. Daran anschließen soll eine Darlegung der vielen unterschiedlichen Problemstellungen der Routenplanung, Ansätze diese Aufgaben zu lösen und teilweise auch die Angabe und Erläuterung von gebräuchlichen Algorithmen. Im daran anschließenden Kapitel wird auf das von mir entwickelte und implementierte System zur Routenplanung eingegangen. Dabei wird zum Einen das zugrundeliegende Datenmodell erläutert, zum Anderen das hierauf zugreifende Programm mit den verwendeten Algorithmen.

2 Erläuterung von Bezeichnungen und Begriffen

Die Grundlage für ein funktionierendes Routenplanungssystem bildet, wie bereits erwähnt, die wirklichkeitsgetreue Abbildung des Straßennetzes. Diese Abbildung in ein mathematisches Modell erfolgt in einen Graphen. In diesem Kapitel werden die Begriffe und Bezeichnung der Graphentheorie erläutert, die für das Verständnis dieser Arbeit wichtig sind und im weiteren Verlauf Verwendung finden. Auf formalmathematische Definitionen wird aus Gründen der Verständlichkeit jedoch verzichtet. Am Ende dieses Kapitels wird auch noch kurz auf die Komplexitätstheorie eingegangen, mit deren Hilfe die Bewertung der Laufzeit von Algorithmen durchgeführt wird.

2.1 Graphentheorie

Die Grundelemente eines Graphen G sind Knoten und Kanten. Knoten stellen als punktförmige Elemente - je nach Grad der Generalisierung - z.B. Straßenkreuzungen oder Ortschaften dar, Kanten sind linienförmige Elemente, die die Verbindungen zwischen je zwei Knoten herstellen. Die Menge aller einzelner Knoten v_i wird als V bezeichnet, die Menge aller einzelner Kanten ei als E. Daraus folgt als Schreibweise für den Graphen G=(V, E). Zur Bewertung eines Graphen können sowohl die Knoten als auch die Kanten mit Gewichten versehen werden. Als Kantengewicht kann die Länge einer Kante in Kilometern oder auch die zum Passieren dieser Kante benötigte Fahrzeit in Minuten gewählt werden. Knotengewichte sind z.B. als besonders lange Wartezeit an einer Kreuzung denkbar, aber eher unüblich. An Stelle von Gewichten wird auch die Bezeichnung Kosten k_i verwendet. Es ist sinnvoll und bei manchen Algorithmen sogar notwendig, nur positive Zahlen als Gewichte zu verwenden.

Ein Graph heißt zusammenhängend, wenn es möglich ist, von jedem Knoten unter Verwendung der vorhandenen Kanten zu jedem anderen Knoten zu gelangen. Ist ein Graph auch nach Wegnahme einer beliebigen Kante noch zusammenhängend, so heißt er zweifach zusammenhängend.

Es besteht die Möglichkeit, gerichtete Kanten zu verwenden. Solche Kanten haben einen Anfangs- und einen Endknoten und werden als Bögen bezeichnet. Ein Graph, der nur Bögen, aber keine Kanten mehr hat, heißt Digraph. Ein stark zusammenhängender Graph ist ein zusammenhängender Digraph (vgl. Abbildung 1). Wenn die Knoten eines Graphen sowohl durch Kanten, als auch durch Bögen miteinander verbunden werden, spricht man von einem gemischten Graphen.

(Abbildung 1: zusammenhängender Digraph - In Downloadversion enthalten)

Es kann vorkommen, dass ein Knotenpaar durch mehrere Kanten verbunden wird. Dieses ist z.B. bei Netzplänen der Deutschen Bahn der Fall. Ein solcher Graph heißt Multigraph. Bei einem Graphen wie dem in Abbildung 1, in dem ein Knotenpaar durch zwei gegenläufige Bögen verbunden ist, handelt es sich nicht um einen Multigraph. Eine Schleife bezeichnet eine Kante oder einen Bogen von einem Knoten auf sich selbst. Eine Folge von Bögen oder Kanten, die ohne Mehrfachnutzung eines Bogens beziehungsweise einer Kante wieder zum Anfangsknoten zurückführt, heißt Kreis. Ein Graph ist kreisfrei, wenn er ungerichtet und ohne Kreise ist. In einem vollständigen Graphen ist jeder Knoten mit jedem anderen Knoten direkt verbunden.

Mit dem Grad oder der Wertigkeit eines Knotens bezeichnet man die Anzahl der Bögen beziehungsweise der Kanten, die diesen Knoten enthalten. Bei Bögen gibt es eine weitere Unterscheidung zwischen den Bögen, die in einen Knoten münden (Ingrad) und Bögen, die von einem Knoten ausgehen (Ausgrad). Der Grad eines Knotens wird zur Formulierung einer wichtigen Eigenschaft von Graphen verwendet, nämlich der, dass jeder Graph eine gerade Anzahl von Knoten ungerader Wertigkeit besitzt. Diese Eigenschaft lässt sich einfach beweisen, indem zunächst ein Graph ohne Kanten gegeben sei. Somit haben alle Knoten eine gerade Wertigkeit, nämlich null. Das Ziehen der ersten Kante führt bei zwei Knoten zu der ungeraden Wertigkeit eins. Wird nun zwischen zwei Knoten geraden Grades eine Kante gezogen, so steigt die Anzahl der Knoten ungeraden Grades um zwei, analog sinkt Diese um zwei beim Ziehen einer Kante zwischen zwei Knoten ungeraden Grades. Eine Kante zwischen einem Knoten ungeraden Grades und einem Knoten geraden Grades ändert nichts an der Anzahl von Knoten ungeraden Grades. Somit ändert sich die Anzahl der Knoten ungerader Wertigkeit begonnen bei null entweder um zwei oder gar nicht, bleibt also immer gerade.

[...]