Hits:

Indexed by:期刊论文

Date of Publication:2012-12-25

Journal:运筹与管理

Included Journals:PKU、ISTIC、CSCD

Volume:21

Issue:6

Page Number:1-9

ISSN No.: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 的求解性能达到一流构建型算法水平.