Record #254247 - GSI Repository

DFG project G:(GEPRIS)315139873

ENS.VRSP: Effiziente Nachbarschaftssuche im Vehicle Routing und Scheduling

Coordinator	Professor Dr. Stefan Irnich ; Professor Dr. Michael Schneider
Grant period	2016 - 2023
Funding body	Deutsche Forschungsgemeinschaft
	DFG
Identifier	G:(GEPRIS)315139873

Note: 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.

Recent Publications

There are no publications

Record created 2023-01-19, last modified 2024-09-28

Similar records

Add to personal basket
Export as Author List with IDs BibTeX (UTF-8), EndNote XML, EndNote Text, RIS, MARC, Print MARC, MARCXML, DC,
Request correction
Submit fulltext

GSI Homepage \| GSI Library \| English Deutsch \| guest :: login GSI Repository
Search	Submit	Personalize Your alerts Your baskets Your searches	Help