The travelling salesman problem (TSP), a famous NP-hard combinatorial optimisation problem (COP), consists of finding a minimum length tour that visits n cities exactly once and comes back to the starting city. This paper presents a resolution of the TSP using the breakout local search metaheuristic algorithm (BLS), which is based on the iterated local search (ILS) framework and improves it by introducing some fundamental features of several well-established metaheuristics such as tabu search (TS) and variable neighbourhood search (VNS). BLS moves from a local optimum of a neighbourhood to another by applying perturbation jumps whose type and number are determined adaptively. It has already been applied to many COP and gives good results. This innovative hybridisation resolved well 41 instances from the commonly used benchmark library TSPLIB. The high quality of experimental results shows the competitiveness of the proposed algorithm compared to other algorithms based on local search.
Publié le : 2018-07-26
Classification:  other areas of Computing and Informatic,  Travelling salesman problem, breakout local search, adaptive perturbation strategy, iterated local search
@article{cai2018_3_656,
     author = {Mehdi El Krari; Computer Science Laboratory, Faculty of Science, Mohammed V University in Rabat and Bela\"\i d Ahiod; Faculty of Science, Mohammed V University in Rabat, LRIT, Associated Unit to CNRST (URAC 29), Rabat and Bouazza El Benani; Computer Science Laboratory, Faculty of Science, Mohammed V University in Rabat},
     title = {Breakout Local Search for the Travelling Salesman Problem},
     journal = {Computing and Informatics},
     volume = {36},
     number = {6},
     year = {2018},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai2018_3_656}
}
Mehdi El Krari; Computer Science Laboratory, Faculty of Science, Mohammed V University in Rabat; Belaïd Ahiod; Faculty of Science, Mohammed V University in Rabat, LRIT, Associated Unit to CNRST (URAC 29), Rabat; Bouazza El Benani; Computer Science Laboratory, Faculty of Science, Mohammed V University in Rabat. Breakout Local Search for the Travelling Salesman Problem. Computing and Informatics, Tome 36 (2018) no. 6, . http://gdmltest.u-ga.fr/item/cai2018_3_656/