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

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.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2003

Author dc:creator

• Funke, Birger

Contributors dc:contributor

• Sebastian, Hans-Jürgen

• info:eu-repo/classification/ddc/330
• Transportproblem
• Nebenbedingung
• Heuristik
• Lokales Suchverfahren
• Wirtschaft

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

ger

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-120661%22

OAI identifier oai:identifier

oai:publications.rwth-aachen.de:58829