Sontrop,H.M.J. Horn,S.P.,van der Teeuwen,G. Uetz,M. (METEOR)
Abstract
This paper introduces new ejection chain strategies to effectively target vehicle routing problems with time window constraints (VRPTW). Ejection chain procedures are based on the idea of compound moves that allow a variable number of solution components to be modified within any single iteration of a local search algorithm. The yardstick behind such procedures is the underlying reference structure, which is the structure that is used to coordinate the moves that are available for the local search algorithm. The main contribution of the paper is a new reference structure that is particularly suited in order to handle the asymmetric aspects in a VRPTW. The new reference structure is a generalization of the doubly rooted reference structure introduced by Glover, resulting in a new, powerful neighborhood for the VRPTW. We use tabu search for the generation of the ejection chains. On a higher algorithmic level, we study the effect of different meta heuristics to steer the tabu chain ejection process. Computational results confirm that our approach leads to very fast algorithms that can compete with the current state of the art algorithms for the VRPTW.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Publisher Info
Paper provided by Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization in its series Research Memoranda with number
012.