基于组合拆分策略求解TSP的动态规划算法

Dynamic Programming Algorithm Based on Combination and Division Strategy for Solving TSP

针对传统动态规划算法只能解决小规模旅行商问题(TSP)的不足,提出一种基于组合拆分策略的动态规划算法,通过5种不同的拆分策略将TSP序列拆分成若干段子序列,利用动态规划方法将子序列优化组合成新的TSP序列,重复该过程直到获得最优解散解。仿真结果表明,该算法能有效减小误差率,求解精确度较高,具有较低的计算复杂度和较好的稳健性。

Because of the deficiency that the typical dynamic programming algorithm can only solve the small-scale Traveling Salesman Problem（TSP）, this paper proposes a new dynamic programming algorithm based on the combination and division. The whole sequence of TSP is divided into several parts by five strategies mentioned by the paper. Those parts are combined using the proposed dynamic programming algorithm to get a new better sequence. It repeats the process until it gets the optimum solution. Simulation results show that this algorithm with the higher solution accuracy can effectively reduce the error rate, and have low complexity and good robustness of the solution.