Mathematische Berechnungen sichern, dass wir gut von A nach B finden. Logistisch schwierig wird es, wenn mehrere Orte zugleich im Spiel sind.
Immer der Nase nach ist auch für einen Routenplaner nicht die beste Idee. Denn mitunter kann auch die richtige Richtung auf die falsche Fährte führen. „Will ich etwa von Wien nach Linz, orientiere ich mich Richtung Westen. Das kann aber auch falsch sein, nämlich dann, wenn die für mich nächste Autobahnauffahrt im Osten liegt“, sagt Günther Raidl vom Institut für Computergraphik und Algorithmen der TU Wien. Es braucht also Berechnungen im Hintergrund, die mehr aussagen als das Bauchgefühl.
Die Rede ist von Algorithmen, den „Kochrezepten“ der Informatiker und Mathematiker, die sich mit Logistik befassen. „Wenn ich eine Speise zubereite, brauche ich gewisse Zutaten. Das Rezept sagt mir, wie sie zu verwenden sind“, erklärt Raidl. „Zutaten“ der Wissenschaftler sind zum Beispiel das Straßennetzwerk und Verkehrsdaten. Was also ein Jamie Oliver für die Kochkunst ist, sind die Forscher und deren Algorithmen für den Computer: Sie sagen ihm, was er tun muss.
Netzwerk der Straßen
Zunächst werden die Straßen in einem Routenplaner als Graphen gespeichert. Jede Kreuzung und jeder möglicherweise interessante Punkt ist als Knoten dargestellt. Dazu sind Daten zu Distanz und den erlaubten Geschwindigkeiten abgelegt.
Dann geht der Routenplaner schrittweise vor: Vom Startpunkt aus berechnet er alle unmittelbar erreichbaren Knoten und speichert diese zusammen mit der Information, wie sie am Besten zu erreichen sind. Aus diesem Pool an Möglichkeiten wählt das System dann den jeweils nächsten Knoten, und berechnet von diesem aus wiederum alle weiteren, unmittelbar erreichbaren Knotenpunkte usw., bis der Endpunkt erreicht ist. Doch welcher Weg ist der beste? Die schnellste Variante muss nicht die kürzeste sein, manche Lenker wollen Autobahnen vermeiden. Solche Wünsche geben sie ins System ein. Gibt es Verzögerungen, etwa durch Stau oder Unfall, fließt das zusätzlich in die Berechnung ein.
Von einem Punkt zu einem anderen zu kommen sei aber grundsätzlich gut berechenbar, sagt Raidl. Als Forscher fordern ihn andere Aufgaben mehr: etwa Logistikanwendungen, bei denen die Wissenschaftler Sicherheitsfirmen helfen, die besten Routen für ihren Wachdienst zu finden.
Oder die Forscher berechnen, wie es gelingt, dass die Stationen eines städtischen Fahrradverleihsystems wie Citybike Wien immer mit ausreichend Fahrrädern versorgt sind. Dazu müssen die Betreiber die Fahrräder nämlich regelmäßig umverteilen. „Da stecken eine komplexe Prognose und ausgeklügelte Routenplanung dahinter“, sagt Raidl. Computerbasierte Lösungen sparen den Betreibern Zeit und Kosten und den Nutzern Wartezeit und Ärger.
Lieber schnell als optimal
„Immer wenn nicht nur ein Weg von A nach B gefragt ist, sondern mehrere Orte besucht werden sollen und deren Reihenfolge nicht vorgegeben ist, wird die Routenplanung aus algorithmischer Sicht ganz erheblich komplexer“, so Raidl. Denn dann steigt der Rechenbedarf für eine optimale Lösung sehr rasch. Dann sind die Forscher auf sogenannte Heuristiken angewiesen: Näherungsverfahren, die zwar sehr gute Lösungen, aber nicht die bestmögliche liefern. Dies dafür aber weit rascher und daher mit dem größeren Nutzen für die Praxis.
Senden Sie Fragen an: wissen@diepresse.com
("Die Presse", Print-Ausgabe, 20.02.2016)