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

Ziel des geplanten 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.

• DFG-Verfahren: Sachbeihilfen