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

2

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

Inhaltsverzeichnis 3

4  IMPLEMENTIERUNG EINES SYSTEMS ZUR ROUTENPLANUNG  51

4.1  DATENMODELL  51

4.2  DEMONSTRATOR  59

5  ZUSAMMENFASSUNG UND AUSBLICK  68

  LITERATURVERZEICHNIS  71

ABBILDUNGSVERZEICHNIS ....................................................................... 73

4

5

Danksagung

An dieser Stelle möchte ich allen danken, die einen Teil zum Gelingen dieser Arbeit beigetragen haben.

Ich bedanke mich bei Herrn Prof. Dr.-Ing. Franz Josef Lohmar für das Ermöglichen dieser Diplomarbeit durch die interessante Aufgabenstellung, für die hilfreichen Gespräche und die sonstige Betreuung.

Bei Herrn Prof. Dr.-Ing. Manfred Bäumker bedanke ich mich für die Übernahme der Aufgabe des Korreferenten.

Des Weiteren möchte ich mich bei Herrn Sebastian Bönigk für die Hilfe bei der Erzeugung einer Datenbank-Schnittstelle bedanken.

Ein besonderer Dank geht an meine Mutter, die mir nach dem Defekt meines Notebooks ihren PC-Arbeitsplatz zur Verfügung gestellt hat, sowie an meine gesamte Familie für die Motivation während des Studiums und den finanziellen Rückhalt.

6

1 | Einleitung 7

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

1 | Einleitung 8

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.

9

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 formal- mathematische 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 e i 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.

2 | Erläuterung von Bezeichnungen und Begriffen 10

einem gemischten Graphen.

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

2 | Erläuterung von Bezeichnungen und Begriffen 11

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.

2.1.1 Euler und Hamilton

Ein Mathematiker, der sich unter anderem mit der Graphentheorie beschäftigt und sie in gewisser Weise begründet hat, ist Leonhard Euler. Aus diesem Grund tragen einige Begriffe in diesem Bereich seinen Namen: Als Eulerweg wird jeder Weg durch einen Graphen bezeichnet, der von einem Startknoten ausgehend jede Kante genau einmal benutzt. Als Eulerkreis wird ein Eulerweg bezeichnet, der in seinem

Startknoten endet. Dem entsprechend wird mit Eulerkreis-Problem die Aufgabe

bezeichnet zu prüfen, ob es in einem Graphen einen Eulerkreis gibt und diesen anzugeben. Falls ein Graph einen Eulerkreis enthält, so heißt er eulersch. Unter Ausnutzung des Grades eines Knotens lässt sich der Satz von Euler aufstellen, der besagt, dass für jeden zusammenhängenden Graphen ein Eulerweg existiert, wenn

höchstens zwei Knoten ungerade Wertigkeit besitzen und dass ein Eulerkreis genau

dann existiert, wenn alle Knoten gerade Wertigkeit besitzen.

Für eine weitere sehr bedeutende Problemstellung ist der irische Astronom und Mathematiker Sir William Rowan Hamilton der Namensgeber. Zur Beschreibung dieser Aufgabe gibt es, analog zu dem Eulerweg und –kreis, den Hamiltonweg und – kreis. Ein Hamiltonweg ist jeder Weg durch einen Graphen, der von einem Startknoten ausgehend jeden Knoten genau einmal benutzt. Der Hamiltonkreis ist ein Hamiltonweg, der in seinem Startknoten endet. Die Suche nach einem

Hamiltonkreis in einem Graphen wird als Hamiltonkreis-Problem bezeichnet.

2 | Erläuterung von Bezeichnungen und Begriffen 12

2.1.2 Bäume

Eine weitere Gruppe von Graphen, auf die kurz eingegangen

werden soll, ist die der Bäume. Ein Baum ist ein kreisfreier, zusammenhängender Graph. Den Knoten am Beginn eines Baumes nennt man Wurzel, die Endknoten eines Baumes heißen Blätter (vgl. Abbildung 2). Bäume spielen in der Graphentheorie eine große Rolle. Sie bilden innerhalb eines Graphen sowohl eine maximale, kreisfreie Teilmenge als auch eine minimale zusammenhängende Teilmenge. Jedes Hinzufügen einer Kante würde zu einem Kreis führen und jede Wegnahme einer Kante würde den Baum in zwei Teile teilen.

2.1.2.1 Minimaler Spannbaum

Ein Spannbaum ist ein Baum, der alle Knoten eines Graphen miteinander verbindet. Ist der Spannbaum minimal, so erzeugt er die geringsten Kosten. Anders ausgedrückt ist die Summe der Gewichte der für den Spannbaum gewählten Kanten minimal. Zum Erzeugen minimaler Spannbäume

ist es wichtig, immer nur die günstigsten Kanten auszuwählen. Algorithmen, vorgehen, werden als Greedy-Algorithmen bezeichnet. Dieser Name stammt von dem englischen Wort greedy (deutsch: gierig), da solche Algorithmen immer „gierig“ nach den günstigsten Kanten greifen. Ein solcher Algorithmus ist beispielsweise der Prim- Algorithmus, dessen Funktionsweise im Folgenden erläutert werden soll. In den nebenstehenden Abbildungen werden die erreichten Knoten des Beispielgraphen rot

2 | Erläuterung von Bezeichnungen und Begriffen 13

