小规模TSP边集裁剪策略研究

由于旅行商问题的计算复杂性,随着问题规模的扩大,精确算法逐渐不能在较短的时间内得到或不能得到问题的全局最优解.通过对该类问题的高质量优化解与全局最优解之间关系的分析,基于概率统计原理建立了问题的简化初始边集,并在分支裁减法中应用了合理的动态上界调整,新建立的混合分支裁减法实现了对小规模旅行商问题的快速精确求解.

Accurate solving hybrid algorithm for small scale TSP

Owing to the computation complexity of traveling salesman problems accurate algorithms couldn't find a global optimal solution in relatively short time or couldn't find a global optimal solution at all along with the enlargement of problem scale.By analyzing the relationship between global optimal solutions and local optimal solutions,the method establishing initial cutting edge set for small scale TSP is put forward based on probability statistic principle.In the meanwhile,dynamic upbound adjustment is applied into the branch and cut algorithm.The global optimal solutions can be found for all of small scale traveling salesman problems by utilizing the new hybrid branch and cut algorithm.