Aktuelle Themen

 

Ausschreibung

 

Ein Framework für das Vehicle Routing Problem mit dynamisch eingefügten Zwischenstopps und dessen Anwendung auf das Absetzkipperproblem

Die Arbeit wird von einem Mitarbeiter der PTV AG in Karlsruhe betreut. Die Arbeit wird idealerweise direkt in Karlsruhe bearbeitet werden. Dort kann auf einer bestehenden Codebasis aufgesetzt werden.

Im Rahmen dieser Abschlussarbeit soll ein theoretisches Framework für VRP-Varianten entwickelt werden, die folgende Gemeinsamkeit haben: Entlang Tour müssen neben Auftragsstopps (beispielsweise Abhol- oder Lieferstopps) spezielle Zwischenstopps eingeplant werden, damit die Tour gültig ist. In seltenen Fällen wird mehr als ein Zwischenstopp angefahren.

Ein Problem mit dieser Eigenschaft ist das Absetzkipperproblem: Mit dem Absetzkipper werden leere Schuttmulden zu Kunden gebracht. In der Regel werden dort wieder volle Mulden mitgenommen und sogleich zu einer Entsorgungsstelle gefahren. Anschließend kann die leere Mulde beim nächsten Kunden abgesetzt werden. Schwierig wird das Problem durch den Umstand, dass es Mulden in zwei Größen (verschiedene DIN) gibt, wobei jedes Fahrzeug beide Muldentypen transportieren kann (homogene Flotte). Es kann passieren, dass eine leere Mulde zunächst an eine Ladestelle gefahren und dort eine andere Mulde aufgeladen werden muss, wenn der nächste Kunde einen anderen Muldentyp benötigt. Bei diesem einfachen Fall gibt es nur eine Ladestelle (hier
Depot genannt) und das Fahrzeug muss genau dann dorthin fahren, wenn der nächste Kunde eine andere Mulde benötigt als geladen ist.

In der Arbeit soll ein theoretisches Framework entwickelt werden, mit dem sich solche Probleme lösen lassen. Nach Implementierung eines Lösungsverfahrens für das Absetzkipperproblem, soll anhand generierter Testinstanzen die Effektivität untersucht werden. Grundsätzlich sollen verschiedene weitere Probleme mit der obigen Eigenschaft mit dem Framework lösbar sein und in der Arbeit besprochen werden (jeweils eine einfache Variante des EVRP und des Truck-und-Trailer-Problems).

Bei Interesse senden Sie bitte eine E-Mail inklusive Lebenslauf und aktuellem Notenspiegel an .

 
 

Ausschreibung

 

Der Lin-Kernighan-Nachbarschaftsoperator für das Vehicle Routing Problem mit Zeitfenstern

Das Capacitated Vehicle Routing Problem (CVRP) befasst sich mit der Aufgabe, mit einer Flotte von Fahrzeugen Bedarfe von Kunden kostenminimal zu decken. Dabei muss jeder Kunde genau einmal besucht werden, Fahrzeugrouten starten und enden am Depot und die Fahrzeugkapazitäten müssen eingehalten werden. Das VRP with Time Windows (VRPTW) stellt eine Erweiterung des CVRPs dar und fordert zusätzlich, dass die Belieferung der Kunden innerhalb von vorgegebenen Zeitfenstern erfolgt.

Zur heuristischen Lösung des VRPTWs wird häufig lokale Suche verwendet. Eine durch eine Konstruktionsheuristik erzeugte Startlösung wird dabei iterativ durch die Anwendung von Nachbarschaftsoperatoren verbessert. Der Lin-Kernighan-Nachbarschaftsoperator löscht und erzeugt schrittweise Kanten, sodass die Summe der Teilverbesserungen positiv bleibt.

Im Rahmen dieser Masterarbeit soll der Lin-Kernighan-Operator für die Lösung des VRPTWs in eine lokale Suche integriert werden. Dabei soll eine verallgemeinerte Zielfunktion verwendet werden, die Verletzungen der Nebenbedingungen zulässt und mit Hilfe von Strafkosten behandelt und so der Suche ermöglicht, unzulässige Lösungen zu betrachten. Die Suche mit dem LK-Operator wird stark beschleunigt, indem nur Teilmoves, die einen positivem Effekt auf die Kostenfunktion haben, evaluiert werden. Da die Bewertung der Teilmoves nun auch von der Einhaltung der Zeitfenster abhängt, diese aber für unvollständige Touren gar nicht bestimmt werden kann, ist eine zentrale Frage der Arbeit, wie potenziell unzulässige Teilmoves im Rahmen der Suche mit dem LK-Operator bewertet werden können.

Für die Bearbeitung dieses Themas sind Programmierkenntnisse von Vorteil. Bei Interesse schreiben Sie bitte eine E-Mail an .

 
 

Learning good starting solutions for local search algorithms

Local-search-based algorithms are widely used to solve vehicle routing problems (VRPs). Starting with an initial solution, the iterative application of so-called neighborhood operators modifies the solution until a local optimum is reached. To escape from these, metaheuristics that rely on local search often use some sort of diversification mechanism. Over the last decades, many different diversification methods have been developed, which, e.g., rely on randomized multi-starts or perturbation steps. Boyan and Moore (2000) introduced the idea of trying to learn good starting solutions by generating an evaluation function that predicts the outcome of a local search given a specific starting solution. They developed the so-called STAGE algorithm that alternates local search and learning steps. Features are thereby used to represent solutions in a compact fashion and serve as input to the evaluation function. Even though the STAGE algorithm has already been successfully applied to combinatorial optimization problems like the bin-packing problem, there is no application to VRPs yet.

The goal of this master thesis is to continue on previous work at the chair and to improve the performance of our version of the STAGE algorithm to solve multi-depot VRPs. Precisely, the following questions shall be addressed:

  • Are there additional features beyond those we have investigated to characterize VRP solutions and how do they perform?
  • Which neighborhood operators should be used to perform the local search? Which should be used to obtain good neighboring solutions according to the evaluation function?
  • Which machine learning model should be used to realize the evaluation function (linear, polynomial regression, …)?

Programming skills are beneficial for working on this topic. If you are interested, please feel free to write an email to schroeder@dpo.rwth-aachen.de.