Die Einbeziehung des Verkehrs VOR der Tourenoptimierung: ein kleines Detail, das alles verändert
- 1 April 2022
- 4 mins
Erläuterungen von Cédric Hervet, Head of Science bei Kardinal
Innerhalb der Logistikkette gestaltet sich die letzte Meile als Schauplatz der großen Herausforderungen: hier konzentrieren sich 30 % des Verkehrsaufkommens in Stadtzentren, 25 % der CO₂-Emissionen und 20 % der Gesamtkosten für eine Lieferung.
Die Tourenoptimierung senkt die Kosten durch die Optimierung der Ressourcen sowie die Reduzierung der gefahrenen Kilometer und positioniert sich angesichts dieser Herausforderungen als konkurrenzloses Mittel der Wahl.
Weil sich jedoch die Begebenheiten auf der letzten Meile ständig verändern, gestaltet sich die Optimierung auf diesem Abschnitt besonders schwierig: Der Verkehr und seine Schwankungen erschweren Tag für Tag die Einhaltung der Verpflichtungen, die die Transportunternehmen gegenüber ihren Kunden eingehen (z. B. die Einhaltung von Zeitfenstern).
Wie aber integrieren die verschiedenen Lösungen den Verkehr in ihre Tourenoptimierung? Und welche Auswirkungen hat es, ob der Verkehr vor oder nach der Optimierung in die Berechnungen miteinbezogen wird? In diesem Artikel finden Sie die Antworten unseres wissenschaftlichen Leiters, Cédric Hervet, zu diesem kleinen Detail, das alles verändert!
Wie funktioniert die herkömmliche Methode zur Einbeziehung des Verkehrs in die Tourenoptimierung?
Optimierungsalgorithmen stützen sich in ihren Berechnungen auf eine sogenannte „Distanzmatrix“. Hierbei handelt es sich um Daten, aus denen hervorgeht, wie lange und wie weit jedes zu optimierende Punktpaar in die eine oder andere Richtung voneinander entfernt ist. Darauf aufbauend versucht der Optimierungsalgorithmus, Touren zu ermitteln, die die zurückgelegte Distanz und/oder die Fahrzeit minimieren. In herkömmlichen Tourenoptimierungsmodellen ist die Distanzmatrix allerdings nicht zeitgebunden. Entsprechend wird die Fahrzeit und/oder Entfernung zwischen zwei Punkten – unabhängig von der Startzeit einer Tour – zu jedem beliebigen Zeitpunkt als gleichbleibend eingeschätzt.
Erst nach der Tourenoptimierung wird die ETA-Berechnung verfeinert, indem der vorhergesagte Verkehr an jedem Punkt der Tour miteinbezogen wird.
Um zu berücksichtigen, dass der tatsächliche Verkehr die Fahrzeiten mit hoher Wahrscheinlichkeit verlängern wird, und realistischere Lösungen zu erhalten, werden Korrekturen in Form von (mehr oder weniger ausgefeilten) Koeffizienten auf die Distanzmatrix angewendet. Doch auch in diesem Fall kann die Matrix Schwankungen im Verkehr nicht miteinbeziehen, da die Dauer zwischen den einzelnen Punkten den ganzen Tag über als gleichbleibend bewertet wird.
Was sind die Mängel einer solchen Lösung? Welche Probleme ergeben sich daraus?
Im Hinblick auf die Optimierung stellt die Nichteinbeziehung des Verkehrs vor der Tourenberechnung ein schwerwiegendes Problem dar, denn in der Realität hat der Verkehr – insbesondere in städtischen Gebieten – den ganzen Tag über starke Auswirkungen auf den möglichen Tourenverlauf. Speziell der Berufsverkehr, mit seinen Staus am Morgen und Abend, stellt immer wieder ein großes Hindernis dar. So kann die Fahrzeit zwischen zwei Punkten mitunter um das Ein- bis Vierfache variieren. Und während einige Strecken zu bestimmten Tageszeiten stark überlastet sind, sind andere zur gleichen Zeit womöglich weitaus weniger von den Auswirkungen des Verkehrs betroffen.
Wenn der Optimierungsalgorithmus die Verkehrsentwicklung für jedes Punktpaar schon vor der Optimierung kennt, kann er bestimmte Touren auf günstigere Zeiten verlegen und besonders überlastete Strecken zu bestimmten Tageszeiten ganz einfach meiden. Werden die Auswirkungen des Verkehrs auf die Tour erst im Nachhinein berechnet, können diese Schwankungen in der Planung nicht erfasst werden. Und so entstehen Touren, die durch zahlreiche Staus führen, Lieferzeitfenster falsch einschätzen und daher letztlich kaum leistungsfähig sind.
Warum gestaltet sich die Einbeziehung des Verkehrs vor der Optimierung so komplex?
Wenn die Auswirkungen des Verkehrs auf die Fahrzeiten realistisch eingeschätzt werden sollen, muss man davon ausgehen, dass sich diese Auswirkungen zu jedem Zeitpunkt und an jedem Ort unterscheiden.
Idealerweise sollte man daher für jedes zu planende Punktpaar und zu jeder Tageszeit (z. B. alle 10 Minuten an einem 8-Stunden-Arbeitstag = 48 Zeitabschnitte) ermitteln, wie sich der Verkehr auf den Tourenverlauf auswirkt. Bei einem relativ überschaubaren Problem, bei dem 500 Punkte geplant werden müssen, gibt es bereits 250.000 mögliche Routen. Diese wiederum müssen für alle 48 Zeitabschnitte des Tages errechnet werden, was insgesamt 12 Millionen mögliche Strecken ergibt – und eine mehrstündige Rechenzeit für den Entfernungsmesser. Bei Problematiken mit 5.000 bis 10.000 Punkten kann die Rechenzeit sogar mehrere Tage in Anspruch nehmen.
Ein derartiger Ansatz ist in der Praxis undenkbar. Insbesondere auf der letzten Meile ist eine Wartezeit von mehreren Stunden – bevor die Optimierung überhaupt beginnt – unrealistisch und steht im starken Widerspruch zu den tatsächlichen Anforderungen an eine Echtzeitoptimierung. Die Frage ist also: Wie erhält man realistische Verkehrsvorhersagen, die die Besonderheiten jeder Strecke und Tageszeit berücksichtigen, ohne dabei die Rechenzeit bei der Tourenoptimierung zu erhöhen?
Wie löst die Tourenoptimierung von Kardinal diese Problematik? Welche Vorteile entstehen daraus?
Unsere Optimierungslösung ist für die anspruchsvollsten Einsatzgebiete auf der letzten Meile im innerstädtischen Raum vorgesehen. Wir haben große Anstrengungen in die Entwicklung eines Optimierungssystems investiert, das die tatsächlichen Verkehrsverhältnisse umfassend berücksichtigt.
Mithilfe von künstlicher Intelligenz haben unsere Doktoren der angewandten Mathematik ein System entwickelt, das prädiktive Verkehrsdaten im großen Rahmen sammelt und aggregiert. Darauf aufbauend können wir im Vorfeld der Optimierung für jeden Zeitpunkt und jede Strecke abschätzen, wie lange eine bestimmte Fahrt dauern wird – und zwar mit einer Rechenzeit, die mit der von Lösungen ohne Verkehrseinbeziehung nahezu identisch ist.
Konkret bedeutet dies, dass wir im Voraus genau wissen, wie lange eine Fahrt mit Verkehr zwischen den Punkten A und B an einem Dienstag um 10 Uhr dauern wird. Das Verkehrsvorhersagemodell ermittelt die spezifischen Daten für die Strecke A → B für diesen Tag und für diese Uhrzeit. Entsprechend den Verkehrsauswirkungen können sich die Ergebnisse für eine Fahrt von A nach C um 10 Uhr an einem Dienstag und für eine Fahrt von A nach B um 16 Uhr an einem Freitag stark unterscheiden. Unsere Machine-Learning-Algorithmen aktualisieren diese Daten täglich und stellen unseren Kunden realistische Touren zur Verfügung.
Lösung zur kontinuierlichen Tourenoptimierung
Beispiel für eine Verkehrsentwicklungskurve zwischen zwei nördlich von Grenoble gelegenen Gemeinden, auf einem stark überlasteten Abschnitt der A49:
Dieses Modell ist für einen Dienstag kalibriert, würde sich also an einem anderen Wochentag anders gestalten. Wir aktualisieren die Modelle alle zwei Wochen automatisch, um Entwicklungen, Bauarbeiten oder außergewöhnliche Situationen (z. B. Covid-19) umfassend zu berücksichtigen.
Auf dieser Route beträgt die Fahrzeit ohne Verkehr etwa 15 Minuten. In der Praxis ist diese Strecke (A49) jedoch häufig überlastet und beeinträchtigt den Verkehr – insbesondere für Lastwagen. Über den Tag hinweg liegt die tatsächliche Fahrzeit zwischen 27 und 29 Minuten, mit zwei leichten Spitzen, die den Zeiten des größten Verkehrsaufkommens am Tag entsprechen.
Beispiel für eine Verkehrsentwicklungskurve zwischen dem Norden und dem Süden von Grenoble, über die Ringstraße:
Diese beiden Beispiele zeigen, dass man die Verkehrsentwicklung für zwei Fahrten differenziert betrachten und so die verkehrsbedingten Besonderheiten des Straßennetzes im Zeitverlauf erfassen kann.
Unsere Algorithmen zur Tourenoptimierung sind darauf ausgelegt, auf Grundlage von zeitgebundenen Distanzmatrizen zu arbeiten. So können sie bei Bedarf Touren erstellen, die überlastete Straßen zu Spitzenzeiten meiden, und wann immer möglich die Nebenzeiten nutzen, um städtische Ballungsgebiete zu beliefern. Auf diese Weise profitieren unsere Nutzer von leistungsfähigeren und zuverlässigeren – weil realistischeren – Touren.
