|
个人信息Personal Information
教授
博士生导师
硕士生导师
性别：男
毕业院校：日本长冈技术科技大学
学位：博士
所在单位：运营与物流管理研究所
学科：管理科学与工程
办公地点：经济管理学院新楼D412
联系方式：辽宁省大连市甘井子区凌工路2号 大连理工大学 经济管理学院 邮编：116024 电话：0411-84709425
电子邮箱：jinchun@dlut.edu.cn
扫描关注
求解TSP问题的最近邻域与插入混合算法
点击次数：
论文类型：期刊论文
发表时间：2011-08-15
发表刊物：系统工程理论与实践
收录刊物：EI、PKU、ISTIC、CSCD、Scopus
卷号：31
期号：8
页面范围：1419-1428
ISSN号：1000-6788
关键字：旅行商问题;混合算法;最近邻域算法;插入算法
摘要：研究了求解旅行商问题(TSP)的构建型启发式算法中的最近邻域算法和插入算法的特点,集最近邻域算法求解速度快、插入算法求解质量高的优点,提出了一种最近邻域与插入混合算法.分析了混合算法的合理性、复杂度及参数取值,并分别采用以上三种算法求解了TSPLIB标准库中多个算例,结果表明混合算法的求解速度接近最近邻域算法,对城市数量小于1000的小规模TSP问题的求解质量与插入算法相当,而对大规模TSP问题的求解质量明显优于插入算法.