24
GIS-Seminar WS00/01 Routen- und Tourenplanung - Motivation - Bedürfnisse - Spezifische Anforderungen - Algorithmen - Systemfunktionen mit ArcInfo - Bewertung von Thorsten Berka

GIS-Seminar WS00/01 Routen- und Tourenplanung

Embed Size (px)

DESCRIPTION

GIS-Seminar WS00/01 Routen- und Tourenplanung. - Motivation - Bedürfnisse - Spezifische Anforderungen - Algorithmen - Systemfunktionen mit ArcInfo - Bewertung. von Thorsten Berka. Motivation. - PowerPoint PPT Presentation

Citation preview

Page 1: GIS-Seminar WS00/01 Routen- und  Tourenplanung

GIS-Seminar WS00/01

Routen- und Tourenplanung- Motivation

- Bedürfnisse

- Spezifische

Anforderungen

- Algorithmen

- Systemfunktionen mit

ArcInfo

- Bewertung

von Thorsten Berka

Page 2: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Motivation

Motivation ist der Wunsch, optimal im Sinne seiner persönlichen Bedürfnisse und der gewählten Fortbewegungsart von seinem Standort zu einem bestimmten Zielort zu gelangen.

Oder wie Konfuzius sagen würde: „Der Weg ist das Ziel.“

Page 3: GIS-Seminar WS00/01 Routen- und  Tourenplanung

BedürfnisseSind hier beispielsweise, möglichst

• anzukommen• schnell am Ziel zu sein• wenig Energie (z.B.: Körperkraft, Benzin...) zu verbrauchen• wenig Gefahrenstellen zu passieren• über bestimmte andere Zielpunkte zu kommen• ...

Page 4: GIS-Seminar WS00/01 Routen- und  Tourenplanung

FortbewegungsartenGemeint sind

• Fahrrad• Auto• zu Fuß• Schiff• Eisenbahn• Flugzeug• ...

Page 5: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Spezifische Anforderungenfür die Routenplanung sind Straßennetze, die enthalten könnten:

- Straßennamen

- Entfernungen

- Höhenunterschiede

- Fahrradwege

- Fußgängerzonen

- Tempolimits

- Baustellen

- Höhen von Tunneln und Unterführungen

- ...

Page 6: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Algorithmus von DijkstraDer Algorithmus von Dijkstra dient dazu, die kürzesten Entfernungen von einem Punkt aus zu allen anderen Punkten einer vorgegebenen Menge zu finden.

Realisierung:AdjazenzmatrixAdjazenzliste

Page 7: GIS-Seminar WS00/01 Routen- und  Tourenplanung

B C D E F G A(A) 11 ∞ 12 13 ∞ ∞11 E1 = 11

P1 = B B --- 10 8 ∞ ∞ ∞ _________________________________________A(A,B) --- 21 12 13 ∞ ∞ 12 E2 = 12

P2 = DD --- ∞ --- ∞ 6 ∞__________________________________________A(A,B,D) --- 21 --- 13 18 ∞13 E3 = 13

P3 = EE --- ∞ --- --- 7 ∞__________________________________________A(A,B,D,E) --- 21 --- --- 18 ∞18 E4 = 18

P4 = FF --- ∞ --- --- --- 9____________________________________________A(A,B,D,E,F) --- 21 --- --- --- 27 21 E5 = 21

P5 = CC --- --- --- --- --- 12____________________________________________A(A,B,C,..,F) --- --- --- --- --- 2727 E6 = 27

P6 = G

Algorithmus von Dijkstra

Page 8: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Algorithmus von Dijkstra

1.) Ausgangspunkt A2.) Auflistung der direkten Verbindungen3.) Vergleich der Abständeund Ermittlung des nächstgelegenen Punktes4.) Aufnahme des neuenPunktes in die Menge und erneute Auflistung der Strecken unter Berücksichtigung diesesPunktes 5.) Eventuell Eliminierung „doppelter“ Strecken und so weiter...

Page 9: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Algorithmus von Dijkstra

Vorteile des Algorithmus von Dijkstra:

- Leicht zu implementieren

- sehr effizienter Algorithmus

Problem dieses Algorithmus:

- Nur ein Kriterium (meistens die Euklidsche Entfernung) wird berücksichtigt

- zwei verschiedene Kanten zwischen zwei Punkten möglich

Page 10: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Komplexität

Komplexität

Nimmt zu

Nimmt abO (log n) logarithmisch

O (n) linear

O (n log n)

O (n²) quadratisch

O (nª) polynomiell

O (an) exponentiell

O (nn)}kritisch

}machbar

Dijkstra

TSP

Page 11: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Traveling Salesman Problem

Beim TSP geht es darum,durch eine Anzahl vonvorgegebenen Städten eine Route zu legen, so daß ein möglichst kurzer Zyklus entsteht.

