Routenberechnung mit partitionierten Straˇendaten · ten Daten skizziert. Es werden graphentheoretische Begri e diskutiert und verschiedene Algorithmen zur Weg ndung vorgestellt

Fakultat fur Elektrotechnik und InformatikInstitut fur Praktische Informatik

Fachgebiet Datenbanken und Informationssysteme

Routenberechnung mit partitioniertenStraßendaten

Bachelorarbeitim Studiengang Informatik

David BormannMatrikelnummer: 2739920

Prufer: Prof. Dr. Udo LipeckZweitprufer: Dr. Hans Hermann Bruggemann

Betreuer: M. Sc. Hendrik Warneke

Juli 2012

Inhaltsverzeichnis

1 Einleitung 4

1.1 Motivation und Aufgabenstellung . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Gliederung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Grundlagen 6

2.1 Die Open-Streetmap-Daten . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.2 Das Simple-Feature-Modell . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2.1 Geometrieschema . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2.2 Topologische Pradikate und Geometriefunktionen . . . . . . . . . 9

2.3 Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.3.1 Graphentheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.3.2 Der abstrakte Datentyp Graph . . . . . . . . . . . . . . . . . . . 11

2.4 Kurzeste-Wege-Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4.1 Der Bellman-Ford-Algorithmus . . . . . . . . . . . . . . . . . . . 13

2.4.2 Der Dijkstra-Algorithmus . . . . . . . . . . . . . . . . . . . . . . 14

2.4.3 Der A*-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.5 Schlussfolgerung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Konzepte 19

3.1 Partitionierungsarten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2 Ablauf der partitionierten Routenberechnung . . . . . . . . . . . . . . . . 21

3.3 Routensuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.3.1 Heuristiken zur Findung von Zielknoten . . . . . . . . . . . . . . 23

3.3.2 Metriken zur Gewichtung der Kanten . . . . . . . . . . . . . . . . 24

2

INHALTSVERZEICHNIS 3

3.3.3 Vorgehen beim Misserfolg . . . . . . . . . . . . . . . . . . . . . . 24

3.4 Komposition der Routen . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4 Implementierung 27

4.1 Anforderungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.2 OpenJUMP und seine Schnittstelle . . . . . . . . . . . . . . . . . . . . . 27

4.3 Beschreibung der Benutzerschnittstelle . . . . . . . . . . . . . . . . . . . 29

4.4 Finden von Koordinaten uber Adressangabe . . . . . . . . . . . . . . . . 31

4.5 Umgang mit den WGS84-Koordinaten . . . . . . . . . . . . . . . . . . . 31

4.6 Aufbau des Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.6.1 Ermittlung von Kanten aus den OSM-Daten . . . . . . . . . . . . 32

4.6.2 Clipping der Kanten in einer Partition . . . . . . . . . . . . . . . 33

4.7 Klassenbeschreibung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.8 Speicherverwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5 Experimente 48

5.1 Die Experimentierumgebung . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.2 Das Vorgehen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.3 A* versus Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.4 Große versus kleine Partitionen . . . . . . . . . . . . . . . . . . . . . . . 53

5.5 Unterschiede der Metriken . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.6 Unterschiede der Heuristiken . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.7 Abhangige versus unabhangige Partitionierung . . . . . . . . . . . . . . . 59

5.8 Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6 Ausblick 64

A Das simple Osmosis-PostGIS-Schema 65

B PL/pgSQL-Funktionen 66

B.1 Funktionen zum Erstellen der Edges-Tabelle . . . . . . . . . . . . . . . . 66

B.2 Funktionen zum Finden von Start- und Zielknoten . . . . . . . . . . . . . 69

B.3 Funktionen zum Graphaufbau . . . . . . . . . . . . . . . . . . . . . . . . 72

Kapitel 1

Einleitung

Dieses Kapitel dient dazu, einen Uberblick uber das Thema dieser Arbeit zu geben.Es wird die Aufgabenstellung beschrieben und eine Gliederung der weiteren Kapitelangegeben.

1.1 Motivation und Aufgabenstellung

Die fur Fahrzeug- oder Fußgangernavigation benotigten Wegenetze werden ublicherwei-se aus geographischen Daten gewonnen. Diese werden in einen gewichteten Graphentransformiert, in dem Kanten Wege darstellen und Knoten Kreuzungen dieser. Mit Hil-fe verschiedener Algorithmen kann in diesem Graphen der kurzeste Pfad zwischen zweiKnoten ermittelt werden. Dies basiert auf einer Gewichtung der Kanten, beispielsweiseaus der Entfernung zwischen zwei Knoten. Nun konnen diese Wegenetze allerdings sehrgroß werden und den kompletten Graph zu speichern, konnte die Arbeitsspeicherkapa-zitaten eines Rechners sprengen, zum Beispiel die von mobilen Kommunikationsgeratenoder mobilen Servicerobotern. In diesem Fall kann der Graph, beziehungsweise dessenAusgangsmaterial aus geographischen Daten, in kleinere Stucke zerlegt werden, um diesedann vollstandig im Arbeitsspeicher abzulegen.

In dieser Arbeit geht es um die Routenplanung mit Straßendaten, die vorab partitio-niert worden sind. Fur die Berechnung einer Route uber mehrere Partitionen, werdendie einzelnen Ergebnisse einer Wegfindung auf einer Partition zusammengesetzt. DurchExperimente soll bestimmt werden, inwiefern ein solches Ergebnis von der optimalenRoute abweicht. Dabei sollen verschiedene Algorithmen, sowie Partitionierungsgradeund -arten getestet werden. Die erforderlichen geographischen Daten stammen aus demOpen-Streetmap-Projekt und werden in einer PostGIS-Datenbank abgelegt.

4

KAPITEL 1. EINLEITUNG 5

1.2 Gliederung

In Kapitel 2 werden zuerst Open-Streetmap und die Struktur der von ihr bereitgestell-ten Daten skizziert. Es werden graphentheoretische Begriffe diskutiert und verschiedeneAlgorithmen zur Wegfindung vorgestellt.

In Kapitel 3 wird der Ablauf der partitionierten Routenberechnung erlautert. Dazu ge-hort das Laden von Graphpartitionen, dann wird auf diesen die Wegesuche ausgefuhrtund anschließend werden die Routen der einzelnen Partitionen zusammengefuhrt.

Das Kapitel 4 beschaftigt sich mit der Implementierung des Graphaufbaus, verschiedenenweiteren Implementierungsdetails und einer Beschreibung der Benutzerschnittstelle desProgramms.

Das nachfolgende Kapitel 5 beschreibt die ausgefuhrten Experimente und ihre Ergebnis-se.

Das Kapitel 6 bietet einen Ausblick, was man bei der partitionierten Routensuche nochandern oder verbessern konnte.

Im Anhang A ist das verwendete Datenbankschema zur Verwendung der Open-Street-Map-Daten dargestellt.

Im Anhang B finden sich entwickelte PL/pgSQL-Funktionen.

Kapitel 2

Grundlagen

In diesem Kapitel wird ein Uberblick uber das Open-Streetmap-Projekt gegeben, sowieuber den Aufbau der Daten, die von Open-Streetmap zur Verfugung gestellt werden.Es folgen notwendige Begriffserklarungen der Graphentheorie und der Aufbau eines Ab-strakten Datentyps eines Graphen. Anschließend werden mehrere Algorithmen vorge-stellt, die kurzeste Wege von einem Startknoten aus finden.

2.1 Die Open-Streetmap-Daten

Open-Streetmap (im Folgendem mit OSM abgekurzt) ist eine freie Weltkarte, an derjeder mitarbeiten kann, sie zu komplettieren.1 Sie wurde 2004 in Großbritannien ins Le-ben gerufen. Mitglieder der OSM-Community zeichnen ihre Bewegung mit einem GPS-Tracker auf und fugen den geographischen Daten anschließend weitere Informationenhinzu. Dies konnen Straßenart und -namen und angrenzende Points of Interests, bei-spielsweise Gebaude oder Parkplatze, aber auch Briefkasten und Bushaltestellen sein.Eine andere Moglichkeit OSM-Karten zu erstellen, ist das Abzeichnen von Luftbildern.Weitere Information zu OSM kann man in [RT09] finden.

Das Datenmodell von OSM enthalt zwei fur das Routing wichtige Typen Ways undNodes. Des Weiteren gibt es noch Relations, die aus Ways und Nodes bestehen undso komplexere Zusammenhange darstellen konnen, zum Beispiel den Grundriss einesGebaudes, Straßen sind allerdings keine Relationen. Ein Node besteht aus seiner geo-graphischen Lange und Breite und, wie die anderen Objekte auch, aus beliebig vielenAttributen, sogenannte Tags. Das sind Schlussel-Wert-Paare, die dabei helfen, Objektegenauer zu klassifizieren und so zum Beispiel eine Autobahn und einen Fußweg auf einerKarte verschieden darzustellen. Alle Straßen erhalten den Schlussel highway, ein Fußweg

1http://www.openstreetmap.org, steht unter der CC-BY-SA 2.0-Lizenz

6

http://www.openstreetmap.org

http://creativecommons.org/licenses/by-sa/2.0/

KAPITEL 2. GRUNDLAGEN 7

erhalt dann den Tag highway=footway, eine Autobahn highway=motorway. Es gibt aberauch Tags wie oneway=yes, an denen man Einbahnstraßen erkennen kann. Ein Waybesteht zusatzlich noch aus mehreren Nodes, wobei es auf die Reihenfolge ankommt, inder die Nodes abgelegt sind. Seit 2009 darf ein Way- oder Nodeobjekt keine zwei Tagsmit dem selben Schlussel besitzen.

Abbildung 2.1: EER-Diagramm zu Node, Way und deren Tags

In Abbildung 2.1 sind diese Zusammenhange als EER-Diagramm dargestellt. Fur dasRouting irrelevante Attribute sind nicht aufgenommen. Zum Beispiel welcher User eineKante oder einen Knoten zu welchem Zeitpunkt hinzugefugt oder verandert hat. DieAttribute lat und lon bestimmen die geographische Lage eines Nodes, die geographischeBreite lat und Lange lon. Die Koordinaten sind in der Form des WGS84 (World GeodeticSystem 1984) gespeichert.

Die OSM-Daten von Deutschland, Stand 06.06.2012, wurden mit Hilfe von Osmosis2,einem Bearbeitungswerkzeug fur OSM-Daten, in eine PostGIS-Datenbank mit dem sim-plen OSM-PostGIS -Schema, siehe Anhang A uberfuhrt. Wichtig fur den Aufbau desGraphen sind dabei folgende Relationen und Attribute:

NODES (Id, Geom)

NODE TAGS (Node Id → NODES, K, V)

WAYS (Id, Linestring)

WAY TAGS (Way Id → WAYS, K, V)

WAY NODES (Way Id → WAYS, Sequence Id, Node Id → NODES)

2http://wiki.openstreetmap.org/wiki/DE:Osmosis, Version 0.40.1

http://wiki.openstreetmap.org/wiki/DE:Osmosis


Die geographische Lage wird zusammengefasst in dem geographischen Attribut GeomDas Attribut Linestring stellt einen Linienzug uber eine geordnete Menge von Koor-dinaten dar. Es gilt die Integritatsbedingung, dass die sequence id von 0 beginnend,fortlaufend fur jeden Way ist. Mit Hilfe der sequence id lasst sich ein Linienzug uber dieNodes eines Ways konstruieren. Die Relation bilden aus dem EER-Diagram wird durchWAY NODES umgesetzt.

Dass die Karten vornehmlich von Hobbykartographen erstellt werden, bedeutet aller-dings auch, dass ein OSM-Datensatz nicht unbedingt vollstandig sein muss, beziehungs-weise Details fehlen konnen, die fur ein Routing benotigt wurden. Dies kann der Fallsein, wenn man eine Route von einem Startpunkt, von dem nur die Adresse bekannt ist,aus sucht, diese Adresse aber nicht in den OSM-Daten verzeichnet ist. Im Normalfallsollte allerdings die Postleitzahl und der Straßenname ausreichen, um einen Start- oderEndpunkt fest zu legen.

2.2 Das Simple-Feature-Modell

2.2.1 Geometrieschema

Das Modell, in dem die OSM-Daten vorliegen, ist das Simple-Feature-Modell3. In die-sem werden Datentypen und raumliche Operationen fur zweidimensionale Geometriendefiniert[Bri08]. Die Geometrien sind deswegen simpel, da ihre Stutzpunkte nur gradli-nig verbunden sind. Es gibt vier Geometrieformen des Typs Geometry in dem Modell,namlich Punkte, Linien, Flachen und Geometriesammlungen.

Punkte werden durch ein Point-Objekt beschrieben, dem eine Koordinate zugeordnetist, auf deren Werte man mittels getX(), beziehungsweisse getY() zugreifen kann. EinOSM-Node wird so dargestellt.

Linien sind Streckenzuge, die durch eine Folge von Stutzpunkten definiert sind. Mankann auf den Anfangs- und Endpunkt, die Lange und den n-ten Stutzpunkt zugreifen.Durch diese LineStrings werden OSM-Ways und somit unter anderem Straßen in OSMdargestellt.

Flachen werden durch Polygone beschrieben. Ein Polygon besteht aus einem geschlosse-nen außeren Streckenzug und beliebig vielen inneren, die Locher beschreiben. In OSMwerden Polygone durch Relationen dargestellt, zum Beispiel durch das Relationentagarea und mit Verweis auf eine Menge von OSM-Ways, die den Tag outer besitzen, wirdder außere Ring eines Polygons beschrieben.

3ISO 19125


Eine Geometriesammlung ist eine Sammlung verschiedener Geometrien. Man kann beieiner GeometryCollection auf die verschiedenen Geometrien zugreifen und falls alle Geo-metrien vom gleichen Typ sind, kann man eine der Unterklassen MultiPoint, MultiLine-String oder MultiPolygon verwenden.

Abgespeichert werden die Geometrien als well-known Binary (WKB) und konnen furMenschen lesbar gemacht werden als well-known Text (WKT). Beispiele fur WKT sind:POINT(6.2 19.90) oder LINESTRING(1 3, 3 7, 4 2).

2.2.2 Topologische Pradikate und Geometriefunktionen

Topologische Eigenschaften beschreiben die raumliche Beziehung von Geometry-Objektenzueinander. Ob eine Geometrie vollstandig oder nur zum Teil in einer anderen enthaltenist oder diese beruhrt wird, wird mit Hilfe von topologischen Pradikaten ausgeduckt.

• contains(Geometry other) - ist true, wenn die Geometrie other komplett in dieserGeometrie enthalten ist

• crosses(Geometry other) - ist true, wenn die beiden Geometrien eine Schnittmengehaben, aber eine Geometrie nicht komplett in der anderen enthalten ist

• touches(Geometry other) - ist true, wenn die beiden Geometrien sich nur an ihrenRandern schneiden

Weitere geometrische Funktionen einer Geometrie sind:

• Envelope(): Geometry - Ruckgabe ist das minimal umgebende Rechteck der Geo-metrie

• Boundary(): Geometry - zuruck gegeben wird der Rand der Geometrie

• Distance(Geometry other): double - es wird der geringste Abstand zwischen zweiPunkten der Geometrie und other berechnet und zuruck gegeben

• Intersection(Geometry other): Geometry - gibt eine Geometrie zuruck, die die Schnitt-menge der Geometrie und other beschreibt

• Difference(Geometry other): Geometry - gibt eine Geometrie zuruck, die die Geo-metrie ohne die Schnittmenge der Geometrie und other beschreibt


2.3 Graphen

2.3.1 Graphentheorie

Ein Graph besteht aus Knoten, die uber Kanten verbunden sein konnen. Oder formalausgedruckt, ein Graph G ist ein Tupel (V,E), welches aus zwei endlichen Mengen V 6= ∅(Vertices fur die Knoten) und E (Edges fur die Kanten) besteht. Die Kanten in einemgerichteten Graphen sind zweistellige Relationen der Knoten, E ⊆ V × V , zum Beispieldie Kante e=(a, b) verbindet die beiden Knoten a und b. Diese sind die Endpunkte vone. Die Knoten a und b sind damit adjazent und diese Knoten mit e inzident. Der Gradeines Knoten v ist die Anzahl der mit v inzidenten Kanten. Eine Schleife ist eine Kante,die einen Knoten mit sich selbst verbindet. In Abbildung 2.2 ist ein gerichteter Graphdargestellt. Ein Graph heißt dunn besetzt, wenn |E| = Θ(|V|).[Jun94]

a

b

c

d e

Abbildung 2.2: Ein gerichteter Graph

Bei einem gewichteten Graphen werden alle Kanten mit einer Zahl, der Lange dieserKante, gewichtet. Das muss nicht unbedingt der geographische Abstand zwischen zweiKnoten sein, sondern kann auch als Kosten, Zeiten oder Kapazitaten genutzt werdenund darf auch negativ sein.

Ein Weg besteht aus einer Menge von Knoten, die jeweils adjazent sind und ein Pfadist ein spezieller Weg, bei dem kein Knoten doppelt auftreten darf. Ein Zyklus in einemGraph ist ein Weg, in dem ein Knoten Start- und Zielknoten zugleich darstellt. Die Langeeines Weges ist dann die Summe der Gewichte der Kanten des Weges.

Der Abstand d(a,b) der Knoten a und b, oder der kurzeste Weg von a nach b, ist dasMinimum der Langen aller Pfade mit Startpunkt a und Endpunkt b, b ist dann von aaus erreichbar. Falls es keinen Pfad von a nach b gibt, wird d(a,b) angenommen als ∞.Ein Weg, der nur einen Knoten enthalt, hat die triviale Lange 0. In Abbildung 2.3 istder kurzeste Weg vom Knoten e zum Knoten d markiert.

Falls es in dem Graphen einen Zyklus gibt, dessen Lange negativ ist, kann es keinen kur-zesten Weg geben. Zumindest nicht, wenn man einen kurzesten Weg von a nach b suchtund man einen solchen Zyklus von a aus erreichen kann. In den folgenden Betrachtungenseien negative Kantengewichte ausgeschlossen.


a

b

c

d e

4

1

31

2

0.51

Abbildung 2.3: Ein kurzester Weg zwischen zwei Knoten

2.3.2 Der abstrakte Datentyp Graph

Der abstrakte Datentyp, kurz ADT, Graph benutzt die ADTs Vertex und Edge. Diesedienen lediglich dazu die Knoten und Kanten darzustellen und stellen, außer einemKonstruktor, nur Anfrage- und Anderungsmethoden bereit, die fur die Bestimmung deskurzesten Weges hilfreich sind.

Der ADT Edge stellt folgende Methode bereit:

• getId(): String - liefert die OSM-Id dieser Kante

• getWeight(): double - liefert das Gewicht einer Kante

• getLineString(): LineString - gibt den Streckenzug der Kante als Geometrie zuruck

Im ADT Vertex wird vermerkt, welchen Abstand ein Knoten zu einem Startknoten hat,beziehungsweise welcher Abstand bisher geschatzt wurde und welcher Knoten in einemkurzesten Weg sein Vorganger ist:

