|
个人信息Personal Information
教授
博士生导师
硕士生导师
性别：男
毕业院校：日本长冈技术科技大学
学位：博士
所在单位：运营与物流管理研究所
学科：管理科学与工程
办公地点：经济管理学院新楼D412
联系方式：辽宁省大连市甘井子区凌工路2号 大连理工大学 经济管理学院 邮编：116024 电话：0411-84709425
电子邮箱：jinchun@dlut.edu.cn
扫描关注
考虑边位置信息的求解ETSP问题改进贪婪算法
点击次数：
论文类型：期刊论文
发表时间：2013-04-15
发表刊物：计算机学报
收录刊物：EI、PKU、ISTIC、CSCD、Scopus
卷号：36
期号：4
页面范围：836-850
ISSN号：0254-4164
关键字：欧几里德旅行商问题;贪婪算法;Michael模型;求解质量;求解耗时
摘要：分析了贪婪算法(Greedy algorithm,GRA)求解欧几里德旅行商问题(Euclidean Traveling Salesman Problem,ETSP)的求解质量和求解耗时的特点,发现边位置信息是影响GRA的求解质量和求解耗时的主要因素,在Michael模型基础上提出了一种考虑添加边所在位置信息的改进贪婪算法(Improved Greedy algorithm,IMGRA),并阐述了IMGRA的设计思想和相应的构造方法.分别采用IMGRA和GRA求解了90个算例,结果表明:固定参数下的IMGRA平均求解质量较GRA提高55％,求解耗时降低20％.为此,对IMGRA比GRA求解质量更高和求解耗时更短的原因进行了分析.