|
|||||
|
|
| 考虑边位置信息的求解ETSP问题改进贪婪算法 | |
| 引用本文： | 饶卫振,金淳,陆林涛.考虑边位置信息的求解ETSP问题改进贪婪算法[J].计算机学报,2013,36(4):836-850. |
| 作者姓名： | 饶卫振 金淳 陆林涛 |
| 作者单位： | 1. 大连理工大学系统工程研究所 辽宁 大连 116024;山东科技大学经济管理学院 山东青岛 266590 2. 大连理工大学系统工程研究所 辽宁 大连 116024 3. 中国人民解放军61512部队 北京 100088 |
| 摘 要： | 分析了贪婪算法(Greedy algorithm,GRA)求解欧几里德旅行商问题(Euclidean Traveling SalesmanProblem,ETSP)的求解质量和求解耗时的特点,发现边位置信息是影响GRA的求解质量和求解耗时的主要因素,在Michael模型基础上提出了一种考虑添加边所在位置信息的改进贪婪算法(Improved Greedy algorithm,IMGRA),并阐述了IMGRA的设计思想和相应的构造方法.分别采用IMGRA和GRA求解了90个算例,结果表明:固定参数下的IMGRA平均求解质量较GRA提高55%,求解耗时降低20%.为此,对IMGRA比GRA求解质量更高和求解耗时更短的原因进行了分析. |
| 关 键 词： | 欧几里德旅行商问题 贪婪算法 Michael模型 求解质量 求解耗时 |
An Improved Greedy Algorithm with Information of Edges' Location for Solving the Euclidean Traveling Salesman Problem |
|
| RAO Wei-Zhen , JIN Chun , LU Lin-Tao.An Improved Greedy Algorithm with Information of Edges' Location for Solving the Euclidean Traveling Salesman Problem[J].Chinese Journal of Computers,2013,36(4):836-850. | |
| Authors: | RAO Wei-Zhen JIN Chun LU Lin-Tao |
| Affiliation: | 1)(Institute of Systems and Engineering,Dalian University of Technology,Dalian,Liaoning 116024) 2)(College of Economics and Management,Shandong University of Science and Technology,Qingdao,Shandong 266590) 3)(Chinese People’s Liberation Army 61512 Armed Forces,Beijing 100088) |
| Abstract: | |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |