求解TSP的插队算法中初始回路的选择

摘要

插队算法是求解旅行商问题(TSP)的一种较好的近似算法.插队算法中初始回路的选择对算法的性能具有至关重要的影响.文章在考虑了城市分布特点的基础上,选用能大致模拟密集城市分布的三角形作为初始回路,以包罗同一方向上更多的城市,然后按照子回路增加路径最短规则依次将其余城市加入到路径中,形成旅行商问题较优的近似解.与其他启发式算法比较,该方法不需迭代,且解的质量更好.TSP测试文件berlin52.tsp仿真结果证明了该方法的优越性.