Creating very large scale neighborhoods out of smaller ones by compounding moves |
| |
Authors: | Özlem Ergun James B Orlin Abran Steele-Feldman |
| |
Institution: | (1) Department of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA;(2) Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA 02139, USA;(3) Quantitative Ecology and Resource Management, University of Washington, Seattle, WA 98195-2182, USA |
| |
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 neighborhoods 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. 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. |
| |
Keywords: | Very-large scale neighborhood search Local search Routing |
本文献已被 SpringerLink 等数据库收录! |
|