中文摘要：

针对大型TSP（traveling salesman problem）实例很难找到最优解的问题,提出了一种选择性集成求解方法。首先通过扩大路径法来选择集成多个较好解,构造出若干个极大路径;然后采用顶点插入法将剩余顶点和这些极大路径连接成一个哈密顿回路;最后使用2-opt方法对该回路进行提升。试验结果表明,算法在5个TSP实例上得出的最好解的最大偏差为1.69%,说明本算法可以有效求解TSP。

英文摘要：

To solve the problem of finding the optimum solution of very large TSP（ traveling salesman problem）,a selective ensemble method was proposed. Firstly,expanding path method was used to selective integrate some high quality solutions,and several maximum paths were obtained. And then vertex insertion method was employed to connect these paths and the remainder vertices to form a Hamiltonian tour. Finally,the tour was improved by 2-opt method. Experimental results on 5 TSP instances showed that the maximal bias was 1. 69%,and the effectiveness was proved.