Robuste dynamische Tourenplanung

Ausgangssituation

Die Tourenplanung befasst sich mit der Aufgabenstellung, Transportaufträge zu Fahrzeugen zuzuordnen (»Clustering«) und für jedes Fahrzeug eine optimale Reihenfolge der Start- und Zielpunkte zu bestimmen (»Routing«). Meistens müssen auch die Ankunfts- und Abfahrtszeiten für die besuchten Punkte ermittelt werden (»Scheduling«). Bei der Erstellung der Tourenpläne sind unterschiedliche Bedingungen zu beachten, wie z. B. Zeitfenster für Liefer- bzw. Abholaufträge, Verfügbarkeiten und Kapazitäten der Fahrzeuge, Fahrzeitregelungen für die Fahrer oder Eignung von Fahrzeugtypen für Aufträge.

Die Tourenplanung muss häufig in einem dynamischen Umfeld durchgeführt werden: Die Situationen und Bedingungen, unter denen Tourenpläne erstellt und durchgeführt werden, unterliegen ständig Veränderungen. Nicht alle Informationen, die eine Probleminstanz beschreiben, liegen a priori vor, sondern es gibt unbekannte oder unvollständige und über die Zeit veränderliche Informationen. Neue Informationen gehen in Form von Ereignissen erst während der Ausführung der Tourenpläne in Echtzeit ein und können bzw. müssen dann unmittelbar verarbeitet werden. Beispiele solcher Ereignisse sind

  • das Eintreffen neuer Transportaufträge,
  • die Stornierung oder Änderung von Aufträgen,
  • das Nicht-Antreffen von zu bedienenden Kunden,
  • Verspätungen gegenüber dem Plan durch verlängerte Fahrt- oder Aufenthaltszeiten sowie
  • der Ausfall von Fahrzeugen.

Lösungszugang

Es werden Modelle und Algorithmen für die robuste dynamische Tourenplanung entwickelt, die im Rahmen eines Softwareprototyps implementiert werden. Mit diesem System ist es zum einen möglich, auf Veränderungen während der Planung und Durchführung automatisiert und in Echtzeit zu reagieren. Zum anderen wird eine neue Qualität der Tourenplanung dadurch erreicht, dass vorausschauend in Bezug auf ungewisse Informationen und mögliche Ereignisse geplant wird und Pläne erstellt werden, die hinsichtlich notwendiger Änderungen robust sind.

Planung in Echtzeit

Eine wesentliche Bedingung für den erfolgreichen praktischen Einsatz des Systems zur dynamischen Tourenplanung ist dessen Echtzeitfähigkeit. Auf viele der genannten Ereignisse muss der Anwender der Tourenplanung zeitnah reagieren. Dies trifft in besonderem Maße im Anwendungsbereich Nahverkehr zu. Die verwendeten Verfahren und Algorithmen sind daher darauf ausgelegt, schnelle Antworten in Echtzeit zu liefern.
 

Berücksichtigung von Ungewissheiten

Die explizite Berücksichtigung der dynamischen Aspekte der Tourenplanung, also die Einbeziehung der verschiedenen Ungewissheiten, steht im Mittelpunkt des neuen Planungs- systems. Anstatt wie üblich nur unter Verwendung bekannter Informationen zu planen, sollen ungewisse Informationen und mögliche Ereignisse bereits vorausschauend bewertet und in die Entscheidungen einbezogen werden. Dadurch erreicht man, dass mögliche zukünftige Ereignisse bereits vor ihrem möglichen Eintritt berücksichtigt werden, so dass aufwändige spätere Korrekturmaßnahmen vermieden werden können.
 

Robustheit von Tourenplänen

Durch die entwickelten Planungsmethoden wird eine hohe Robustheit der erstellten und veränderten Tourenpläne erreicht. Das heißt, es wird durch das Softwaresystem sichergestellt, dass bei kleinen Änderungen der Situation auch nur kleine Änderungen in den Tourenplänen erzeugt werden. Diese Eigenschaft trägt zur Erhöhung der Akzeptanz des Planungssystems durch die Anwender bei und ist in vielen Fällen auch eine Voraussetzung für die organisatorische Umsetzung der Planungsergebnisse.
 

RoDyTour – Gewiss Ungewiss

Der Gegner: der robuste dynamische Tourenplaner.
Die Aufgabe: schnelles Einsammeln aller Pakete.
Der Haken: der gewiss ungewisse Stau.

 

Einsatzbereich

Potenzielle Anwender des dynamischen Tourenplanungssystems sind Unternehmen, welche einen großen Anteil an Transportaufträgen zu erledigen haben, die bereits kurz nach ihrer Bekanntgabe auszuführen sind oder die, die viele Aufträge verarbeiten müssen, die kurzfristig storniert oder verändert werden. Die Entwicklung des Logistikmarktes und insbeson- dere der Transportbranche zeigt deutlich, dass der Anteil der zeitkritischen Sendungen zunimmt. Unternehmen aus dieser Branche stehen daher vermehrt vor der Herausforderung, Dienstleistungen in zeitlicher Hinsicht zu flexibilisieren, ohne dabei gleichzeitig höhere Kosten in Kauf nehmen zu müssen.

Beispielhafte Anwendungsfälle sind:

  • Paket- und Expressdienste
  • Sammelgutspeditionen
  • Entsendung von Kundendienst- und Technikmitarbeitern
  • Transport von Flüssiggasen
  • Einsatz von Entsorgungsfahrzeugen