next up previous contents
Next: Sonderforschungsbereich ,,Umwelt`` Up: Anwendungsprojekte Previous: Anwendungsprojekte

Online-Routing in großen Straßennetzen

Der Markt für Fahrzeug-Navigationssysteme hat in den letzten Jahren zunehmend an Bedeutung gewonnen. Fast jeder Automobilhersteller von Modellen der Oberklasse und der gehobenen Mittelklasse bietet seinen Kunden einen solchen elektronischen Piloten an, der den Fahrer mit Hilfe von Display und akustischen Anweisungen individuell zum Fahrtziel leitet.

Während die Routenführung bei den Geräten der ersten Generation in erster Linie auf statischen Daten in Form einer digitalisierten Straßenkarte auf CD-ROM basierte, sind neuere Geräte in der Lage, aktuelle Staumeldungen, die über das Mobilfunknetz oder Radio übertragen werden, miteinzubeziehen. Verbunden mit dem Engagement verschiedener privatwirtschaftlicher Unternehmen und staatlicher Stellen zur Schaffung einer zumindest in Ansätzen flächendeckenden Informationsinfrastruktur für die aktuelle Verkehrslage soll dadurch in naher Zukunft das individuelle Routen von Verkehrsteilnehmern auf Basis von Online-Daten ermöglicht werden.

Für den Bereich der eigentlichen Routenberechnung bedarf es dazu intelligenter Strategien, da bei der praktischen Anwendung vorgeschlagene Routen hinreichend schnell gefunden werden müssen und mit der tatsächlichen schnellsten Route dabei soweit wie möglich übereinstimmen müssen.

Das darunter liegende Problem der Bestimmung von kürzesten Wegen in Graphen ist eine der grundlegenden und bestuntersuchten Fragestellungen in der kombinatorischen Optimierung. Zu den Charakteristiken des Problems auf realen Straßengraphen gehört die Komplexität des Netzwerkes als rechen- und speicherintensiver Faktor sowie die spezielle Stuktur dieser Graphen als Ansatzpunkt für effiziente Verfahren.

Aufbauend auf unseren Ergebnissen aus einem Projekt innerhalb des von der DFG geförderten Schwerpunktprogrammes ,,Echtzeitoptimierung großer Systeme ``werden von uns algorithmische Verfahren entwickelt, die die stark hierarchische Struktur (Autobahnen - Bundesstraßen - Landstraßen) der Graphen und die gegebene Straßengeometrie mitberücksichtigen.

Im Hinblick auf das Routen von Verkehrsteilnehmern auf Basis von Online-Daten interessiert darüber hinaus, in welcher Weise bereits generierte Lösungen von dynamischen Veränderungen der Verkehrssituation betroffen sind. Die von uns in diesem Zusammenhang herangezogenen Analysen zur Robustheit kürzester Wege zielen darauf, effiziente Alternativen zur vollständigen Neuberechnung der Route zu entwickeln.

Ein weiterer Arbeitsschwerpunkt ist die geeignete Beschreibung der zu beobachtenden zeitlichen Dynamik in Straßennetzen. Da sich die Erfassung von aktuellen Verkehrsdaten bisher und in der nahen Zukunft in erster Linie auf das Autobahnnetz beschränkt, müssen bei der Routenbestimmung für den überwiegenden Teil des Straßnnetzes Annahmen über die Verkehrssituation getroffen werden, die dennoch von entscheidender Bedeutung für die gefundenen kürzesten Wege sind. Zu diesen Annahmen zählen sowohl zugrundegelegte Durchschnittsgeschwindigkeiten als auch die Auswirkungen von gemeldeten Staus auf umliegende Straßen, für die keine Online-Daten zur Verfügung stehen. Um für diese Art von Fragestellungen realitätsnahe Antworten bereitstellen zu können, wird auf die an unserem Institut entwickelte Verkehrssimulation zurückgegriffen, da sich mit Ihrer Hilfe die Dynamik des Straßenverkehrs auch in hinreichend großem Maßstab sehr gut nachbilden läßt.


next up previous contents
Next: Sonderforschungsbereich ,,Umwelt`` Up: Anwendungsprojekte Previous: Anwendungsprojekte
Webmaster<www@zpr.uni-koeln.de>
1999-07-28