Aktuelle Themen

 

Reinforcement Learning a Stochastic Dynamic Vehicle Routing Problem with Incomplete Information

Vehicle Routing Problems (VRPs) concern the decision of determining a set of routes for a fleet of vehicles that travel from (possibly more than) one central depot to provide service to (or collect items from) a set of customers, often in an urban environment. VRPs have a colorful range of applications in logistics and mobility services, such as transporting goods or passengers, or conducting services at customer homes. In many cases of VRPs, the decision maker (DM) is uncertain about the problem data. In such situations, the DM learns about such information sequentially, over multiple periods, in a dynamic manner. For example, additional customer requests might arrive during the routing mission, the travel time might increase due to road congestions, and the size of the available fleet might change due to accidents and malfunction of vehicles. In such situations, the dynamic nature of how the stochastic information unfolds gives rise to a class of VRPs known as Stochastic Dynamic Vehicle Routing Problem (SDVRP).

The goal of this thesis is to study an SDVRP in which a single vehicle is available to serve customer requests in a given time horizon defined by the vehicle driver’s shift. In this problem, some customer requests are known in advance, but others are received during the day. When a new request occurs, the DM needs to decide whether the new request is accepted or rejected. If the new request is accepted, the DM has to decide on how to update the route to include the location of the newly accepted request. Otherwise, the rejected requests are lost forever. The goal of the DM is to maximize the number of fulfilled requests.

A common approach to proceed with solving an SDVRP is to (1) assume that the underlying stochastic process can be analyzed and transferred into a predictive model (e.g., nominal probability distribution), (2) use the predictive model to anticipate future scenarios (e.g., the likelihood of a customer request occurring at a given location), and (3) incorporate the predicted scenarios into the framework of optimizing the routing decision. Nevertheless, constructing the predictive model requires sufficient past observations (e.g., previous customer requests), which might not always be available. This can be circumvented by leveraging a reinforcement learning framework that allows the DM to use an adaptive prediction model. In this case, initially, the DM is unsure how the predictive model should reflect the uncertainty. However, as time progresses, the DM observes new realizations of the stochastic process (e.g., new demand requests) and updates their belief about how the predictive model should anticipate the uncertainty. For instance, this could be a situation in which the DM does not know in advance the demand distribution at different locations. However, as more demand requests arrive, the DM revises the predictive model to reflect the different levels of demand requests at different locations.

If you are interested, please feel free to write an email with your CV and your transcript of records to siddig@dpo.rwth-aachen.de.

 

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 bomsdorf@dpo.rwth-aachen.de.