摘要

本文探讨了旅行商问题（TSP）的解决方法，特别是针对Lin-Kernighan-Helsgaun（LKH）启发式算法的改进。LKH算法在处理复杂实例时经常遇到超时问题，主要原因是使用基于树结构的固定候选集。研究团队发现，基于哈密顿回路的候选集包含更多最优边，因此提出将POPMUSIC初始化策略集成到LKH的高效重启版本中。实验结果表明，这种改进的TSP启发式算法在减少超时和提高性能方面取得了显著效果，挑战了TSP解决的现有技术水平。

原理

LKH算法的核心是通过构建连续的k-opt移动来寻找最优解，其中k是无限的。为了减少计算复杂性，LKH采用了一种修剪搜索空间的策略，即通过最小1-树来推导出更准确的边接近最优回路的近似值。此外，还使用了子梯度优化技术来进一步细化这些估计，从而提高算法在寻找高质量解决方案时的有效性。通过这种方式，LKH能够有效地减少搜索空间，同时保持找到最优解的可能性。

流程

论文中详细描述了LKH算法的工作流程，包括初始化候选集、执行连续的k-opt移动以及使用子梯度优化技术来调整距离矩阵。具体来说，算法首先构建一个基础的最小1-树，然后通过添加或删除边来调整这个树，使其更接近一个哈密顿回路。在每次基本移动后，生成的边必须形成一个哈密顿回路。通过这种方式，LKH能够在保持搜索空间可管理的同时，有效地探索可能的解决方案。

应用

改进后的LKH算法在TSP解决方面展示了显著的性能提升，特别是在处理小型到中型实例时。这种改进不仅减少了超时情况，还提高了算法的整体效率。因此，该算法有望在物流、运输科学和计算机科学等多个领域中得到广泛应用，特别是在需要高效解决TSP及其变体的场景中。