Routenplanung – stets aktuell
Knobelaufgabe für Optimierer
Es ist die wohl bekannteste Knobelaufgabe für Optimierer – das Problem des Handlungsreisenden. Ein Vertreter soll eine bestimmte Anzahl von Orten aufsuchen und dabei einen möglichst kurzen Weg zurücklegen. Es geht aber noch komplizierter: Die Reisezeit soll möglichst gering sein, seine Gesprächspartner sollen nicht warten müssen und der Reisende soll dennoch viele Stationen pro Tag schaffen. Eine solche Aufgabe haben sich die Forscher im Projekt „Simple Fleet“ gestellt, das kürzlich gestartet wurde.
„Wir wollen ein Verfahren etablieren, mit dem klein- und mittelständische Unternehmen ihre Fahrzeugflotte optimal einsetzen können“, sagt der Projektleiter Rüdiger Ebendt vom Deutschen Zentrum für Luft- und Raumfahrt (DLR) in Berlin-Adlershof. Ein Beispiel könnte eine Großbäckerei sein, die ihre Fahrzeuge durch Berlin schickt, um Filialen mit Brot, Brötchen und Kuchen zu beliefern. In der traditionellen Logistik erhalten die Fahrer morgens ihre Routen, die sie in den folgenden Stunden abfahren. In dringenden Fällen ändert ein Disponent vielleicht noch hier und da etwas, doch das grobe Schema steht. „Wenn die Autos im Stau stehen, geht wertvolle Zeit verloren“, sagt Ebendt. „Durch aktuelle Änderungen, die an das jeweilige Verkehrsgeschehen angepasst sind, lässt sich noch einiges gewinnen.“
Der Verkehrsforscher denkt dabei nicht nur an Routenänderungen, sondern gegebenenfalls auch an Korrekturen in der sogenannten Stoppreihenfolge. Im Falle der Bäckerei hieße das, die Filialen in anderer Reihenfolge anzusteuern. Das kann nur gelingen, wenn die Computerprogramme für die Routenplanung aktuelle Verkehrsdaten erhalten. In Berlin und einigen wenigen weiteren Städten ist das kein Problem. Bereits vor Jahren haben die DLR-Verkehrsforscher hier ein System etabliert, das Statusmeldungen von 4.800 Taxis in der Stadt erfasst. Alle 30 Sekunden funken die Wagen ihre GPS-Position an einen Zentralrechner. Aus zwei aufeinanderfolgenden Datenpunkten eines Fahrzeuges lässt sich die Geschwindigkeit errechnen.
Aber die Forscher wollen es noch genauer. Sie erfassen auch den Fahrzeugstatus, der zum Beispiel besagt, ob das Taxi auf dem Weg zu einem Fahrgast ist oder dieser bereits eingestiegen ist. Denn das hat Einfluss auf die Fahrweise. „Wenn der Fahrer beispielsweise nach einem Fahrgast sucht, wird manchmal langsamer gefahren“, sagt Ebendt. Solche Effekte werden dann herausgerechnet. „Über Wochen und Monate entsteht so ein Datensatz, der den Geschwindigkeitsverlauf auf großen Straßen über einen typischen Tag abbildet“, sagt der DLR-Forscher. Anhand dieser Hinweise würde die Software in Berlin beispielsweise die Leipziger Straße morgens halb zehn sicher umgehen wollen. „Über die Echtzeitmessungen der Taxis erfahren wir zudem sehr schnell, wo gerade ein Stau ist.“ Anhand dieser Informationen optimiert die Software im Lauf des Tages die Routen immer wieder neu.
Dass das funktioniert, haben die Wissenschaftler bereits im Projekt „Smart Truck“ demonstriert. Damals wurden für ausgewählte Lieferfahrzeuge des Paketdienstleisters DHL die Routen mithilfe dieser „dynamischen Verkehrslenkung“ optimiert. Inzwischen wurde das Konzept auch auf die gelben Fahrzeuge im Gebiet Köln-Bonn übertragen und läuft auch in Berlin weiter.
Mit dem im Mai gestarteten Projekt „Simple Fleet“ sollen die Taxidaten weiteren Nutzern dienen. „Floating Car Data“, abgekürzt zu FCD, nennen die Forscher die preiswerte Ressource. „Wir wollen einerseits den Unternehmen die Verkehrsdaten verfügbar machen und sie zudem unterstützen, die für sie interessanten Dienste in die jeweilige Software zu integrieren“, erläutert Ebendt.
Je nach Branche könnten folgende Fragen besonders spannend sein: Wann trifft mein Fahrzeug beim Kunden ein? Wo befinden sich gerade sämtliche Fahrzeuge meiner Flotte? Wie viele Kilometer haben sie heute bereits zurückgelegt?
Simple Fleet ist nicht auf Berlin beschränkt. Die DLR-Forscher arbeiten parallel dazu an einem ähnlichen System für Wien und Athen.
Von Ralf Nestler für Adlershof Journal