Mit dem Einzug der Navigationsgeräte in die Autos ist vieles einfacher geworden. Über die Wegfindung muss man sich als Autofahrer keine Gedanken mehr machen, sondern kann sich ganz entspannt auf die Anweisungen verlassen, die aus dem kleinen Kästchen kommen. Aber ganz so entspannt ist es dann doch nicht immer. Wie oft kommt es vor, dass man sich denkt „Warum soll ich denn jetzt hier abbiegen? Das ist doch bestimmt nicht der schnellste Weg.” Oder es passiert, dass man versehentlich eine Abbiegung verpasst und dann darauf warten muss, bis eine neue Route berechnet wurde. Solche Situationen in Zukunft vermeiden zu können, war das Ziel meiner Dissertation: Ich entwickelte Routenplanungsverfahren, die einen optimalen Weg bestimmen und dies so schnell tun, dass die Berechnung schon fertig ist, bevor man überhaupt merkt, dass sie angefangen hat.
Erstaunlicherweise handelt es sich dabei um ein sehr aktives Forschungsfeld, „erstaunlich” deshalb, weil die Grundlagen bereits vor 50 Jahren geschaffen wurden – in der noch jungen Informatik ist dies eine sehr lange Zeitspanne. Der niederländische Wissenschaftler Edsger W. Dijkstra stellte 1959 seinen Kürzeste-Wege-Algorithmus vor, auf dem ein Großteil der heute zum Einsatz kommenden Verfahren basiert. Die Grundidee ist, mit dem Startpunkt zu beginnen und nacheinander auf systematische Weise den schnellsten Weg zu allen anderen Straßenkreuzungen zu bestimmen, und zwar in der Reihenfolge, wie die Entfernung vom Startpunkt zunimmt. Abbrechen kann man, sobald der Zielpunkt erreicht wurde. Dann hat man die Gewissheit, dass es keinen schnelleren Weg geben kann, da alle noch nicht betrachteten Straßenkreuzungen schon weiter weg sind als das Ziel.
Das Verfahren von Dijkstra ist zuverlässig und einfach umzusetzen, hat aber einen entscheidenden Nachteil: Es ist zu langsam, wenn man es zum Beispiel auf einem Navigationsgerät einsetzen möchte oder für einen Routenplanungsdienst, der im Internet tausenden Benutzern zur Verfügung steht. Dass es Verbesserungspotenzial gibt, kann man sich leicht an einem Beispiel klarmachen, einer Autofahrt von Karlsruhe nach Hamburg. Auf der A 5 wird man dabei an Frankfurt am Main vorbeikommen. Man wird vielleicht einmal nach rechts aus dem Fenster schauen und die Skyline bewundern, man wird aber sicher nicht auf die Idee kommen, die Autobahn zu verlassen und einen günstigeren Weg durch die Innenstadt zu suchen. Genau dies versucht aber Dijkstras Algorithmus: Systematisch betrachtet er alle Straßenkreuzungen der Stadt Frankfurt (und später auch alle Straßenkreuzungen von Kassel und Hannover), bevor er feststellen kann, dass es am besten ist, auf der Autobahn zu bleiben.
Als Mensch hingegen sind wir es gewohnt, die hierarchischen Eigenschaften von Straßennetzen bei unseren Planungen auszunutzen: Wir wissen einfach, dass wir auf Autobahnen in der Regel schneller vorankommen und die Benutzung von kleinen Ortsstraßen nur selten Vorteile bringt. Wie aber können wir dem Computer dieses intuitive Wissen beibringen? Und insbesondere wie stellen wir sicher, dass das Programm auch mit Ausnahmen richtig umgeht? Denn natürlich gibt es auch Fälle, wo es sich doch lohnen kann, die Autobahn zu verlassen, um eine Abkürzung zu nehmen. Es gibt mehrere Lösungen für dieses Problem: Diverse hierarchische Verfahren wurden entwickelt, deren Korrektheit man sogar mathematisch beweisen kann. Das schnellste unter ihnen möchte ich näher vorstellen. Die Grundidee lässt sich am einfachsten am Beispiel von Karlsruhe einführen. Obwohl ich über drei Jahre in der Stadt wohnte, kannte ich mich als Autofahrer innerhalb der Stadt kaum aus – ich nahm lieber die Straßenbahn. Für weite Fahrten nutzte ich aber gerne mein Fahrzeug und stellte dabei fest, dass ich mir, egal wo ich auch hinwollte, nur drei verschiedene Wege merken musste: Wenn das Ziel irgendwo im Norden oder Osten lag, fuhr ich zur A 5, Auffahrt Karlsruhe-Durlach, für den Süden ebenfalls zur A 5, allerdings zur Auffahrt Karlsruhe-Süd, und für Ziele im Westen musste ich den Rhein überqueren, so dass ich die einzige Brücke weit und breit ansteuerte. Interessanterweise lässt sich meine Beobachtung prinzipiell auf beliebige Startpunkte in ganz Europa übertragen: Mit Hilfe eines Computerprogramms identifizierte ich im europäischen Straßennetz 10 000 besonders wichtige Straßenkreuzungen, ein kleiner Bruchteil der insgesamt 18 Millionen Kreuzungen, die in elektronischen Karten heutzutage erfasst sind. Eine automatisch durchgeführte Analyse des Straßennetzes ergab dann, dass für jeden möglichen Startpunkt im Durchschnitt zehn dieser wichtigen Kreuzungen für Fernreisen relevant sind.
FERNREISE GETEILT DURCH DREI
Wir können also festhalten: Bei Fernreisen verlassen wir unseren Startpunkt immer über einen von wenigen in Frage kommenden wichtigen Verkehrsknotenpunkten. Diesen nennen wir die Startauffahrt, was nicht bedeuten soll, dass es sich unbedingt immer um eine Autobahnauffahrt handeln muss. In großen Teilen Norwegens gibt es zum Beispiel gar keine Autobahnen, trotzdem gibt es auch dort wichtige Verkehrsknotenpunkte, die als Startauffahrt in Frage kommen. Eine analoge Aussage gilt natürlich auch für das Ziel, das wir ebenfalls immer über einen von wenigen wichtigen Verkehrsknotenpunkten erreichen, den wir die Zielabfahrt nennen.
Bei Fernreisen besteht die Route also gewissermaßen aus drei Abschnitten: erstens dem Weg vom Startpunkt zur Startauffahrt, zweitens dem Weg von der Startauffahrt zur Zielabfahrt und drittens dem Weg von der Zielabfahrt zum Zielpunkt. Diese Beobachtungen können wir nun folgendermaßen ausnutzen: Wir berechnen für jeden möglichen Startpunkt alle Startauffahrten und speichern diese ab. Dadurch, dass jeweils nur wenige Startauffahrten in Frage kommen, hält sich der Gesamtspeicherbedarf noch in Grenzen. Analoges gilt wieder für die Zielabfahrten. Darüber hinaus berechnen wir die schnellsten Wege zwischen allen wichtigen Verkehrsknotenpunkten und speichern die ermittelten Reisezeiten in einer großen Tabelle, die 10 000 mal 10 000 Einträge umfasst. Mit all diesen Informationen ausgestattet, wird die Routenplanung plötzlich zum Kinderspiel: Nehmen wir wieder an, ich möchte von Karlsruhe nach Hamburg fahren, mein Startpunkt hat 3 mögliche Startauffahrten und mein Zielpunkt hat 15 verschiedene Zielabfahrten. Die möglichen Startauffahrten und Zielabfahrten kann ich nun sofort nachschlagen, da ich diese ja im Vorfeld abgespeichert habe. Nun probiere ich nacheinander alle 3 mal 15 Kombinationen von Startauffahrten und Zielabfahrten. In jedem der 45 Fälle schlage ich in der großen Tabelle den Abstand von Startauffahrt zu Zielabfahrt nach und addiere dazu die Reisezeit vom Start zur Startauffahrt und von der Zielabfahrt zum Ziel. Auf diese Weise, nämlich durch Aufsummieren der Reisezeiten der drei Wegabschnitte, erhalte ich die Gesamtreisezeit des betrachteten Weges. Unter den 45 Möglichkeiten kann ich mir dann ganz einfach die schnellste aussuchen. Dieses Ausprobieren der wenigen Möglichkeiten geht rasend schnell. Im Schnitt benötigt das Verfahren auf einem 2,0-Gigahertz-Rechner vier millionstel Sekunden, um die optimale Reisezeit zu bestimmen – das ist über eine Million mal schneller als Dijkstras Verfahren.
EINSATZPLANUNG VON LKW-Flotten
Um nicht nur die Reisezeit, sondern auch eine komplette Beschreibung der Route zu ermitteln, benötigt man 0,00015 Sekunden. Diese Zeiten gelten allerdings nur, wenn man die Vorberechnung der großen Tabelle und aller Startauffahrten und Zielabfahren bereits erledigt hat – was vergleichsweise aufwendig ist und über eine Stunde dauert. Dies ist aber nicht schlimm, denn im Prinzip müssen wir die Analyse des Straßennetzes nur einmal pro Vierteljahr durchführen, so häufig wird nämlich gewöhnlich das Kartenmaterial aktualisiert. Dazwischen können wir drei Monate lang die vorberechneten Daten nutzen, um beliebig viele Routen extrem schnell zu bestimmen.
Einen wichtigen Aspekt dürfen wir aber nicht unterschlagen: Das beschriebene Verfahren funktioniert so nur für Fernreisen. Wenn ich doch mal innerhalb von Karlsruhe mit dem Auto unterwegs bin, werde ich bestimmt nicht erst zu einer der drei Autobahnauffahrten fahren und dann von dort aus mein Ziel ansteuern. Solche Reisen im Nahbereich müssen also vom Programm erkannt und gesondert behandelt werden. Da aber gerade die Fälle, bei denen Start und Ziel nahe beieinander liegen, besonders einfach sind, bereitet dies keine großen Schwierigkeiten. Der Speicherbedarf der vorberechneten Daten ist nicht gerade klein, aber immerhin passen sie auf eine DVD. Für einfache Navigationsgeräte, die über eine kleinere Speicherkapazität verfügen, bietet sich die Verwendung anderer hierarchischer Verfahren an, die zwar etwas langsamer sind, aber dafür weniger Speicherplatz benötigen. Das vorgestellte, extrem schnelle Verfahren ist besonders interessant, wenn es sich um Anwendungen handelt, bei denen eine riesige Zahl an Routenplanungsanfragen bearbeitet werden muss, zum Beispiel bei der Einsatzplanung von Lkw-Flotten oder bei Verkehrssimulationen. ■
von Dominik Schultes
