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

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