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.
