A new approach to solve the traveling salesman problem

This paper presents a technique that uses the Wang recurrent neural network with the "Winner Takes All" principle to solve the traveling salesman problem (TSP). When the Wang neural network presents solutions for the assignment problem with all constraints satisfied, the "Winner Takes All" principle is applied to the values in the neural network's decision variables, with the additional constraint that the new solution must form a feasible route for the TSP. The results from this new technique are compared to other heuristics (SOM, SA and heuristics of remotion and insertion of arcs), with data from the traveling salesman problem library (TSPLIB). The 2-opt local search technique is applied to the final solutions of the proposed technique and shows a considerable improvement of the results. The advantages of this new technique are the easy computational implementation, the low computational complexity, the good results obtained and the possibility of solving symmetrical and asymmetrical problems with the same technique. (c) 2006 Elsevier B.V. All rights reserved.