分层融合算法提升TSP求解精度：8.47%优于经典方法

本文主要探讨了一种创新的旅行商问题（Traveling Salesman Problem, TSP）解决方法，即"一种基于分层模型的TSP构建算法"。该算法针对最近邻域法和贪婪算法在寻找TSP可行解时存在的不合理长边问题提出了改进策略。首先，算法利用伪凸包算子构建了一个分层模型，通过对城市分布进行深入分析，识别出城市的层次结构。这个分层模型的关键在于它能区分城市之间的相对重要性和距离关系。 算法的核心步骤是将分层模型中相对较外层的城市按照一定的规则逐步加入到内层，这一过程旨在形成更加优化的路径，避免生成过长的边。这种方法通过逐层合并，减少了局部最优导致的全局最优解质量下降的情况，从而提高了求解的精度。 作者宋海声、吕耕耕和刘岸果对TSPLIB标准库中的40个实例进行了仿真实验，将新提出的分层融合算法与传统的最近邻域法和贪婪算法进行了对比。实验结果显示，分层融合算法在平均求解质量上显著优于传统方法，达到了8.47%的提升。这表明该算法不仅在解决效率上有所提高，而且在求解效果上具有更高的精度。 文章强调了旅行商问题在多个领域的实际应用价值，如物流配送、生产和制造调度等，以及启发式算法研究的重要性，特别是构建型和改进型算法的区别。构建型算法如最近邻域法因其简单性和快速性而受到青睐，但可能牺牲求解质量；而改进型算法如遗传算法、蚁群算法等虽然求解质量高，但计算速度较慢。分层融合算法作为一种构建型算法的改进，兼顾了效率和质量，为TSP问题的求解提供了一种新的有效途径。 总结来说，这篇论文的主要贡献在于提出了一种新的TSP构建策略，通过分层模型优化了解决方案，使得算法在求解质量和执行效率上取得了显著的进步，对于TSP问题的实际应用具有重要意义。