TY - CHAP
T1 - Large Neighborhood Search
AU - Pisinger, David
AU - Røpke, Stefan
PY - 2018
Y1 - 2018
N2 - In the last 15 years, heuristics based on large neighborhood search (LNS) and the variant adaptive large neighborhood search (ALNS) have become some of the most successful paradigms for solving various transportation and scheduling problems. Large neighborhood search methods explore a complex neighborhood through the use of heuristics. Using large neighborhoods makes it possible to find better candidate solutions in each iteration and hence follow a more promising search path. Starting from the general framework of large neighborhood search, we study in depth adaptive large neighborhood search, discussing design ideas and properties of the framework. Application of large neighborhood search methods in routing and scheduling are discussed. We end the chapter by presenting the related framework of very large-scale neighborhood search (VLSN) and discuss parallels to LNS, before drawing some conclusions about algorithms exploiting large neighborhoods.
AB - In the last 15 years, heuristics based on large neighborhood search (LNS) and the variant adaptive large neighborhood search (ALNS) have become some of the most successful paradigms for solving various transportation and scheduling problems. Large neighborhood search methods explore a complex neighborhood through the use of heuristics. Using large neighborhoods makes it possible to find better candidate solutions in each iteration and hence follow a more promising search path. Starting from the general framework of large neighborhood search, we study in depth adaptive large neighborhood search, discussing design ideas and properties of the framework. Application of large neighborhood search methods in routing and scheduling are discussed. We end the chapter by presenting the related framework of very large-scale neighborhood search (VLSN) and discuss parallels to LNS, before drawing some conclusions about algorithms exploiting large neighborhoods.
KW - Business and Management
KW - Operations Research/Decision Theory
KW - Operations Research, Management Science
KW - Math Applications in Computer Science
U2 - 10.1007/978-3-319-91086-4_4
DO - 10.1007/978-3-319-91086-4_4
M3 - Book chapter
T3 - Handbook of Metaheuristics
SP - 99
EP - 127
BT - Handbook of Metaheuristics
PB - Springer
ER -