Oder: Ein Kraftfahrer muß zu verschiedenen Städten je ein Produkt liefern. Zum Schluß muß er wieder zumLager zurückkehren.Wie schafft er das am schnellsten?

Page 12: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Traveling Salesman ProblemVoraussetzungen: - Lagekoordinaten der Sehenswürdigkeiten

- alle Sehenswürdigkeiten sind miteinanderverbunden

Damit gibt es (n-1)! mögliche Routen.

Anzahl der Anzahl derSehenswürdigkeiten möglichen Routen

5 24 6 120 7 720 8 5.040 9 40.320 10 362.880 11 3.628.800 12 39.916.800 13 479.001.600 14 6.227.020.800 15 87.178.291.200 20 121.645.100.408.832.000 50 608.281.864.034.268.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000

Page 13: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Traveling Salesman Problem

Zwei Arten von Algorithmen:

- Systematische Algorithmen

- Heuristische Algorithmen

- Lokal Search

- The Elastic Net

Heuristische Algorithmen:

Page 14: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Traveling Salesman ProblemLokal Search:

Erst einmal müssen für Lokal Search einige Voraussetzungen erfüllt sein, damit sie arbeitet werden können.

1.) Methode zur Generierung einer Anfangslösung u

2.) Kostenfunktion f(u)

3.) Operationsziel

4.) Nachbarschaftsfunktion N(u)

Page 15: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Traveling Salesman ProblemLokal Search:

Programmschema von LS:

Initialize (u);

while not terminate (u) do

u´ := generate (u);

if accept (u´) then

u := u´

Startlösung

Abbruchkriterium

Auswahlverfahrender Lösungen

- iterativer Algorithmus

- generiert Lösungen aus der Nachbarschaft von u

- Vergleich dieser mit der aktuellen Lösung u´

Page 16: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Traveling Salesman ProblemLokal Search:

Es gibt einzelne Untertypen von Lokal Search, welche sichvor allem durch das Auswahlverfahren der Lösungen unter-scheiden. Das sind:

- Ramdom Walk

- Simple Descent (Hill Climbing)

- Steepest Descent

- Simulated Annealing

- Tabu Search

Page 17: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Traveling Salesman ProblemLokal Search:

- Simple Descent (Hill Climbing):

- klassisches Verfahren

- Vergleichslösung zufällig aus Nachbarschaft

- Lösung wird übernommen, wenn f(u´) < f(u)

- dann u´ := u

Page 18: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Traveling Salesman ProblemLokal Search:

- Simulated Annealing:

- Erweiterung von Simple Descent

- Akzeptanzniveau gesenkt

- auch u´ mit f(u´) > f(u) können bei hinreichend kleinem | f(u´) - f(u) | zu u gesetzt werden

- jetzt Ermittlung und Vergleich mehrerer Minima möglich

Page 20: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Traveling Salesman ProblemThe Elastic Net:

- interativer Algorithmus

- Funktionsweise:

- Ein Kreis bestehend aus vielen Punkten wird über die Karte mit den Städten gelegt.

- Jeder Punkt wird der Reihe nach durch zwei Kräfte beeinflußt

- Die erste bewegt ihn zur nächstgelegenen Stadt - Die zweite zieht ihn zu seinen jeweiligen Nachbarn.

http://nuweb.jinr.dubna.su/~filipova/tsp.htmlO Elastic Net

Page 21: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Routenplanung mit ArcInfo

Voraussetzungen sind gegeben:

Ist Routenplanung mit ArcInfo möglich?

- Features entsprechen Kantenkosten

- Knoten, Kanten und Features ergeben Netzwerke (=>Adjazenzliste)

Für uns wichtige Prozeduren:

- Bestimmung des kürzesten Weges zwischen zwei Punkten

- Ausschließen bestimmter Kanten möglich

- Route durch mehrere Punkte bedingt möglich

Page 22: GIS-Seminar WS00/01 Routen- und  Tourenplanung

BewertungWie könnte Routenplanung in Zukunft aussehen?

- Globale Route mittels TSP-Algorithmen

- Lokal zwischen zwei benachbarten Punkten mit Algorithmus von Dijkstra

- Ermittlung der Kantenkosten im Vorfeld mit einer anwenderspezifischen Formel

Kantenkosten = α * Distanz + β * Steigung + γ * Panorama +...

Für Fahrradbote: α >> β >> γFür Oma (zum Einkauf): β > α >> γFür Tourist: γ >> β >= α

Page 23: GIS-Seminar WS00/01 Routen- und  Tourenplanung

Route zur GIS-TourHinfahrt 14 km:

Loser-Route 11 km:

Winner-Route 16 km:

Kaffee-Route 21 km:

Heavy-Route 29 km:

Page 24: GIS-Seminar WS00/01 Routen- und  Tourenplanung

The End ?