-
题名一种求解平面旅行商问题的新算法—内外环周游法
- 1
-
-
作者
宇德明
-
机构
中南大学土木建筑学院
-
出处
《基建优化》
2005年第6期92-95,共4页
-
文摘
首先提出一种求解平面旅行商问题新算法—内外环周游法,它是一种确定型算法,时间复杂性小于或等于O(n2)。然后,利用自己编写的内外环周游法和最近临算法程序,对不同规模随机平面旅行商问题和标准平面旅行商问题进行数值试验,对两种算法的求解质量进行对比分析,得到如下结论:(1)内外环周游法和最近临算法求解质量的相对优劣取决于具体问题中城市的数量和分布。(2)对于4城市问题,内外环周游法总能得到最优解,而最近临算法经常不能得到最优解。(3)对于城市数少于20的问题,内外环周游法的求解质量一般优于最近临算法的求解质量。(4)对于城市数介于20和70的问题,内外环周游法的求解质量总体上相当于最近临算法的求解质量。(5)对于城市数多于70的问题,内外环周游法的求解质量一般次于最近临算法的求解质量。
-
关键词
组合优化
内外环周游法
数值试验
平面旅行商问题
最近临算法
对比分析
-
Keywords
oornbination optimization
travelling-around-inner-ring-and-outer-ring method
numerical tests
planetravelling salesman problem
nearest neighbor algorithm
comparison analysis
-
分类号
F59
[经济管理—旅游管理]
TP301.6
[经济管理—产业经济]
-
-
题名一种求解平面旅行商问题的新算法——绕中心周游法
- 2
-
-
作者
宇德明
-
机构
中南大学土木建筑学院
-
出处
《科技导报》
CAS
CSCD
2007年第15期53-57,共5页
-
文摘
提出了一种求解平面旅行商问题的新算法——绕中心周游法,它是一种确定型算法,时间复杂性与最近邻算法相同,为O(n2),其中n为城市数。利用所编写的绕中心周游法和最近邻算法程序,对不同规模的平面旅行商问题进行了数值试验,对两种算法的求解质量进行了对比分析。结果表明:①绕中心周游法和最近邻算法求解质量的相对优劣取决于具体问题中城市的数量和分布;②对于4城市问题,绕中心周游法总能得到最优解,而最近邻算法经常不能得到最优解;③对于小规模(n<20)问题,绕中心周游法的求解质量一般优于最近邻算法的求解质量;④对于中等规模(20≤n≤30)问题,绕中心周游法的求解质量总体上相当于最近邻算法的求解质量;⑤对于大规模(n>30)问题,绕中心周游法的求解质量一般次于最近邻算法的求解质量。
-
关键词
平面旅行商问题
绕中心周游法
数值试验
最近邻算法
对比分析
-
Keywords
plane travelling salesman problem
travelling-around-the-center method
numerical tests
nearest neighbor algorithm
comparison analysis
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
