路径交叉检测与消除方法和邻节点置换方法改进TSP的解

• 作者: 伍国华 马满好
• 来源期刊: 计算机应用研究
• 关键词: 旅行商问题 路径交叉检测与消除 邻节点置换
• 年，卷（期）: 2011,（2）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 485-487
• 分类号: TP18
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2011.02.021

摘要

针对当前算法在求解规模较大的TSP时得到的近似解中常常存在路径交叉这一不足,提出了一种路径交叉检测与消除方法.可以完全消除路径交叉从而提高近似解的质量;通过分析近似解的结构,发现一些相邻节点相互交换位置也可以有效提高解的质量,因此提出了一种邻节点置换方法.实验表明提出的方法可以有效改进模拟退火算法求得的TSP近似解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	马满好	国防科学技术大学信息系统与管理学院	15	109	7.0	10.0
2	伍国华	国防科学技术大学信息系统与管理学院	12	86	6.0	9.0