一种基于分层模型的TSP构建算法

A construction algorithm for TSP based on hierarchical model

提出了一种新算法,有效地减少了最近邻域法和贪婪算法在构建旅行商问题可行解过程中引入不合理长边的问题。该算法先借助一种由伪凸包算子所得到的分层模型对旅行商问题中的城市分布进行分析,之后通过将分层模型中相对外层的点逐个添加到内层的规则得到可行解。借助仿真实验求解TSPLIB标准库中的40实例,并与最近邻域法和贪婪算法进行对比,结果表明分层融合算法具有更高的精度,其平均求解质量达到8.47%。

This paper proposes a new algorithm for making a feasible solution of traveling salesman problem,which availably reduces unreasonable long sides introduced in nearest neighborhood algorithm and greedy algorithm. With the hierarchical model formed from pseudo convex hull algorithm,the algorithm,at first,analyzes the city distribution of traveling salesman problem and then a feasible solution can be found by inserting the point in the relatively outside layer to the relatively inside layer one by one. We use 40 examples from TSPLIB to test the algorithm and contrast it with the nearest neighborhood algorithm and greedy algorithm. The result shows that hierarchical fusion algorithm has a better result with the average solution quality of 8. 47%.