Abschlussarbeiten am DPO

 

Es werden laufend aktuelle Themen vergeben, bei Interesse senden Sie bitte ihren Lebenslauf und einen aktuellen Leistungsspiegel an .

Die Betreuung von Praxisarbeiten in Kooperation mit Unternehmen ist nach Absprache möglich. Sollte auf Seiten Ihres Unternehmens Interesse an einer Zusammenarbeit bestehen, nehmen Sie bitte Kontakt mit uns auf, bevor Sie mit dem Unternehmen ein Thema fest vereinbaren.

Zu vergebende Themen

 

Time-Dependent Truck Driver Scheduling and Routing with Two Types of Breaks


Given a sequence of customers, the task of a truck driver is to visit each of these within certain time windows. At the same time, truck drivers must take breaks on a regular basis. In order to take a break, drivers have to look for an appropriate place where to park their vehicle. We consider the problem of finding a shortest path in a network
and a corresponding schedule such that every customer is visited in time, applicable break rules are respected, and every break is taken either at a customer or at a parking location. This is called the truck driver scheduling and routing problem. The goal of this master thesis is to develop both an exact and a heuristic solution method for a variant of this problem where

  • driving times on the edges of the network depend on the time of day, and
  • short breaks (lunch breaks) and long breaks (nightly rests) need to be distinguished.

Diese Arbeit wird gemeinsam mit der PTV Group betreut. Falls Sie an der Bearbeitung dieses Themas interessiert sind, kontaktieren Sie bitte . Ihr Ansprechpartner bei PTV ist .

 

Simultane Routenplanung für Kommissionierer und fahrerlose Transportsysteme

Fahrerlose Transportfahrzeuge (engl. Automatic Guided Vehicles, kurz AGVs) werden in Warenlagern für den Transport von Waren eingesetzt. In dem hier betrachteten Szenario kommissionieren mehrere menschliche Kommissionierer Aufträge in einem Warenlager, wobei sie von einer Flotte von AGVs unterstützt werden. Jeder Auftrag besteht aus einer Liste von Artikelpositionen im Lager. Die AGVs werden dazu verwendet, die benötigten Artikel zu einem Zentraldepot zu transportieren. Dazu muss zunächst festgelegt werden, welche Aufträge von welchem AGV transportiert werden sollen. Ein Auftrag darf dabei nicht auf mehrere AGVs verteilt werden. Sobald ein AGV an einer Artikelposition ankommt, wird ein menschlicher Kommissionierer benötigt, um den Artikel aus seinem Lagerort zu entnehmen und ihn auf das AGV zu verladen. Ziel ist es, alle Aufträge in möglichst kurzer Zeit zu kommissionieren.

Als Lösungsansatz bietet sich die Zerlegung des Problems in Teilprobleme an, welche getrennt gelöst werden. Dabei können exakte (z.B. dynamische Programmierung, Constraint Programming, gemischt-ganzzahlige Programmierung) und heuristische Lösungsverfahren (lokale Suche, Metaheuristiken) zum Einsatz kommen. Zusätzlich ist eine Untersuchung der Komplexität des Problems wünschenswert. Für die Bearbeitung dieses Themas sind Programmierkenntnisse von Vorteil. Bei Interesse schreiben Sie bitte eine E-Mail an .

 

Designing a Scheduled Service Network for Postal Operations

DPDHL, the worldwide leading mail service provider, is responsible for the mail transport of millions of letters coming from all over the world. Its letter processing chain starts with the letters being collected at mailboxes, post offices, and business partners. Letters must then be transported to their designated origin facilities where the letters are sorted and loaded into letter boxes according to their final destinations. These letter boxes are in turn loaded into wagons which are then loaded into vehicles. To reduce cost, boxes can be moved from one wagon into another at intermediate facility locations (hubs) so that they can be transported by other vehicles. To find cost-minimal assignments of letter boxes to wagons, the problem faced by DPDHL can be modeled as a multi-commodity flow problem with nodes representing different facility centers which can have a supply or demand, and directed arcs representing the wagon origins and wagon destinations, i.e., where the wagons are closed and opened, respectively (wagon arcs). Then, the objective is to minimize the cost when sending boxes from their origin nodes through the network to the respective destinations. Instead of imposing variable cost per unit of goods transported by a vehicle, we consider an individual fixed cost for each used trip while we define a trip as the direct connection of two nodes in the network.

Based on a path flow formulation that models the aforementioned problem at DPDHL, the task is to model the problem as an arc flow formulation. An exact solution approach has to be developed and applied on small problem instances using CPLEX. It is further desired that the student evaluates the impact of different instance characteristics on the solutions obtained. In addition, heuristic components need to be developed to sparsify the time expanded network on which the problem is defined and to reduce the complexity of the problem formulation. The solution approach has to be implemented in C++.

If you are interested please send an email to .

 

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.

 

Traveling Salesman Problem with Time Windows: Minimizing the Latency

The Traveling Salesman Problem with Time Windows (TSPTW) is a classic routing problem in which a set of customers must be sequenced under strict time window restrictions. The standard objective used in the literature is to minimize the total travel time. Because waiting times can occur if the vehicle arrives at a customer before the time window opens, we consider a variant of the TSPTW in which we minimize the total latency while respecting the time windows. The latency of a customer is defined to be the travel duration before visiting the customer. In the standard case in which the departure time at the depot is fixed, this corresponds to minimizing the total arrival time (i.e., completion time). However, in many real-life situations, the departure time at the depot is not fixed but only has to lie within a given time window. The goal of this thesis is to develop a heuristic solution method which can solve all problem variants that emerge from the above discussion. If you are interested, please feel free to write an email to .