• getId(): String - liefert die OSM-Id dieses Knotens

• setPred(Vertex v) - setzt den Vorganger von diesem Knoten auf v

• getPred(): Vertex - gibt den Vorganger dieses Knotens zuruck

• setD(double distance) - setzt den Abstand von dem Startknoten zu diesem aufdistance

• getD(): double - gibt den Abstand zum Startknoten zuruck

• getPoint(): Point - gibt die geometrische Lage diese Knotens als Geometrie zuruck

• markAsTarget(): - markiert den Knoten als Ziel einer Wegesuche

• isTarget(): boolean - gibt true zuruck, falls der Knoten ein Zielknoten ist


Der ADT Graph besitzt folgende Methoden. Eine Sequence ist eine verkettete Liste mitIndexzugriff. Ein Großteil der Methoden entstammt [Lip12];

• size(): int - liefert die Anzahl der Knoten dieses Graphen

• vertices(): Sequence - liefert die Knoten dieses Graphen

• insertVertex(Vertex v) - fugt den Knoten v in den Graphen ein

• removeVertex(Vertex v) - entfernt den Knoten v und seine inzidenten Kanten ausdem Graph

• edges(): Sequence - liefert die Kanten dieses Graphen

• insertEdge(Vertex v, Vertex w, Edge e) - fugt die gerichtete Kante e zwischen denKnoten v und w ein

• removeEdge(Edge e) - entfernt die Kante e aus dem Graphen

• inDegree(Vertex v): int - liefert die Anzahl der eingehenden Kanten von v

• inIncidentEdges(Vertex v): Sequence - liefert die eingehenden Kanten vom Knotenv

• inAdjacentVertices(Vertex v): Sequence - liefert die Knoten, die uber eine einge-hende Kante zum Knoten v adjazent sind

• areAdjacent(Vertex v, Vertex w): boolean - gibt true zuruck, falls v uber eine Kantemit w verbunden ist

• origin(Edge e): Vertex - liefert den Knoten, von dem die Kante e ausgeht

• destination(Edge e): Vertex - liefert den Knoten, wohin die Kante e fuhrt

• findEdge(Vertex v, Vertex w): Edge - liefert die Kante, uber die die Knoten v undw verbunden sind

• getVertexWithId(String id): Vertex - liefert die Knoten mit der ubergebenen id,sofern vorhanden

• containsVertexWithId(String id): boolean - liefert true, falls ein Knoten mit derdieser id im Graphen existiert

Die Methoden outDegree(), outIncidentEdges() und outAdjacentVertices() werden ana-log definiert. Die Methode findEdge() hat fur beliebige Graphen eine Laufzeit von O(|E|).Da ein Straßennetz in der Regel dunn besetzt ist, Knoten hochstens den Grad 4 habenund ein- und ausgehende Kanten eines Knoten mit Indizenzlisten fur jeden Knoten fest-gehalten werden konnen, betragt die Laufzeit in diesem Fall O(1).


2.4 Kurzeste-Wege-Algorithmen

Man unterscheidet zwischen einer kurzesten Wegfindung von einem Startknoten ausund zwischen allen Knoten. Manche Algorithmen kann man abbrechen, falls man einenkurzesten Weg zu einem gesuchten Zielknoten gefunden hat.

Die Initalisierung ist bei allen Algorithmen gleich. Man benotigt einen Graph G undeinen Startknoten, Vertex s, siehe Algorithmus 1. Dieser ist aus [CLRS10] entnommen,wie auch die Algorithmen 2 und 3. Die Distanz zum Startknoten wird fur alle Knoten auf

Algorithm 1

1: procedure Init-Single-Source(Graph G, Vertex s)2: for all Vertex v ∈ G.vertices() do3: v.setD(∞);4: v.setPred(NULL);5: end for6: s.setD(0);7: end procedure

den maximal zulassigen Wert gesetzt, bis auf die triviale Distanz vom Startknoten s zu sauf 0. Da jeder Knoten so initalisiert wird, hat die Methode die Laufzeit O(|V|). Wird dieRoutensuche nur einmal auf einen Graphen angewandt, kann schon bei der Initalisierungder Knoten die Distanz auf ∞ gesetzt werden, wodurch die Laufzeit konstant ware.

Die folgenden Algorithmen berechnen alle kurzesten Wege von einem Knoten zu prinzi-piell allen anderen.

2.4.1 Der Bellman-Ford-Algorithmus

Der Bellman-Ford-Algorithmus wurde auch ein Ergebnis bei negativen Kanten liefern,hat aber eine Laufzeit von O(|E||V |). Er wird im Algorithmus 2 beschrieben. Da esnur positve Kanten gibt, wird auf die Darstellung des Programmcodes, der pruft, obder Graph einen Zyklus mit negativer Lange enthalt, verzichtet. Die Zeilen 6-9 sindbei allen Algorithmen ahnlich und beschreiben die Relaxation einer Kante. Dabei wirdgepruft, ob sich der geschatzte Abstand vom Startpunkt zum Endknoten einer Kanteverringert, falls man diese Kante in den kurzesten Weg mit aufnehmen wurde. Wenndies der Fall ist, wird der neue Schatzwert vermerkt und der Startknoten der Kante wirdzu dem Vorganger des Endknotens in diesem geschatzten kurzesten Weg. Dies wird furalle Kanten |V|-1 mal gemacht

Der Algorithmus arbeitet korrekt, falls der Graph keinen Zyklus mit negativer Langeenthalt. Denn dann kann ein kurzester Weg hochstens aus |V|-1 Kanten bestehen, da


Algorithm 2

1: procedure Bellman-Ford(Graph G, Vertex s)2: Init-Single-Source(G,s);3: int newDist=0;4: for i=1 to G.size()-1 do5: for all Edge e ∈ G.edges() do6: newDist=G.origin(e).getD()+e.getWeight();7: if G.destination(e).getD()>newDist then8: G.destination(e).setD(newDist);9: G.destination(e).setPred(G.origin(e));10: end if11: end for12: end for13: end procedure

ein Zyklus mit positiver Lange einen Weg nur verlangert. Wenn es einen kurzesten Wegvon s zu einem Knoten gibt, dann kann man diesen erhalten, indem man die Kanten inder Reihenfolge dieses Weges sukzessiv relaxiert. Pro außeren Schleifendurchlauf, werdenalle Kanten relaxiert. Da dies |V|-1 mal passiert, relaxiert man unter anderem auch dieKanten eines kurzesten Weges mit |V|-1 Kanten. Daher die Laufzeit O(|E||V|).

2.4.2 Der Dijkstra-Algorithmus

Djikstras Algorithmus, der Algorithmus 3, kann nur auf einen Graphen mit positivenKantengewichten ausgefuhrt werden, lauft dafur aber auch schneller, bei geeigneter Im-plementierung der PriorityQueue Q, in O((|V|+|E|)log|V|). Die Idee hinter Djkstras Al-gorithmus ist, dass in einer Menge von Knoten, der cloud, vermerkt wird zu welchenKnoten kurzeste Wege schon bekannt sind. Dies wird erreicht, in dem der Knoten mitder kurzesten Lange zur cloud in eben diese aufgenommen wird, siehe die Zeilen 8 und 9.Dann werden alle Kanten, die von diesem Knoten ausgehen, relaxiert. Das funktioniert,da es nur positive Kantengewichte gibt und so ein aktuelles Minimum einer Distanz zurcloud nicht nachtraglich unterschritten werden kann. Insgesammt wird jede Kante nurgenau einmal relaxiert.

In Q werden die noch nicht in die cloud aufgenommenen Knoten nach ihrer bisher be-rechneten Lange des kurzesten Weges aufsteigend geordnet. Dabei muss ein Knoten nacheiner erfolgreichen Relaxation einer eingehenden Kante eventuell neu positioniert wer-den, siehe Zeile 15 replaceKeyAt(). Q.poll() gibt den Knoten mit kleinster Distanz zuruckund loscht diesen aus Q. Die Implementierung dieser Methoden, beeinflusst die Laufzeitdes Dijkstra-Algorithmus. Wird die Priorityqueue mit einem Min-Heap realisiert, erhaltman eine Laufzeit von O(|E|log|V|). Ein Knoten mit der geringsten Distanz zur cloud,


Algorithm 3

1: procedure Dijkstra(Graph G, Vertex s)2: Init-Single-Source(G,s);3: int newDist=0;4: Vertex u=NULL;5: Set cloud=∅;6: PriorityQueue Q=G.vertices(); . Der Schlussel ist getD()7: while Q 6= ∅ do8: u=Q.poll();9: cloud.add(u);10: for all Vertex v ∈ G.outAdjacentVertices(u) do11: newDist=u.getD()+G.findEdge(u,v).getWeight();12: if v.getD()>newDist then13: v.setD(newDist);14: v.setPred(u);15: Q.replaceKeyAt(v, newDist);16: end if17: end for18: end while19: end procedure

also der Aufruf Q.poll(), wird maximal |V|-mal aus Q benotigt. Die Umstrukturierungnach dem Entfernen des Minimums lauft, bei maximal |V| Knoten im Heap, in einerLaufzeit von O(log|V|), also insgesammt O(|V|log|V|). Die nach der Relaxation notigeUmstrukturierung des Heaps, kann in O(log|V|) geschehen, durch schrittweises Vertau-schen des betreffenden Heapknotens mit seinen Elternknoten, bis die Heapeigenschaftwieder erfullt ist4. Da dies hochstens |E|-mal passieren kann ergibt sich eine Laufzeit vonO(|E|log|V|). Die Laufzeiten von replaceKeyAt() und Q.poll() ergeben also insgesammtO((|V|+|E|)log|V|).

Falls man die Route zu einem bestimmten Zielknoten sucht, kann der Algorithmus abge-brochen werden, wenn der Zielknoten in die cloud aufgenommen wurde oder man nichtalle Knoten erreichen kann und sich in Q nur noch Knoten mit einer unendlichen Distanzzum Startknoten befinden.

4Da die Java-Implementierung der PriorityQueue die replaceKeyAt()-Methde nicht anbietet, wirdder Knoten aus dem Heap entfernt und neu einsortiert. Durch das Entfernen eines Nicht-Wurzel-Knotensverschlechtert sich die Laufzeit auf O(|V|)


2.4.3 Der A*-Algorithmus

Die bisher vorgestellten Algorithmen bedienen sich nur Eigenschaften eines abstraktenGraphen. Sind zusatzlich noch andere Informationen bekannt, wie zum Beispiel die geo-graphische Lage der Knoten, lasst sich eine Heuristik bestimmen, mit deren Hilfe mangezielter nach einem kurzesten Weg suchen lassen kann. Im Falle des A*-Algorithmus,siehe Algorithmus 4, wird es vermieden, Kanten zu relaxieren, die wahrscheinlich nichtzu dem kurzesten Weg gehoren. Dazu mussen aber auch eine Menge von Zielknoten Tbekannt sein.

Um zu entscheiden, welche Kante als nachstes relaxiert wird, wird eine Schatzfunktion fbenutzt,[HNR68]. Die Lange des kurzesten Weges von einem Start- zu einem Zielpunktuber einen Knoten n wird beschrieben durch f(n) = g(n) + h(n). g(n) ist die Lange deskurzesten Weges zum Knoten n, wahrend h(n) die Lange des kurzesten Weges von nzum Zielpunkt bestimmt, beziehungsweise zu einem Zielpunkt t ∈ T , zum Beispiel zumWeitentferntesten vom Startpunkt aus. Die Schatzfunktion fur die Lange eines kurzestenWeges ist dann f(n) = g(n) + h(n). g(n) ist eine Schatzung der Lange des Wegeszum Knoten n, h(n) dementsprechend analog. Fur g(n) kann also die Lange des bisherberechneten kurzesten Weges genutzt werden. Wird h fur alle Knoten auf 0 gesetzt,erhalt man dadurch Dijkstra’s Algorithmus und es gilt sogar f(n) = f(n), da durch dieAufnahme des Knotens mit dem kurzesten Abstand zur cloud, g(n) = g(n) gilt.

h(n) darf die wirkliche Lange nicht uberschatzen, dann bestimmt der Algorithmus auchden kurzesten Weg. Eine mogliche Schatzung fur die Lange des Restwegs ist der Luft-linienabstand, da kein Weg kurzer sein kann, als der direkte. Die Schatzfunktion h istkonsistent, genau dann wenn fur jeden Knoten n und jeden seiner Nachfolger m die Drei-ecksungleichung h(n,m)+ h(m) ≥ h(n) gilt, wobei h(n,m) die wirkliche Lange zwischenn und m ist. Die Luftlinie ist eine konsistente Schatzfunktion, da die Dreiecksunglei-chung der euklidischen Distanz in der Ebene gilt. Die Berechnung der Schatzfunktionunter Verwendung des euklidischen Abstandes fur einen Knoten v sahe folgendermaßenaus, wobei t ein Point sei, der die geographische Lage des Zielpunktes besitzt und tx furdie X-Koordinate von t steht.

f(v) = v.getD() +√

(vx − tx)2 + (vy − ty)2

Der Algorithmus 4 zeigt den allgemeinen Fall, in dem h(n) nicht konsistent ist. Es wer-den wie bei Dijkstra zwei Mengen von Knoten benutzt, die zwar disjunkt sind, abervereinigt nicht die Menge aller Knoten ergeben mussen. Es wird eine PriorityQueue, hieropen, benutzt, um zu ermitteln welcher Knoten als nachstes in die Liste closed kommt.Der Schlussel, nach dem die Priorityqueue sortiert ist, ist der Wert von f fur den je-weiligen Knoten. Sobald ein Weg zum Startknoten bekannt ist, wird der Knoten inopenaufgenommen, Zeile 14 f. Wenn der geschatzte kurzeste Weg zu einem Knoten bekanntist, wird er in closed aufgenommen. Falls der Knoten zu T gehort, kann der Algorithmusabgebrochen werden. Wenn ein Knoten in closed aufgenommen wird, werden alle aus-


Algorithm 4

1: procedure A*(Graph G, Vertex s)2: Init-Single-Source(G, s);3: int newDist=0;4: Vertex u=NULL;5: Sequence closed=∅; . Hier ist der Schlussel f(n), Pendant zu Dijkstra’s cloud6: PriorityQueue open.add(s); . enhalt Knoten, zu denen ein Weg bekannt ist7: while open 6= ∅ do8: u=open.poll();9: closed.add(u);10: if u.isTarget() then11: break12: end if13: for all Vertex v ∈ G.outAdjacentVertices(u) do14: if v /∈ closed ∧ v /∈ open then15: open.add(v);16: end if17: newDist=u.getD()+G.findEdge(u,v).getWeight();18: if v.getD()>newDist then19: v.setD(newDist);20: v.setPred(u);21: if v ∈ closed then22: closed.remove(v);23: open.add(v)24: else25: open.replaceKeyAt(v, f(v));26: end if27: end if28: end for29: end while30: end procedure


gehenden Kanten relaxiert. Ist h konsistent, dann entspricht die Laufzeit im worst-caseder des Dijkstra Algorithmus. Denn dann wird kein Knoten mehr nachtraglich aus closedentfernt, beziehungsweise muss die Schatzung fur die Lange des kurzesten Weges nichtmehr nachtraglich korrgiert werden. Ist h(n) konsistent, kann Dijkstras Algorithmusubernommen werden, nur der Schlussel, der zum Einordnen in die PriorityQueue benutztwird, muss f(n) sein.[Bri08] Aber unter Anwendung der gleichen Heuristik, relaxiertkein Algorithmus weniger Kanten als der A*-Algorithmus, bis er mit einer geeignetenHeuristik einen Zielknoten gefunden hat.

2.5 Schlussfolgerung

Die OSM-Daten sind schon als Graph organisiert, weshalb es nicht schwer ist, aus dieseneinen Graphen aufzubauen. Die OSM-Nodes werden zu Knoten in dem Graphen unddie Kanten entstehen aus den Teilabschnitten der Ways, die zwei Nodes verbinden. Daes Einbahnstraßen gibt, bietet sich ein gerichteter Graph an. Gewichtete Kanten wer-den vorausgesetzt, bleibt also nur noch die Frage offen, wie man die Kanten gewichtet.Zusatzlich zu der Lange des Weges, den eine Kante darstellt, konnten auch andere Fak-toren, wie die Art der Straße, das Gewicht einer Kante bestimmen. Die vorgestelltenAlgorithmen bestimmen kurzeste Wege von einem Knoten zu allen anderen. Das wirdnicht notig sein und der Dijkstra- und A*Algorithmus konnen abgebrochen werden, wennein kurzester Weg zum Zielknoten gefunden oder ein Zielknoten aus einer Menge vonKnoten erreicht wurde. Dies ist beim Bellman-Ford-Algorithmus nicht der Fall, daherwird auf die Implementierung verzichtet, da er die gleiche kurzeste Route wie Dijkstraliefert. Der A*-Algorithmus ist der einzige Algorithmus, der die geographische Lage derKnoten beachtet, dadurch wird er durch das zielgerichtete Suchen wahrscheinlich amSchnellsten ein Ergebnis liefern.

Kapitel 3

Konzepte

In diesem Kapitel wird der Ablauf der partitionierten Routenberechnung erlautert. Dazugehort zunachst das Laden von Graphpartitionen, dann wird auf diesen die Wegesucheausgefuhrt und anschließend werden die Routen der einzelnen Partitionen zusammenge-fuhrt.

3.1 Partitionierungsarten

Bevor die Routensuche beginnen kann, mussen die geographischen Daten partitioniertwerden. Es werden nun zwei Arten der Partitionierung vorgestellt.

Die Straßendaten werden partitioniert, indem sie in Gitterzellen zerlegt werden. DieseGitterzellen sind alle gleich breit und gleich lang und sind luckenlos aneinander gereiht.Die geometrischen Daten in Punktform sind so disjunkt aufgeteilt. Bei Linienzugen wirddurch sogenanntes Clipping der Teil, der außerhalb einer Gitterzelle liegt, abgeschnitten,so dass auch die Straßen disjunkt aufgeteilt sind. Einzig die Knoten auf dem Gitter sind inden jeweiligen Graphen mehrmals vorhanden. Im Folgenden unterscheiden wir zwischenPartitionierungsarten, die abhanig oder unabhangig von der gesuchten Route sind. Eineunabhangige Partitionierung kann fur verschiedene Routensuchen genutzt werden, nurdie Wahl der relevanten Partitionen ware unterschiedlich.

Ein Beispiel fur eine unabhangige Partitionierung ist in Abbildung 3.1(a) dargestellt.Die Gitterlinien sind horizontal und vertikal angeordnet. Alle geographischen Daten lie-gen innerhalb der schwarzen Umrandung. Zusatzlich ist ein Weg von einem Punkt s zueinem Punkt t eingezeichnet. In 3.1(b) ist eine abhangige Partitionierung dargestellt.Die Gitterlinien sind parallel und orthogonal zur Luftlinie zwischen Start- und End-punkt ausgerichtet. Der Start- und Endpunkt befinden sich im Zentrum einer Partition.

19

