ENS.VRSP: Effiziente Nachbarschaftssuche im Vehicle Routing und Scheduling

• Antragsteller: Professor Dr. Stefan Irnich; Professor Dr. Michael Schneider
• Fachliche Zuordnung: Accounting und Finance
• Förderung: Förderung von 2016 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 315139873

• Erstellungsjahr: 2023

Zusammenfassung der Projektergebnisse

Ziel des Vorhabens ist die Gewinnung neuer Erkenntnisse und die Entwicklung neuer Methoden auf dem Gebiet der Nachbarschaftssuche für Vehicle-Routing- und -Scheduling-Probleme (VRSP). VRSP lassen sich generisch folgendermaßen beschreiben: Gegeben ist eine Menge von Transportaufträgen und eine Flotte von Fahrzeugen. Gesucht ist eine Menge von Fahrzeugrouten, die alle Transportaufträge (oder eine Auswahl) mit der gegebenen Flotte bestmöglich ausführen. Insbesondere ist zu entscheiden, welches Fahrzeug welche Aufträge in welcher Reihenfolge in zulässiger Weise ausführt. Laut herrschender Meinung können VRSP nicht bewiesen optimal in einer bezüglich der Größe der Probleminstanz durch ein Polynom beschränkten Zeit gelöst werden, d.h. sie sind NP-schwer. Daher werden heuristische Algorithmen zur Lösung entwickelt, wobei man zwischen Eröffnungs- und Verbesserungsverfahren unterscheidet. Unter den Verbesserungsverfahren spielen Nachbarschaftssuchen eine führende Rolle: Diese Verfahren nehmen wiederholt und systematisch Veränderungen an einer gegebenen Lösung vor, um so zu besseren Lösungen zu gelangen. Bekannte Beispiele für Nachbarschaftssuchen sind das 2-Opt- und das Lin-Kernighan-Verfahren zur Lösung des Traveling-Salesman-Problems. Nach Einschätzung der Antragsteller besteht trotz der vielen existierenden Veröffentlichungen im Bereich der Metaheuristiken für VRSP ein starker Forschungsbedarf bei der Entwicklung und Analyse von Basiskomponenten zur Nachbarschaftssuche. Solche Basiskomponenten beziehen sich auf grundlegende Aspekte von Nachbarschaftssuchen. Das sind insbesondere die effiziente Überprüfung von durch Suchschritte veränderten Lösungen hinsichtlich Zulässigkeit und Kosten sowie die Bestimmung geeigneter Reihenfolgen der auszuführenden Suchschritte. Um Verbesserungen bei diesen Komponenten zu erreichen, sollen insbesondere Konzepte aus dem Bereich der exakten Verfahren (Ressourcen, Ressourcenerweiterungsfunktionen) mit modernen Ansätzen auf dem Gebiet der Heuristiken (Granular Search, Time Travel) verknüpft werden. Hierfür bietet sich eine Zusammenarbeit zwischen den Antragstellern an, deren Kompetenzen sich diesbezüglich in sinnvoller Weise ergänzen. Die erwähnten Basiskomponenten sind nicht auf einzelne spezielle Verfahren oder spezielle VRSP beschränkt, sondern grundsätzlich problem- und nachbarschaftsunabhängig. Den angestrebten Ergebnissen kommt daher eine sehr weitreichende Bedeutung zu: Sie erlauben eine wesentliche Verbesserung der Leistungsfähigkeit zahlreicher verschiedener Lösungsmethoden für ein breites Spektrum von Problemen, die sowohl aus wissenschaftlicher Perspektive als auch aus Praxissicht von hoher Relevanz sind.

Projektbezogene Publikationen (Auswahl)

• Large multiple neighborhood search for the clustered vehicle-routing problem. European Journal of Operational Research, 270(1), 118-131.
  Hintsch, Timo & Irnich, Stefan
  
• Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem. Transportation Science, 53(2), 480-491.
  Gschwind, Timo & Drexl, Michael
  
• An adaptive large neighborhood search with path relinking for a class of vehicle‐routing problems with simultaneous pickup and delivery. Networks, 74(3), 207-250.
  Hof, Julian & Schneider, Michael
  
• Upper and lower bounds for the vehicle-routing problem with private fleet and common carrier. Discrete Applied Mathematics, 264, 43-61.
  Goeke, Dominik; Gschwind, Timo & Schneider, Michael
  
• Routing electric vehicles with a single recharge per route. Networks, 76(2), 187-205.
  Löffler, Maximilian; Desaulniers, Guy; Irnich, Stefan & Schneider, Michael
  
• Rule-based design of a granular tabu search for the multi-depot vehicle routing problem. Working Paper DPO-2021-01. Aachen, Germany: Deutsche Post Chair – Optimization of Distribution Networks, RWTH Aachen University, 2021
  C. Becker, R. Cavagnini, S. Irnich & M. Schneider
  
• A Large Neighborhood Search for the Vehicle Routing Problem with Multiple Time Windows. Transportation Science, 56(5), 1369-1392.
  Schaap, Hendrik; Schiffer, Maximilian; Schneider, Michael & Walther, Grit
  
• Inter-depot moves and dynamic-radius search for multi-depot vehicle routing problems. Technical Report LM-2022-04. (completely revised version of LM-2020-03). Mainz, Germany: Chair of Logistics Management, Gutenberg School of Management und Economics, Johannes Gutenberg University Mainz, 2022
  J. B. Gauthier & S. Irnich
  
• New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem. EURO Journal on Computational Optimization, 10(2022), 100029.
  Schmidt, Jeanette & Irnich, Stefan
  
• In-depth analysis of granular local search for capacitated vehicle routing. Discrete Applied Mathematics, 329, 61-86.
  Becker, Christian; Gauthier, Jean Bertrand; Gschwind, Timo & Schneider, Michael