Dancing to the State of the Art? How Candidate Lists Influence LKH for Solving the Traveling Salesperson Problem

尽管在现代场景中有许多广义应用，但解决旅行商问题（TSP）仍然是一项持久的挑战。启发式求解器解决了高效地找到高质量解决方案的需求。在这些求解器中，Lin-Kernighan-Helsgaun（LKH）启发式算法突出表现，因为它在各种问题实例的范围内补充了遗传算法的性能。然而，在具有挑战性的实例中频繁的超时阻碍了求解器的实际应用。在这项工作中，我们调查了一个之前被忽视的导致许多超时的因素：使用基于树结构的固定候选集。我们的调查发现，基于哈密顿回路的候选集包含更多最优边。因此，我们建议将这种有前途的初始化策略（即POPMUSIC）集成到LKH的高效重启版本中。正如我们的实验研究所证实的那样，这种改进的TSP启发式算法更加高效——导致的超时更少，并且将性能（以惩罚性平均运行时间为指标）提高一个数量级，从而挑战了TSP求解的现有技术水平。

解决问题：论文试图通过改进LKH启发式算法来解决旅行商问题（TSP）中的超时问题。

关键思路：论文提出了使用基于哈密顿回路的候选集来改进LKH启发式算法的初始化策略，以减少超时并提高性能。

其他亮点：论文的实验结果表明，这种改进后的启发式算法比原先的LKH算法更有效，可以减少超时问题并提高性能。实验使用了多个TSP数据集，并开源了代码。

相关研究：与本文相关的其他研究包括使用遗传算法和其他启发式算法来解决TSP问题的研究，例如“Genetic Algorithm for the Traveling Salesman Problem”和“Ant Colony Optimization for the Traveling Salesman Problem”。