基于大邻域搜索的旅行商问题求解

摘要

旅行商问题(Travelling Salesman Problem, TSP)作为组合优化领域的经典问题，在物流、路径规划等领域具有广泛的实际应用价值。传统的精确求解方法在处理大规模问题时面临计算效率低下的挑战，而启发式算法因其灵活性与高效性成为解决TSP问题的主流方法。文章采用了一种基于大邻域搜索(Large Neighborhood Search, LNS)的TSP求解方法，通过破坏和修复算子对解进行迭代优化以平衡搜索的广度与深度。实验基于TSPLib数据库中的多个标准实例展开，结果表明，所提方法在不同规模与分布特性的数据集上均表现出优异的求解性能，能够快速收敛到高质量的解。

关键词

旅行商问题 / 大邻域搜索 / 破坏算子 / 修复算子 / 组合优化

基金资助

2024年内蒙古自治区教育科学十四五规划课题,“高职院校高等数学课程评价体系的改革与研究”(NZJGH2024137)成果