| 一种求解平面旅行商问题的新算法--内外环周游法 |
| |
| 引用本文： | 宇德明. 一种求解平面旅行商问题的新算法--内外环周游法[J]. 基建优化, 2005, 26(6): 92-95 |
| |
| 作者姓名： | 宇德明 |
| |
| 作者单位： | 中南大学,土木建筑学院,长沙,410075 |
| |
| 摘 要： | 首先提出一种求解平面旅行商问题新算法—内外环周游法，它是一种确定型算法，时间复杂性小于或等于O（n^2）。然后，利用自己编写的内外环周游法和最近临算法程序，对不同规模随机平面旅行商问题和标准平面旅行商问题进行数值试验，对两种算法的求解质量进行对比分析，得到如下结论：（1）内外环周游法和最近临算法求解质量的相对优劣取决于具体问题中城市的数量和分布。（2）对于4城市问题，内外环周游法总能得到最优解，而最近临算法经常不能得到最优解。（3）对于城市数少于20的问题，内外环周游法的求解质量一般优于最近临算法的求解质量。（4）对于城市数介于20和70的问题，内外环周游法的求解质量总体上相当于最近临算法的求解质量。（5）对于城市数多于70的问题，内外环周游法的求解质量一般次于最近临算法的求解质量。
|
| 关 键 词： | 组合优化 内外环周游法 数值试验 平面旅行商问题 最近临算法 对比分析 |
| 文章编号： | 1000-7717(2005)06-0092-04 |
| 收稿时间： | 2005-07-02 |
| 修稿时间： | 2005-07-02 |
A New Algorithm to Solve Plane Travelling Salesman Problems the Travelling-around-Inner-Ring-and-Outer-Ring |
| |
| YU De-ming. A New Algorithm to Solve Plane Travelling Salesman Problems the Travelling-around-Inner-Ring-and-Outer-Ring[J]. Optimization of Capital Construction, 2005, 26(6): 92-95 |
| |
| Authors: | YU De-ming |
| |
| Abstract: | |
| |
| Keywords: | oornbination optimization travelling-around-inner-ring-and-outer-ring method numerical tests planetravelling salesman problem nearest neighbor algorithm comparison analysis |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
