论文部分内容阅读
针对大型TSP(traveling salesman problem)实例很难找到最优解的问题,提出了一种选择性集成求解方法。首先通过扩大路径法来选择集成多个较好解,构造出若干个极大路径;然后采用顶点插入法将剩余顶点和这些极大路径连接成一个哈密顿回路;最后使用2-opt方法对该回路进行提升。试验结果表明,算法在5个TSP实例上得出的最好解的最大偏差为1.69%,说明本算法可以有效求解TSP。
Aiming at the problem that it is difficult to find the optimal solution for a large traveling salesman problem (TSP), a method of selective integration is proposed. First of all, we use the extended path method to choose to integrate multiple good solutions to construct a number of maximal paths. Then, the vertex interpolation method is used to connect the remaining vertices with these maximal paths into a Hamiltonian loop. Finally, Loop to enhance. The experimental results show that the maximum deviation of the best solution obtained by the algorithm from the five TSP instances is 1.69%, which shows that this algorithm can effectively solve the TSP.