一种求解平面旅行商问题的新算法--内外环周游法

• 作者: 宇德明
• 来源期刊: 基建优化
• 学科: 工学
• 关键词: 组合优化 内外环周游法 数值试验 平面旅行商问题 最近临算法 对比分析
• 年，卷（期）: 2005,（6）
• 所属期刊栏目: 规划与设计
• 页码范围: 92-95
• 页数: 4页
• 分类号: F59|TP301.6
• 字数: 3825字
• 语种: 中文

摘要

首先提出一种求解平面旅行商问题新算法-内外环周游法,它是一种确定型算法,时间复杂性小于或等于O(n2).然后,利用自己编写的内外环周游法和最近临算法程序,对不同规模随机平面旅行商问题和标准平面旅行商问题进行数值试验,对两种算法的求解质量进行对比分析,得到如下结论:(1)内外环周游法和最近临算法求解质量的相对优劣取决于具体问题中城市的数量和分布.(2)对于4城市问题,内外环周游法总能得到最优解,而最近临算法经常不能得到最优解.(3)对于城市数少于20的问题,内外环周游法的求解质量一般优于最近临算法的求解质量.(4)对于城市数介于20和70的问题,内外环周游法的求解质量总体上相当于最近临算法的求解质量.(5)对于城市数多于70的问题,内外环周游法的求解质量一般次于最近临算法的求解质量.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宇德明	中南大学土木建筑学院	37	221	9.0	13.0