论文部分内容阅读
研究了求解旅行商问题(TSP)的构建型启发式算法中的最近邻域算法和插入算法的特点,集最近邻域算法求解速度快、插入算法求解质量高的优点,提出了一种最近邻域与插入混合算法.分析了混合算法的合理性、复杂度及参数取值,并分别采用以上三种算法求解了TSPLIB标准库中多个算例,结果表明混合算法的求解速度接近最近邻域算法,对城市数量小于1000的小规模TSP问题的求解质量与插入算法相当,而对大规模TSP问题的求解质量明显优于插入算法.
In this paper, the characteristics of nearest neighbor algorithm and interpolation algorithm in constructing heuristic algorithm to solve Traveling Salesman Problem (TSP) are studied. Combining the advantages of nearest neighbor algorithm in solving fast and inserting algorithm in solving high quality problem, a nearest neighbor Domain and insert hybrid algorithm.The rationality, complexity and parameter values of the hybrid algorithm are analyzed, and three examples of TSPLIB standard library are respectively used to solve the multiple examples in the standard library. The results show that the hybrid algorithm is close to the nearest neighborhood Algorithm, the quality of solution to the small-scale TSP problem with the number of cities less than 1000 is equivalent to that of the insertion algorithm, while the quality of solving the large-scale TSP problem is obviously better than the insertion algorithm.