多旅行商问题的广义变邻域搜索启发式算法

本文主要探讨了多旅行商问题（Multiple Traveling Salesman Problem, MTSP），这是一种比单旅行商问题（Single Traveling Salesman Problem, TSP）更广泛的问题，因为它涉及到了多个（m>1）销售员，每个销售员都在固定的服务点（depot）开始并结束他们的行程。MTSP的目标是优化两个不同的目标函数：一是最小化最长旅程长度，这保证了所有销售员中的最差表现；另一个是总旅程长度最小化，关注的是整体性能。 文章中，作者Banu Soylu，来自埃尔吉耶斯大学工业工程系，提出了一种广义变邻域搜索（General Variable Neighborhood Search,GVNS）算法，这是一种针对组合优化问题的常用启发式方法。GVNS在处理MTSP时，通过探索各种局部改进策略，试图在搜索空间中找到全局最优解或接近最优的解。 作者首先将新提出的GVNS算法应用到文献中的一些测试问题上，与现有方法进行了性能比较。结果显示，GVNS展现出良好的适应性和有效性，能够在复杂的问题实例中找到相对高效的解决方案。此外，为了验证其实际应用价值，作者还进一步将该算法应用于现实生活中的一个问题，可能是物流配送、货物分发等场景，展示了解决多目标优化问题的实际可能性。 总结来说，这篇文章的关键贡献在于提供了一种有效的GVNS算法来解决多旅行商问题，不仅关注单个销售员的最差表现，也注重整体效率。通过实验验证，该算法展现出了在理论和实践上的潜力，对于提高MTSP求解的效率和精确度具有重要意义。对于那些处理大规模运输优化问题的公司或研究者来说，这篇论文提供了有价值的研究参考和技术工具。