一个求解旅行商问题的松弛算法

A relaxation algorithm for solving the traveling salesman problem

在旅行商问题(TSP)的传统模型中,子回路消除约束的数量随着问题规模的增大具有指数增长的特性,极大地限制了TSP的求解效率。基于TSP的松弛问题,本文提出一种有效生成子回路消除约束的方法。该方法通过求解一系列线性整数规划,来实现TSP的精确快速求解。数值结果表明,本方法相比于采用Cplex直接求解,能够更快地找到TSP的最优解。

In the traditional traveling salesman problem(TSP) models,the number of sub-tour elimination constraints exponentially increases with an increase in the size of the problem,which considerably limits the efficiency of solving the TSP.Based on the TSP relaxation problems,a method has been proposed in this study to effectively generate sub-tour elimination constraints.Further,the proposed method achieves an accurate and quick solution of TSP by solving the linear integer programming series.The numerical results denote that when compared with the Cplex direct solution,the proposed method can obtain the optimal solution of TSP more rapidly.