KAPITEL 3. KONZEPTE 20

s

t

(a) Eine unabhangige Partitionierung

s

t

(b) Eine abhangige Partitionierung

Abbildung 3.1: Zwei Partitionierungsarten

Dadurch soll verhindert werden, dass Straßen nicht vollends berucksichtigt werden kon-nen, falls bei der unabhangigen Partitionierung der Start- oder Endpunkt der gesuchtenRoute am Rand zu einer nicht weiter betrachteten Partition liegt. Das soll die Wahr-scheinlichkeit erhohen, dass Straßen, die zu dem optimalen kurzesten Weg gehoren, nichtan einem Rand abgeschnitten werden und nicht weiter untersucht werden konnen. Durchdie Ausrichtung entlang der Luftlinie, kann sich die Anzahl der relevanten Partitionenverringern, vergleiche Abbildung 3.1. Wir nehmen an, dass eine Vorgabe existiert, wiebreit und wie lang eine Gitterzelle sein soll.

Das abhangige Gitter soll also in zwei Kriterien von der gesuchten Route abghangig sein.

• Start- und Zielpunkt sollen mittig in ihrer Partition liegen

• Die Gitterlinien sollen parallel, beziehungsweise orthogonal zur Luftlinie ausgerich-tet sein.

Anders als bei der unabhangien Partitionierung muss die vorgegebene Breite oder Hohe,die eine Partitionsgitterzelle besitzen soll, wahrscheinlich noch angepasst werden, damitdie Partitionierung dem ersten Kriterium gerecht wird. Die Vorgaben der Lange undHohe werden dabei als Mindestlange und -hohe interpretiert und werden gegebenenfallsnoch angepasst. Um das zweite Kriterium zu erfullen, mussen nun die Partitionen inRichtung der Luftlinie vom Startpunkt aus rotiert werden.


Beispiel zur Erstellung einer abhangigen Partitionierung

Gegeben sei der Startpunkt s bei (0,0) und ein Endpunkt t bei (2.5,5). Die Hohe undBreite einer Gitterpartition soll 1 betragen. Eine unabhangige Partitionierung sahe wieim Bild von Abbildung 3.2(a) aus.

Um aus ihr eine abhangige Partitionierung zu machen, wird zuerst beispielsweise dieHohe einer Partition neu angepasst. Der Abstand zwischen s und t betragt 5,59. Dasbedeutet, dass bei der Hohe von 1 nach sechs Partitionen der Zielpunkt erreicht wird.Damit beide Punkte jeweils mittig liegen, wird der Nachkommateil der Differenz auf diePartitionshohe von funf Partitionen aufgeteilt. Das macht 1+(0,59/5) also etwa 1,18.Nachdem man das Gitter um die Halfte der neuen Hohe und der Breite verschoben hat,erhalt man eine Partitionierung, wie sie im Bild 3.2(b) dargestellt ist.

Nun muss noch das gesammte Gitter um den Winkel, der zwischen der Y-Achse undder Luftlinie liegt, im Startpunkt gedreht werden, in diesem Beispiel sind das 26,565◦. Indiesem Beispiel wurde die Y-Achse genommen, da der Startpunkt im Ursprung liegt undso um den kleinsten Winkel gedreht werden konnte. Die fertige abhangige Partitionierungist in Bild 3.2(c) zu sehen.

s

t

(a) Erster Schritt

s

t

(b) Zweiter Schritt

s

t

(c) Dritter Schritt

Abbildung 3.2: Beispiel zur Erstellung einer abhangigen Partitionierung

3.2 Ablauf der partitionierten Routenberechnung

Ziel einer partitionierten Routenberechnung ist es, den kurzesten Weg von einem Start-punkt in einer Partition zu einem Endpunkt in einer anderen Partition uber beliebigviele Partitionen zu finden. Es ergibt sich grob der folgende Programmablauf aus Algo-rithmus 5.


Algorithm 5

1: procedure PartitionStreetRouting()2: Erstelle Partitionen und3: Bestimme Start- und Zielpartition . benotigt Start- und Zielpunkt4: Beginne in der Startpartition5: while aktuelle Partition ist nicht die Zielpartition do6: Baue den Graph auf . benotigt Partitionspolygon7: Ermittle den Rand, zu dem geroutet werden soll8: Markiere den oder die Zielknoten nach gewahlter Heuristik9: Suche einen Weg vom aktuellen Startknoten aus10: if Kein weiterer Rand erreichbar then . siehe Algorithmus 711: Breche Routensuche komplett ab12: end if13: Setze neuen Startknoten auf Zielknoten dieser Route14: Verarbeite das Routingergebnis15: Verwerfe den Graphen16: Wechsel in die nachste Partition17: end while18: Baue Graph auf und markiere Zielknoten19: Finde Route zum Endpunkt20: Gib das Ergebnis der Gesamroute zuruck21: end procedure


Ein Graph wird dabei fur eine Partition hochstens ein Mal aufgebaut, man kann al-so nicht zweimal die gleiche Partition untersuchen. In den nachfolgenden Abschnittenwerden ein Großteil der Zeilen erlautert. In Abschnitt 3.2 werden zwei Partitionierungs-arten vorgestellt. Die while-Schleife und was genau mit Heuristik gemeint ist, wird inAbschnitt 3.3 geklart.

3.3 Routensuche

Nachdem die Art der Partitionierung gewahlt wurde, kann man mit der Routensuchein der Partition mit dem Startpunkt beginnen.Die nachfolgenden Abschnitten beziehensich auf die Schleife in Algorithmus 6.

Der Zwischenzielpunkt der Routensuche in einer Partition ist ein Randpunkt zu eineranderen Partition. Dieser Rand wird vor jeder Routensuche durch die geringste Distanzeines Randes zum Zielpunkt bestimmt.

3.3.1 Heuristiken zur Findung von Zielknoten

Zu Beginn der Routensuche in einer Partition hat man genau einen Startknoten. Das istentweder der Startpunkt der gesuchten Route in der ersten Partition oder ein Knoten,der die gleiche geographische Lage besitzt, wie der Zielknoten, der in der vorherigenPartition berechnet wurde. Den Zielknoten auf dem Zielrand einer Partition kann manuber folgende Heuristiken bestimmen.

a) Kurzeste Distanz zum Start: Der Randknoten mit dem berechneten kurzesten Wegzum Startpunkt wird ausgewahlt

b) Kurzeste Distanz zum Ziel: Der Randknoten mit dem geschatztesten geringstenAbstand zum Zielpunkt wird ausgewahlt

c) Gewichtung der Straßenart: Ein Randknoten einer Autobahn wird dem einer Land-straße vorgezogen

Wird die Heuristik a) gewahlt, hat man eine Menge von Zielknoten, namlich alle die aufdem Rand zur nachsten relevanten Partition liegen.

Verwendet man b), kann man vor dem Starten der Routensuche den Knoten auf demZielrand berechnen, der den geringsten Abstand zum Zielknoten der gesamten Routebesitzt, und nur diesen als Ziel markieren. Man sollte jedoch sicher stellen, dass dieserKnoten auch erreichbar ist und man nicht die Spur einer Autobahn wahlt, die in die


Partition hineinfuhrt. Denn dann kann dieser Zielknoten nicht erreicht werden und eswerden solange Kanten relaxiert, bis zu allen erreichbaren Knoten ein kurzester Wegbestimmt worden ist. Jedoch kann man dies nicht nur uber das Ausschließen von be-stimmten Einbahnstraßen losen und diese Gefahr besteht immer bei einer ungeschicktenPartitionierung.

Die Heuristik c), die die Art der Straße berucksichtigt, muss entweder mit a) oder b)kombiniert werden. Im Falle von a) werden zum Beispiel nur Autobahnknoten und vonb) nur der Autobahnknoten mit dem geringsten Abstand zum Ziel markiert.

3.3.2 Metriken zur Gewichtung der Kanten

Zur Gewichtung der Kanten haben wir zwei verschiedene Metriken gewahlt.

i) Die kurzeste Route: Das Maß ist die Lange des LineStrings einer Kante

ii) Die schnellste Route: Das Maß ist die Lange des LineStrings ÷ Durchschnittsge-schwindigkeit, bestimmt durch die Art der Straße

In der Tabelle 3.1 sind die highwaytags, ihre Bedeutung und die Wahl der Durchschnitts-geschwindigkeit dieser Straßenart in der Reihenfolge notiert, in der sie von der Heuristikc) bevorzugt werden. Die Geschwindigkeiten entsprechen denen von OpenRouteService1,ein Webservice, das eine Routensuche mit OSM-Daten anbietet.

3.3.3 Vorgehen beim Misserfolg

Stellt man wahrend des Routings fest, dass man in einer Partition nicht den Zielknotenoder Zielgrenzknoten erreichen kann, muss die Auswahl des Zielrandes korrigiert werden.Wir gehen aber davon aus, dass man die Partitionen so groß wahlt und das Straßennetzvon Deutschland so ausgebaut ist, dass man von einem Rand einen Weg zu jedem an-deren Rand finden kann. Erreicht man trotzdem keine anderen Randknoten, weil manzum Beispiel durch eine ungeschickte Partitionierung auf einer Halbinsel angekommenist, wird die Routensuche ohne Ergebnis abgebrochen. Auch falls man bereits in derEndpartition angelangt ist und man den Zielpunkt nicht erreichen kann, wird abgebro-chen, da kein Partitionsgraph mehrfach berechnet werden soll. Dieses Vorgehen ist imAlgorithmus 6 dargestellt.

Das Rand erreichbar aus Zeile 7 soll einerseits ausdrucken, dass es einen Knoten auf die-sem Rand gibt, der bei der Routensuche erreicht wurde, als auch dass man die Partition

1http://www.openrouteservice.org

http://www.openrouteservice.org


Highway-Tag Bedeutung Ø Geschwindigkeit (km/h)

motorway Autobahn 110motorway link Autobahnauffahrt 90

trunk Kraftfahrstraße 90trunk link Kraftfahrstraßenauffahrt 70primary Bundesstraße 70

primary link Bundesstraßenauffahrt 60secondary Landesstraße 60tertiary Kreisstraße 55

unclassified Nebenstraße 50residential Straße in einem Wohngebiet 40

service Zugangsweg 30living street Wohn- oder Spielstraße 10

track Feld- oder Waldweg 10

Tabelle 3.1: Die Straßenarten und ihre Gewichtungen

noch untersuchen darf. Wurde der Zielrand nicht erreicht gibt es somit nur noch zweimogliche Rander, da man auch nicht mehr die Partition untersuchen kann, aus der manin diese Partition gelangt ist.


Algorithm 6

1: function Kein weiterer Rand erreichbar()2: if mindestens ein Knoten auf dem Zielrand erreichbar then3: Bestimme Zielknoten4: return false;5: else6: for all Rander dieser Partition do . sortiert nach Entfernung zum Ziel7: if Rand erreichbar then8: Bestimme Zielknoten9: return false;10: end if11: end for12: Bestimme Teilergebnis der Routensuche13: return true; . Suche muss endgultig abgebrochen werden14: end if15: end function

3.4 Komposition der Routen

Die Ergebnisse der Routensuche in einer Partition bestehen aus dem berechneten Wegund dem Gewicht dieses Kantenzugs. Um Speicherplatz zu sparen wird lediglich derLineString gespeichert, der aus den Kanten des kurzesten Weges bestimmt wird, sowiedas Gewicht. Dadurch gehen zwar Informationen verloren, die in dieser Arbeit aberauch keine Rolle spielen, wie eine detailierte Beschreibung des Weges, beispielsweise”nach zwanzig Kilometern auf der A2, rechts abbiegen“. Die Gewichte der einzelnenPartitionen auf dem Gesamtweg werden aufsummiert und die Linestring-Geometrienvereinigt.

Kapitel 4

Implementierung

Dieses Kapitel beschaftigt sich mit der Implementierung des Graphaufbaus, verschiede-nen Implementierungsdetails, einer Beschreibung der Klassen und einer Beschreibungder Benutzerschnittstelle.

4.1 Anforderungen

Das Programm soll einen Weg durch verschiedene Partitionen berechnen konnen. Dabeisollen die Faktoren Partitionsgroße, Metrik zur Gewichtung der Kanten, Heuristik zurAuswahl der Randknoten und Wahl des Kurzeste-Wege-Algorithmus, entweder Dijkstraoder A*, beliebig kombinierbar sein. Da das alleinige Gesamtgewicht der Route wenigAussagekraft hat, soll die Route noch visuell dargestellt werden konnen. Dies geschiehtdurch die Umsetzung als PlugIn fur das Open-Source-Programm OpenJUMP1. Der Be-nutzer soll Ziel- und Endpunkt entweder als WGS84-Koordinaten oder als Adressenangeben konnen. Da die Straßendaten partitioniert werden sollen, um den Arbeitsspei-cher zu entlasten, sollte der Speicherplatz des Graphen, der in einer Partition berechnetwurde, wieder freigegeben werden, wenn man eine andere Partition betrachtet.

4.2 OpenJUMP und seine Schnittstelle

OpenJUMP ist ein Open-Source-Programm, das in Java geschrieben ist und unter derGNU-Lizenz steht. Es ist ein geographisches Informationssystem und bietet die Anzei-ge und Bearbeitung von Geometrien. Die Geometrien konnen zum Beispiel aus einer

1http://www.openjump.org/

27

http://www.openjump.org/

KAPITEL 4. IMPLEMENTIERUNG 28

PostGIS-Datenbank geladen und in Features, die aus einer Geometrie und beliebig vie-len anderen Attributen bestehen, uberfuhrt werden. Die Geometrien werden mit Da-tentypen von der Java Topology Suite, kurz JTS, dargestellt, ein Framework, das dasSimple Feature Format unterstutzt. Diese Features konnen in der Workbench dargestelltwerden, dem Arbeitsbereich in OpenJUMP. Die Features befinden sich in Layern, diein ihrer Darstellung in Farbe, Transparenz oder Linienbreite angepasst werden konnen.Außer Geometrien, konnen auch Bilder dargestellt werden und auch Karten, zum Bei-spiel mittels einem sogenannten Web-Map-Service, kurz WMS. In Abbildung 4.1 ist dieOberflache mit einem Ausschnitt eines WMS-Layers von Deutschland dargestellt.

Abbildung 4.1: Die OpenJump-Oberflache

OpenJUMP unterstutzt das PlugIn Framework. Damit OpenJUMP ein PlugIn benut-zen kann, muss es sich entweder im Extension-Ordner, der von OpenJUMP spezifiziertwird, befinden oder man teilt OpenJUMP uber eine workbench-property.xml -Datei mit,an welchem Ort im Dateisystem sich ein zu ladenes PlugIn befindet. Ein PlugIn be-kommt dann ein PluginContext ubergeben, uber das es auf die Workbench zugreifenund neue Layer oder Menupunkte anlegen kann. Das Programm wird also als PlugIn furOpenJUMP realisiert.


Abbildung 4.2: Das Einstellungsfenster

4.3 Beschreibung der Benutzerschnittstelle

Wurde das PlugIn in OpenJUMP geladen, erscheint ein Menue-Punkt, der PRS lautet.Betatigt man diesen kann man das Partitionierte Routensuche-PlugIn auswahlen. Eserscheint ein Fenster in dem man verschiedene Einstellungen bezuglich der Routensuchetreffen kann. In Abbildung 4.2 ist dieses Fenster zu sehen. Man kann zwischen folgendenEinstellungen wahlen.

Start/Ziel Es kann gewahlt werden zwischen der Eingabe des Start- und Zielpunktesals Adresse, bestehend aus Postleitzahl und Straßenname oder als Koordinaten imdezimalen Gradsystem. In das jeweils linke Textfeld wird die Postleitzahl oder derBreitengrad angegeben.

Routingalgorithmus Man kann zwischen Dijkstra und A* als Algorithmus fur dieRoutensuche wahlen.

Heuristik Es kann zwischen den vier Heuristiken eine ausgewahlt werden, die der kur-zesten Distanz zum Startknoten, zum Zielknoten oder jeweils unter Berucksichti-


gung der Straßenart.

Metrik Hier muss man die Entscheidung treffen, ob man die kurzeste oder die schnellsteRoute suchen mochte.

Partitionierung In diesem Bereich mussen die Hohe und die Breite einer Gitterzelle ge-setzt werden. Wird als Einteilung ausgewahlt, wird die Flache Deutschlands in einGitter der Form Breite mal Hohe aufgeteilt. Wird in km gewahlt werden die Anga-ben im Textfeld als Breite- und Langeangaben einer Partition in km interpretiert.Zudem kann zwischen einer abhangigen und einer unabhangigen Partitionierunggewahlt werden.

Damit die Verbindung zu einer PostGIS-Datenbank hergestellt werden kann, muss sichim OpenJUMP-Ordner einer Datei namens db.con befinden. In ihr mussen folgendeVerbindungseinstellungen befinden, wobei es nicht auf die Reihenfolge ankommt: Host,Port, Datenbank, Benutzer, Passwort.

host:<Host>

port:<Port>

database:<Datenbank>

user:<Benutzer>

password:<Passwort>

Bestatigt man die Eingabe, wierden die Partitionen aufgebaut. Liegen bei der abhan-gigen Partitionierung die eingegebenen Punkte zu nah beieinander, sodass nicht beidemittig in einer Partition liegen konnen, wird der Benutzer aufgefordert die Partitions-großen anzupassen. Ansonsten beginnt die Routensuche und es werden erst die Start-und Zielpunkte angezeigt. Fur jede Partition erscheint das Partitionspolygon und nachdem Aufbau des Graphen und der Routensuche wird der Ergebnis-LineString dargestellt.Dahinter wird ein WMS-Layer aus OSM-Daten2 angezeigt.

Am Ende erscheint ein Fenster, in dem die Lange des kurzesten Weges oder die Informati-on, dass abgebrochen werden musste, steht. Nach der Berechnung einer Route kann mandas PlugIn erneut starten und die neue Route wird gezeichnet, wahrend die bisherigeRoute in der Workbench verbleibt. Man kann die Berechnung des PlugIns auch abbre-chen, allerdings sollte dann vor einem erneuten Durchlauf, OpenJUMP neu gestartetwerden.

2http://ows.terrestris.de/dienste.html#openstreetmap-deutschland

http://ows.terrestris.de/dienste.html#openstreetmap-deutschland


4.4 Finden von Koordinaten uber Adressangabe

Da sowieso nicht alle Straßennummern in den OSM-Daten verzeichnet sind, werdenKoordinaten nur uber eine Postleitzahl und eine Straße gesucht.

Es gibt zwei Modellierungsmoglichkeiten fur Postleitzahlen. Entweder werden OSM-Nodes mit Schlussel-Wert-Paaren der Form addr:postcode und addr:street angelegt oderes gibt Polygone, die uber eine Relation mit einer Postleitzahl verknupft sind.

