旅行商问题的一种选择性集成求解方法

作者：王立宏; 李强

来源：山东大学学报(工学版), 2016, 46(01): 42-48.

• 人工智能
• 选择性集成学习
• 旅行商问题
• 极大路径
• 顶点插入

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

• 单位
  经济管理学院; 烟台大学