Constraint Programming basierte Lokale Suche für die Tourenplanung

Diplom-/Masterarbeit

Tourenplanungsprobleme, die sich in der industriellen und speditionellen Praxis oder auch bei Paketdienstleistern stellen, sind extrem vielfältig und ähneln sich häufig nur in ihren Grundzügen. In der Regel unterscheiden sie sich durch sehr heterogene zusätzliche Anforderungen: So tauchen neben den üblichen Zeitfensterrestriktionen, Restriktionen bzgl. der Fahrzeug- oder Fahrerqualifikation auf, neben den gebräuchlichen Zielkriterien sollen zeitlich sowie distanzmäßig möglichst ausgeglichene oder „faire“ Touren geplant werden oder es müssen die gesetzlichen Regelungen zu Lenk- und Ruhezeiten berücksichtigt werden, etc.. Tourenplanungsprobleme, die sich aufgrund solcher „Real-Welt-Restriktionen“ nicht in die typischen VRP-Problemklassen einteilen lassen, werden als Rich Vehicle Routing Probleme kategorisiert und finden in der wissenschaftlichen Literatur immer mehr Berücksichtigung.

Aufgrund seiner sehr hohen Flexibilität bietet sich Constraint Programming (CP) zur Abbildung dieser „Real-Welt“ Restriktionen an, doch ein vollständiges Durchsuchen des Lösungsraumes mit CP-Techniken ist aufgrund der Problemkomplexität von Tourenplanungsproblemen schwierig. In der kombinatorischen Optimierung sind eher Verfahren, die sich auf ein lokales Durchsuchen des Lösungsraumes - in der Regel gesteuert von einer Metaheuristik - beschränken, zielführend. Eine erfolgversprechende Kombination der für Tourenplanungsproblemen üblichen lokalen Suche und des Constraint Programming stellt die Large Neighborhood Search (LNS) dar. Hier werden immer wieder Kunden aus einer gültigen Lösung entfernt und mit Hilfe von CP-Techniken wieder eingefügt. So lassen sich die Vorteile beider Methoden, „exploration“ und „propagation“, gemeinsam nutzen.

Ziel der Arbeit ist es, aufbauend auf Erkenntnissen aus der Literatur und Vorarbeiten am FZI, einen LNS-Ansatz für Tourenplanungsprobleme mit Zeitfenstern zu implementieren. Ein Schwerpunkt der Arbeit liegt auf der Evaluierung verschiedener aus der Literatur bekannter CP-Modellierungen des Problems und auf der Untersuchung möglicher unterer Schranken, ein weiterer auf der Beurteilung sinnvoller Auswahlstrategien zum Entfernen der Kunden aus der gültigen Lösung. Neben der Implementierung wird daher insbesondere Wert auf ein aussagekräftiges Experimentdesign zur Messung der Performance gelegt. Die Tests können auf der aus der Literatur bekannten „Benchmark-Problemen“ durchgeführt werden. Um den Nachweis der Flexibilität des Systems zu führen, soll zudem das Modell so angepasst werden, dass statt der zu fahrenden Distanz der CO2 Verbrauch der Fahrzeuge zum Zielkriterium wird.

Die Umsetzung des Algorithmus erfolgt in C++ und Gecode, einer mächtigen, freien C++ Bibliothek zur Entwicklung von CP Applikationen. Neben der Implementierung des Systems sind eine Ausarbeitung anzufertigen und ein Vortrag zu halten.

Ausschreibung als pdf

Diplom-/Masterarbeit

In dieser Arbeit soll die Kombination aus Constraint Programming und Large Neighborhood Search aufbauend auf Vorarbeiten am FZI weiter untersucht werden. Schwerpunkte der Arbeit sind:

• Evaluierung verschiedener aus der Literatur bekannter CP-Modellierungen für VRP mit Zeitfenstern
• Untersuchung unterer Schranken an das Optimum einer Instanz
• Beurteilung sinnvoller Strategien zur Auswahl des aus der gültigen Lösung zu entfernenden Kundens
• Implementierung in C++ und Gecode, einer mächtigen Bibliothek zur Entwicklung von CP-Applikationen
• Aussagekräftiges Experimentdesign zur Performancemessung auf aus der Literatur bekannten Instanzen
• Nachweis der Flexibilität des Systems durch Anpassung des Zielkriteriums: Minimierung des CO2-Verbrauchs der Fahrzeuge statt Minimierung der Tourenlänge
• Ausarbeitung und Vortrag

• Grundkenntnisse in Algorithmik und solide Programmierkenntnisse
• erwünscht: Interesse an Fragestellungen aus der Tourenplanung
• nicht erforderlich: Vorkenntnisse in Constraint Programming

Dr. Julian Dibbelt, Anne Meyer

Webpage FZI

• Gilbert Laporte: Fifty Years of Vehicle Routing. In: Transportation Science 43(4): 408-416 (2009) LINK
• Paul Shaw: Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. CP 1998:417-431 LINK
• Philip Kilby and Paul Shaw: Vehicle routing. In: F. Rossi, P. Van Beek, and T. Walsh, editors, Handbook of Constraint Programming, Foundations of Artificial Intelligence, chapter 23, pages 801-836. Elsevier, 2006.