摘要
由于旅行商问题的计算复杂性,随着问题规模的扩大,精确算法逐渐不能在较短的时间内得到或不能得到问题的全局最优解。通过对该类问题的高质量优化解与全局最优解之间关系的分析,基于概率统计原理建立了问题的简化初始边集,并在分支裁减法中应用了合理的动态上界调整,新建立的混合分支裁减法实现了对小规模旅行商问题的快速精确求解。
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.
出处
《系统工程与电子技术》
EI
CSCD
北大核心
2008年第9期1693-1696,共4页
Systems Engineering and Electronics
关键词
分支裁减法
旅行商问题
小规模
精确求解
混合算法
branch and cut
traveling salesman problem
small scale
accurate computing
hybrid algorithm
