摘要
首先提出一种求解平面旅行商问题新算法—内外环周游法,它是一种确定型算法,时间复杂性小于或等于O(n2)。然后,利用自己编写的内外环周游法和最近临算法程序,对不同规模随机平面旅行商问题和标准平面旅行商问题进行数值试验,对两种算法的求解质量进行对比分析,得到如下结论:(1)内外环周游法和最近临算法求解质量的相对优劣取决于具体问题中城市的数量和分布。(2)对于4城市问题,内外环周游法总能得到最优解,而最近临算法经常不能得到最优解。(3)对于城市数少于20的问题,内外环周游法的求解质量一般优于最近临算法的求解质量。(4)对于城市数介于20和70的问题,内外环周游法的求解质量总体上相当于最近临算法的求解质量。(5)对于城市数多于70的问题,内外环周游法的求解质量一般次于最近临算法的求解质量。
A new algorithm, called the travelling-around-inner-ring-and-outer-ring method, is first put forward in this paper. It is a definite algorithm, and its time complexity is equal to or less than O（n^2） , where n is the city number. Then, numerical tests of plane travelling salesman problems with various sizes are carried out by using the new algorithm program and the nearest neighbor algorithm program, which are developed by the author, and the relative qualities of the solutions obtained by applying both of them are compared. Finally, the following conclusions are obtained： （1） The relative qualities of the solutions obtained by applying both of them depend on the number and distribution of the cities in a specific travelling salesman problem. （2） For n=4, the new algorithm can always obtain the best solution, while the nearest neighbor algorithm often cannot do so. （3） For small size problems with n〈20, the new algorithm can generally obtain better solutions than the nearest neighbor algorithm. （4） For plane travelling salesman problems with 20≤n≤70, as a whole, the quality of the solution obtained by the new algorithm is equivalent to that obtained by the nearest neighbor algorithm. （5） For plane travelling salesman problems with n〉70, the quality of the solution obtained by the new algorithm is generally not as good as that obtained by the nearest neighbor algorithm.
出处
《基建优化》
2005年第6期92-95,共4页
Optimization of Capital Construction
关键词
组合优化
内外环周游法
数值试验
平面旅行商问题
最近临算法
对比分析
oornbination optimization
travelling-around-inner-ring-and-outer-ring method
numerical tests
planetravelling salesman problem
nearest neighbor algorithm
comparison analysis
