Die Max-Planck Gesellschaft in Deutschand ist zuständig für Grundlagenforschung und wird beim Thema Navi diesem Anspruch auch voll gerecht. “Fast Routing in Road Networks with Transit Nodes” lautet der Titel eines in der Zeitschrift Science erschienenen Aufsatzes. Neben dem Max-Planck-Institut für Informatik in Saarbrücken waren auch Wissenschaftler der Universität Karlsruhe an den dort beschriebenen Arbeiten beteiligt. Einer der Autoren – Dominik Schultes – hat dankenswerter Weise die bisher verfügbaren Veröffentlichungen im Netz hier zusammen gestellt.

Nach eigenem Bekunden können die Forscher die Rechengeschwindigkeit von Navis um den Faktor 100 erhöhen und zwar nicht durch mehr Hardwareleistung, sondern mittels eines intelligenteren Algorithmus. Sie nehmen sich damit dem Grundproblem aller Routenplaner an: Die Unlogik eines historisch gewachsenen Straßennetzes. Es gibt aufgrund dieser Tatsache nämlich keine logisch-mathematische Lösung für die Aufgabe den kürzesten oder schnellsten Weg von A nach B zu finden. Das Straßennetz entzieht sich jeder Berechnungsformel.

Theoretisch muss ein Navi deshalb alle denkbaren Wegverbindungen ausprobieren und durch Vergleich die optimale Lösung herausfinden. Eine zeitaufwändige Angelegenheit, wenn die Software keine Methode kennt, die vollkommen unwahrscheinlichen und indiskutablen Strecken (von Berlin nach Hamburg eine Wegführung über München zum Beispiel) von vornherein auszuschließen. In diesem möglichst intelligenten und umfassenden Auschluss theoretisch möglicher, aber unsinniger Lösungen lagen bisher die bekannten Optimierungspotenziale von Navis. (So richtig zeigt sich das Problem ja immer dann, wenn man mit einem Navi die berechnete Strecke verlasst und das Gerät eine Neuberechnung vornimmt, oder das eben nicht tut, sondern stur eine Wende verlangt. Letzteres könnte durchaus an einem eher simpel gestrickten Suchalgorithmus liegen.)

Die Wissenschaftler der genannten Institute haben nun einen neuen Ansatz entwickelt. Sie setzen an der Anzahl der zu berücksichtigenden Knotenpunkte im Straßenetz an. Aus Sicht eines Navis ist das Straßenetz nämlich zunächts nichts anderes als ein Netz von sich kreuzenden Linien. Die Knotenpunkte der Linien sind für die Routenfindung entscheidend. Prinzipiell prüft ein herkömmlicher Rechenalgorithmus ausgehend vom Startpunkt an jedem Knotenpunkt neu die sich daraus ergebenden Wegmöglichkeiten, um jedesmal alle unwahrscheinlichen Varianten (im Sinne bestimmter Parameter, die eine Strecke als vom Nutzer unerwünscht kennzeichnen) auszuschließen. Man kann dieses Navi-Prinzip bisweilen erkennnen, wenn so ein Gerät an einer Kreuzung überflüssigerweise die Richtung “geradeaus” angibt, denn dann wird gerade so ein Knoten passiert, für den offenbar von einigen möglichen Wegführungen genau jene herausgepickt wurde, die “geradeaus” führt.

Die Experten haben nun versucht, die Zahl der zu prüfenden Knoten drastisch zu reduzieren, indem sie im Straßennetz entscheidende Transitknoten identifizierten, über die eine Vielzahl von Strecken zwangsläufig führen. Man kennt das Prinzip aus eigenem Erleben: Vollkommen egal, wo man von zu Hause aus hinfährt, man fährt aus dem eigenen Ort höchtens auf zwei oder drei unterschiedlichen Wegen hinaus.

Auf diese Weise wurden aus 20 Millionen Knoten im europäischen Straßennetz knapp 11.000. Ist die grobe Wegführung zwischen diesen Punkten berechnet folgt in einem zweiten Rechenschritt die Wegführung zwischen Transitknoten zweiter Ordnung. Das sind rund 300.000 Punkte, von denen aber aufgrund des bereits festgelegten groben Weges nur wenige geprüft werden müssen. Der gleiche Vorgang in einem dritten Schritt. Hier verbleiben nun rund drei Millionen Transitknoten, von denen wiederum aufgrund der zu diesem Zeitpunkt bereits berechneten Strecke die Mehrzahl gar nicht mehr berücksichtigt werden muss. Falls jetzt noch Streckenabschnitte fehlen, können die dann vorzunehmenden wenigen Streckenvergleiche mit den bislang benutzten Algorithmen locker bewältig werden. Die Konzentration auf entscheidende Transitpunkte und eine Hierarchisierung der Berechnung in drei Schritten sorgen somit zusammen für die um den Faktor 100 schnellere Berechnung einer Route gegenüber heutigen Navigationssystemen.

Jetzt bleibt noch abzuwarten, wann diese Forschungen den Weg aus dem Informatik-Labor herausfinden, aber in Karlsruhe sitzt ja die PTV AG, jenes auf Verkehrs- und Routenplanungen spezialisierte Unternehmen, das über beste Beziehungen zur örtlichen Uni verfügen dürfte. Die können die Forscher ja mal in ihre Entwicklungsabteilung lotsen (falls die PTV nicht ohnehin ihre Finger im Spiel hat).