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

摘要：

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

关键词：欧几里德旅行商问题、贪婪算法、Michael模型、求解质量、求解耗时

所属期刊栏目：36

分类号：TP301(计算技术、计算机技术)

资助基金：国家教育部博士点基金20100041110024

在线出版日期：2013-07-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：836-850