Vorausschauende Optimierung für stochastisch-dynamische Tourenplanung

von Dr. Ninja Scherr (Gewinnerin des YRA 2025)

In den letzten Jahren stieg die Beliebtheit von Services, die noch am Tag der Bestellung ausgeführt werden. Serviceprovider bedienen dann häufig eine Mischung aus vorzeitig bekannten und spontanen Kund:innen. Wir betrachten das tägliche Optimierungsproblem eines solchen Anbieters. Vorab bekannte Anfragen müssen bedient werden, spontane Anfragen können abgelehnt werden. In dem betrachteten Problem wird über die Touren von mehreren Mitarbeitenden entschieden, die im Depot losfahren, während der Schicht Kund:innen besuchen und danach ins Depot zurückkehren.

In diesem Problem erfolgt eine initiale Tourenplanung, die die bekannten Kund:innen beinhaltet. Bei neuen Anfragen muss entschieden werden, ob sie bedient werden und in welcher Tour. Das Problem besteht daher aus der initialen Tourenplanung und dem dynamischen Entscheidungsprozesses.

Für die initiale Tourenplanung modifizieren wir einen bekannten Algorithmus, der versucht, möglichst kurze Touren zu erstellen. Dabei kann es passieren, dass alle Kund:innen in einer Fahrzeugtour untergebracht werden und die übrigen Fahrzeuge keine Tour erhalten. Unsere Modifikation nutzt einen Faktor, der bestimmt, ob alle Kund:innen in einer Tour bedient werden dürfen oder ob gleichmäßig ausgelastete Touren entstehen müssen (oder auch eine Lösung dazwischen).

Für die dynamischen Entscheidungen entwerfen wir einen Ansatz, der Simulationen nutzt, um zu lernen, welche Entscheidung in welcher Situation getroffen werden soll. In diesem Problem gibt es unendlich viele verschiedene Situationen, weswegen wir drei verschiedene Aggregationen der Situationsinformationen vorschlagen.

Die Ergebnisse zeigen, dass eine Aggregation mit wenig Information ausreicht, wenn die initialen Touren eher ausgeglichen sind. Wenn die initialen Touren eher ungleich ausgelastet sind, sollte zusätzliche Information genutzt werden, um Situationen zu beschreiben. Außerdem ist es vorteilhaft, wenn die initialen Touren möglichst ausgeglichen sind.