Abstract:

This paper proposes the thought of getting the edges of exact solution to access the approximate solution of the whole Traveling Salesman Problem(TSP). On the basic of the thought, a new algorithm called collision algorithm is designed. Experiments with the test data from internationally accepted TSPLIB in different cities and size show that the results got through the algorithm is the same or similar with current optimal solution. The algorithm can apply the TSP on a large scale as well as small scale ones.

Key words: Traveling Salesman Problem(TSP), triangulation, combinatorial optimization, collision algorithm

摘要：

提出通过寻找精确解的边获得旅行商问题(TSP)近似解的思想，并以该思想为指导，设计一种新的碰撞算法。对国际通用的TSPLIB中不同城市规模的数据进行测试表明，该算法可以得到与目前已知最优解或相同或相近的结果。该算法不仅可以计算小规模的TSP，而且同样适用较大规模的TSP。

关键词: 旅行商问题, 三角剖分, 组合优化, 碰撞算法

CLC Number: 

• TP301.6