Sequential variable neighborhood descent variants: an empirical study on the traveling salesman problem - Université Polytechnique des Hauts-de-France Accéder directement au contenu
Article Dans Une Revue International Transactions in Operational Research Année : 2017

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

Résumé

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.
Fichier non déposé

Dates et versions

hal-03401944 , version 1 (25-10-2021)

Identifiants

Citer

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, 2017, 24 (3), pp.615-633. ⟨10.1111/itor.12282⟩. ⟨hal-03401944⟩
21 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More