arXiv:2505.15862v1 公告类型：新论文
摘要
针对路由问题设计的算法通常依赖高质量的候选边（candidate edges）来引导搜索，以缩小搜索空间并提升搜索效率。然而，许多现有算法（如经典的用于解决旅行商问题（Traveling Salesman Problem, TSP）的Lin-Kernighan-Helsgaun算法，LKH）在局部搜索过程中往往使用预设的静态候选边集合。这种刚性策略可能导致算法陷入局部最优解，限制其寻找更优方案的潜力。为解决此问题，本研究提出扩展候选集，纳入其他有潜力的边，并通过动态调整赋予其选择机会。具体而言，本文引入多臂强盗模型（multi-armed bandit models），在每一步迭代中动态选择最合适的候选边，从而增强LKH算法的智能性，推动其找到更优的解决方案。针对多个TSP基准的实验验证表明，本文方法在性能上表现出色。此外，该基于强盗模型的方法被进一步应用于LKH-3（LKH的扩展版本，用于解决多种TSP变体问题），结果在典型TSP变体中显著提升了LKH-3的性能。
[科技领域] 高频英文短语及解析
1. Multi-armed Bandit Models
翻译：多臂强盗模型。
解析：该术语源自强化学习领域，用于描述在有限资源下权衡“探索-利用”（exploration-exploitation trade-off）的在线决策问题。在本文中，通过模拟多臂强盗的策略，动态选择候选边，避免算法陷入局部最优。
- Candidate Edge Selection
翻译：候选边选择。
解析：在组合优化问题（如TSP）中，候选边通常指被优先考虑的边集合，用于减少搜索空间并加速收敛。高效的候选边选择策略直接影响算法最终解的质量和计算效率。 -
Local Optima
翻译：局部最优解。
解析：优化算法中无法超越的次优解状态，限制全局最优解的搜索。局部最优问题是许多贪心或启发式算法的共性缺陷，常需引入随机性或动态调整机制以规避。 -
Search Space Reduction
翻译：搜索空间缩减。
解析：指通过算法设计减少待探索的可能解范围，以提升效率。本文中，候选边的扩展虽增加潜在选择，但通过动态优先级机制仍实现有效缩减。 -
Extensive Experiments
翻译：广泛实验。
解析：科技论文中常用于强调实验覆盖的多样性和严谨性，表明方法已在多类数据集或场景中验证，增强结论的可信度。
最优标签标签（Tags）
1. 多臂强盗模型
2. 旅行商问题优化