Learning to Optimize (L2O)

Während die Tourenplanung für kleinere bis mittlere Anzahlen an Fahrzeugen mit Methoden des klassischen Operations Research (OR) seit langem zuverlässig gelöst werden kann, stellen Probleme mit mehr als 100 Fahrzeugen sowie komplexen Nebenbedingungen (relevant im Bereich von Logistik- Unternehmen und Flotten großer mobiler Pflegedienste) Herausforderungen dar, die im Normalfall sehr lange Rechenzeit in Anspruch nehmen und häufig nur noch näherungsweise gelöst werden können. Darüber hinaus kann eine Re- bzw. Neuplanung aufgrund von veränderten Bedingungen (z. B. Integration neuer Kunden, längere Streckenfahrzeiten wegen erhöhten Ver-kehrsaufkommens, unbekannte Baustellen oder Unfälle) oft nur im Einzelfall nach Bedarf erfolgen. Wird ein dynamisches Tourenplanungsproblem durch Re-Planung gelöst, kommen oft nur Tourenpläne heraus, die weit von der Optimalität entfernt liegen und daher ein großes Verbesserungspotential aufweisen.

Das Projekt zielt auf die effektive und innovative Kombination von klassischen Optimierungsmethoden des OR und Techniken der Künstlichen Intelligenz (KI) ab. Zur Lösung der dynamischen Tourenplanung mit vielen Attributen und komplexen Nebenbedingungen soll aus vorhandenen Daten und Erfahrungen gelernt werden, um die Qualität der Lösungen zu erhöhen.

Im Kern verfolgt das Projekt einen parallelen Ansatz, in dem einerseits das Maschinelle Lernen dazu eingesetzt werden soll, um klassische OR Verfahren zu beschleunigen und Korrekturen bzw. Re-Planung in nahezu Echtzeit durchführen zu können. Andererseits sollen OR Methoden die KI-basierten Ansätze unterstützen, um die Güte der erzielten Lösungen sicherzustellen. Zu diesem Zweck werden zunächst Planungsdaten von diversen Industriepartnern analysiert, auf dieser Basis geeignete Lösungsmethoden entwickelt sowie anschließend kontinuierlich angepasst und verbessert.

DIMACS Implementation Challenge:
Erster Platz wird an den BWOR-L2O solver, entwickelt von Christian Ackermann, für das Dynamic Ride Hailing Problem der Vehicle Routing Challenge vergeben: Result page
Twitter Post vom 02.02.2022: Bekanntmachung auf Twitter

Presse:
Artikel im NDR vom 08.06.2020:
NDR: Hildesheimer Forscher optimieren Routenplanung
Artikel in der Hildesheimer Allgemeinen Zeitung vom 11.06.2020.:
HAZ: Uni hilft Fahrern auf die Sprünge

Projektträger:
BMBF

Partner:
Arbeitsgruppe Betriebswirtschaft und Operations Research - Universität Hildesheim
Spedition Hahne GmbH
SpediFix Logistiksoftware GmbH & Co. KG

Kontakt

Lars Schmidt-Thieme
Jonas Falkner

Publications

• Christian Ackermann, Julia Rieck (2021):
  New Optimization Guidance for Dynamic Dial-a-Ride Problems, in Operations Research Proceedings, Springer.
• Cornelius Rüther, Shabanaz Chamurally, Julia Rieck (2021):
  An a-priori Parameter Selection Approach to Enhance the Performance of Genetic Algorithms Solving Pickup and Delivery Problems, in Operations Research Proceedings, Springer.
• Maik Trott, Niels-Fabian Baur, Marvin Auf der Landwehr, Julia Rieck (2021):
  Evaluating the role of commercial parking bays for urban stakeholders on last-mile deliveries – A consideration of various sustainability aspects, in Journal of Cleaner Production, .
• Cornelius Rüther, Julia Rieck (2020):
  A grouping genetic algorithm for multi depot pickup and delivery problems with time windows and heterogeneous vehicle fleets, in Lecture Notes in Computer Science (LNCS), EvoCOP Proceedings 2020: European Conference on Evolutionary Computation in Combinatorial Optimization, Springer, pp. 148-163.