一类求解TSP构建型算法的通用改进策略

摘要：

分析了求解旅行商问题(traveling salesman problem,TSP)的4种贪婪构建型算法的特点,发现这类算法的最大缺点是在求解初期以贪婪的方式构建解,导致求解后阶段为初期的贪婪付出代价.本文在Held Karp模型基础上提出了一种改造TSP问题距离矩阵的方法——距离矩阵方差最小法(minimizing variance of distance matrix,MVODM),以降低这类算法构建初期的贪婪性,提高算法的总体求解质量.分别采用4种贪婪构建型算法结合和不结合MVODM两种方式,求解了TSPLIB标准库中54个算例,以验证MVODM的有效性.求解结果表明:MVODM能够非常有效地提高4种算法的求解质量,部分改进后的算法质量甚至超过很多世界一流的构建型算法,并且MVODM的执行效率非常高,当算例的规模达到2319时在本实验计算机上的耗时仅为o.076 s,算法的耗时增加量几乎可以忽略不计.

关键词：组合优化、旅行商问题、构建型算法、计算方法、通用策略

所属期刊栏目：45

分类号：TP391;TP242;TP18

资助基金：国家自然科学基金;山东省优秀中青年科学家科研奖励基金;人才引进科研启动基金

在线出版日期：2015-09-16（万方平台首次上网日期，不代表论文的发表时间）

页码：1060-1079