Cellular Competitive Decision Algorithm for Traveling Salesman Problem
Xiaohua Xiong, Aibing Ning · 2014
Among all combinatorial optimization problems, traveling salesman problem (TSP) is one of the widely studied problems. Though the optimization version of this problem is NP-hard, practical solution techniques don't require optimality. And many different heuristics and approximation algorithms are used to solve this problem. Cellular competitive decision algorithm (CCDA) is a new heuristic for solving hard problem, especially those NP-hard problems. One of the biggest characteristic of CCDA is easy to integrate the mathematical feature with the problem itself together. Firstly, mathematical properties of traveling salesman problem are analyzed to calculate the lower bound of the problem. Then a CCDA for traveling salesman problem is presented. In order to test its validity, we carry out extensive computational experiments. From the results we know the presented algorithm has a satisfactory behavior both in running time and the quality of the solution found.