求解TSP问题的最近邻域与插入混合算法  

Hybrid algorithm of the nearest neighbor and insertion for the traveling salesman problem

作　　者：饶卫振[1] 金淳[1] 黄英艺[1] 

机构地区：[1]大连理工大学系统工程研究所,大连116024

出　　处：《系统工程理论与实践》2011年第8期1419-1428,共10页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(70571008);辽宁省自然科学基金(20062184)

摘　　要：研究了求解旅行商问题(TSP)的构建型启发式算法中的最近邻域算法和插入算法的特点,集最近邻域算法求解速度快、插入算法求解质量高的优点,提出了一种最近邻域与插入混合算法.分析了混合算法的合理性、复杂度及参数取值,并分别采用以上三种算法求解了TSPLIB标准库中多个算例,结果表明混合算法的求解速度接近最近邻域算法,对城市数量小于1000的小规模TSP问题的求解质量与插入算法相当,而对大规模TSP问题的求解质量明显优于插入算法.This paper presented a new hybrid construction heuristic algorithm（NNIN） -combination of the nearest neighbor algorithm（NN） and the insertion algorithm（IN）,based on analyzing properties of NN and IN algorithm for solving the traveling salesman problem（TSP）.Moreover,we studied the rationality, complexity,parameter setting of the hybrid algorithm and solved many benchmark instances from TSPLIB using NN,NNIN,IN algorithm respectively.Computational results show that NNIN algorithm whose running time is close to NN can yield solutions as good as IN for small TSP（the number of city is less than one thousand） and better solutions for large TSP than IN,and prove that the efficiency and effectiveness of the proposed hybrid algorithm outperform both NN algorithm and IN algorithm.

关 键 词：旅行商问题 混合算法 最近邻域算法 插入算法 

分 类 号：F502[经济管理—产业经济]