Integration von Maschinellem Lernen in die kombinatorische dynamische Optimierung für urbane Transportdienste

Das Ziel des Projektes ist die Kombination der gemischt-ganzzahligen linearen Programmierung (MILP) und des Reinforcement Learning (RL), um eine effektive Entscheidungsunterstützung für stochastische dynamische Pickup-and-Delivery Probleme (SDPDPe) zu erreichen.SDPDPe spielen in der urbanen Logistik eine zunehmend wichtige Rolle. Sie beschreiben den oft zeitkritischen Transport von Personen oder Waren in der Stadt. Beispiele sind Kurierdienste, Onlineessenslieferung, Same-day Lieferdienste, oder Ridesharing. Für all diese Probleme müssen operative Entscheidungen über Fahrzeugzuordnung und Tourenplanung in Echtzeit getroffen werden. Solche Entscheidungen müssen den aktuellen Bedarf effizient erfüllen und die Fahrzeugflotte gleichzeitig flexibel für zukünftige Anfragen halten.Aus Modellsicht sind SDPDPe durch eine Folge von Entscheidungszuständen unter Unsicherheit gekennzeichnet, bei der der volle Wert einer Entscheidung sich erst später im Verlauf des Tages offenbart. Das Durchsuchen des kombinatorischen Entscheidungsraums nach effizienten Touren in jeden Zustand erfordert die Lösung eines komplexen MILPs. Diese Komplexität wird nun durch die Herausforderung verstärkt, dass eine Bewertung von Entscheidungen auf ihre Effektivität angesichts zukünftiger Unsicherheit notwendig ist - eine ideale Anwendung für RL. Beides ist von zentraler Bedeutung, um den operativen Anforderungen gerecht zu werden. Somit wäre eine direkte Kombination beider Methodenklassen notwendig. Diese steht allerdings aus unterschiedlichen Gründen noch aus und ist Ziel dieses Forschungsprojektes. Konkret schlagen wir vor das MILP durch RL zu manipulieren, um sowohl effiziente als auch effektive Entscheidungen zu erhalten. Die Manipulation kann die Zielfunktion oder die Nebenbedingungen verändern. So werden Anreiz- oder Strafbedingungen hinzugefügt, um bestimmte Entscheidungen zu erzwingen oder zu verbieten. Alternativ werden Nebenbedingungen angepasst, zum Beispiel, um Flotten-Ressourcen zu reservieren.Die Herausforderung ist, zu entscheiden, wo und wie die Manipulation stattfinden sollen. Je nach SDPDPe setzt sich die Zielfunktion unterschiedlich zusammen und haben Nebenbedingungen wie Zeitfenster oder Fahrzeugkapazitäten unterschiedliche Relevanz. Der erste Schritt des Projektes zielt somit auf die Identifikation relevanter Bereiche innerhalb des MIPs mittels (un)supervised learning. Sind die "interessanten" Bereiche identifiziert, besteht die zweite Herausforderung darin, die richtige Parametrisierung zu finden. Hier werden RL-Methoden eingesetzt, die die relevanten MIP-Komponenten zustandsabhängig manipulieren.

Integrating machine learning in combinatorial dynamic optimization for urban transportation services

The goal of this project is to provide effective decision support for stochastic dynamic pickup and delivery problems by combining the strengths of mixed-integer linear programming (MILP) and reinforcement learning (RL).Stochastic dynamic pickup-and-delivery problems play an increasingly important role in urban logistics. They are characterized by the often time-critical transport of wares or passengers in the city. Common examples are same-day delivery, ridesharing, and restaurant meal delivery. The mentioned problems have in common that a sequence of decision problems with future uncertainty must be solved in every decision step where the full value of a decision reveals only later in the service horizon. Searching the combinatorial decision space of the subproblems for efficient and feasible tours is a complex task of solving a MILP. This complexity is now multiplied by the challenge of evaluating such decision with respect to their effectiveness given future dynamism and uncertainty; an ideal case for RL. Both are crucial to fully meet operational requirements. Therefore, a direct combination of both methods is needed. Yet, a seamless integration has not been established due to different reasons and is the aim of this research project. We suggest using RL to manipulate the MILP itself to derive not only efficient but also effective decisions. This manipulation may change the objective function or the constraints. Incentive or penalty terms can be added to the objective function to enforce or prohibit the selection of certain decisions. Alternatively, the constraints may be adapted to reserve fleet-resources.The challenge is to decide where and how the manipulation takes place. SDPDPs have constraints with respect to routing, vehicle capacities, or time windows. Some constraints may be irrelevant for the fleet’s flexibility while others might be binding. The first part of the research project focuses on identifying the "interesting” parts of the MILP via (un-)supervised learning. Once the "interesting” parts are identified, the second challenge is to find the right parametrization. Here, we will apply RL methods to learn the state-dependent manipulation of the MILP components.