基于二点组合算法的旅行商问题应用性能分析

旅行商问题模型应用广泛，其求解策略的研究具有重要的理论和实践意义。为高效快速解决旅行商问题，给出一种基于环路改造的二点组合算法，即选取一条汉密尔顿环路作为目标解，任取两个顶点删除与之相关的边形成2至4个环路片断，对这些环路片断进行排列组合，尝试寻找更优的解替换目标解的方法。仿真实验结果表明，该算法的计算效率和计算误差性能皆优于蚁群算法，实际应用结果也表明本算法在解决中小规模旅行商问题时的实用性。因此，本算法具有较强的理论价值和较强的实用价值，可以较好地完成中等规模的TSP问题，且适用于一系列的优化组合问题。

Performance Analysis of Two Vertices Combination Algorithm in TSP

In order to efficiently solve TSP problem, given a two vertices combination algorithm based on loop transformation. Hamilton Circle is selected as the target of a solution, take any two vertices associated with edges removed to form 2 to 4 loop clips, clips of permutations and combinations of these loops, try to find better solutions replaced target solution method. Comparing this method with ant colony algorithm, its time complexity and computational accuracy are better than those of the latter. The results show that this proposed algorithm possesses a better practicability in solving the middle and small scale traveling salesman problem. So, .this method has strong theoretical and practical value. It can better complete the medium-scale TSP problems, and it applied to a series of optimization.