Constraint-Programming-basierte lokale Suche für die Tourenplanung

Bachelorarbeit, Masterarbeit

Themen-Schwerpunkt: Logistik und Supply-Chain-Optimierung
Studiengänge: Informatik, Informationswirtschaft

Umfeld

Tourenplanungsprobleme (Vehicle Routing Problem, VRP), 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 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 Komplexität von Tourenplanungsproblemen schwierig. In der kombinatorischen Optimierung haben sich Verfahren als zielführend erwiesen, die sich, gesteuert von einer Metaheuristik, auf ein lokales Durchsuchen des Lösungsraumes beschränken. Eine erfolgversprechende Kombination dieser üblichen lokalen Suche und des Constraint Programming stellt die Large Neighborhood Search (LNS) dar. Hierbei werden iterativ 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.

Aufgaben

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 der aus der gültigen Lösung zu entfernenden Kunden
  • 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

Wir bieten

  • Ein interdisziplinäres Arbeitsumfeld mit Partnern aus Wissenschaft, Wirtschaft und Anwendern
  • Eine wirtschafts-/industrienahe Arbeitsumgebung und -organisation
  • Eine angenehme Arbeitsatmosphäre

Wir erwarten

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

Ihre Bewerbung

  • Aktueller Notenauszug
  • Tabellarischer Lebenslauf

Weitere Informationen