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

An Improved Greedy Algorithm with Information of Edges' Location for Solving the Euclidean Traveling Salesman Problem

作　　者：饶卫振[1,2] 金淳[1] 陆林涛[3] 

机构地区：[1]大连理工大学系统工程研究所 [2]山东科技大学经济管理学院 [3]中国人民解放军61512部队

出　　处：《计算机学报》2013年第4期836-850,共15页Chinese Journal of Computers

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

摘　　要：分析了贪婪算法(Greedy algorithm,GRA)求解欧几里德旅行商问题(Euclidean Traveling SalesmanProblem,ETSP)的求解质量和求解耗时的特点,发现边位置信息是影响GRA的求解质量和求解耗时的主要因素,在Michael模型基础上提出了一种考虑添加边所在位置信息的改进贪婪算法(Improved Greedy algorithm,IMGRA),并阐述了IMGRA的设计思想和相应的构造方法.分别采用IMGRA和GRA求解了90个算例,结果表明:固定参数下的IMGRA平均求解质量较GRA提高55%,求解耗时降低20%.为此,对IMGRA比GRA求解质量更高和求解耗时更短的原因进行了分析.This paper presents an improved greedy algorithm（IMGRA） with information of edges＇ location,by using Michael model and analyzing the disadvantages of greedy algorithm（GRA） for solving the Euclidean traveling salesman problem（ETSP）.We described the core idea and construction method of IMGRA and solved 90 benchmark instances from TSPLIB and literatures using IMGRA and GRA respectively.Computational results indicate that the average quality of solutions generated by IMGRA improve by 55 percent than that of solutions generated by GRA,furthermore,the running time of IMGRA reduce by about 20 percent than that of GRA.We analyze the causes that IMGRA can produce the better solutions in less running time than GRA.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]