考虑边位置信息的求解ETSP问题改进贪婪算法

被引：19

作者：

饶卫振 ^{[1
,2
]}

金淳 ^{[1
]}

陆林涛 ^{[3
]}

机构：

[1] 大连理工大学系统工程研究所

[2] 山东科技大学经济管理学院

[3] 中国人民解放军部队

来源：

计算机学报 | 2013年 / 36卷 / 04期

关键词：

欧几里德旅行商问题; 贪婪算法; Michael模型; 求解质量; 求解耗时;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

分析了贪婪算法(Greedy algorithm,GRA)求解欧几里德旅行商问题(Euclidean Traveling SalesmanProblem,ETSP)的求解质量和求解耗时的特点,发现边位置信息是影响GRA的求解质量和求解耗时的主要因素,在Michael模型基础上提出了一种考虑添加边所在位置信息的改进贪婪算法(Improved Greedy algorithm,IMGRA),并阐述了IMGRA的设计思想和相应的构造方法.分别采用IMGRA和GRA求解了90个算例,结果表明:固定参数下的IMGRA平均求解质量较GRA提高55%,求解耗时降低20%.为此,对IMGRA比GRA求解质量更高和求解耗时更短的原因进行了分析.

引用

页码：836 / 850

页数：15

共 12 条

[1] 基于求解TSP问题的双向扩展差额算法 [J].

饶卫振 ;

金淳 ;

黄英艺 .

管理工程学报, 2011, 25 (02) :95-102

[2] 蚁群算法与免疫算法的融合及其在TSP中的应用 [J].

刘朝华 ;

张英杰 ;

章兢 ;

吴建辉 .

控制与决策, 2010, 25 (05) :695-700+705

[3] A Hybrid Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery [J].

FangGeng Zhao JiangSheng Sun SuJian Li WeiMin Liu Vehicle Management Institute Bengbu PRC Department of Logistics Engineering University of Science and Technology Beijing Beijing PRC Ordnance Technology Research Institute Shijiazhuang PRC .

International Journal of Automation & Computing, 2009, (01) :97-102

[4] 求解TSP问题的离散粒子群优化算法 [J].