Breakout Local Search for the Travelling Salesman Problem

Authors

  • 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

Keywords:

Travelling salesman problem, breakout local search, adaptive perturbation strategy, iterated local search

Abstract

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.

Downloads

Download data is not yet available.

Downloads

Published

2018-07-26

How to Cite

El Krari, M., Ahiod, B., & El Benani, B. (2018). Breakout Local Search for the Travelling Salesman Problem. COMPUTING AND INFORMATICS, 37(3), 656–672. Retrieved from http://www.cai.sk/ojs/index.php/cai/article/view/2018_3_656