基于二维凸包的TSP算法

• 作者: 刘宏兵 周文勇 邬长安
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: 二维凸包 旅行商问题 长度增量 快速凸包算法 凸点
• 年，卷（期）: 2009,（8）
• 所属期刊栏目: 人工智能
• 页码范围: 1954-1956,2000
• 页数: 4页
• 分类号: TP301.6
• 字数: 2666字
• 语种: 中文

摘要

二维凸包是指包含平面点集的最小简单多边形,广泛应用于GIS.将二维凸包与TSP相结合,提出了基于二维凸包的TSP算法,首先快速凸包算法构造城市点集的凸包,该凸包是经过部分城市点且其余点都在其内部的回路.其次将其余的城市点依次插入回路形成新回路,使新回路的长度增量最小,直至所有的城市点都在回路上.在TSPLIB中的典型实例上的实验结果表明,该算法比简单遗传算法更快得到问题的近似解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘宏兵	武汉理工大学计算机科学与技术学院	11	75	5.0	8.0
5	邬长安	信阳师范学院计算机与信息技术学院	36	223	9.0	12.0
6	周文勇	信阳师范学院计算机与信息技术学院	15	55	4.0	7.0