Local Search for Vehicle Routing and Scheduling Problems: Review and Conceptual Integration

• Published in: Journal of heuristics 2005-07, Vol.11 (4), p.267-306
• Main Authors: Funke, Birger, Grünert, Tore, Irnich, Stefan
• Format: Article
• Language: English
• Subjects: Algorithms; Decomposition; Heuristic; Methods; Neighborhoods; Routing; Scheduling; Studies; Traveling salesman problem
• ISSN: 1381-1231; 1572-9397
• DOI: 10.1007/s10732-005-1997-2

Local search and local search-based metaheuristics are currently the only available methods for obtaining good solutions to large vehicle routing and scheduling problems. In this paper we provide a review of both classical and modern local search neighborhoods for this class of problems. The intention of this paper is not only to give an overview but to classify and analyze the structure of different neighborhoods. The analysis is based on a formal representation of VRSP solutions given by a unifying giant-tour model. We describe neighborhoods implicitly by a set of transformations called moves and show how moves can be decomposed further into partial moves. The search method has to compose these partial moves into a complete move in an efficient way. The goal is to find a local best neighbor and to reach a local optimum as quickly as possible. This can be achieved by search methods, which do not scan all neighbor solutions explicitly. Our analysis shows how the properties of the partial moves and the constraints of the VRSP influences the choice of an appropriate search technique. [PUBLICATION ABSTRACT]