作者：饶卫振 金淳运筹学旅行商问题改进贪婪算法heldkarp模型
摘要：分析了求解旅行商问题（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的求解性能达到一流构建型算法水平。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
