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

• 作者: 金淳 陆林涛 饶卫振
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 欧几里德旅行商问题 贪婪算法 Michael模型 求解质量 求解耗时
• 年，卷（期）: 2013,（4）
• 所属期刊栏目: 计算机理论
• 页码范围: 836-850
• 页数: 15页
• 分类号: TP301
• 字数: 9039字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2013.00836

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	金淳	大连理工大学系统工程研究所	66	976	18.0	28.0
2	饶卫振	大连理工大学系统工程研究所	19	186	7.0	13.0