Effiziente lokale Suche für vehicle routing und Scheduling-Probleme mit Ressourcenbeschränkungen
type: CreativeWork
description: 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 neigbor…
abstract: 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 neigbor…
author: Funke, Birger
language: ger
keywords: info:eu-repo/classification/ddc/330, Transportproblem, Nebenbedingung, Heuristik, Lokales Suchverfahren, Wirtschaft
date published: 2003
date modified: 2026-07-30T19:42:31Z
provider: RWTH Aachen University
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: Publikationsserver der RWTH Aachen University