Diese Polygone sind weit verbreitet, decken aber nicht ganz Deutschland ab. Es wirdzuerst gepruft, ob es ein passendes Polygon zu der gegebenen Postleitzahl gibt. Fallskein Polygon existiert werden alle Edges und Nodes aus den OSM-Daten uberpruft, ob sieeinen Tag-key besitzten mit addr:postcode und der value gleich der gesuchten Postleitzahlist. Um diese Geometrien wird eine BoundingBox gelegt und als Polygonersatz genutzt.

Wurde ein Polygon oder eine BoundingBox gefunden, wird in dieser Geometrie nachder Straße mit dem angegebenen Straßennamen gesucht und die Node Id und Point-Geometrie, eines Knotens zuruckgegeben. Dies fuhrt die Funktion getNodeIdForAdress(text,text)aus, die im Anhang B.2 zu finden ist.

4.5 Umgang mit den WGS84-Koordinaten

Die OSM-Daten liegen in zweidimensionalen Koordinaten bezogen auf den WGS84-Referenzellipsoiden in dezimaler Schreibweise vor. Das bedeutet unter anderem, dass dieEntfernung zwischen zwei beliebigen Koordinaten nicht uber den euklidischen Abstandder Ebene bestimmt werden kann. Zumindest nicht, wenn man den realen Abstand zwei-er Punkte auf der Erde in beispielsweise Kilometern wissen mochte. Dazu musste manden kurzesten Weg auf einer Kugel oder besser noch auf dem WGS84-Referenzellipsoidenbestimmen.

PostGIS hat fur geographische Daten und Geometrien mit geographischen Koordinatenab der Version 1.5 einen eigenen Typen, Geography, der bestimmte Geometrieberechnun-gen auf dem WGS84-Referenzellipsoiden anbietet. So kann die Distanz zwischen zweiKoordinaten mit ST Distance(Geography,Geography) bestimmt werden und auch dieLange eines LineStrings kann mit ST Length(Geography) in Metern ausgedruckt werden.Die Linestrings liegen zwar als Geometry vor, konnen jedoch automatisch zu Geographygecastet werden, wenn eindeutig ist, dass eine Geography benotigt wird.

Den Abstand zwischen zwei Koordinaten kann man mit dem Verfahren nach Andoyer aus[Mee91], Seite 81, bestimmen. Alternativ, da sowieso nur Distanzen innerhalb Deutsch-lands bestimmt werden sollen, konnte auf trigonometrische, sparischen Berechnungenverzichtet und angenommen werden, dass die Krummung der Erde keine Rolle spielt. Es


wird die Abstandsberechnung der Ebene modifiziert und um die durchschnittliche Di-stanz in Kilometern zwischen zwei WGS84-Koordinaten mit dem Abstand einer Langen-und einer Breiteneinheit in dem Weltkoordinatensystem, erweitert. Der 1◦-Breitenkreis-Abstand variert jedoch stark innerhalb Deutschlands, so dass es nicht sehr genau ist, dieAbweichung betragt zum Beispiel sechs Kilometer bei der Distanz zwischen Hamburgund Dresden.

Der Durchschnittsabstand von 70,5 km fur eine Langeneinheit wird dennoch benutzt,um eine gegebene Partitionslange von km in Gradabstanden umzurechnen. Fur die Be-stimmung der Distanz zum Startpunkt, sei es fur die Heuristik b) zum Finden einesRandzielknotens oder die Schatzfunktion beim A*-Algorithmus, benutzen wir das Ver-fahren nach Andoyer. Die Lange eines LineStrings wird mit PostGIS bei der Erstellung,beziehungsweise wahrend des Clippings berechnet.

4.6 Aufbau des Graphen

4.6.1 Ermittlung von Kanten aus den OSM-Daten

Nach dem Import der OSM-Daten in die PostGIS-Datenbank legen wir eine Tabelle an,in der die Straßen in Kanten aufgeteilt sind.

EDGES( Edge Id, Linestring, Length, Node Id1 → NODES,Node Id2 → NODES, Oneway, Highway)

Die Funktion, die diese Tabelle erstellt, buildEdges() ist im Anhang B.1 zu finden. Zuder LineString-Geometrie wird ein raumlicher Index angelgt. Dabei werden nur Kantenubernommen, die zu Straßen gehoren, auf denen ein vierradiges Fahrzeug fahren kann,siehe Abschnitt 3.3.2, fur eine Beschreibung der hierfur notwendigen Tags. Sackgassenwerden nicht in den Graph mit aufgenommen oder Teile einer Straße, die nur einen Wen-dekreis bilden - unter der Annahme, dass die Straßen ‘‘vernunftig’’ modelliert wurden,das heißt, dass Straßen nicht unnotig durch viele kleine LineStrings modelliert werden,wenn auch einer genugen wurde und dass kreuzende Straßen sich auch in dem selbenOSM-Node treffen und es nicht verschiedene OSM-Nodes mit gleichen Koordinaten sind.

Die Straßenart wird im Attribut Highway vermerkt und ob die Straße eine Einbahnstra-ße ist, im Attribut Oneway. Um eine Straße als Einbahnstraße zu klassifizieren, beno-tigt man den Tagschlussel oneway, nur nicht bei Autobahnen, die auch ohne Tag alsEinbahnstraßen betrachtet werden. Der Tagschlussel ist dann yes, true, 1 oder -1. DieEinbahnstraße verlauft dann in die Richtung, in die der LineString erstellt wurde. Es seidenn, der Tagwert ist -1, dann ist die Richtung umgekehrt zu der des LineStrings.


In Abbildung 4.3 ist dargestellt, wie die OSM-Ways und -Nodes in den Graphen uber-nommen werden. Es werden nur Kreuzungen ubernommen, nicht aber die OSM-Nodes,durch die schwarzen Punkte dargestellt, die nur fur die Darstellung des Linienzuges be-notigt werden. Die magenta-farbene Straße wird nur bis zum Knoten c ubernommen,die Sackgasse jedoch nicht.

b

a

c

Abbildung 4.3: Transformation des OSM-Graphen

4.6.2 Clipping der Kanten in einer Partition

Um zu entscheiden welche Geometrien in welcher Partition liegen, wird jeder Partitionein Polygon zugeordnet, das die Partitionsflache beschreibt.

Die LineStrings von Kanten in der Datenbank, die in einer fraglichen Partition beginnenund auch enden, werden komplett in den Graphen ubernommen. Die anderen LineStrings,die das Polygon nur kreuzen, also nur zum Teil innerhalb des Polygons liegen, werden,sofern sie aus der Partition heraus und nicht wieder zuruck fuhren, am Rand der Par-tition abgeschnitten (geclippt). Beginnt eine Kante in der Partition, aber endet dortnicht, dann wird sie am ersten Schnittpunkt mit dem Rand abgeschnitten. Endet sie nurin einer Partition, wird der LineString bis auf den Teil vom Start- zum ersten Schnitt-punkt ubernommen. Dadurch werden Kanten, die sich um den Rand zweier Partitionenschlangeln, disjunkt und eindeutig aufgeteilt.

Das ist in Abbildung 4.4 graphisch dargestellt, wobei die Pfeile die Richtung andeuten,in die der LineString modelliert ist. Der blaue Teil eines LineStrings wird in der unte-ren Partition aufgenommen, die roten nicht. Fuhrt eine Kante durch drei Partitionen,was selten passiert, aber wenn, dann an einer Ecke vorkommt, muss sie in der mittlerenPartition so gekurzt werden, dass die Vereinigung der drei Teil-LineStrings wieder denGesammten ergibt. Um dies zu erreichen mussen die vier Kombinatinen von Startpunktliegt/liegt nicht und Endpunkt liegt/liegt nicht in der gegebenen Partition untersuchtwerden. Das wird von den zwei PL/pgSQL-Funktionen getEdges(Geometry) und getBor-derEdges(Geometry) erledigt, die ebenfalls im Anhang B.3 zu finden sind.


a b

c

d e

f g

h

Partitionsgrenze

Abbildung 4.4: Clipping an der Partitionsgrenze

4.7 Klassenbeschreibung

Im Folgenden werden die implementierten Klassen kurz erlautert und wie sie zusam-menhangen. Die Architektur wurde an das MVC-Muster angelehnt. Allerdings gibt eswenig Interaktion mit dem Benutzer, wodurch es es viele Models, aber wenige Viewsund Controller gibt. Alle Klassen, die mit den Knoten des Graphen arbeiten, haben einetidyUp()-Methode, die dafur sorgt, dass nicht mehr auf diese Knoten referenziert wird,wodurch sie von der GarbageCollection von Java geloscht werden konnen. Reine Get-und Set-Methoden werden nicht weiter erklart, es werden nur die Attribute erlautert.Welche Get- und Set-Methoden eine Klasse anbietet, kann man den Klassendiagrammenentnehmen.

Das Package Graph

In diesem Package befinden sich die drei Klassen Vertex, Edge und Graph, die zusammeneinen Graph darstellen. Sie implementieren die Methoden, die in Kapitel 2 vorgestelltworden sind, sowie Methoden, die zur Verwaltung der Relationen zwischen Knoten undKanten benotigt werden, aber nur Package-weit sichtbar sind. In Abbildung 4.5 sind dieKlassen diese Packages als Klassendiagramm dargestellt.

Graph

Die Klasse Graph wurde als Singleton implementiert. Das bedeutet, dass es nur eineInstanz dieser Klasse gibt. Zusatzlich zu den Knoten- und Kanten-Mengen wurde eineHashtabelle erstellt, die eine rasche Zuordnung von einer Vertex-Id zu ihrem Vertexermoglicht.

• getInstance():Graph - Liefert die Instanz des Graphen


• tidyUp() - leert die Knoten- und Kanten-Menge und sorgt dafur, dass auch zwi-schen den Knoten und Kanten untereinander keine Referenzen mehr bestehen

Edge

Jede Edge, besitzt eine Referenz auf die beiden Vertices, start und end, die sie verbindet.Die Methoden zum Setzen dieser Vertices ist nicht offentlich, sondern nur Package-weitzuganglich. Straßen, die keine Einbahnstraßen sind, werden nur durch eine Kante darge-stellt, daher wird in einem boolean oneway gespeichert, ob es sich um eine Einbahnstraßehandelt. Die Art der Straße wird uber ein Enum Highway vermerkt, das im Abschnittuber die Model -Klassen erlautert wird. Noch nicht genannte Methoden sind folgende.

• Edge(String id, LineString line, boolean oneway) - Erstellt eine neue Kante, die,falls oneway true ist, eine Einbahnstraße darstellt, mit der ubergebenen id unddem PostGIS-LineString line

• Edge(String id, LineString line) - Erstellt eine Kante, die keine Einbahnstraße ist

Vertex

Jeder Vertex hat eine Liste von ein- (in) und ausgehenden (out) Edges. Die Methoden, diediese Listen verandern konnen nicht von außerhalb dieses Packages aufgerufen werden.Die Klasse Vertex implementiert zusatzlich das Interface Comparable<Vertex>, wodurcheine naturliche Ordnung der Knoten festgelegt wird, namlich die Lange des kurzestenWeges zu einem Startknoten.

• Vertex(String id, Point p) - erstellt einen neuen Knoten mit der ubergebenen idund dem PostGIS-Point p

Die Geometrien der Knoten- und Kanten werden jeweils als PostGIS-Geometrie abgelegt.Um die Geometrien in OpenJUMP darstellen zu konnen, mussen sie erst noch JTS-Geometrien transformiert werden. Da dies aber nicht fur alle Kanten notwendig ist,wird dies nur bei den Kanten auf dem kurzesten berechneten Weg vorgenommen.

Das Package Partition

Die Klassen in diesem Package dienen der Darstellung einer Partition. Die Klassen sindauch in Abbildung 4.6 dargestellt.


Abbildung 4.5: Die Klassen des Graph-Packages


Partition

Diese Klasse besitzt ein JTS-Polygon, das ihre Flache beschreibt, eine Liste von PostGIS-LineStrings, die den Weg in dieser Partition wiedergeben und einen double-Wert fur deLange des kurzesten Weges. Desweiteren zwei boolsche Werte, die anzeigen, ob es sich umdie Partition mit dem Endpunkt der Route handelt, target und ob sie schon untersuchtwurde, used. Es wird ein JTS-Polygon verwendet, da die PostGIS-Geometrieklassen keineGeometrie-Methoden anbieten. Mit JTS ist es leichter eine Partition zu drehen oder zuprufen, ob eine Koordinate auf dem Rand liegt.

• Partition(Polygon p) - erstellt eine neue Partition mit dem ubergebenen Polygonp

• buildResultLineString(Vertex v) - Baut die Route vom Startpunkt der Route, biszum Knoten v auf

Border

Uber das Enum Border, das die Werte RIGHT, LEFT, ABOVE und BELOW annehmenkann, ist eine Bezeichnung der Rander moglich, sofern es sich um ein Gitter handelt.

GridPartition

Eine Spezialisierung der Partition-Klasse ist die GridPartition, in ihr wird vermerkt inwelcher Spalte i und Zeile j sich die Partition im Gitter befindet. Sie hat folgendeMethoden.

• GridPartition(int i, int j, Polygon p) - erstellt eine neue Gitterpartition mit demubergebenen Polygon p und der Postion (i,j ) im Gitter

• getBorders():Collection<Border> - gibt die Rander, sortiert nach der geringstenDistanz zum Startpunkt, zuruck

• getBorder(Gridpartition other):Border - gibt den Rand zuruck, an den die uberge-bene GridPartition other grenzt

Das Package Routingalgorithm

In diesem Package befindet sich ein Interface IRoutingAlgorithm, das von zwei Klassenimplementiert wird , Dijkstra und AStar. Die Klassen sind zusatzlich in Abbildung 4.7


BorderEnum

Border[] values() Border valueOf(String)

GridPartitionPartition

void setPolygon(Polygon) Collection getBorders() int getJ() int getI() Border getBorder(GridPartition) boolean equals(Object) String toString()

PartitionObject

double getResultWeigth() void buildResultLineString(Vertex) Polygon getPolygon() String toString() void setPolygon(Polygon) boolean isTargetPartition() void setTargetPartition(boolean) boolean isUsed() void setUsed(boolean)

Abbildung 4.6: Die Klassen des Partition-Packages

dargestellt. IRoutingAlgorithm verlangt folgende Methoden.

• routes(String startVertexId) - Startet die Routensuche mit dem Vertex, der diestartVertexId aufweist

• getreachedVertices():Collection<Vertex> - gibt die Knoten zuruck, die erreichbarwaren, bis die Routensuche abgebrochen wurde

• tidyUp() - Leert die Container, in denen Vertices gespeichert waren

Im Gegensatz zur Dijkstra-Klasse implementiert AStar noch eine weitere Methode:

• setTargetPoint(Point target)- Setzt den Zielpunkt, zu dem die Distanz geschatztwerden soll auf den PostGIS-Point target

Das Package View

In diesem Package befinden sich zwei Klassen. Sie sind in Abbildung 4.8(a) als Klassen-diagramm dargestellt. Die eine ist ein spezialisiertes JPanel, die SettingsView und wirdbenutzt um die Routing-Einstellungen, die zu Beginn vom PlugIn abgefragt werden, anzu zeigen, siehe Abbildung 4.2. Sie implementiert einen KeyListener, um einen Teil vonfehlerhaften Eingaben nicht zu zu lassen.


Abbildung 4.7: Die Klassen des RoutingAlgorithm-Package

OpenJumpView

Die andere Klasse ist die OpenJumpView, die als Singleton implementiert ist. Diese Klassedient dem Anzeigen des Start- und Zielpunktes, der Partitionen und den LineStrings dererrechneten Route.

• getInstance():OpenJumpView - gibt die Instanz der OpenJumpView zuruck

• init(PlugInContext context, TaskMonitor monitor) - nimmt den context und monitorentgegen

• addResultLineString(Collection<LineString> linestrings) - wandelt die linestringsin eine JTS-Geometrie um und stellt sie in der Workbench dar

• addPolygon(Polygon p) - stellt das JTS-Polygon p in der Workbench dar

• setPoints(Point start, Point end) - stellt start und end in der Workbench dar

• setMonitorText(String text) - setzt die Anzeige des Monitors auf text

Das Package Controller

Die einzige Klasse in diesem Package dient dazu, die Angaben, die im SettingsPanelgetroffen wurden, an die verschiedenen Models weiterzugeben. Der SettingsController ist


(a) View (b) Controller

Abbildung 4.8: Die Klassen des Controller- und View-Packages

in Abbildung 4.8(b) dargestellt un nutzt dafur folgende Methoden.

• SettingsController(SettingsView settings) - erstellt einen neuen SettingsControllermit den Komponenten der ubergebenen SettingsView settings

• store():boolean - ubergibt den verschiedenene Models die Einstellungen, die ge-troffen wurden und gibt true zuruck, falls keine fehlerhaften Eingaben getroffenwurden.

Das Package Connectors

In diesem Package befinden sich Klassen, die in irgendeiner Art und Weise Verbindungzu anderen Systemen als unsere Programm aufbauen oder selbst von anderen Systemenbenutzt werden. Ihre Klassen sind auch in Abbildung 4.9 dargestellt.

PSR OJ Plugin

Diese Klasse ist das PSR OJ Plugin, das ThreadedPlugIn implementiert, ein Interface,das von OpenJUMP bereitgestellt wird und benutzt werden kann, falls nicht absehbarist, wie lange eine Aufgabe dauert. Bei einem normalen PlugIn friert die Workbenchein, wahrend ein PlugIn beim ThreadedPlugin die Workbench verandern kann, allerdingskann der Benutzer nicht an der Workbench arbeiten, sondern hochstens das Plugin ab-brechen. Außerdem wird ein kleines Fenster, ein TaskMonitor, geoffnet, in dem kurzeTextnachrichten erscheinen konnen.

• initalisize(PlugInContext context) - Fugt dem Menue einen neuen Punkt hinzu,uber das das PlugIn gestartet werden kann

• execute(PlugInContext context) - Offnet ein Fenster, in dem die SettingsView ange-zeigt wird und beendet das Plugin, falls die Eingaben fehlerhaft sind


• run(TaskMonitor monitor, PlugInContext context) - Gibt den context und den mo-nitor an die OpenJumpView weiter und startet die Routensuche

PSR Extension

Die Klasse PRS Extension, sorgt lediglich dafur, dass das Plugin geladen wird, falls es imExtension-Ordner von OpenJump liegt. Dazu muss es von Extension, welches ebenfallsvon OpenJUMP bereitgestellt wird, erben und folgende Methode uberschreiben.

• configure(PlugInContext context) - erstellt ein neues PSR OJ Plugin-Objekt undinitalisiert es mit dem ubergebenen context

DataBase

Die dritte Klasse in diesem Package ist die DataBase-Klasse. Sie ist als Singleton im-plementiert und verarbeitet die Anfragen an die PostGIS-Datenbank. Es werden zweiArten von Anfragen gestellt, die zum Finden von Start und Endpunkt am Anfang unddie zum Aufbau des Graphen, die mehrmals pro Routensuche benotigt wird.

• getInstance():DataBase - gibt die DataBase-Instanz zuruck

• buildEdges(Polygon p) -stellt die Anfrage an die PostGIS-Datenbank und gibt dieErgebnisse dieser Anfrage weiter, siehe die Beschreibung zum GraphModel

