Skip to Main content Skip to Navigation
Journal articles

Sequential variable neighborhood descent variants: an empirical study on the traveling salesman problem

Abstract : In a single local search algorithm, several neighborhood structuresare usually explored. The simplest way is todefine a single neighborhood as the union of all predefined neighborhood structures; the other possibility is tomake an order (or sequence) of the predefined neighborhoods,and to use them in the first improvement or thebest improvement fashion, following that order. In this work, first we classify possible variants of sequentialuse of neighborhoods and then, empirically analyze them in solving the classical traveling salesman problem(TSP). We explore the most commonly used TSP neighborhood structures, such as 2-opt and insertionneighborhoods. In our empirical study, we tested 76 differentsuch heuristics on 15,200 random test instances.Several interesting observations are derived. In addition, the two best of 76 heuristics (used as local searcheswithin a variable neighborhood search) are tested on 23 test instances taken from the TSP library (TSPLIB).It appears that the union of neighborhoods does not perform well.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03401944
Contributor : Kathleen Torck Connect in order to contact the contributor
Submitted on : Monday, October 25, 2021 - 2:52:03 PM
Last modification on : Tuesday, November 23, 2021 - 9:48:02 AM

Identifiers

Collections

Citation

Anis Mjirda, Raca Todosijević, Said Hanafi, Pierre Hansen, Nenad Mladenovic. Sequential variable neighborhood descent variants: an empirical study on the traveling salesman problem. International Transactions in Operational Research, Wiley, 2017, 24 (3), pp.615-633. ⟨10.1111/itor.12282⟩. ⟨hal-03401944⟩

Share

Metrics

Record views

5