Variable Neighborhood Descent

Abraham Duarte (1) , Nenad Mladenovic (2, 3) , Jesús Sánchez-Oro (1) , Raca Todosijević (3, 4)

1 URJC - Universidad Rey Juan Carlos [Madrid]
2 GERAD - Groupe d’études et de recherche en analyse des décisions
3 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201
4 SANU - Mathematical Institute of the Serbian Academy of Sciences and Arts

Local search heuristic that explores several neighborhood structures in a deterministic way is called variable neighborhood descent (VND). Its success is based on the simple fact that different neighborhood structures do not usually have the same local minimum. Thus, the local optima trap problem may be resolved by deterministic change of neighborhoods. VND may be seen as a local search routine and therefore could be used within other metaheuristics. In this chapter, we discuss typical problems that arise in developing VND heuristic: what neighborhood structures could be used, what would be their order, what rule of their change during the search would be used, etc. Comparative analysis of usual sequential VND variants is performed in solving traveling salesman problem

Mots clés: "Deterministic exploration"; "Intensification"; "Local search"; "Variable neighborhood descent"

Domaines: Informatique [cs]

Abraham Duarte, Nenad Mladenovic, Jesús Sánchez-Oro, Raca Todosijević. Variable Neighborhood Descent. Handbook of Heuristics, Springer International Publishing, pp.341-367, 2018, 978-331907124-4. ⟨10.1007/978-3-319-07124-4_9⟩. ⟨hal-03674503⟩