Effiziente lokale Suche für vehicle routing und Scheduling-Probleme mit Ressourcenbeschränkungen

Funke, Birger; Sebastian, Hans-Jürgen

doi:urn:nbn:de:hbz:82-opus-5415

Effiziente lokale Suche für vehicle routing und Scheduling-Probleme mit Ressourcenbeschränkungen

Funke, Birger (Author)

2003

Verantwortlichkeitsangabevorgelegt von Birger Funke

ImpressumAachen : Publikationsserver der RWTH Aachen University 2003

UmfangX, 240 S.

Aachen, Techn. Hochsch., Diss., 2003

Genehmigende Fakultät
Fak08

Hauptberichter/Gutachter
Sebastian, Hans-Jürgen (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2003-02-04

Online
URN: urn:nbn:de:hbz:82-opus-5415
URL: https://publications.rwth-aachen.de/record/58829/files/Funke_Birger.pdf

Einrichtungen

Fakultät für Wirtschaftswissenschaften (800000)

Inhaltliche Beschreibung (Schlagwörter)
Transportproblem (Genormte SW) ; Nebenbedingung (Genormte SW) ; Heuristik (Genormte SW) ; Lokales Suchverfahren (Genormte SW) ; Wirtschaft (frei)

Thematische Einordnung (Klassifikation)
DDC: 330

Kurzfassung
Die Entwicklung leistungsfähiger Heuristiken für Vehicle Routing und Scheduling Probleme ist seit mehreren Jahrzehnten Gegenstand intensiver weltweiter Forschung. Die meisten publizierten Algorithmen können jedoch nur auf Instanzen eines bestimmten Problemtyps angewendet werden. Für praktische Anwendungen stellt die daraus resultierende fehlende Robustheit dieser Heuristiken gegenüber Änderungen der Modellstruktur ein ernsthaftes Problem dar. Der Beitrag dieser Dissertation liegt in der Entwicklung effizienter Verbesserungsheuristiken auf der Basis eines allgemeinen Ressourcenmodells. Damit können sehr unterschiedliche Restriktionen, wie z.B. Beschränkungen der Tourdauer, der Tourlänge, Fahrzeug-Kapazitäten, Zeitfenster, Reihenfolgeabhängigkeiten oder Inkompatibilitäten von Aufträgen usw., formuliert werden. Heuristiken, die auf diesem allgemeinen Modell basieren, lösen einen großen Teil aller Vehicle Routing und Scheduling Probleme. Kantenaustausch-Nachbarschaften und Cyclic-Transfer-Nachbarschaften sind zwei in der Literatur lange bekannte große Klassen von Austausch-Nachbarschaften. Die vorliegende Arbeit zeigt, daß diese Nachbarschaften unter Berücksichtigung der Ressourcenbeschränkungen effizient abgesucht werden können. Die Einbindung der Nachbarschaften in eine Meta-Heuristik ist die zugrundeliegende Intention der Untersuchungen, steht aber nicht selbst im Zentrum der Betrachtungen. Ein weiterer wichtiger Beitrag der Arbeit besteht in der Verallgemeinerung, Weiterentwicklung und der teilweise erstmalig vorgenommenen formalen Beschreibung grundlegender Konzepte dieser Nachbarschaften. Die Einführung geeigneter Begriffe und Definitionen macht es möglich, bereits bekannte Zusammenhänge einfacher darzustellen und neue Erkenntnisse abzuleiten. Die vorgenommenen Generalisierungen bekannter Methoden decken zahlreiche Alternativen bei deren konkreter Ausgestaltung auf. Methodisch baut die Arbeit auf einem Artikel von Savelsbergh aus dem Jahr 1985 auf. Darin wird beschrieben, wie Zeitfensterrestriktionen bei der Suche in 2-opt- und 3-opt-Nachbarschaften mit Hilfe einer Lexikographischen Suche effizient überprüft werden können. Die Ideen von Savelsbergh werden erweitert und auf abstrakte beschränkte Ressourcen und beliebige k-opt-Schritte übertragen. Die effiziente Überprüfung unterschiedlicher Restriktionen kann dadurch nach einem allgemeinen Schema durchgeführt werden. Dabei können auch mehrere, teilweise voneinander abhängige Restriktionen berücksichtigt werden. Für die Suche in den Cyclic-Transfer-Nachbarschaften wird eine für diese Problemstellung neuartige Formulierung verwendet, die aus einem im Jahr 2001 publizierten Artikel von Ahuja, Orlin und Sharma übernommen und für Vehicle Routing und Scheduling Probleme adaptiert wurde. Diese Darstellung erlaubt es, die sehr großen Cyclic-Transfer-Nachbarschaften auf der Basis der Dynamischen Programmierung implizit zu durchsuchen. Bei diesen Nachbarschaften kann die Einhaltung der Ressourcenbeschränkungen für Teillösungen ähnlich einem Preprocessing sichergestellt werden. Dabei finden dieselben Operationen Verwendung, die auch bei den k-opt-Nachbarschaften eingesetzt werden. In der vorliegenden Arbeit wird der Fokus bewußt auf die Gestaltung der Lokalen Suche gelegt. Diese ist ein Kernelement vieler moderner Meta-Heuristiken, wie z.B. Tabu-Search, Variable Neighborhood Search, Iterated Local Search, Guided Local Search. Mit den entwickelten Modellen und Methoden ist es erstmalig möglich, zwei sehr unterschiedliche große Klassen von Nachbarschaften auf der Basis eines allgemeinen Ressourcenmodells effizient zu durchsuchen. Die präsentierten Ergebnisse zeigen, daß bereits mit einer reinen Lokalen Suche einige bekannte Meta-Heuristiken übertroffen werden können. Dies gibt zu der Vermutung Anlaß, daß durch eine adäquate Integration der Nachbarschaften in eine Meta-Heuristik leistungsfähige Algorithmen entwickelt werden können, die den meisten heutigen Implementierungen überlegen sind. Dies zu verwirklichen bleibt als eine erfolgversprechende Aufgabe künftigen Arbeiten vorbehalten.

The development of efficient heuristics for Vehicle Routing and Scheduling Problems has been the subject of many research activities during the last decades. Most of the algorithms published up to now can only be applied to instances of problem types specific to the algorithm. The according lack of robustness with regard to changes in the model structure is a serious problem in practical applications. The contribution of this thesis is the development of high-performance improvement heuristics based on a general resource model that enables the formulation of different constraints, e.g., restrictions of tour duration or tour length, vehicle capacities, time windows, order dependencies, or incompatibility of tasks. Heuristics based on this general model are able to solve a larger part of all Vehicle Routing and Scheduling Problems. Edge-exchange neigborhoods and Cyclic Transfer neigborhoods are two large classes of neigborhoods well-known in the literature. The thesis shows that these neigborhoods can be efficiently searched, taking into account constraints on the resources. The integration of these neigborhoods into a meta-heuristic is the underlying intension of the work, although it is not the subject of consideration itself. An additional contribution of the work consists of the generalization, further development, and partially new formal description of basic concepts of these neigborhoods. The introduction of new appropriate notions and definitions facilitates the illustration of known results as well as the derivation of new insights. Numerous alternatives in the implementation of known methods are discovered by generalizations. Methodologically, the thesis is based on a publication of Savelsbergh from 1985. There, the author describes how time window restrictions can be checked efficiently in 2-opt and 3-opt neigborhoods using a lexicographic search strategy. The ideas of Savelsbergh are extended and applied to generalized resources and arbitrary k-opt neigborhoods. The efficient check of different constraints can, therefore, be performed by a general uniform scheme. Several constraints can be taken into account at the same time even if they are partially dependent on each other. Furthermore, a new problem formulation published in 2001 by Ahuja, Orlin, and Sharma is adapted for Vehicle Routing and Scheduling Problems and used for the search in Cyclic Transfer neigborhoods. This formulation allows to implicitly search very large Cyclic Transfer neigborhoods on the basis of a Dynamic Programming methodology. In these neigborhoods the compliance with the constraints can be checked for partial solutions in advance, as in a preprocessing step. Thereby, the same operations as used within the k-opt neigborhoods can be applied. The thesis is intendedly focused on the design of the local search, which is the core element of many up-to-date meta-heuristics, e.g., Tabu Search, Variable Neighborhood Search, Iterated Local Search, and Guided Local Search. Using the developed models and methods, it is for the first time possible to efficiently search two large classes of neigborhoods, based on a very general resource model. The presented results indicate that even pure local search can outperform many well-known meta-heuristics. It can be expected that the proper integration into a meta-heuristic framework should be superior to most implementations available today. This is a promising path for future research.

OpenAccess:
PDF
(additional files)