Particle Swarn Optimization with Fast Local Search for the Blind Traveling Salesman Problem

The classical travelling salesman problem (TSP) is to determine a tour in a weighted graph (that is, a cycle that visits every vertex exactly once) such that the sum of the weights of the edges in this tour is minimal. Hybrid methods, based on nature inspired heuristics, have shown their ability to provide high quality solutions for the TSP. The success of a hybrid algorithm is due to its tradeoff between the exploration and exploitation abilities in search space. This work presents a new hybrid model, based on Particle Swarm Optimization and Fast Local Search, with concepts of Genetic Algorithms, for the blind TSP A detailed description of the model is provided, emphasizing its hybrid features. The control parameters were carefully adjusted and the implemented system was tested with instances from 76 to 2103 cities. For instances up to 439 cities, the best results were less than 1% in excess ofthe known optima. In the average, for all instances, results are 2.538% in excess. Simularion results indicated that the proposed hybrid model performs robustly. These results encourage further research and improvement of the hybrid model to tackle with hard combinatorial problems.