Gestaltung

Navigation

Daten

Die Aufgabe

Bereitstellung eines Moduls zur Berechnung „optimaler“ RoutenWas ist optimal ?

Beantwortung ist nutzerabhängigRennradfahrer -> guter Strassenbelag, schöne Landschaft entlang der RouteMountainbike -> Landschaft, möglichst große Steigungen, gerne unbefestigte WegeKulturinteressierter Wochenendurlauber -> Möglichst alle Sehenswürdigkeiten in kurzer Zeit besuchen (kürzeste Wege)

Die Aufgabe

Was ist eine Route ?Routen können aus mehrerenZwangspunkten bestehen

AnforderungenWegberechnung muß parameterabhängig sein Es müssen evt. mehrere Teilrouten errechnet werden

Lösungskonzept

Dimensionen der LösungAlgorithmen zur Bestimmung „optimaler“ WegeDatenstruktur und Datengrundlage Art der Implementierung

Algorithmen

„Travelling-Salesman-Problem“Optimale Lösung

Berechnung des besten Weges zwischen jeweils 2 Wegpunkten

- sehr rechenaufwändig:n*(n-1) Verbindungen müssen berechnet werden(n-1)! – Routen müssen verglichen werden

Pragmatische LösungNutzer gibt Punkte in gewünschter Reihenfolge vor

Nur noch n-1 Teilrouten zu berechnen

Algorithmen

Berechnung „optimaler“ TeilroutenFloyd

Vorberechnung aller kürzesten Wege und Speicherung in einer Wegmatrix

Danzig & Dijkstra

Berechnung des „optimalen“ Weges zwischen zwei Knoten - Min( Kantengewichte)

Algorithmen

Realisierung nutzerspezifisch „optimaler“ Routen mit Danzig & Dijkstra

Algorithmus minimiert KantengewichtBerücksichtigung von Nutzervorlieben mittels einer Kanten-Kosten-Funktion

Umfangreiche Kantenattributierung notwendig

Kantenkostenfunktion

Anforderungen:Basis sollte die Weglänge seinGleicher Einfluß der einzelnen AttributeEinfache Erweiterbarkeit erstrebenswert

Typbildung + Bewertung der Relevanz der einzelnen Attribute

Kantenkostenfunktion

Umsetzung:Ausprägungen jedes Attributs wird eine Typzahl zugeordnet:3 = schlecht2 = gut1 = sehr gut

Der Nutzer kann die Relevanz jedes Attributs durch eine Bewertungszahl beeinflussen:-1 = lege Wert auf Gegenteil 0 = ist mir egal1 = würde ich bevorzugen2 = sollte unbedingt gegeben sein

Kantenkostenfunktion

G(k)=[ (Bewertungszahl * Typzahl) + n*3+1)] * Länge

Vermeidung negativer Kantenkosten

Kantenkostenfunktion

Kantenkostenfunktion

Kantenkostenfunktion

Kantenkostenfunktion

Programmentwicklung

Erstellung einer VBA - Applikation (DLL ) zu AutoCAD2000Java – Klassen mit direkter Kommunikation zu „Servlet“

Routenberechnung dauert pro Teilroutemax. 0.5 s[Intel Pentium 450MHZ (GIS-Labor)]

Längsprofil

Auf Wunsch wird ein Längsprofil entlang der Route errechnet und mit Hilfe eines Java-Applets in einer HTML – Seite eingebunden

Anbindung GPS

Download der GPS-Datei

Auswählen der Maximalpunktzahl

Angabe eines Dateiformats

Anbindung GPS

H SOFTWARE NAMEI Fahrradroutenplaner Bonn H R DATUM IDX DA DF DX DY DZM E WGS 84 100 +0.000000e+00 +0.000000e+00 +0.000000e+00 +0.000000e H COORDINATE SYSTEMU LAT LON DM R TESTROUTEinhdddmm.mmm H IDNT LATITUDE LONGITUDE DATE TIME ALT DESCRIPTIONW 111111 N5045.985 E00708.001 17-AUG-01 09:34:08 -9999 XXXXXXXXXW 211111 N5046.101 E00707.832 17-AUG-01 09:34:08 -9999 XXXXXXXXXW 311111 N5046.073 E00707.820 17-AUG-01 09:34:08 -9999 XXXXXXXXXW 411111 N5045.956 E00707.745 17-AUG-01 09:34:08 -9999 XXXXXXXXX

$GPWPL,5043.32,N,0705.28,E,KARTOINSTITUT*2F$GPWPL,5043.43,N,0705.07,E,NUSSALLEE*21$GPWPL,5043.39,N,0704.57,E,MENSA*26$GPWPL,5043.31,N,0705.03,E,SCHUPPEN*7C$GPWPL,5043.27,N,0705.13,E,CARL-TROLL-STR*7C$GPWPL,5043.32,N,0705.21,E,KATZENBURGWEG*21$GPWPL,5043.30,N,0705.27,E,BOTGARTEN*2F

PCX-5 NMEA

Dateiformate

Gestaltung

Navigation

Daten