Research Group Geoinformation


Home | Research | Publications | Download | Projects | Teaching | Staff



... to the Cartography Group

Sedlak Michael

Linking Yellow Pages into Vehicle Navigation Systems


Automobilnavigationssysteme (ANS) ersetzen immer öfter Straßenkarten. Dadurch kann der Fahrer seine Aufmerksamkeit dem Verkehr widmen, anstatt auf der Karte nach dem weiteren Weg zu suchen. Als Start- und Endpunkt einer Reise gibt man je eine Adresse an. Eine logische Weiterentwicklung wäre die Einbindung eines Branchenverzeichnisses in Navigationssysteme. Der Autofahrer kann damit Zwischenpunkte in Form von Branchen angeben: Auf dem Weg von A nach B möchte ich bei einem Blumengeschäft vorbei.

Zur Lösung einer solchen Aufgabe müssen verschiedene Algorithmen entwickelt werden, die die zugrundeliegenden Straßen- und Branchendaten verknüpfen und die Suche nach dem besten Weg durchführen. Dazu müssen zunächst die Straßendaten in einem Straßengraph gespeichert werden. Dieser Graph ist gerichtet und gewichtet, wobei sich die Richtung aus den Richtungsfahrbahnen der einzelnen Straßen ergibt. Die Gewichte im Graphen lassen sich aus mehreren Faktoren errechnen, die mit den Straßendaten gespeichert sind: aus der Länge eines Straßenabschnittes, der Straßenkategorie, der Benutzergruppe, aus temporären Fahrverboten oder aus der Tageszeit. Welche Faktoren bei der Berechnung tatsächlich verwendet werden, hängt von der Komplexität des Datensatzes ab. Es gibt Gewichte für die Kanten, die die Straßenabschnitte darstellen, aber auch für die Knoten, die Kreuzungen repräsentieren.

Nach der Eingabe der Start-, End- und eventueller Zwischenpunkte müssen diese Orte im Straßengraph gefunden werden. Dies geschieht mit Hilfe einer Address Matching-Funktion. Sind Branchen als Zwischenpunkte angegeben, so müssen zunächst die Adressen sämtlicher Firmen dieser Branchen ermittelt werden. Die Anzahl der Firmen einer Branche kann sehr groß werden und damit auch die Zeit zur Berechnung einer Route. Daher müssen aus allen Firmen einer Branche jene ausgewählt werden, die zusammen mit den bisher bekannten Punkten den kürzesten Weg ergeben. Die Heuristiken, die diese Auswahl durchführen, arbeiten mit verschiedenen Methoden, je nach Präferenz des Benutzers. Dieser kann beispielsweise verlangen, daß alle Branchen-Zwischenpunkte in der Nähe des Startpunktes liegen. In diesem Fall wird eine kreisförmige Zelle um den Startpunkt gelegt und alle Firmen bzw. deren zugeordnete Kanten untersucht, ob sie innerhalb dieses Kreises liegen. Andere Möglichkeiten sind ein Kreis um den Endpunkt, die Suche nach Firmen, die auf dem Weg vom Start- zum Endpunkt liegen oder eine Pufferzone zwischen Start- und Endpunkt. Durch Heuristiken kann es passieren, daß die gefundene Route nur eine suboptimale ist.

Zur Berechnung einer Route bei freier Reihenfolge der Zwischenpunkte werden zunächst alle möglichen Kombinationen der fixen Punkte und der gefundenen Brancheneinträge aufgestellt. Dann werden für jede dieser Kombinationen mit Hilfe eines Traveling Salesman-Algorithmus alle möglichen Abfolgen der Zwischenpunkte berechnet und diejenige mit dem kürzesten Weg gespeichert. Jener Weg mit der kürzesten Länge unter allen berechneten wird als gefundene Route ausgegeben.

Die beschriebenen Algorithmen sind in einem Programm implementiert worden, das die Eingabe von Punkten in Form von Adressen oder Branchen, die Berechnung einer Route sowie die Ausgabe ebendieser ermöglicht.

Powered by CMSimple