改进的求解TSP混合分支裁剪法

分支裁减法是一种有效的求解小规模TSP的整数规划方法.随着TSP规模的逐步扩大,问题求解的复杂性也随之增加.在TSP的可计算数学研究领域中,局部搜索算法能快速求解TSP的局部最优解.通过将局部搜索算法与分支裁减法结合,利用局部搜索算法对分支裁减法获得上界所对应环路进行优化,使分支限界算法的上界更快地向全局最优解靠近,提高算法的求解效率,扩大了分支裁减法求解TSP的规模.

Improved hybrid branch and cut algorithm for solving TSP

Branch and cut algorithm is a kind of integer programming method to solve small scale TSP effectively. The computing complexity of TSP will scale up along with increment of TSP scale. In the field of computable mathematics of TSP, local search algorithms can find local optimum solution quickly. Through combining branch and cut algorithm with local search algorithm, it make the upbound more close to global optimum solution by utilizing local search algorithm to optimize the path corresponding to current upbound. Furthermore, the efficiency of the algorithm will be improved, and the scale of TSP that can be solved is scaled up.