A reactive bone route algorithm for solving the traveling salesman problem

Abstract

The traveling salesman problem (TSP) is a well-known optimization problem in graph theory, as well as in operations research that has nowadays received much attention because of its practical applications in industrial and service problems. In this problem, a salesman starts to move from an arbitrary place called depot and after visits all of the nodes, finally comes back to the depot. The objective is to minimize the total distance traveled by the salesman. Because this problem is a non-deterministic polynomial (NP-hard) problem in nature, it requires a non-polynomial time complexity at runtime to produce a solution. Therefore, a reactive bone route algorithm called RBRA is used for solving the TSP in which several local search algorithms as an improved procedure are applied. This process avoids the premature convergence and makes better solutions. Computational results on several standard instances of TSP show the efficiency of the proposed algorithm compared to other meta-heuristic algorithms.