• findVertexWithAddress(String postcode, String street, boolean startPoint) - startetdie Anfrage getPointForAddress(postcode, street) und falls startpoint true ist, wirddas Ergebnis als Startpunkt gespeichert, sonst als Endpunkt der Routensuche

• findVertexWithPoint(String lat, String lon, boolean startPoint) - startet die Anfra-ge getPointForPoint(Point) mit einem PostGIS-Point, der aus lat und lon erstelltwurde

Das Package Model

In diesem Package befinden sich eine Reihe von Klassen, die das Haupt-Model, das Rou-tingModel, unterstutzen, in dem in ihnen Funktionen ausgelagert sind. Es sind allesSingleton-Klassen, mit Ausnahme eines Enums. Sie sind in Abbildung 4.10 zusehen.Durch die Assoziationspfeile ist angedeutet, dass jediglich das RoutingModel alle ande-ren Models kennt. Nur das TargetModel kennt ebenfalls ein anderes Model.


Abbildung 4.9: Die Klassen des Connectors-Packages

Highway

Das Highway-Enum stellt die verschiedenen Straßenarten aus Tabelle 3.1 dar. Sie besitztnur eine nicht-Enum-spezifische Methode.

• getWeight(Highway street):int - gibt die Durchschnittsgeschwindigkeit der Straßen-art street zuruck

RoutingModel

Dieser Klasse kummert sich um die Hauptaufgabe des PlugIns, eine Route zu finden. Siesetzt den Ablauf um, der im Algorithmus 5 zusammen mit der Funktion aus 3.3.3 be-schrieben ist. Also solange in Partitionen die Routensuche durch zu fuhren, bis die End-partition und in ihr der Zielpunkt der Route erreicht wurde. Im RoutingModel werdenuber startPoint und endPoint die Koordinaten des Start- und Zielpunktes als PostGIS-Point gehalten. Das resultWeight bezeichnet das bisher errechnete Gesamtgewicht derRoutenberechnung. Es besitzt als einziges Model eine Referenz auf einen IRoutingAl-gorithm und es wird vermerkt, welche Heuristik gewahlt wurde, ohne die Gewichtungder Straßen mit ein zu beziehen, daher reicht ein Boolean targetHeuristic aus. Es bietetfolgende Methoden an.

• getInstance():RoutingModel - gibt die RoutingModel-Instanz zuruck

• route():boolean - startet die partitionierte Routensuche und gibt true zuruck, fallsder Endpunkt gefunden wurde


• setTargetPointForAStar(Point p)- verandert den Punkt, zu dem geroutet werdensoll auf p, wird nur benotigt, wenn der A*-Algorithmus mit der Heuristik derniedrigsten Distanz zum Zielpunkt gewahlt wird

PartitionModel

Das PartitionModel sorgt fur die Einteilung in Gitterzellen und verwaltet diese. Bei derErstellung vermerkt sie die Partition, in der die Route beginnt in der GridPartition start-Partition.

• getInstance():PartitionModel - gibt die PartitionModel-Instanz zuruck

• init(Point start, Point end) - nimmt den Startpunkt start und Zielpunkt end ent-gegen

• buildGrid(double width, double height, boolean absolut, boolean dependent) - er-stellt das Gitter, wenn dependent true ist ein abhangiges, ansonsten eine unabhan-giges; ist absolut true dann werden width und height als Gitterhohe und -breite inkm interpretiert, sonst wird ein Gitter der Form width mal height erstellt

• getNextPartition(GridPartition partition, Border next):GridPartition - gibt die Grid-Partition zuruck die an den Rand next von partition angrenzt

GraphModel

Das GraphModel ist fur den Aufbau des Graphen zustandig. Es wird auch vermerktwelche Knoten in der aktuellen Partition auf welchem Rand liegen. Diese Knoten wer-den jeweils in einer Periphery-Liste fur jeden Rand gehalten. Um zu entscheiden, obein Randknoten prinzipiell erreichbar ist, muss es eine Referenz auf den Rand mit demStartpunkt geben, startBorder. Der Border targetBorder stellt den Zielrand der aktuellenRoutensuche dar. Das GraphModel verwaltet die Ids des Start- und Endknotens, start-VertexId und endVertexId und welche Metrik gewahlt wurde in der boolschen VariablevelocityMetric. Ist diese true, wird die schnellste Route gesucht. Es beinhaltet folgendeMethoden.

• getInstance():GraphModel - gibt die GraphModel-Instanz zuruck

• buildGraph(Polygon p) - veranlasst die DataBase-Instanz die Anfrage nach denKanten in dem JTS-Polygon p vorzunehmen die Ergebnisse werden an die folgendenMethoden ubermittelt


• addEdge(String id, LineString line, String vertexId1, String vertexId2, String oneway,String highway, double weight) - Fugt dem Graph eine Kante mit den UbergebenenEigenschaften zwischen den Vertices mit den Ids vertexId1 und vertexId2

• addBorderEdge(String id, LineString line, String vertexId1, String vertexId2, Stringoneway, String highway, double weight) - siehe addEdge(...), nur dass zusatzlich dieRandknoten auf die Rander aufgeteilt werden

• isIrrelevantBorderVertex(Vertex v):boolean - gibt true zuruck, falls der Knoten zueiner Kante gehort, die zu einem anderen Rand fuhrt als der auf dem v liegt, unddieser nicht der Startrand ist; der Knoten kann folglich nicht erreicht werden

• getTargetPeripheryVertices():Collection<Vertex> - gibt die Knoten zuruck, die aufdem Zielrand liegen

• getPeripheryVertices(Border b):Collection<Vertex> - gibt die Knoten zuruck, dieauf dem Rand b liegen

• tidyUp(): - leert die Collections mit den Rand-Vertices

Das TargetModel

Das TargetModel ist fur das Markieren der Zielknoten zustandig und wahlt auch nachder Routensuche in einer Partition den Knoten aus, der der Startpunkt in der nachstenPartition sein soll. Dafur benotigt es eine Menge von Randknoten oder den Knoten, derden Zielpunkt der Routensuche beschreibt, falls in der Endpartition geroutet werdensoll. Diese werden ebenfals in einer Periphery-Sammlung von Knoten gehalten. Einzigdas TargetModel weiß uber eine boolsche Variable withType, ob die Art der Straße indie Bestimmung der Zielknoten mit ein bezogen werden soll. Es muss wissen, ob derA*-Algorithmus verwendet wird, um nach dem Markieren des einen Zielknotens dessenPunkt als neues Ziel fest zu legen, siehe die Klasse RoutingModel, Methode setPoint-ForAStar(). Das wird uber das Boolean aStar gelost. Die Methoden des TargetModelssind:

• getInstance():TargetModel - gibt die TargetModel-Instanz zuruck

• markTarget() - wird benutzt wenn mit der Heuristik b, oder c in Kombination mitb, nur ein Knoten als Ziel markiert wird

• markAllAsTargets(): - markiert alle Knoten auf dem Zielrand, Heuristik a, odernur die mit der hochsten Gewichtung, also c plus a

• getNextStartVertex():Vertex - gibt den Knoten zuruck, der auf dem Zielrand er-reicht wurde oder einen default-Vertex mit der Id deadend, wenn kein Knoten aufdem Rand erreicht wurde


GraphModelObject

GraphModel getInstance() void buildGraph(Polygon) void addEdge(String,LineString,String,String,String,String,double) void addBorderEdge(String,LineString,String,String,String,String,double) boolean isIrrelevantBorderEdge(Vertex) Collection getTargetPeripheryVertices() Collection getPeripheryVertices(Border) void tidyUp() void setVelocityMetric (boolean) void setTargetBorder(Border) void setStartBorder(Border) void setStartVertexId(String) void setEndVertexId(String) String getStartVertexId() String getEndVertexId() boolean isVelocityMetric ()

HighwayEnum

int getWeight(Highway) Highway[] values() Highway valueOf(String)

PartitionModelObject

PartitionModel getInstance() void init(Point,Point) GridPartition getNextPartition(GridPartition,Border) GridPartition getStartPartition() void buildGrid(double,double,boolean,boolean)

RoutingModelObject

RoutingModel getInstance() boolean route() void setTargetPointForAStar(Point) double getResultWeight() void addResultWeight(double) Point getEndPoint() void setEndPoint(Point) Point getStartPoint() void setStartPoint (Point) void setRoutingAlgorithm(IRoutingAlgorithm) void setHeuristic (boolean)

TargetModelObject

TargetModel getInstance() void markTarget() void markAllAsTargets() Vertex getNextStartVertex() void tidyUp() void setPeriphery(Collection) void setPeriphery(Vertex) void setWithType(boolean) void setTargetHeuristic(boolean) void setAStar (boolean)

Abbildung 4.10: Die Klassen des Model-Packages

• tidyUp(): - leert die Collections mit den Rand-Vertices

Interaktion zwischen den Models

Im folgenden Sequenzdiagramm, Abbildung 4.11, ist der allgemeine Ablauf als Interakti-on zwischen den Model-Klassen und einem IRoutingAlgorithm dargestellt, die Korrekturdes Weges ist der Ubersicht halber nicht mit aufgenommen wurde. Dies ist nur eineSchleife in der gepruft wird, ob man in die angrenzenden Partitionen gelangen kann,falls sie noch nicht besucht worden sind. Falls in eine Partition gewechselt werden darf,wahlt das TargetModel den nachsten Startknoten aus.

Es ist stark vereinfacht und stellt nur die wichtigsten Methoden der Model-Klassen dar,um zu zeigen, dass vom RoutingModel die Aktionen ausgehen und die anderen Models esnur unterstutzen.

4.8 Speicherverwaltung

In Java hat man nur einen indirekten Zugriff auf die Speicherverwaltung. Die Garba-geCollection pruft in gewissen Abstanden oder wenn der Speicher knapp wird, welche


Objekte nicht mehr referenziert werden und gibt deren Speicherplatz frei. Das mussaber nicht sofort geschehen. Das hat zur Folge, dass eine Partition, die ein Viertel desGebiets Deutschlands beinhaltet und dadurch 2 bis 2,5GB groß ist, noch Speicher ver-braucht, obwohl es keine Referenzen auf die Knoten und Kanten des Graphen gibt undder Speicher ausgeht, beim Versuch die nachste Partition zu laden. Bei etwas kleinerenPartitionen ab circa 1,8GB kann es zu Verzogerungen im Graphaufbau kommen, aberdie GarbageCollection schafft es meistens rechtzeitig genug Speicherplatz zu schaffen.


:PR

SO

JP

lugi

n:R

outi

ngM

odel

: Par

titi

onM

odel

: Gra

phM

odel

: Tar

getM

odel

: IR

outi

ngA

lgor

ithm

route

()

getS

tart

Par

titi

on()

Par

titi

on

findT

arge

tBor

der

()

buildG

raph(

Par

titi

on)

mar

kT

arge

t()

route

s(Sta

rtV

erte

x)

getN

extS

tart

Ver

tex()

Ver

tex

getN

extP

arti

tion

()

Par

titi

on

Loop

Loop

bis

die

Endpartition

erreichtist

Abbildung

4.11

:D

erA

bla

uf

des

Rou

tings

als

Seq

uen

zdia

gram

m(v

erei

nfa

cht)

Kapitel 5

Experimente

Das folgende Kapitel beschreibt die ausgefuhrten Experimente und ihre Ergebnisse. AmEnde werden diese in einem Fazit zusammengefasst.

5.1 Die Experimentierumgebung

Die Experimente wurden an einem fachgebietseigenen Rechner vorgenommen. Die be-nutzte PostgreSQL-Datenbank ist von der Version 9.1 und wurde unter dem Linux-Betriebssystem openSUSE kompiliert. Instaliert ist auch die PostGIS-Erweiterung inder Version 1.5. Der Rechner ist mit 4 GB Arbeitsspeicher ausgestattet und hat einenQuad-Core mit jeweils 3 Ghz. Der virtuellen Maschine wurden 2,5 GB Arbeitsspeicherzugestanden.

5.2 Das Vorgehen

Es wurden drei Routen gewahlt, an deren Beispiel die Laufzeit und die Gute der par-titionierten Routenberechnung getestet werden soll. Diese Routen gehen von Hamburgnach Dresden, von Dresden nach Munchen und von Hannover nach Munchen. Um dieGute der errechneten Routen abzuschatzen, wurde zuerst die optimale Route berechnet.

Die Heuristiken aus Kapitel 3 werden wie folgt abgekurzt.

a) Kurzeste Distanz zum Start

b) Kurzeste Distanz zum Ziel

48

KAPITEL 5. EXPERIMENTE 49

Route kurzeste in km schnellste in h

Dresden-Munchen 435.73 4.22Hamburg-Dresden 438.06 4.58

Hannover-Munchen 549.32 5.82

Tabelle 5.1: Die optimalen kurzesten Routen

c.a) Kurzeste Distanz zum Start unter Berucksichtigung der Gewichtung der Straßenart

c.b) Kurzeste Distanz zum Ziel unter Berucksichtigung der Gewichtung der Straßenart

Als Abweichung der berechneten Route zur optimalen, wurde die Differenz zwischender Lange der kurzesten Wege von berechneter und optimaler Route ins Verhaltnis zurLange der optimalen Route gesetzt. Betragt die Lange des optimalen Weges 400 km undwurde ein Weg der Lange 600 km errechnet, betragt die Abweichung 50%.

Wenn in einer Tabelle die Anzahl der Knoten vermerkt sind, so ist dies die durchschnitt-liche Knotenanzahl der Partitionen, durch die die Route berechnet wurde. Spielt die An-zahl der untersuchten Knoten, also die Große der cloud oder der closed-List, eine Rolle,so wurde wieder der Durchschnitt uber den Partitionsweg ermittelt. Um den Schnittnicht nach unten zu ziehen, wurden dabei nur die Partitionen betrachtet, in denen nachmehr als funfhundert untersuchten Knoten ein kurzester Weg gefunden wurde. Tritt derText k.E. in einer Tabelle auf, so heißt das, dass keine Route zum Zielpunkt gefundenwerden konnte. Wurde kein Grund dafur angegeben, so wurde in ein Teil einer Partitiongeroutet, von der aus man keinen anderen Partitionsrand mehr erreichen konnte.

In den folgenden Experimenten soll geklart werden, welche Unterschiede es zwischenDijkstra und A* gibt, wie die Gute und die Laufzeit von den Partitionsgroßen abhangt,ob die abhangige Partitionierung bessere Ergebnisse erzeugt, als die unabhangige, welcheUnterschiede es zwischen den Metriken der schnellsten und der kurzesten Route gibt undob eine Heuristik den anderen vielleicht uberlegen ist.

5.3 A* versus Dijkstra

Das erste Experiment befasst sich mit der Fragestellung, um wieviel ‘‘schneller’’ derA*-Algorithmus im Vergleich zu Dijkstra ist und ob beide Algorithmen in den selbenPartitionen die gleiche Route finden. Dafur wurde die schnellste Route von Dresden nachMunchen und die kurzeste von Hamburg nach Dresden mit verschiedenen Partitionsgro-ßen gesucht.

Im ersten Experiment wurde die kurzeste Route zwischen Dresden und Munchen mit


einer abhangigen Partitionierung und der Heuristik c.b) gesucht. Es wird also genauein Zielknoten gesucht und deswegen errechnen Dijkstra und A* die gleichen optimalenRouten fur eine Partition und diesen Zielrandpunkt. Sie unterscheiden sich nur in derAnzahl der untersuchten Knoten. In der folgenden Tabelle 5.2 ist der Zusammenhangzwischen Knoten in einer Partition und untersuchten Knoten dargestellt. Dabei wurdennur Partitionen betrachtet, in denen der Zielrandknoten auch erreicht wurde Die Anzahlder Knoten der Route ist der Durchschnitt uber die Partitionen auf der berechnetenRoute.

P.Große in km2 # Knoten # unters. Kn. (D) # unters. Kn. (A*) #Knoten der Route

3 080 50 162 34 249 8 571 2593 300 54 909 39 954 9 155 2424 265 72 546 49 298 16 188 3124 620 60 028 40 835 17 316 29910 265 172 812 109 396 25 650 321

Tabelle 5.2: Dresden-Munchen, Vergleich Knotenanzahl Dijkstra und A*

Es gibt in der Tabelle eine Auffalligkeit. So verringert sich die durchschnittliche Anzahlder Knoten bei dem Wechsel der Partitionsgroße von 4 265km2 auf 4 620km2 um fast12 000, da verschiedene Wege eingeschlagen werden und die Route mit den großerenPartitionen durch zwei landlichere Gebiete fuhrt, was die Anahl der Knoten insgesamtverringert. Dadurch werden auch weniger Knoten von Dijkstra untersucht, wahrend sichder Großenunterschied beim A*-Algorithmus bemerkbar macht. Wird die Partition ver-großert, werden auch mehr Knoten untersucht.

Wie man in der Tabelle 5.2 und im Diagramm 5.1 sehen kann, untersucht Dijkstrazwei bis vier Mal so viele Knoten wie Dijkstra. Wobei man bei der großten Partitionam besten sehen kann, wie viele kurzeste Wege zu nicht relevanten Knoten ermitteltwerden. Nur 0,2% der Knoten sind Bestandteil des kurzesten Weges, wahrend es beimA*-Algorithmus immerhin gut 1,5% sind. Das ist zwar auch nicht viel, aber dafur wurdenauch nur 15% der Gesamtknoten untersucht, statt 63% wie bei Dijkstra. Aber was sagtdas uber die Geschwindigkeit und die Gute der beiden Algorithmen aus?

In Tabelle 5.3 wird gezeigt, wie lange die Routenberechnung ohne Graphaufbau gedauerthat. Es ist zudem die Anzahl der untersuchten Knoten der beiden Algorithmen darge-stellt und die Große der Partitionen.

Dabei fallt auf, dass der A*-Algorithmus in den meisten Fallen weniger als 1% der Zeitbenotigt, die Dijkstra rechnet.

Im zweiten Experimente wurde die kurzeste Route gesucht, aber diesmal von Hamburgnach Dresden und die Heuristik c.a) wurde benutzt, es wurden also mehrere Randknoten


0.4 0.6 0.8 1 1.2 1.4 1.6 1.8

·105

0

0.2

0.4

0.6

0.8

1

·105

Anzahl Knoten

unte

rsuch

teK

not

en

DijkstraA*

Abbildung 5.1: A* und Dijkstra, Vergleich untersuchter Knoten

P.Große in km #unt. Kn. (D) Rout.Ber.(D) in s #unt. Kn. (A*) Rout.Ber. (A*) in s

3 080 34 249 31,23 8 571 0,323 300 39 954 40,07 9 155 0,314 265 49 298 68,89 16 188 0,434 620 40 835 53,61 17 316 0,5710 265 109 396 638,01 25 650 0,97

Tabelle 5.3: Dresden-Munchen, Vergleich Routingdauer zwischen Dijkstra und A*

