基于二维凸包的TSP算法

作     者：刘宏兵 邬长安 周文勇 LIU Hong-bing;WU Chang-an;ZHOU Wen-yong

作者机构：武汉理工大学计算机科学与技术学院湖北武汉430070 信阳师范学院计算机与信息技术学院河南信阳464000 

基　　金：河南省教育厅自然科学基金项目(2006520012) 校青年骨干教师计划基金项目(20060503) 

出 版 物：《计算机工程与设计》 (Computer Engineering and Design)

年 卷 期：2009年第30卷第8期

页      码：1954-1956,2000页

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

主 题 词：二维凸包 旅行商问题 长度增量 快速凸包算法 凸点 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.16208/j.issn1000-7024.2009.08.012

馆 藏 号：203687112...