Antizipierende Tourenplanung durch Approximative Dynamische Programmierung
Final Report Abstract
Zielsetzung des Projektes war, das Konzept der Approximativen Dynamischen Programmierung auf komplexere Problemstellungen des Vehicle Routings zu übertragen. Die bisherige Problemstellung wurde auf Erweiterungen hinsichtlich mehrperiodischer Planung, Kundenabbildung und Flottenmanagement untersucht. Aufgrund der Wahl einer kundenorientierten Zustandsraum-Modellierung wurde der Schwerpunkt auf die Kundenabbildung und die tagesübergreifende Planung gelegt. Durch die Attribute war eine Neukonzipierung des Zustandsraumes notwendig. Grundsätzlich wurde das Routing vom Lernprozess entkoppelt, um die Größe des Zustandsraumes zu reduzieren. Zum einen wurde mittels Clustering ein Zustands-Repräsentantensystem erzeugt. Hierbei wurden mittels Ähnlichkeitsmaß auftretende Zustände den Repräsentanten zugeordnet. Zum anderen wurde eine Zustandsbeschreibung definiert, die allein auf Zeitpunkt, zu bedienenden Kunden und freier Zelt basiert. Der Entscheidungsraum wurde durch Relaxationen eingeschränkt, um einen schnelleren Lernfortschritt zu erzielen. Die Variation bezüglich initialer Wertbelegung und Schrittgröße hatten kaum Einfluss auf den Lernprozess, welcher somit robust bezüglich Parametrisierung ist. Zur Evaluation der Ergebnisse wurden einige Heuristiken auf das Problem übertragen und weitere erstellt. Als Referenz wurde die Cost-Benefit-Heuristik gewählt, die Kosten und Nutzen des Hinzufügens eines neuen Kunden abwägt. Diese erreichte im Vergleich die besten Ergebnisse. Zusätzlich wurden Algorithmen zur Ermittlung einer ex post-Optimallösung implementiert. Es wurden unterschiedliche Instanzen generiert, die bezüglich Kundenanzahl, Zeitlimit und Kundenverteilung variieren. Für Instanzen mit wenigen Kunden erreichte ADP im Vergleich die besten Ergebnisse. Bei größeren Instanzen war weiterhin Antizipation möglich, allerdings konnte die Benchmark-Heuristik in einigen Fällen nicht übertroffen werden. Es konnte somit gezeigt werden, dass eine Übertragung der ADP auf komplexere Problemstellungen möglich ist. Zusätzlich ist der Lernerfolg signifikant vom zugehörigen Zustandsraum abhängig. Somit ist in der weiteren Forschung ein besonderer Fokus auf das Zustandsraum-Design zu legen.
Publications
- (2013). Modeling Customers in the Euclidean Plane for Routing Applications, Proceedings of the 14th EU/ME Workshop (pp. 98-103)
Ulmer, M.W., 8t Mattfeld, D.C.