als Ziel markiert. Es wurde eine abhangige Partitionierung genutzt. Die Metriken und diePartitionierung wurden verandert, um beispielhaft zu zeigen, dass diese keinen Einflussauf die Laufzeit und die Gute der berechneten Routen der beiden Algorithmen haben. Inder Tabelle 5.4 ist die Dauer der Routenberechnung dargestellt. Die Tabelle ist genausowie die Tabelle 5.3 aufgebaut.

Man kann die gleiche Beobachtung wie in der Tabelle 5.3 machen, namlich dass derDijkstra-Algorithmus bei jeder Partitionsgroße mehr Zeit benotigt. Besonders auffalligist die Dauer bei großen Partitionen, wie der in der letzten Zeile. Insgesamt vier Stundenund vierzig Minuten benotigt Dijkstra um durch zwei Partitionen von Hamburg nachDresden zu gelangen, wahrend der A*-Algorithmus es in 73 Sekunden schafft. Das liegtdaran, dass zum Beispiel in der Zielpartition der A*-Algorithmus nur 45 000 Knotenuntersucht und dafur 3-8 Sekunden benotigt, wahrend Dijkstra in der Zielpartition fast300 000 Knoten untersuchen muss und dafur fast 110 Minuten braucht.

Dadurch dass mehrere Knoten als Zielknoten innerhalb einer Partition markiert werden,konnen sich die kurzesten Wege unterscheiden, die von den beiden Algorithmen errechnet


P.Große in km #unt. Kn. (D) Rout.Ber.(D) in s #unt. Kn. (A*) Rout.Ber. (A*) in s

2 432 23 896 14,3 10 354 0,6753 242 25 318 24,75 14 758 0,894 539 22 910 42,25 17 728 1,136 808 42 775 98,1 22 517 2,2611 347 66 576 250,75 38 898 3,8522 693 88 167 685,25 36 446 4,3568 074 373 919 7 918,2 150 492 36,5

Tabelle 5.4: Hamburg-Dresden, Vergleich Routingdauer zwischen Dijkstra und A*

werden. Dijkstra bestimmt wirklich den kurzesten Weg zu einem Randpunkt, wahrendder A*-Algorithmus den Randknoten zu finden versucht, der einen kurzen Weg aus vomStart aufweist und am nachsten am Zielpunkt liegt. Tatsachlich ermittelt Dijkstra in die-ser Testreihe nur einmal einen schnelleren Weg als A* bei gleichen Partitionsgroßen, sieheTabelle 5.5. In ihr ist dargestellt, welche Abweichungen die Routen der beiden Algorith-men von der optimalen Route aufweisen und wieviele Partitionen auf dem berechnetenWeg liegen.

P.Große in km Abweichung (D) % Abweichung (A*) in % # Part. (D) # Part. (A*)

2 432 45,6 34,9 10 83 242 58,5 49,3 7 84 539 19,9 42,8 10 76 808 40,8 39,1 6 611 347 43,2 40,6 4 422 693 5,4 4,6 5 568 074 19,4 6,7 2 2

Tabelle 5.5: Hamburg-Dresden, Vergleich Gute zwischen Dijkstra und A*

Dass die Abweichungen so groß sind, meistens zwischen 40 und 60%, liegt daran, dass derschnellste Weg zwischen Hamburg und Dresden uber eine Autobahn durch Brandenburgfuhrt und nicht wie die Luftlinie durch Sachsen-Anhalt. Im Falle des besseren Ergeb-nisses von Dijkstra, routet der A*-Algorithmus schon in der ersten Partition zu einemRandknoten, der nicht auf der optimalen Route liegt, wahrend Dijkstra einen Umwegvon drei Partition nimmt und ein doppelt so gutes Ergebnis errechnet. Siehe Bild 5.2. DieRoute, die von Dijkstra gefunden wird ist in rot dargestellt, wahrend der blaue Linienzugdie berechnete Route vom A*-Algorithmus darstellt. Man kann erkennen, dass DijkstrasWeg in der Startpartition echt kurzer ist als der vom A*-Algorithmus, allerdings ist diesauch die einzige Partitionierung, in der der vorausberechnete Rand nicht erreicht wird,weshalb es zu diesem Umweg kommt, der trotzdem ein besseres Ergebnis liefert.


Abbildung 5.2: Vorteil von Dijkstra gegenuber A*

An diesen zwei Beispielen kann man die Vorteile bezuglich der Laufzeit des A*-Algorithmusim Vergleich zu dem von Dijkstra erkennen. In den nachfolgenden Vergleichen wird daherauf Dijkstra verzichtet und alle Berechnungen mit dem A*-Algorithmus gemacht.

5.4 Große versus kleine Partitionen

Die folgenden Experimente sollen zeigen, in wie fern die Große der Partition die Guteder Routensuche bestimmt. Man sollte annehmen, dass große Parttionen ein besseresErgebnis als kleine liefern, da man uber mehr Informationen in einer Partition verfugtund man insgesamt weniger Partitionen untersuchen muss.

Als erste Route wurde die schnellste Route von Hannover nach Munchen mit der Heu-ristik c.b) mit einer unabhangigen Partitionierung gesucht. Dabei wurde die FlacheDeutschlands in Quadrate unterteilt. Die erste Tabelle 5.6, zeigt die Unterschiede ver-schiedener Partitionsgroßen in Gesamtrechendauer und Abweichung von der optimalenRoute. Es sind zudem die Große der Partitionen, die Dauer, in der der Graph aufgebautwurde, die Anzahl der Knoten pro Partition und die Anzahl von Partitionen auf derRoute angegeben.

Man kann in dieser Tabelle erkennen, dass die Gute mit jeder Vergroßerung einer Parti-tion besser wird. Die Zeit fur die Erstellung des Graphen wachst scheinbar proportionalmit der Anzahl der Knoten. Wie erwartet verringert sich auch die Anzahl der Partitionenmit der Vergroßerung der Partitionen. Das kann man auch an der Tabelle 5.7 ablesen.


Aufteilung Große (km2) # Knoten # Part. Aufbau (s) Dauer (s) Abweichung (%)

10x10 6 052 115 120 10 24 318 34,198x8 9 392 141 260 7 28 287 31,446x6 17 011 311 755 5 56 496 9,624x4 37 989 608 616 4 105 734 9,113x3 69 023 1 101 969 2 206 677 5,15

Tabelle 5.6: Hannover-Munchen, Vergleich Partitionsgroßen

Sie zeigt die Ergebnisse der kurzesten Route von Hamburg nach Dresden, die mit derHeuristik c.a und einer abhangigen Partitionierung gesucht wurde.


10x10 6 267 57 221 8 17 138 29,438x8 9 813 99 225 6 20 153 26,856x6 17 506 162 327 5 31 163 24,314x4 39 661 338 600 5 60 312 18,943x3 69 023 669 354 4 119 332 15,432x2 161 831 1 037 545 3 180 555 9,12

Tabelle 5.7: Hamburg-Dresden, Vergleich Partitionsgroßen

Die Tabelle 5.8 zeigt jedoch, dass eine Partitionierung mit großen Partition nicht au-tomatisch besser ist als eine mit kleineren Partitionen. In ihr sind die Ergebnisse einerRoutensuche des schnellsten Weges von Dresden nach Munchen mit einer unabhangi-gen Partitionierung und der Heuristik c.b) in dem gleichen Format wie die vorherigenzwei Tabellen dargestellt. In dieser Tabelle kann man einen Nachteil großer Parttionenerkennen, namlich wenn eine Partition Straßen beinhaltet, die zwar zum kurzesten oderschnellsten Weg gehoren, aber nicht vom Startpunkt in dieser Partition aus erreichbarsind. Da man keine Partition zweimal untersuchen kann, sind diese Straßen nicht mehrzu erreichen und folglich kann die optimale Route nicht mehr gefunden werden. DiesesVerhalten ist bei der Route von Dresden nach Munchen bei einer Aufteilung von dreimal drei Gitterzellen zu sehen. Dafur ergibt die Aufteilung von vier mal vier Gitterneine Route, die der optimalen Route nahe kommt.


8x8 9 392 130 265 6 26 177 17,776x6 17 011 191 572 4 46 257 3,794x4 37 989 405 843 3 71 320 1,183x3 69 023 888 601 3 148 686 7,82

Tabelle 5.8: Dresden-Munchen, Vergleich Partitionsgroßen

Die Ergebnisse zeigen, dass die Große der Partitionen eine Rolle spielen, es aber auch


immer darauf an kommt, ob die Partitionierung glucklich gewahlt ist. Wurde eine Routegesucht, deren Luftlinie nicht das Bundesgebiet verlasst, wurde durch eine Vergroßerungder Partitionen ein besseres Ergebnis erzielt. Die Route von Dresden nach Munchenbesitzt noch weitere Besonderheiten, wie die folgenden Abschnitte zeigen werden.

5.5 Unterschiede der Metriken

Dieser Abschnitt soll die Unterschiede der beiden Metriken bei der partitionierten Rou-tensuche deutlich machen. Dazu wurde mit der Heuristik c.b) und einer unabhangigenPartitionierung und verschiedenen Partitionsgroßen der schnellste und kurzeste Weg aufden den drei Teststrecken gesucht. In den Tabellen sind die Abweichungen der kurzestenund schnellsten berechneten Route zu den verschiedenen Aufteilungen dargestellt.

In der Tabelle 5.9 sind die Ergebnisse der Route in Form der Abweichung von der opti-malen Route in % von Hannover nach Munchen vermerkt. In den meisten Fallen liegtdie Gute der kurzesten Routen unterhalb der der schnellsten oder sie sind etwa gleichgut..

Aufteilung schnellste kurzeste

10x10 34,36 30,258x8 31,44 12,446x6 9,62 8,044x4 9,11 9,503x3 5,15 3,57

Tabelle 5.9: Hannover-Munchen, Vergleich Gute bezuglich der Metriken

In der Tabelle 5.11 sind die Ergebnisse der Route von Dresden nach Munchen dargestellt.Bei einer Aufteilung von zehn mal zehn Gitterzellen wird keine Route gefunden, sieheauch den Abschnitt uber Heuristiken 5.6. Hier schneidet die schnellste Route etwas besserab, als die schnellste Route zwischen Hannover und Munchen. Die Aufteilung in drei maldrei Gitterzellen liefert ein ungenaueres Ergebnis als die Aufteilung von vier mal vier,da ein Teil des kurzesten Weges in einer Partition nicht erreichbar ist und so dieser Teilnicht mehr genutzt werden kann.

In Tabelle 5.11 sind die Ergebnisse der Route Hamburg-Dresden enthalten. Hier liegtdie Gute der kurzesten Route wieder fur jede Aufteilung unterhalb der der schnellsten.

Wie schon bemerkt sind die Abweichungen der schnellsten Route sehr groß, da die op-timale Route nicht mit der Luftlinie ubereinstimmt. Die Abweichungen sind zum Teilnoch großer, wenn man eine abhangige Partitionierung verwendet, siehe Tabelle 5.5.Die Methode, den Zielrand uber die geringste Entfernung zum Zielpunkt der Route zuermitteln, ist also nicht immer optimal fur das Finden der schnellsten Route.



10x10 k.E. k.E.8x8 41,71 18,406x6 8,77 10,174x4 1,18 0,393x3 7,82 10,16

Tabelle 5.10: Dresden-Munchen, Vergleich Gute bezuglich der Metriken


10x10 51,09 20,288x8 18,56 9,206x6 k.E. 4,154x4 15,50 1,19

Tabelle 5.11: Hamburg-Dresden, Vergleich Gute bezuglich der Metriken

Insgesamt hat sich gezeigt, dass das Finden einer kurzesten Route mit einer geringenAbweichung zur optimalen meistens eher gelingt als mit der schnellsten Route.

5.6 Unterschiede der Heuristiken

In diesem Abschnitt geht es um die Unterschiede zwischen den Heuristiken a), c.a),b) und c.b). Es wurden die drei bekannten Strecken bei fester Partitionsgroße einerAufteilung von zehn mal zehn Gitterzellen untersucht. Es wurde eine abhangige Parti-tionierungen gewahlt und diese mit den beiden Metriken kombiniert. In der Tabelle 5.12sind die Abweichungen in Prozent der Route Hamburg-Dresden dargestellt.

Metrik Heuristik a Heuristik c.a Heuristik b Heuristik c.b

schnellste 46,72 40,39 94,98 46,72kurzeste 1,42 2,85 17,99 10,84

Tabelle 5.12: Hamburg-Dresden, Gute der verschiedenen Heuristiken

Es tritt das wieder das Problem auf, dass die Abweichung sehr groß wird, wenn dieschnellste Route nicht ungefahr mit der Luftlinie ubereinstmmt. Trotzdem ist es schonuberraschend, dass die Heuristik b) eine fast doppelt so langsame Strecke ermittelt. Diekurzesten Strecken sind gemessen an der geringen Partitionsgroße bei den Heuristikena und c.a uberraschend nah an der optimalen Route mit jeweils weniger als 3% Abwei-chung.

Die Tabelle 5.13 liegt im gleichen Format vor und beschreibt die Abweichungen der



schnellste 17,30 10,66 k.E. 13,51kurzeste 13,45 7,86 k.E. 9,25

Tabelle 5.13: Dresden-Munchen, Gute der verschiedenen Heuristiken

Strecke Dresden-Munchen. Bei dieser Route schneidet die Heuristik c.a) am besten ab.Die Heuristik b) gerat mit ihrem gewahlten Zielknoten in eine Sackgasse. Im Vergleichzu der schnellsten Strecke von Hamburg nach Dresden sind die Abweichungen bei derschnellsten Route von Dresden nach Munchen geringer, obwohl auch hier die schnellsteRoute nicht mit der Luftlinie ubereinstimmt.

In tabelle 5.14 sind die Abweichungen zur optimalen Route bezuglich der Route vonHannover nach Munchen dargestellt. Auch hier sind die Ergebnise fur diese kleine Parti-tionsgroße mit den Heuristiken a) und c.a) ziemlich gut mit weniger als 2%. Die Abwei-chung bei der Heuristik b) hingegen ist wieder sehr groß, auch auf dieser Strecke stimmtdie schnellste Route nur zum Teil mmit der Luftlinie uberein.


schnellste 6,36 6,01 89,35 5,50kurzeste 1,19 1,70 10,06 5,97

Tabelle 5.14: Hannover-Munchen, Gute der verschiedenen Heuristiken

Insgesamt liegt die Heuristik b, was die Gute betrifft zum Teil deutlich - 60% Unterschiedund mehr in der Abweichung - hinter den anderen zuruck. Die Routen, die ermitteltwerden sehen auch nicht naturlich aus, sie sind sehr zackig, siehe Abbildung 5.3. Es istdie schnellste Route von Hannover nach Munchen mit der Heuristik b) dargestellt. Es isteine Aufteilung in zehn mal zehn Gitterzellen genutzt worden mit einer unabhangigenPartitionierung. Bei der unabhangigen Partitionierung ist noch deutlicher das Verhaltendieser Heuristik zu erkennen und liefert auch ein noch schlechteres Ergebnis, namlich eineAbweichung von 95%. Die kurzeste Route in Kombination mit der Heuristik a) liefernmeistens die besten Ergebnisse. Es kommt allerdings auf eine gluckliche Partitionierungan, siehe die kurzeste Strecke von Dresden nach Munchen, in der die Heuristik c.a dasbeste Ergebnis liefert.

Wird die schnellste Route gesucht, schneiden die Heuristiken c.a) und c.b) am Bestenab. Siehe die drei Tabellen dieses Abschnittes und zum Beispiel Tabelle 5.8 in der mitder Heuristik c.b) eine Abweichung von nur 1,18% erreicht wird.

In der Abbildung 5.4 ist allgemein die Probleme der Heuristiken zu sehen. Dargestellt istdie kurzeste optimale Route in grun von dem oberen Punkt zum unteren. Die untere roteLinie symbolisiert die Route, die mit der Heuristik a bestimmt wurde, wahrend die obereRoute mit der Heuristik b bestimmt wurde. Die schwarze Linie ist ein Partitionsrand. Die


Abbildung 5.3: Probleme der Heuristiken

Abbildung 5.4: Probleme der Heuristiken


Heuristiken c.a und c.b sind nicht dargestellt, da sie eine Autobahn als Zielrandknotenbestimmt, der sehr weit von dem Zielpunkt entfernt liegt.

Die Heuristiken sind eben nur Heuristiken und bestimmen nicht zwangslaufig den opti-malen Zielrandknoten. Rein optisch wurde von der Heuristik a) der kurzeste Weg in derStartpartition bestimmt, nur ist dieser gewahlte Randknoten nicht Teil der optimalenRoute. Den Zielpunkt, den die Heuristik b) gewahlt hat, liegt zwar am nachsten zumZielpunkt, aber uber diesen Randknoten fuhrt der optimale kurzeste Weg nicht. DiesesBeispiel ist zwar konstruiert, aber es verdeutlicht das Problem, dass je mehr Partitio-nen genutzt werden, die Wahrscheinlichkeit steigt, dass wie in der Abbildung nicht dieoptimalen Randknoten gewahlt werden.

Die Ergebnisse zeigen, dass die Heuristik b) in den meisten Fallen ungeeignet ist denkurzesten Weg zu finden. Die Heuristen c.a) und c.b) konnen der optimalen schnellstenRoute nahe kommen, sofern sie mit der Luftlinie ubereinstimmt. Die Heuristik a) liefertmeistens gute Ergebnisse auf der Suche nach der kurzesten Route.

5.7 Abhangige versus unabhangige Partitionierung

Im letzen Abschnitt befassen wir uns mit der Frage, welchen Vorteil eine abhangigePartitionierung bringt oder ob sie die Ergebnisse der Routensuche uberhaupt verbessernkann.

In den folgenden Tabellen sind die Ergebnisse des letzten Abschnitts noch um die Abwei-chungen der unabhangigen Partitionierung erweitert. Es ist also wieder die Abweichungder verschiedenen Heuristiken bei einer Partitionierungsaufteilung von zehn mal zehnGitterzellen dargestellt. Die Tabelle 5.15 zeigt diese fur die Route Hamburg-Dresden.

Fur beide Metriken und alle Heuristiken liefert die abhangige Partitionierung ein besseresErgebnis. Bei der unabhangigen Partitionierung in Kombination mit der Heuristik b wirdeine Route gefunden, die in eine Sackgasse auf halber Strecke fuhrt. Auch kann man hierwieder sehen, dass die Auswahl des Zielrandes uber die kurzeste Distanz zum Zielpunkt,nicht geeignet ist zur Findung der schnellsten Route.

Partitionierung Metrik Heuristik a Heuristik c.a Heuristik b Heuristik c.b

unabhangigschnellste 52,40 51,09 k.E. 47,82kurzeste 16,40 20,28 k.E. 17,60

abhangigschnellste 46,72 40,39 94,98 46,72kurzestee 1,42 2,85 17,99 10,84

Tabelle 5.15: Hamburg-Dresden, Gute bzgl. der Partitionierung und Heuristiken


Abbildung 5.5: Nachteil der unabhangige Partitionierung

