Routenplaner

Routenplanung mit dem Algorithmus von Dijkstra

Routenplaner sind Programme, die einen Weg (eine Route) zwischen einem vorgegebenen Startort und einem vorgegebenen Zielort berechnen. Wir simulieren im Folgenden die Arbeitsweise eines Routenplaners mit Hilfe des Algorithmus von Dijkstra.

Zunächst betrachten wir das vereinfachte Autobahnnetz rund um Ludwigshafen und Mannheim.

Die Daten zu diesem Graphen findest du in der Datei graph_bab_lu_ma.xml.

Zur Simulation des Routenplaners benutzen wir die Implementierung des Algorithmus von Dijkstra (vgl. graph_dijkstra.txt) und das folgende Testprogramm:

from graph_dijkstra import *

# Erzeugung des Graph-Objekts
g = GraphDijkstra()
# Erzeugung der Knoten und Kanten aus einer GraphML-Datei
print('Autobahndaten werden geladen ...')
datei = open('graph_bab_lu_ma.xml', 'r')
xml_quelltext = datei.read()
g.graphmlToGraph(xml_quelltext) 
# Ausführung des Dijkstra-Algorithmus
start = 'Kreuz Frankenthal'
ziel = 'Kreuz Heidelberg'
print('kürzester Weg von', start, 'nach', ziel, ':')
(weg, laenge) = g.kuerzesterWegDijkstra(start, ziel)
for w in weg:
    print(w)
print('Weglänge:', laenge)

Für den hier angegebenen Start- und Zielknoten erhält man den folgenden Weg:

>>> 
Autobahndaten werden geladen ...
kürzester Weg von Kreuz Frankenthal nach Kreuz Heidelberg :
('Kreuz Frankenthal', 'Viernheimer Dreieck') ('A 6', 19.0)
('Viernheimer Dreieck', 'Viernheimer Kreuz') ('A 6', 4.0)
('Viernheimer Kreuz', 'Kreuz Mannheim') ('A 6', 7.0)
('Kreuz Mannheim', 'Kreuz Heidelberg') ('A 656', 8.0)
Weglänge: 38.0

Aufgabe 1

Teste selbst die Implementierung des Dijkstra-Algorithmus.

Ein Routenplaner für das Autobahnnetz in Deutschland

Interessanter und aufwendiger sind Routenplanungen im gesamten Autobahnnetz in Deutschland.

Quelle: http://de.wikipedia.org/wiki/Autobahn_%28Deutschland%29
Autor der Karte: M. Stadthaus

Die Daten zum gesamten Autobahnnetz in Deutschland findest du in der Datei graph_bab.xml. Beachte aber die folgenden Hinweise.

Die Daten zum Bundesautobahnnetz wurden vom Autobahnatlas übernommen und in das hier benutzte Format transformiert. Ergänzt wurden sie um Geo-Koordinaten vom OpenStreetMap-Projekt. Die Daten sind weder vollständig noch in allen Details korrekt. Zur realen Routenplanung im Bundesautobahnnetz sind sie daher nur bedingt geeignet. Wenn du offensichtliche Fehler findest, dann hilf bei der Beseitigung.

Beachte auch die Darstellung der Knoten in der Datei graph_bab.xml. Die Bezeichner der Autobahnausfahrten und Autobahnkreuze wurden vom Autobahnatlas übernommen und sind infolgedessen nur mit Großbuchstaben dargestellt. Da es vorkommt, dass Ausfahrten auf unterschiedlichen Autobahnen den gleichen Bezeichner haben (z.B. ROHRBACH - im Saarland und in der Pfalz), wurden die Bezeichner um die Angabe der Autobahn erweitert, so dass alle Knotenbezeichner eindeutig sind.

Aufgabe 2

Benutze die Daten zum Autobahnnetz in Deutschland, um den kürzesten Weg vom 'KREUZ FRANKENTHAL' zum 'KREUZ HEIDELBERG' bzw. von 'TRIER - VERTEILERKREIS (A 602)' nach 'KREUZ MÜNCHEN - WEST' zu bestimmen. Vergleiche die Ergebnisse auch mit denen, die ein professioneller Routenplaner liefert.

Aufgabe 3

Die Bestimmung kürzester Wege mit dem Algorithmus von Dijstra in der bisher gezeigten Form dauert - bei einer großen Datebasis - sehr lange. Woran liegt das? Entwickle Ideen, wie man den Suchaufwand verringern könnte. Versuche eventuell auch, diese Ideen umzusetzen.

Simulationsprogramm mit grafischer Benutzeroberfläche

Zur Veranschaulichung der gefundenen Routen benutzen wir ein Simulationsprogramm mit grafischer Benutzeroberfläche. Beachte, dass dieses Programm nicht die Qualitätsanforderungen an benutzerfreundliche Software erfüllt. So muss man als Benutzer z.B. genau wissen, wie die Knoten des Autobahngraphen bezeichnet sind. Du kannst gerne das Programm nach deinen Wünschen verbessern.

Aufgabe 2

(a) Lade den gepackten Ordner routenplaner_mit_gui.zip herunter und führe das Programm GUITestApp.py aus. Beachte, dass hier durchaus längere Wartezeiten beim Laden der Daten und bei der Suche des kürzesten Weges entstehen.

(b) Vergleiche die vom Simulationsprogramm gelieferten Daten auch mit den Ergebnissen realer Routenplaner.