|
个人信息Personal Information
教授
博士生导师
硕士生导师
性别：男
毕业院校：日本长冈技术科技大学
学位：博士
所在单位：运营与物流管理研究所
学科：管理科学与工程
办公地点：经济管理学院新楼D412
联系方式：辽宁省大连市甘井子区凌工路2号 大连理工大学 经济管理学院 邮编：116024 电话：0411-84709425
电子邮箱：jinchun@dlut.edu.cn
基于求解 TSP 问题的改进贪婪算法
点击次数：
论文类型：期刊论文
发表时间：2012-12-25
发表刊物：运筹与管理
收录刊物：PKU、ISTIC、CSCD
卷号：21
期号：6
页面范围：1-9
ISSN号：1007-3221
关键字：运筹学 旅行商问题 改进贪婪算法 Held Karp 模型 operations research traveling salesman problem improved greedy heuristic Held Karp model
摘要：分析了求解旅行商问题(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 的求解性能达到一流构建型算法水平.