Creating very large scale neighborhoods out of smaller ones by compounding moves

Creating very large scale neighborhoods out of smaller ones by compounding moves

0.00 Avg rating0 Votes
Article ID: iaor20062262
Country: Netherlands
Volume: 12
Issue: 1/2
Start Page Number: 115
End Page Number: 140
Publication Date: Jan 2006
Journal: Journal of Heuristics
Authors: , ,
Keywords: heuristics
Abstract:

This paper discusses neighborhood search algorithms where the size of the neighborhood is ‘very large’ with respect to the size of the input data. We concentrate on such a very large scale neighborhood (VLSN) search technique based on compounding independent moves (CIM) such as 2-opts, swaps, and insertions. We present a systematic way of creating and searching CIM neighbourhoods for routing problems with side constraints. For such problems, the exact search of the CIM neighborhood becomes NP-hard. We introduce a multi-label shortest path algorithm for searching these neighborhoods heuristically. Results of a computational study on the vehicle routing problem with capacity and distance restrictions shows that CIM algorithms are very competitive approaches for solving vehicle routing problems (VRPs). Overall, the solutions generated by the CIM algorithm have the best performance among the current solution methodologies in terms of percentage deviation from the best-known solutions for large-scale capacitated VRP instances.

Reviews

Required fields are marked *. Your email address will not be published.