摘要
TSP是经典的组合优化问题。根据欧氏平面TSP最优环路的性质提出了子路径及相关的概念,利用点集凸壳设计了环路构造算法,并以点集Delaunay三角剖分图为启发信息设计了改进的遗传算法,通过中国144城市TSP等验证了算法的有效性。
The TSP is a classic combinatorial optimization problem. According to the character of the optimal tour of Euclidean plane TSP problem, the sub-path and related notions are presented. A tour construction algorithm is designed by using convex hull, and a genetic algorithm is improved to solve the problem by using Delaunay triangulation diagram as heuristic information. The experimental results in the 144 cities in China and other TSP instances show that the algorithm is effective.
出处
《国防科技大学学报》
EI
CAS
CSCD
北大核心
2004年第5期109-114,共6页
Journal of National University of Defense Technology
基金
国家部委资助项目(2003-5130801-1-3)
关键词
欧氏平面
TSP
凸壳
DELAUNAY三角剖分
遗传算法
Euclidean plane
traveling salesman problem
convex hull
Delaunay triangulation
genetic algorithm
