旅行商问题新算法：参考点相邻插入法与两阶段策略

"本文主要探讨了旅行商问题(TSP)的一种新解法——基于参考点的相邻插入法(RPBN I)以及其改进策略(I2RPBN I)，并结合模拟退火算法提出了一种两阶段解决方法。这种方法的时间复杂度分别为O(n^2)和O(n^3)，在实际应用中展现了良好的效率和鲁棒性。" 在旅行商问题中，一个旅行商需要找到一条访问所有城市恰好一次然后返回起始城市的最短路径。传统的最近插入法虽然简单，但在面对大规模问题时效率较低。作者王凌、童行行和郑大钟通过分析现有的最近插入法，提出了一种基于参考点的相邻插入法。此方法引入了参考点的概念，使得在构建初始路径时能更有效地考虑城市之间的距离关系，从而提高了解决问题的速度，时间性能达到O(n^2)。 进一步，他们对RPBN I进行了改进，提出了I2RPBN I策略，该策略通过优化插入规则和调整搜索策略，使得算法在保持较低时间复杂度O(n^3)的同时，提升了路径优化的能力。这两种方法对于解决旅行商问题都表现出较高的效率。 然而，为了解决更复杂的情况和寻找全局最优解，作者还引入了模拟退火算法。模拟退火是一种启发式搜索算法，能够跳出局部最优解，寻找全局最优。结合I2RPBN I的两阶段方法，首先使用I2RPBN I生成初始解，然后通过模拟退火进行迭代优化，这样既利用了I2RPBN I的高效性，又利用了模拟退火的全局搜索能力，提高了算法的整体性能。 通过典型算例的数值仿真，研究者验证了提出的算法在解决旅行商问题时的有效性、高效性和鲁棒性。这意味着无论是在简单的还是复杂的实例中，该方法都能稳定地找到接近最优的解决方案，并且在面对问题规模变化时仍能保持良好的性能。 这篇研究提供了一种新的解决旅行商问题的策略，它不仅在时间复杂度上有所优化，而且通过结合不同算法的优势，提高了找到近似最优解的可能性，对于实际应用具有重要的理论和实践价值。