Die Tabelle 5.16, in der die Ergebnisse der Routensuche von Hannover nach Munchendargestellt ist, bestatigt den Eindruck, dass die abhangige Partitionierung geeigneterzur Routensuche ist. Wie bei der Route Hamburg-Dresden sind alle Ergebnisse mit einerabhangigen Partitionierung genauer. Bei der Heuristik c.a und der kurzesten Route sogarum 50%.


unabhangigschnellste 8,93 30,07 95,70 34,36kurzeste k.E. 54,51 26,09 31,07

abhangigschnellste 6,36 6,01 89,35 5,50kurzeste 1,19 1,70 10,06 5,97

Tabelle 5.16: Hannover-Munchen, Gute bzgl. der Partitionierung und Heuristiken

In Abbildung 5.5 kann man den Nachteil der unabhangigen Partitionierung sehen, wennder Startpunkt nahe der Partitionsgrenze liegt. Dargestellt sind die Routen die bei einerAufteilung von 8x8 Gitterzellen entstehen (blau) und bei einer Aufteilung von 6x6 (rot).Der Zielrand der ersten Partition bei der Aufteilung 8x8 ist schwarz hervorgehoben. Esstehen bei der Partitionierung mit den kleineren Partitionen nicht genug Informationenin der Startpartition zur Verfugung, wodurch eine komplett andere Route gefunden wirdund ein Unterschied von 20% in der Abweichung entsteht.

Die Tabelle 5.17 zeigt die Ergebnisse der Route Dresden-Munchen. Auffallig ist, das beider unabhangigen Partitionierung einzig in Kombination mit der Heuristik b eine Routegefunden wird. Das liegt daran, dass bei den anderen Heuristiken zu fruh eine Partition



unabhangigschnellste k.E. k.E. 128,20 k.E.kurzeste k.E. k.E. 11,86 k.E.

abhangigschnellste 17,30 10,66 k.E. 13,51kurzeste 13,45 7,86 k.E. 9,25

Tabelle 5.17: Dresden-Munchen, Gute bzgl. der Partitionierung und Heuristiken

verlassen wird und in einen Teil einer Partition gerat, den man nicht wieder verlassenkann. Gleichzeitig findet man mit der Heuristik b) keine Route bei einer abhangigenPartitionierung, dies liegt allerdings an einem Modellierungsfehler in den OSM-Daten,sodass die Route in eine Sackgasse fuhrt.

Bei der Suche nach der schnellsten oder kurzesten Route von Dresden nach Munchenschneidet die Heuristik a), abgesehen von der Aufteilung von zehn mal zehn Gitterzel-len, immer schlechter ab als die anderen Heuristiken. Das liegt daran, dass sowohl diekurzeste als auch die schnellste Route nicht entlang der Luftlinie fuhren kann, da diesedas Bundesgebiet zwischenzeitlich verlasst.

Die Tabelle 5.18 ist eine Erweiterung der Tabelle 5.11, in ihr ist zusatzlich die Abwei-chungen einer abhangigen Partitionierung dargestellt. Benutzt wurde also die Heuristikc.b).

Bis auf eine Ausnahme sind mit einer abhangigen Partitionierung bessere kurzeste Rou-ten als mit der unabhangigen errechnet worden. Durch die Heuristik c.b) werden dieErgebnisse aber auch ungenauer mit großeren Partitionen, bis auf die Aufteilung viermal vier.

Aufteilungabhangig unabhangig

schnellste kurzeste schnellste kurzeste

10x10 40,39 2,85 51,09 20,288x8 43,45 8,94 18,56 9,206x6 48,47 12,27 k.E 4,154x4 19,00 1,12 15,50 1,19

Tabelle 5.18: Hamburg-Dresden, Vergleich Gute bzgl. der Partitionierung und den Me-triken

Die Tabelle 5.19 zeigt im gleichen Format die Abweichungen der Strecke Dresden-Munchenmit der Heuristik c.b). Auf dieser Strecke wurde mit einer abhangigen Partitionierungdie schnellste Route gemessen an der Abweichung besser errechnet als die kurzeste. Dashangt mit der Heuristik zusammen, die besser schnellere Routen bestimmen kann. Zudemwird die Routensuche ohnehin schwieriger, da die sie nicht nicht nur der Luftlinie folgenkann. Wurde die kurzeste Route bei der unabhangigen Partitionierung gefunden, wurde


bis auf eine Ausnahme eine bessere kurzeste Route berechnet als mit der abhangigenPartitionierung.

Die Tabelle zeigt aber vor allem eins, namlich dass eine optimale Route in partitioniertenStraßendaten gefunden werden kann, allerdings wurden hierfur auch nur zwei Partitionenuntersucht.

Aufteilungabhangig unabhangig

schnellste kurzeste schnellste kurzeste

10x10 10,66 29,43 k.E. k.E.8x8 20,85 26,85 41,71 18,406x6 21,09 24,31 8,77 10,174x4 0,00 18,94 1,18 0,393x3 0,00 9,12 7,82 10,16

Tabelle 5.19: Dresden-Munchen, Vergleich bzgl. der Partitionierung und den Metriken

Die Ergebnisse zeigen, dass eine abhangige Partitionierung in Verbindung mit der Heu-ristik a) meist bessere Ergebnisse liefert, als die abhangige Partitionierung. Liegt dieschnellste Route nicht auf der Luftlinie, tragen beide Partitionierungen selten zu einerguten schnellsten Route bei.

5.8 Fazit

Die Ergebnisse der Experimente haben gezeigt, dass es schwierig ist die Partitionierungund Heuristik im Vorfeld zu bestimmen, die zu einer optimalen kurzesten Route fuhrt.Siehe zum Beispiel das Beispiel der besseren Routenberechnung von Dijkstra, die nurentsteht, da der Zielrand nicht erreicht werden kann. So kann ein Teil des optimalenschnellsten Weges genutzt werden, der sonst nicht in Betracht gezogen wird, da er nichtzum Zielrand fuhrt.

Der A*-Algorithmus nutzt die Zusatzinformation der geographischen Lage der Knoteneffizient aus, was sich in der Anzahl der untersuchten Knoten und damit in der Laufzeitim Vergleich zu Dijkstra bemerkbar macht.

Eine Vergroßerung der Partitionen ist solange ein Vorteil, bis ein Zielrand nicht erreichtwird. Dann muss die Partition gewechselt werden und Strecken der optimalen kurzestenRoute konnen nicht mehr erreicht werden.

Die Auswahl des Zielrandes uber die kurzeste Entfernung zum Zielpunkt der Route ist furdie Findung der schnellsten Route nicht immer optimal, wenn die Partitionen nicht großgenug gewahlt wurde. Das man die optimale Route finden kann, zeigt die Tabelle 5.19.


Die Heuristik a) liefert zum Teil auch bei kleinen Partitionen ein annehmbares Ergebnis,solange der die kurzeste Route auch uber die Luftlinie fuhrt. Die Heuristik b) liefert inder Regel die Ergebnisse mit der hochsten Abweichung. Das Problem des nicht erreichtenZielknotens kann auch mit den Heuristiken b) und c.b) auftreten und macht dadurchvor allem die Heuristik b) noch unattraktiver zur Bestimmung des kurzesten Weges.

Die abhangige Partitionierung kann die Ergebnisse der Routensuche verbessern, hat aberdie gleichen Probleme, wie die abhangige, wenn der Zielrand nicht erreicht wird oder diegesuchte Route nicht mit der Luftlinie ubereinstimmt.

Kapitel 6

Ausblick

Insgesamt hat sich gezeigt, dass es nicht zwangslaufig eine perfekte Partitionierung zuroptimalen Routenbestimmung gibt.

Es konnen noch alternative Routing-Moglichkeiten umgesetzt werden, zum Beispiel dashierarchische Kurzeste-Wege-Suchen. Man konnte die Routensuche zusatzlich auch vomEndpunkt zum Startpunkt durchfuhren und sie mit der normalen Route vergleichen.

Der A*-Algorithmus verletzt unter gewissen Umstanden die Heuristik a), das konntevermieden werden, in dem alle markierten Randknoten gefunden werden und von diesenden mit dem kurzesten Weg auszuwahlen. Allerdings wurde dann, falls ein einziger dieserRandknoten nicht erreicht wurde, wieder alle Kanten zu erreichbaren Knoten relaxiertwerden, was der A*-Algorithmus ja gerade vermeiden soll. Man konnte auch die Rou-tensuche, die bisher nur von einem Start- zu einem Zielpunkt auf mehrere Start- undZielpunkte erweitern.

Die vorhandenen Daten aus OpenStreetMap konnten noch besser fur das Routing ge-nutzt werden. So existieren noch mehr Tags, die man beachten konnte, wie ein max-speed -Tag oder ein Tag fur Ampeln, den man benutzen konnte, um zum Beispiel eineWartezeit pro Ampel auf den schnellsten Weg addieren konnte.

Die Art der Partitionen konnten auf beliebige Polygone erweitert werden, wie Polygone,die die Bundeslander beschreiben.

Falls man eine genauere Beschreibung der Route wunscht, musste diese Beschreibungebenfalls bei der Komposition der Routen zusamengefuhrt werden, damit man nichtdurch die Partitionierung die Anweisungen “zehn Kilometer auf der A2” und “nach funfKilometern rechts abbiegen”erhalt, sondern“nach funfzehn Kilometern auf der A2 rechtsabbiegen”.

64

Anhang A

Das simpleOsmosis-PostGIS-Schema

Osmosis ist ein Kommandozeilen-Werkzeug zur Verarbeitung von OSM-Daten. Um dieOSM-Daten, die zum Beispiel im .osm-Format vorliegen, in eine PostGIS-Datenbankzu laden, muss diese Tabellen gemaß dem Osmosis PostGIS simple Schema vorliegen.Im Osmosis-Software-Paket befindet sich ein Ordner script, in dem Erstellungsskriptefur dieses Schema vorliegen. Benotigt werden fur unsere Anwendung die Skripte pgsim-ple schema 0.6.sql und pgsimple schema 0.6 linestring.sql, das in der WAYS-Tabelle eineLineString-Geometrie hinzufugt. Insgesamt werden folgende Tabellen erstellt:

SCHEMA INFO (Version)

USERS (Id, Name)

NODES (Id, Version,User ID → USERS, Tstamp, Changeset Id, Geom)

NODE TAGS (Node Id → NODES, K, V)

WAYS (Id, Version,User ID → USERS, Tstamp, Changeset Id, Linestring)

WAY NODES (Way Id → WAYS, Node Id → NODES, Sequence Id)

WAY TAGS (Way Id → WAYS, K, VNULL)

RELATIONS (Id, Version,User ID → USERS, Tstamp, Changeset Id)

RELATION MEMBERS (Relation Id → RELATIONS, Member Id,Member Type, Member Role, Sequence Id)

RELATION TAGS (Relation Id → RELATIONS, K, V)

Wenn nicht anders angegeben, wird NOT NULL fur die Attribute angenommen. Zu-satzlich werden raumliche Indexe fur die Geometrien Geom und Linestring angelegt,sowie Indexe fur die Tag-Relationen fur den jeweiligen Typen (Node Id, Relation Id undWay Id) und bei der WAY NODES-Relation fur die Way Id.

65

Anhang B

PL/pgSQL-Funktionen

B.1 Funktionen zum Erstellen der Edges-Tabelle

Die folgende Funktion nimmt einen Linestring entgegen und gibt den Teil des Linestringszuruck, der zwischen dem first-ten und last-en Knoten besteht.

CREATE OR REPLACE FUNCTION makeSubLineString(geometry, integer, integer)

RETURNS geometry AS

$BODY$

DECLARE

line ALIAS FOR $1;

first ALIAS FOR $2;

last ALIAS FOR $3;

result geometry;

BEGIN

--ST_PointN beginnt bei 1, die Sequence_id bei 0

result:=ST_MakeLine(ST_PointN(line,first+1),ST_PointN(line,first+2));

FOR i IN first+2..last LOOP

result:=ST_AddPoint(result, ST_PointN(line,i+1));

END LOOP;

return result;

END;

$BODY$

66

ANHANG B. PL/PGSQL-FUNKTIONEN 67

Die folgenden Sichten edge view und node view dienen nur zur Abkurzung der Abfragenin der nachsten Funktion.

CREATE OR REPLACE VIEW edge_view AS

SELECT DISTINCT ways.id, ways.linestring, wt2.v AS highway,

CASE wt1.v

WHEN ’1’ THEN ’yes’

WHEN ’-1’ THEN ’vice_versa’

WHEN ’true’ THEN ’yes’

WHEN ’yes’ THEN ’yes’

ELSE ’no’

END AS oneway

FROM ways

LEFT JOIN way_tags wt1 ON ways.id = wt1.way_id AND wt1.k = ’oneway’

JOIN way_tags wt2 ON ways.id = wt2.way_id

WHERE wt2.k = ’highway’ AND (w2.v = ANY (ARRAY[’motorway’, ’motorway_link’,

’trunk’, ’trunk_link’, ’primary’, ’primary_link’,

’secondary’, ’tertiary’, ’residential’, ’living_street’,

’unclassified’, ’service’, ’track’]));

Die Highway-Tags sind in Abschnitt 3.3.2 beschrieben und die genaue Auflistung ist beider Node View weggelassen worden. Alternativ kann man auch zwei Edge Views joinen,aber in denen ware jeweils ein unnotiger Join fur die LineString-Geometrie.

CREATE OR REPLACE VIEW node_view AS

SELECT DISTINCT wn1.way_id, wn1.node_id, nodes.geom, wn1.sequence_id

FROM way_nodes wn1

JOIN way_nodes wn2 ON wn1.node_id = wn2.node_id AND wn1.way_id <> wn2.way_id

JOIN nodes ON nodes.id = wn1.node_id

JOIN way_tags wt1 ON wn1.way_id = wt1.way_id

JOIN way_tags wt2 ON wn2.way_id = wt1.way_id

WHERE wt1.k = ’highway’ ... AND wt2.k = ’highway’ ... --siehe oben

ORDER BY wn1.way_id;

Die folgende Funktion legt die Tabelle EDGES neu an.

CREATE OR REPLACE FUNCTION buildEdgeTable()

RETURNS void AS

$BODY$

BEGIN

--Die Tabelle edges neu anlegen

DROP TABLE IF EXISTS edges;


CREATE TABLE edges (

edge_id text,

linestring geometry,

oneway text,

highway text,

length double precision,

node_id1 text,

node_id2 text,

);

CREATE INDEX index_linestring

ON edges

USING gist

(linestring);

END;

$BODY$

LANGUAGE plpgsql

Die Funktion buildEdges() erstellt die Kanten fur den Graphen. Dabei werden fur alleStraßen, die jenigen OSM-Nodes identifiziert, die Kreuzungen auf dieser Straße darstellenund an diesen wird der Linestring des OSM-Ways aufgespalten.

CREATE OR REPLACE FUNCTION buildedges()

RETURNS void AS

$BODY$

DECLARE

--Die richtigen Automobilstraßen herausfinden

way_cursor Cursor IS SELECT * FROM edge_view;

--Kreuzungen ermitteln

edge_cursor Cursor (id bigint) IS SELECT * FROM node_view WHERE way_id=id;

i integer;

edge_record Record;

old_seqence_id integer;

old_node_id bigint;

new_edge geometry;

line geometry;

BEGIN

SELECT buildEdgeTable();

--Jede Straße an den Kreuzungen in Kanten umwandeln

FOR way_record IN way_cursor

LOOP

i:=0;

Open edge_cursor(way_record.id);

FETCH edge_cursor INTO edge_record;


old_seqence_id:=edge_record.sequence_id;

old_node_id:=edge_record.node_id;


--den LineString zwischen den sequence_id’s aufspalten

WHILE FOUND LOOP

line:=makeSubLineString(way_record.linestring, old_seqence_id,

edge_record.sequence_id);

INSERT INTO edges VALUES (way_record.id||’_’||i, line,

way_record.oneway,way_record.highway, ST_Length(line,true),

old_node_id,edge_record.node_id);

i:=i+1;

old_seqence_id:=edge_record.sequence_id;

old_node_id:=edge_record.node_id;


END LOOP;

CLOSE edge_cursor;

END LOOP;

END;

$BODY$

LANGUAGE plpgsql

B.2 Funktionen zum Finden von Start- und Zielkno-

ten

Die Funktion liefert den Knoten, der innerhalb eines Radius von 500m, am nachstenzum ubergebenen Punkt liegt.

CREATE OR REPLACE FUNCTION getnodeidforPoint(IN geometry, OUT nodeid text,

OUT resultPoint geometry)

AS

$BODY$

DECLARE

point ALIAS FOR $1;

edge edges%ROWTYPE;

BEGIN

--Die Kante ermittelt die am nachsten zum ubergebenen Punkt liegt

SELECT * FROM edges WHERE ST_DWithin(point,linestring,500,TRUE) ORDER BY

ST_Distance(linestring,point,TRUE) LIMIT 1 INTO edge;

IF ST_Distance(ST_Startpoint(edge.linestring),point)<=

ST_Distance(ST_Endpoint(edge.linestring),point) THEN

nodeId:=edge.node_id1;


resultPoint:=st_startpoint(edge.linestring);

ELSE


resultPoint:=st_endpoint(edge.linestring);

END IF;

RETURN;

END;

$BODY$

LANGUAGE plpgsql

Die Funktion liefert ein Plygon zuruck, in dem nach der Straße gesucht werden kann.

CREATE OR REPLACE FUNCTION getPostcodePolygon(IN postcode text,

IN street text, OUT postcodepolygon geometry)

RETURNS geometry AS

$BODY$

BEGIN

SELECT ST_Buildarea(ST_Collect(linestring)) INTO postcodepolygon

FROM relation_members r1 JOIN relation_tags r2 USING (relation_id) JOIN

ways ON r1.member_id=id WHERE (member_role=’outer’

OR member_role=’’) AND r2.k=’postal_code’ AND v=postcode;

--wenn kein Polygon gefunden wurde, dann selbst eines "basteln"...

IF postcodepolygon IS NULL THEN

SELECT ST_ENVELOPE(ST_COLLECT(ARRAY((

(SELECT geom FROM node_tags JOIN nodes n ON n.id=node_id

WHERE v=postcode AND k IN (’postal_code’,’addr:postcode’))

--...indem um alle Knoten und Kanten mit dieser Postleitzahl

--eine Boundingbox gelegt wird

UNION

(SELECT linestring FROM way_tags JOIN ways w ON w.id=way_id

WHERE v=postcode AND k IN (’postal_code’,’addr:postcode’))))))

INTO postcodepolygon;

END IF;

END;

$BODY$

LANGUAGE plpgsql


Die Funktion ermittelt einen Knoten, der zu einer Straße mit dem ubergebenen Namenund in dem Postleitzahlgebiet liegt.

CREATE OR REPLACE FUNCTION getnodeidforaddress(IN text, IN text,

OUT nodeid text, OUT point geometry)

AS

$BODY$

DECLARE

postcode ALIAS FOR $1;

street ALIAS FOR $2;

postcodepolygon geometry;

