摘要
分析了求解旅行商问题(traveling salesman problem,TSP)的4种贪婪构建型算法的特点,发现这类算法的最大缺点是在求解初期以贪婪的方式构建解,导致求解后阶段为初期的贪婪付出代价.本文在Held Karp模型基础上提出了一种改造TSP问题距离矩阵的方法——距离矩阵方差最小法(minimizing variance of distance matrix,MVODM),以降低这类算法构建初期的贪婪性,提高算法的总体求解质量.分别采用4种贪婪构建型算法结合和不结合MVODM两种方式,求解了TSPLIB标准库中54个算例,以验证MVODM的有效性.求解结果表明:MVODM能够非常有效地提高4种算法的求解质量,部分改进后的算法质量甚至超过很多世界一流的构建型算法,并且MVODM的执行效率非常高,当算例的规模达到2319时在本实验计算机上的耗时仅为0.076 s,算法的耗时增加量几乎可以忽略不计.
In this paper, we analyze the characteristics of four construction heuristics for solving the traveling salesman problem（TSP） and determine that the greatest common weakness of this type of heuristic lies in the greedy construction of solutions during the initial search period. Based on the Held Karp model, we propose the method of Minimizing Variance of Distance Matrix（MVODM） to transform the distance matrix for TSP problems. This method could reduce the greediness of construction during the initial period and improve the overall quality of the solutions. To evaluate the effectiveness of the method, we solve 54 benchmark instances from TSPLIB by using four greedy construction heuristics with and without MVODM for comparison. The results show that MVODM could greatly enhance the solution quality of four heuristics, and some improved heuristics even outperform many world-leading construction heuristics. Moreover, the efficiency of MVODM is so high that an instance size of 2319 cities was run in only 0.076 s on our computer. The increased computation time caused by MVODM could largely be omitted.
出处
《中国科学：信息科学》
CSCD
北大核心
2015年第8期1060-1079,共20页
Scientia Sinica(Informationis)
基金
国家自然科学基金(批准号:71271041)
山东省优秀中青年科学家科研奖励基金(批准号:BS2014SF001)
山东科技大学人才引进科研启动基金(批准号:2013RCJJ020)资助项目
关键词
组合优化
旅行商问题
构建型算法
计算方法
通用策略
combinatorial optimization
traveling salesman problem
construction heuristic
computational meth-ods
universal strategy
