Schneller zum Ziel

Wie komme ich am schnellsten von A nach B? Um diese Frage zu beantworten, muss ein Navigationsgerät oder ein Routenplaner einen kürzesten Weg in einem großen Netzwerk berechnen. Für Straßennetzwerke wurde dazu in den letzten Jahren sehr viel geforscht und Lösungen gefunden, die im Bruchteil einer Sekunde Ergebnisse liefern. Für Netzwerke öffentlicher Verkehrsmittel versagten alle diese Lösungen bisher jedoch. Haltestellen, Abfahrts- und Ankunftszeiten, unterschiedliche Fahrpläne an Wochenenden und an Feiertagen, Pufferzeit für Umsteigen, Laufen zwischen Stationen – alles Umstände die die Berechnungen sehr aufwändig gestalten.

Prof. Dr. Hannah Bast, vom Lehrstuhl für Algorithmen und Datenstrukturen am Institut für Informatik, hat ein Verfahren entwickelt, das die Wegeberechnung um Größenordnungen schneller macht und neuerdings bei Google Maps eingesetzt wird. Dort kann man mit der Maus Start- und Zielpunkt einer Verbindung eingeben und in Echtzeit wird die beste Verbindung ausgegeben. Das funktioniert sogar in Städten wie Sao Paulo mit Tausenden von Buslinien und auf einem ganzen Kontinent wie Nordamerika.

„Der Durchbruch in unserer Arbeit war die Erkenntnis, dass es zwischen fast jedem Paar von Stationen, egal wie nah beieinander oder wie weit voneinander entfernt, nur sehr wenige Umsteigemuster gibt. Zwischen Freiburg und Zürich beispielsweise, sind alle optimalen Verbindungen entweder Direktzüge oder man steigt einmal in Basel um, egal an welchem Tag und egal zu welcher Tageszeit. “ erklärt Bast. Diese Umsteigemuster werden alle vorberechnet und geschickt komprimiert abgespeichert. Für das Netzwerk der gesamten Welt mit seinen Milliarden von Haltestellen und Verbindungsstrecken lässt sich das in zehn Gigabyte und somit einem ganz gewöhnlichen Rechner abspeichern. Der Suchaufwand zur Anfragezeit ist dann auf ein Minimum reduziert. Natascha Thoma-Widmann

Albert-Ludwigs-Universität Freiburg
Technische Fakultät

Institut für Informatik
Prof. Dr. Hannah Bast
Tel: 0761/203-8163
E-Mail: bast [a] informatik.uni-freiburg (p) de

Referentin PR/Marketing
Natascha Thoma-Widmann
Tel.: 0761/203-8056
E-Mail: thoma-widmann [a] tf.uni-freiburg (p) de
www.tf.uni-freiburg.de