findEdge CURSOR (line geometry) IS SELECT node_id1,linestring,node_id2

FROM edges WHERE ST_Intersects(postcodepolygon,linestring)

ORDER BY ST_Distance(linestring,line) LIMIT 1;

findWay CURSOR (geom geometry) IS SELECT linestring FROM ways JOIN way_tags

ON id=way_id WHERE ST_Intersects(geom,linestring)

AND k=’name’ AND v=street LIMIT 1;

BEGIN

SELECT * FROM getPostCodePolygon(postcode,street) INTO postcodepolygon;

FOR way IN findWay(postcodepolygon) LOOP

FOR edge IN findEdge(way.linestring) LOOP

IF ST_Distance(ST_Startpoint(edge.linestring),way.linestring)<=

ST_Distance(ST_Endpoint(edge.linestring),way.linestring) THEN


point:=ST_Startpoint(edge.linestring);

ELSE


point:=ST_Endpoint(edge.linestring);

END IF;

END LOOP;

END LOOP;

RETURN;

END;

$BODY$

LANGUAGE plpgsql


B.3 Funktionen zum Graphaufbau

Liefert alle Kanten, die nicht geclippt werden mussen.

CREATE OR REPLACE FUNCTION getEdges(polygon geometry) RETURNS SETOF edges AS

$BODY$

BEGIN

--einfach nur die Kanten zuruckgeben, die im Polygon beginnen und auch enden

RETURN QUERY SELECT * FROM edges

WHERE ST_Contains(polygon,ST_Startpoint(linestring))

AND ST_Contains(polygon, ST_Endpoint(linestring));

END;

$BODY$

LANGUAGE plpgsql

Liefert alle Kanten, die in der gegebenen Partition beginnen und clippt sie vorher

CREATE OR REPLACE FUNCTION getBeginningBorderedges(polygon geometry)

RETURNS SETOF edges AS

$BODY$

DECLARE

count integer;

temp geometry;

result edges%rowtype;

--Die Kanten die in dieser Partition beginnen, konnen gleich mit "Intersection()"

--abgeschnitten werden, es wird ja nur dieser Teil des LineStrings benotigt

beginning CURSOR FOR SELECT edge_id,ST_Intersection(polygon,linestring) linestring,

oneway, highway,length,node_id1,node_id2 FROM edges WHERE

ST_Crosses(polygon, linestring) AND

ST_Contains(polygon, ST_Startpoint(linestring))

AND NOT ST_Contains(polygon, ST_Endpoint(linestring));

BEGIN

--Die abgeschnittenen Kanten konnen so zuruckgegeben werden, es sei denn es

--gab mehrere Ergebnisse bei der Intersection(), dann wird nur die

--erste Geometrie ubernommen

FOR edge IN beginning LOOP

result:=edge;

result.node_id2:=edge.edge_id||’_e’;

IF(ST_Geometrytype(edge.linestring)=’ST_MultiLineString’) THEN

result.linestring:=ST_Geometryn(edge.linestring,1);

END IF;

result.length:=ST_Length(result.linestring,TRUE);


RETURN NEXT result;

END LOOP;

RETURN;

END;

$BODY$

LANGUAGE plpgsql

Liefert alle geclippten Kanten, die in der Partition enden.

CREATE OR REPLACE FUNCTION getEndingBorderEdges(polygon geometry)


$BODY$

DECLARE

count integer;

temp geometry;


--Fur die Kanten, die in dieser Partition enden, muss noch gepruft werden,

--welche wie geclippt werden muss

ending CURSOR FOR SELECT * FROM edges WHERE ST_Crosses(polygon, linestring)

AND NOT ST_Contains(polygon, ST_Startpoint(linestring))

AND ST_Contains(polygon, ST_Endpoint(linestring));

BEGIN

FOR edge IN ending LOOP

result:=edge;

result.node_id1:=edge.edge_id||’_b’;

--Es wird der Schnittpunkt des Polygonrandes mit dem

--Kanten-LineString ermittelt

temp:=ST_Intersection(edge.linestring,ST_Boundary(polygon));

--wenn die Kante den Polygonrand nur einmal schneidet, ist alles

--in Ordnung, wenn nicht...

IF ST_Geometrytype(temp)=’ST_MultiPoint’ THEN

--muss hier gepruft werden, ob der erste oder letzte dieser Punkte naher

--zum Startpunkt liegt und dann dieser als Schnittpunkt festgelegt werden

IF ST_Distance(ST_Startpoint(edge.linestring),ST_Geometryn(temp,1)) <

ST_Distance(ST_Startpoint(edge.linestring),

ST_Geometryn(temp,ST_Numgeometries(temp))) THEN

temp:=ST_Geometryn(temp,1);

ELSE

temp:=ST_Geometryn(temp,ST_Numgeometries(temp));

END IF;

END IF;

--ST_Line_Substring(a,b) liefert den linestring von a nach b, aber es sind

--keine Koordinaten, sondern relative Werte z.B. 0.5, diesen


--berechnet ST_Locate_Point

result.linestring:=ST_Line_Substring(edge.linestring,

ST_Line_Locate_Point(edge.linestring,temp),1);

result.length:=ST_Length(result.linestring,TRUE);

RETURN NEXT result;

END LOOP;

RETURN;

END;

$BODY$

LANGUAGE plpgsql

Gibt die Kanten zuruck, die in der Partition enden oder beginnen.

CREATE OR REPLACE FUNCTION getSimpleBorderEdges(polygon geometry)


$BODY$

BEGIN

--einfach nur die Kanten dieser Funktionen zuruckgeben

RETURN QUERY SELECT * FROM getBeginningBorderEdges(polygon)

UNION SELECT * FROM getEndingBorderEdges(polygon);

END;

$BODY$

LANGUAGE plpgsql

In den folgenden Funktion tauchen immer wieder die gleichen Parameter auf. Border1bezeichnet die Geometrie, die entsteht, wenn man einen Rand, der den LineString derKante schneidet, border2 analog. Wenn firstBorder wahr ist, heißt das, dass border1 ausder Sicht des LineStrings zuerst geschnitten wurde.

Pruft, ob der linestring das polygon an mindestens zwei Randern schneidet und gibtdie Schnittmenge der Rander mit dem Linienzug zuruck, sowie welcher Rand zuerstgeschnitten wurde.

CREATE OR REPLACE FUNCTION realCrossing(IN polygon geometry,

IN linestring geometry, OUT firstborder boolean, OUT count integer,

OUT border1 geometry, OUT border2 geometry)

AS

$BODY$

DECLARE

temp geometry;

BEGIN

firstborder:=FALSE;


count:=0;

border1:=NULL; --die Geometrien, die entstehen, wenn

border2:=NULL; --man den Polygonrand mit dem LineString schneidet

--zahlen, wie viele Polygonrander geschnitten wurden

FOR i IN 0..3 LOOP

temp:=makeSubLinestring(ST_Boundary(polygon),i,i+1);

IF ST_Intersects(temp,linestring) THEN

IF count=0 THEN

border1:=ST_Intersection(temp,linestring);

count:=count+1;

ELSE

border2:=ST_Intersection(temp,linestring);

--firstBorder zeigt an, dass der erste Rand der gefunden wurde naher

--am Startpunkt des Linestrings liegt

IF ST_Distance(border1,ST_Startpoint(linestring))<=

ST_Distance(border2,ST_Startpoint(linestring)) THEN

firstborder:=TRUE;

END IF;

count:=count+1;

END IF;

END IF;

END LOOP;

END;

$BODY$

LANGUAGE plpgsql

Ermittelt, falls der linestring den Polygonrand mehrfach geschnitten hat, welcher derPunkt zum clippen ist.

CREATE OR REPLACE FUNCTION getRightPoint(IN linestring geometry,

IN multipoint geometry, IN toEnd boolean, OUT point geometry)

AS

$BODY$

DECLARE

BEGIN

--toEnd bedeutet, dass der LineString "hinten" abgeschnitten werden soll

IF toEnd THEN

--prufen, ob der erste oder letzte Punkt von

--multipoint naher zum Ende liegt

IF ST_Distance(ST_Endpoint(linestring),ST_Geometryn(multipoint,1)) <

ST_Distance(ST_Endpoint(linestring),

ST_Geometryn(multipoint,ST_Numgeometries(multipoint))) THEN

point:=ST_Geometryn(multipoint,1);


ELSE

point:=ST_Geometryn(multipoint,ST_Numgeometries(multipoint));

END IF;

ELSE

--analog, nur mit Startpunkt

IF ST_Distance(ST_Startpoint(linestring),ST_Geometryn(multipoint,1)) <

ST_Distance(ST_Startpoint(linestring),

ST_Geometryn(multipoint,ST_Numgeometries(multipoint))) THEN

point:=ST_Geometryn(multipoint,1);

ELSE

point:=ST_Geometryn(multipoint,ST_Numgeometries(multipoint));

END IF;

END IF;

END;

$BODY$

LANGUAGE plpgsql

Bastelt den LineString, der von beiden Seiten geclippt wurde

CREATE OR REPLACE FUNCTION buildSubLineString(IN linestring geometry,

IN border1 geometry, IN border2 geometry, OUT line geometry)

AS

$BODY$

DECLARE

BEGIN

line:=linestring;

--gegebenenfalls den richtigen Point aus den Multipoints auswahlen

IF ST_Geometrytype(border1)=’ST_MultiPoint’ THEN

SELECT point INTO border1 FROM

getRightPoint(linestring, border1, FALSE);

END IF;

IF ST_Geometrytype(border2)=’ST_MultiPoint’ THEN

SELECT point INTO border2 FROM

getRightPoint(linestring, border1, TRUE);

END IF;

--nur einen neuen LineString erstellen, wenn der erste Randpunkt

--vor dem zweiten auf dem LineString liegt

IF ST_Line_Locate_Point(linestring,border2)>

ST_Line_Locate_Point(linestring,border1) THEN

line:=ST_Line_Substring(edge.linestring,

ST_Line_Locate_Point(linestring,border1),

ST_Line_Locate_Point(linestring,border2));

END IF;


END;

$BODY$

LANGUAGE plpgsql

Gibt die Kanten zuruck, die von beiden Seiten geclippt wurden.

CREATE OR REPLACE FUNCTION getComplicatedBorderEdges(polygon geometry)


$BODY$

DECLARE

firstborder boolean;

count integer;

border1 geometry; --border1 und border2 sind Geometrien, die man erhalt,

border2 geometry; --wenn man die Kante mit dem Polygonrand schneidet


middle CURSOR FOR SELECT * FROM edges WHERE ST_Crosses(polygon, linestring)

AND NOT ST_Contains(polygon, ST_Startpoint(linestring))

AND NOT ST_Contains(polygon, ST_Endpoint(linestring));

BEGIN

FOR edge IN middle LOOP

result:=edge;

SELECT * INTO firstborder,count,border1,border2

FROM realCrossing(polygon,result.linestring);

--wenn count>1, dann schneidet die Kante zwei Rander dieses Polygons

IF count>1 THEN

result.node_id1:=edge.edge_id||’_b’;

result.node_id2:=edge.edge_id||’_e’;

--firstBorder zeigt an, an welchem Rand die Kante

--das Polygon zuerst schneidet

IF firstborder THEN

result.linestring:=buildSubLineString(

edge.linestring, border1, border2);

ELSE

result.linestring:=buildSubLineString(

edge.linestring, border2, border1);

END IF;

result.length:=st_length(result.linestring,TRUE);

RETURN NEXT result;

END IF;

END LOOP;

RETURN;

END;

$BODY$

LANGUAGE plpgsql


Gibt alle Rankkanten zuruck, die in dem ubergebenen Polygon liegen.

CREATE OR REPLACE FUNCTION getBorderEdges(polygon geometry)


$BODY$

BEGIN

RETURN QUERY SELECT * FROM getSimpleBorderEdges(polygon)

UNION SELECT * FROM getComplicatedBorderEdges(polygon);

END;

$BODY$

LANGUAGE plpgsql

Abbildungsverzeichnis

2.1 EER-Diagramm zu Node, Way und deren Tags . . . . . . . . . . . . . . . 7

2.2 Ein gerichteter Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.3 Ein kurzester Weg zwischen zwei Knoten . . . . . . . . . . . . . . . . . . 11

3.1 Zwei Partitionierungsarten . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2 Beispiel zur Erstellung einer abhangigen Partitionierung . . . . . . . . . 21

4.1 Die OpenJump-Oberflache . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4.2 Das Einstellungsfenster . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.3 Transformation des OSM-Graphen . . . . . . . . . . . . . . . . . . . . . 33

4.4 Clipping an der Partitionsgrenze . . . . . . . . . . . . . . . . . . . . . . . 34

4.5 Die Klassen des Graph-Packages . . . . . . . . . . . . . . . . . . . . . . . 36

4.6 Die Klassen des Partition-Packages . . . . . . . . . . . . . . . . . . . . . 38

4.7 Die Klassen des RoutingAlgorithm-Package . . . . . . . . . . . . . . . . . 39

4.8 Die Klassen des Controller- und View-Packages . . . . . . . . . . . . . . 40

4.9 Die Klassen des Connectors-Packages . . . . . . . . . . . . . . . . . . . . 42

4.10 Die Klassen des Model-Packages . . . . . . . . . . . . . . . . . . . . . . . 45

4.11 Der Ablauf des Routings als Sequenzdiagramm (vereinfacht) . . . . . . . 47

5.1 A* und Dijkstra, Vergleich untersuchter Knoten . . . . . . . . . . . . . . 51

5.2 Vorteil von Dijkstra gegenuber A* . . . . . . . . . . . . . . . . . . . . . . 53

5.3 Probleme der Heuristiken . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.4 Probleme der Heuristiken . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.5 Nachteil der unabhangige Partitionierung . . . . . . . . . . . . . . . . . . 60

79

Tabellenverzeichnis

3.1 Die Straßenarten und ihre Gewichtungen . . . . . . . . . . . . . . . . . . 25

5.1 Die optimalen kurzesten Routen . . . . . . . . . . . . . . . . . . . . . . . 49

5.2 Dresden-Munchen, Vergleich Knotenanzahl Dijkstra und A* . . . . . . . 50

5.3 Dresden-Munchen, Vergleich Routingdauer zwischen Dijkstra und A* . . 51

5.4 Hamburg-Dresden, Vergleich Routingdauer zwischen Dijkstra und A* . . 52

5.5 Hamburg-Dresden, Vergleich Gute zwischen Dijkstra und A* . . . . . . . 52

5.6 Hannover-Munchen, Vergleich Partitionsgroßen . . . . . . . . . . . . . . . 54

5.7 Hamburg-Dresden, Vergleich Partitionsgroßen . . . . . . . . . . . . . . . 54

5.8 Dresden-Munchen, Vergleich Partitionsgroßen . . . . . . . . . . . . . . . 54

5.9 Hannover-Munchen, Vergleich Gute bezuglich der Metriken . . . . . . . . 55

5.10 Dresden-Munchen, Vergleich Gute bezuglich der Metriken . . . . . . . . . 56

5.11 Hamburg-Dresden, Vergleich Gute bezuglich der Metriken . . . . . . . . 56

5.12 Hamburg-Dresden, Gute der verschiedenen Heuristiken . . . . . . . . . . 56

5.13 Dresden-Munchen, Gute der verschiedenen Heuristiken . . . . . . . . . . 57

5.14 Hannover-Munchen, Gute der verschiedenen Heuristiken . . . . . . . . . 57

5.15 Hamburg-Dresden, Gute bzgl. der Partitionierung und Heuristiken . . . . 59

5.16 Hannover-Munchen, Gute bzgl. der Partitionierung und Heuristiken . . . 60

5.17 Dresden-Munchen, Gute bzgl. der Partitionierung und Heuristiken . . . . 61

5.18 Hamburg-Dresden, Vergleich Gute bzgl. der Partitionierung und den Me-triken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.19 Dresden-Munchen, Vergleich bzgl. der Partitionierung und den Metriken 62

80

Literaturverzeichnis

[Bri08] T. Brinkhoff. Geodatenbanksysteme in Theorie und Praxis. Herbert Wich-mann Verlag, 2. Aufl., 2008. ISBN 978-3-87907-472-3.

[CLRS10] T. H. Cormen, C. E. Leiserson, R. Rivest, C. Stein. Algorithmen - EineEinfuhrung. Oldenbourg Verlag Munchen, 3. Aufl., 2010. ISBN 978-3-486-59002-9.

[HNR68] P. E. Hart, N. J. Nilsson, B. Raphael. A formal basis for the heuristic deter-mination of minimum cost paths. IEEE Transactions on Systems, Science,and Cybernetics, SSC-4(2), 1968, 100–107.

[Jun94] D. Jungnickel. Graphen, Netzwerke und Algorithmen. BI-Wissenschaftsverlag,3. Aufl., 1994. ISBN 3-411-14263-4.

[Lip12] U. Lipeck. Vorlesung Datenstrukturen und Algorithmen, WiSe 2011/12. URLhttp://www.dbs.uni-hannover.de/dsalg1112.html.

[Mee91] J. H. Meeus. Astronomical Algorithms. Willmann-Bell, Incorporated, 1991.ISBN 0943396352.

[Pap80] U. Pape. Algorithm 562: Shortest Path Lengths [H]. ACM Trans. Math.Softw., 6(3), 1980, 450–455. ISSN 0098-3500. URL http://doi.acm.org/

10.1145/355900.355919.

[RT09] F. Ramm, J. Topf. OpenStreetMap - Die freie Weltkarte nutzen und mitge-stalten. Lehmanns Media, Berlin, 2. Aufl., 2009. ISBN 978-3-86541-320-8.

[Sch00] W. Schmid. Berechnung kurzester Wege in Straßennetzen mit Wegeverboten.Dissertation, Universitat Stuttgart, Holzgartenstr. 16, 70174 Stuttgart, 2000.URL http://elib.uni-stuttgart.de/opus/volltexte/2002/1190.

[WL12] H. Warneke, U. W. Lipeck. Ein Partitionierungsdienst fur GeographischeDaten in Raumlichen Datenbanken. Proceedings of the 24th GI-Workshop”Grundlagen von Datenbanken 2012”, 2012, 35–40. URL http://ceur-ws.

org/Vol-850/paper_warneke.pdf.

81

http://www.dbs.uni-hannover.de/dsalg1112.html

http://doi.acm.org/10.1145/355900.355919

http://doi.acm.org/10.1145/355900.355919

http://elib.uni-stuttgart.de/opus/volltexte/2002/1190

http://ceur-ws.org/Vol-850/paper_warneke.pdf

http://ceur-ws.org/Vol-850/paper_warneke.pdf

Erklarung

Hiermit versichere ich, dass ich die vorliegende Arbeit und die zugehorige Implemen-tierung selbststandig verfasst und dabei nur die angegebenen Quellen und Hilfsmittelverwendet habe.

Hannover, 15. Juli 2012

David Bormann

82

Documents

Routenberechnung mit partitionierten Straˇendaten · ten Daten skizziert. Es werden graphentheoretische Begri e diskutiert und verschiedene Algorithmen zur Weg ndung vorgestellt