Release Time:2019-03-11  Hits:

Indexed by: Journal Article

Date of Publication: 2012-12-25

Journal: 运筹与管理

Included Journals: CSCD、ISTIC、PKU

Volume: 21

Issue: 6

Page Number: 1-9

ISSN: 1007-3221

Key Words: 运筹学 旅行商问题 改进贪婪算法 Held Karp 模型 operations research traveling salesman problem improved greedy heuristic Held Karp model

Abstract: 分析了求解旅行商问题(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 的求解性能达到一流构建型算法水平.