基于求解TSP问题的改进贪婪算法  

An Improved Greedy Heuristic Based on Solving Traveling Salesman Problem

作　　者：饶卫振[1] 金淳[1] 

机构地区：[1]大连理工大学系统工程研究所,辽宁大连116024

出　　处：《运筹与管理》2012年第6期1-9,共9页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(70571008);辽宁省自然科学基金资助项目(20062184)

摘　　要：分析了求解旅行商问题(Traveling Salesman Problem,TSP)的经典贪婪算法(Greedy Heuristic,GR)的特点,发现影响GR求解质量的主要因素是在构造后期添加的边过长,从而导致最终求解质量不高。为此,借鉴Held Karp模型的思路,构造了一种新的距离矩阵改造法(Transforming Distance Matrix,TDM)。GR结合TDM得到的改进贪婪算法GR-TDM能够有效地克服传统GR在构造后期添加长边的缺点。通过计算来自TSP算例标准库和TSP世界挑战赛网站中的40个算例表明,GR-TDM耗时较GR仅增加了0.5～2%,然而GR-TDM的求解质量较传统的GR提高了43%。另外,通过与当前构建型算法比较发现,GR-TDM的求解性能达到一流构建型算法水平。In this paper, we analyze the properties of the classic construction heuristic GR. It is found that the main disadvantage of GR is that the edges added by GR at last are too long, resulting in a poor tour. Thus an ap- proach transforming distance matrix（TDM） is proposed to improve the tour quality of GR, based on the theory of Held Karp model. As a consequence, GR combining TDM（GR-TDM） results in an efficient and effective heuris- tic, and GR-TDM overcomes significantly the disadvantage of GR. The experimental results on 40 instances from TSPLIB and TSP Challenge website show that GR-TDM is slower by 0.5-2% than GR for all instances, but the average tour quality of GR-TDM is better by 43% than that of GR. Moreover, GR-TDM is the first class heuristic among existing construction heuristics by comparing their tour quality and running time.

关 键 词：运筹学 旅行商问题 改进贪婪算法 HeldKarp模型 

分 类 号：F502[经济管理—产业经济]