gefärbt, die gewählten Kanten schwarz, die als nächstes auswählbaren Kanten grün und der Rest des Graphen wird in grau dargestellt. Der Prim-Algorithmus wählt als erste Kante die aus, die den Startknoten am günstigsten verlässt. Dies ist im Beispiel die Kante von s nach a mit dem Gewicht 3. Im nächsten Schritt wird die Kante gewählt, die den Startknoten oder den soeben erreichten Knoten am günstigsten verlässt. Die nun gewählte Kante ist die von

Knoten a nach b mit dem Gewicht 1. In diesem Schritt wird außerdem die Kante von s nach b aus dem Graphen gelöscht, da die Auswahl dieser Kante einen für Bäume unzulässigen Kreis erzeugen würde. Die Strategie ist also, unter allen Kanten, die die erreichten Knoten verlassen, die insgesamt Günstigste zu wählen, wobei jedoch Kreise zu vermeiden sind. Als Ergebnis liefert dieser Algorithmus den in Abbildung 4 dargestellten minimalen Spannbaum. Dieser Algorithmus wurde zur detaillierteren Beschreibung ausgewählt, da er dem in Kapitel

3.1.1 beschriebenen Dijkstra-Algorithmus zur Bestimmung kürzester Wege sehr

ähnlich und somit durch eine leichte Modifikation hieraus ableitbar ist. In Abbildung 5 ist der Prim-Algorithmus dargestellt, die Änderungen gegenüber dem Dijkstra- Algorithmus sind rot hervorgehoben.

2 | Erläuterung von Bezeichnungen und Begriffen 14

Ein weiteres Verfahren aus der Gruppe der Greedy-Algorithmen, das an dieser Stelle nur nachrichtlich erwähnt wird, ist der Kruskal-Algorithmus. Während der Prim- Algorithmus nur die von erreichten Knoten abgehenden Kanten betrachtet, sucht der Kruskal-Algorithmus immer die im gesamten Graphen günstigste Kante. Es ist jedoch auch hier darauf zu achten, dass Kanten, die einen Kreis erzeugen würden, aus dem Graphen entfernt werden, damit sie nicht ausgewählt werden können. Auch dieser Algorithmus liefert als Ergebnis einen minimalen Spannbaum.

2.1.2.2 1-Baum

Ein ganz besonderer Baum ist der 1-Baum (sprich Einsbaum). Um einen 1-Baum zu erhalten, muss man zunächst einen beliebigen Knoten mit seinen abgehenden Kanten aus dem Graphen entfernen und aus dem verbleibenden Graphen einen

minimalen Spannbaum bestimmen. Anschließend wird der minimale Spannbaum um den zuvor entfernten Knoten mit seinen beiden günstigsten Kanten ergänzt. In Abbildung 6 ist ein 1-Baum dargstellt. Hierbei sind die grünen Kanten die für den minimalen Spannbaum gewählten, die roten Kanten und der mit einer 1 versehene Knoten wurden zu Beginn entfernt und zum Schluss wieder angefügt. Die Zahlen an den Kanten sind die Kantengewichte. Der 1-Baum wird bei der Bestimmung von Rundreisen eine Rolle spielen.

2 | Erläuterung von Bezeichnungen und Begriffen 15

2.2 Komplexitätstheorie

Zum Abschluss dieses Kapitels soll kurz auf die Bewertung von Algorithmen eingegangen werden. Hierzu ist es nötig, sich mit der Komplexitätstheorie auseinander zu setzen. Die Komplexitätstheorie ist ein Teilgebiet der theoretischen Informatik, das sich eben mit dieser Problematik beschäftigt. Zur Bewertung algorithmisch behandelbarer Probleme werden zunächst mathematische Modelle von Rechnern aufgestellt. Dies ist notwendig, um Algorithmen unabhängig von der Leistungsstärke des jeweiligen Computers bewerten und vergleichen zu können. Anschließend wird ein Vergleichsmaßstab festgelegt, wie etwa der Speicherplatzbedarf oder die Rechenzeit.

2.2.1 Komplexität von Algorithmen

Im Folgenden soll auf das wohl wichtigste Modell, die Turing Maschine, eingegangen werden. Die Turing Maschine wurde 1937 von dem britischen Mathematiker, Logiker und Kryptoanalytiker Alan Mathison Turing entwickelt. Das Besondere an diesem Modell ist, dass es hierdurch möglich wird, die Laufzeit eines Algorithmus auf die Anzahl weniger Grundoperationen zurückzuführen. Diese

Grundoperationen sind die Grundrechenarten Addition, Subtraktion, Multiplikation

und Division sowie die Vergleichsoperationen kleiner, größer und gleich und die

Zuweisung eines Wertes. Zur Ermittlung der Laufzeit wird die Anzahl der

durchzuführenden Grundoperationen beim Durchlaufen des Algorithmus bestimmt. Hierbei ist es nicht wichtig, die genaue Anzahl festzustellen, sondern vielmehr wird eine obere Schranke als Wert festgelegt, der unterschritten oder maximal erreicht, nie aber überschritten wird. Da es sich um die Bestimmung einer oberen Schranke handelt, wir als Symbol der Buchstabe O verwendet. Die Anzahl der ermittelten Grundoperationen wird bei Routenplanungsproblemen je nach Algorithmus in Verhältnis zur Anzahl der im Graphen vorkommenden Knoten oder Kanten bewertet.

Sind beispielsweise bei einem Graphen mit n Knoten n 2 Grundoperationen notwendig, so wird diese Komplexität dargestellt als O(n 2 ) und man sagt, der