摘要
提出了一种求解平面旅行商问题的新算法——绕中心周游法,它是一种确定型算法,时间复杂性与最近邻算法相同,为O(n2),其中n为城市数。利用所编写的绕中心周游法和最近邻算法程序,对不同规模的平面旅行商问题进行了数值试验,对两种算法的求解质量进行了对比分析。结果表明:①绕中心周游法和最近邻算法求解质量的相对优劣取决于具体问题中城市的数量和分布;②对于4城市问题,绕中心周游法总能得到最优解,而最近邻算法经常不能得到最优解;③对于小规模(n<20)问题,绕中心周游法的求解质量一般优于最近邻算法的求解质量;④对于中等规模(20≤n≤30)问题,绕中心周游法的求解质量总体上相当于最近邻算法的求解质量;⑤对于大规模(n>30)问题,绕中心周游法的求解质量一般次于最近邻算法的求解质量。
A new algorithm, called the travelling-around-the-center method, is proposed in this paper. It is a deterministic algorithm, with its time complexity the same as the nearest neighbor algorithm, that is, O（n^2）, where n is the number of cities. Numerical tests for plane travelling salesman problems with various sizes are carried out by using the travelling-around-the-center method and the nearest neighbor algorithm, and the performances of both algorithms are compared. The following conclusions are drawn： （1） The relative performances of the solutions of the travelling-around-the-center method and the nearest neighbor algorithm depend on the number and distribution of the cities in a specific travelling salesman problem. （2） For n =4, the travelling-around-the-center method can always obtain the best solution, while the nearest neighbor algorithm often cannot do so. （3） For a small size problem with n〈20, the travelling-around-the-center method can generally obtain better solutions than the nearest neighbor algorithm. （4） For a middle size problem with 20≤n≤30, the quality of the solution obtained by the travellingaround-the-center method is similar to that obtained by the nearest neighbor algorithm. （5） For a large size problem with n〉30, the quality of the solution obtained by the travelling-around-the-center method is generally not as good as that obtained by the nearest neighbor algorithm.
出处
《科技导报》
CAS
CSCD
2007年第15期53-57,共5页
Science & Technology Review
关键词
平面旅行商问题
绕中心周游法
数值试验
最近邻算法
对比分析
plane travelling salesman problem
travelling-around-the-center method
numerical tests
nearest neighbor algorithm
comparison analysis
