The traveling salesman problem

The traveling salesman problem (TSP) is an NP-hard problem, which has been an interesting problem for a long time in the field of discrete or combinatorial optimization techniques, which are based on linear and non-linear programming. The TSP presents the task of finding an optimum path or route through a set of given locations (cities), such that each location is passed through only once, and the route looped in such a way that it ends at the starting location 1, 2. In Operational Research, TSP problems still remain one of the most challenging problems, which cannot be solved easily by using traditional optimization techniques such as enumeration methods and mathematical programming 3. Solving TSP optimally takes huge computational time and therefore the need for the development of an approximate algorithms or heuristics that gives near optimal solution in a reasonable computational effort 4.
In the last decades, many heuristics based algorithmic strategies were proposed in the quest for finding near-optimum solutions to the TSP problems, among which include tabu search (TS) 5, simulated annealing (SA) 6, genetic algorithm (GA) 7, ant colony optimization (ACO) 8, particle swarm optimization (PSO) 9, artificial immune system (AIS) 10, artificial neural network (ANN) 11, elastic net (EN) 12. All the algorithms listed here draw their inspiration from nature, through the observation of physical processes that occur in nature. They are implemented by mimicking different natural systems and processes using mathematical models and algorithms.
In this paper, the possibility of applying a hybrid symbiotic organisms search (SOS) algorithm with local search simulated annealing (SA) to solve the traveling salesman problem is investigated. The symbiotic organisms search algorithm was first introduced in 12, inspired by the symbiotic relationships strategies, which exist among organisms in the ecosystem. The SOS algorithm was initially proposed to solve continuous engineering optimization problems. Several experimental results from literatures 13-16, which have used SOS algorithm as an optimization tool to find global optimum solutions, indicate that the algorithm shows a considerable robustness in its performance when tested on complex mathematical benchmark problems. Therefore, the potential of SOS in finding global solution to the aforementioned optimization problems makes it attractive for further investigation. In addition, since, SOS has not gained wide recognition in solving discrete problems, such as, routing and assignment problems, we believe that, this could be our motivation to introduce SOS to solve complex discrete problem such as the TSP.
The remainder of this paper is organised as follows: Section 2 presents related works; Section 3 provides a short description of the TSP problem; Section 4 presents the proposed SOS-SA method of solving TSP problem; while Section 5 describes and discusses the simulation results carried out on some benchmarked TSP instances; finally, conclusions and directions for future research are given in Section 6.