Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems

Long Wanga, Jiongzhi Zheng, Zhengda Xiong, Chumin Li, Kun HearXiv 2025 · DOI · arXiv

Abstract

The Lin-Kernighan-Helsgaun (LKH) algorithm is a cornerstone for solving the Traveling Salesman Problem (TSP), but its reliance on static candidate edge sets can lead to local optima. We present bandLKH, a novel approach that integrates a Multi-Armed Bandit (MAB) model to dynamically select promising edges from an expanded candidate pool. By balancing exploration and exploitation during the search process, bandLKH significantly reduces the optimality gap and outperforms both traditional LKH and state-of-the-art deep learning-based solvers on standard benchmarks and routing variants.

Introduction

The Traveling Salesman Problem (TSP) remains a fundamental challenge in combinatorial optimization. For large-scale instances, local search heuristics like the Lin-Kernighan-Helsgaun (LKH) algorithm are widely considered the gold standard. To maintain computational efficiency, LKH restricts its search to a small, fixed set of "candidate edges" for each city, typically chosen based on a static metric called the $\alpha$-value.

However, this static approach creates a significant bottleneck. If the edges required for the global optimal tour are not included in the initial candidate sets, the algorithm is mathematically precluded from finding the optimum. Simply increasing the number of candidate edges is not a viable solution, as it introduces noise and significantly slows down the search. This paper addresses the challenge of considering a wider array of potential edges without sacrificing search efficiency.

The bandLKH Framework

The proposed bandLKH algorithm integrates reinforcement learning principles into the LKH local search process by modeling edge selection as a Multi-Armed Bandit (MAB) problem. Instead of relying on a fixed set of 5 edges, bandLKH expands the candidate pool (e.g., to 7 edges) and treats each city as a bandit where the "arms" are the available edges.

Visualization of sequential 3-opt and non-sequential 4-opt local search operators.

During each iteration, the algorithm "pulls" a subset of arms to select active candidate edges for the local search operators, such as $k$-opt (illustrated above). Edges that contribute to finding a better overall tour receive a reward, updating their "$M$-value"—a dynamic metric of historical usefulness. To prevent stagnation and balance exploration with exploitation, bandLKH rotates through three distinct selection policies:

  • $\epsilon$-greedy: Randomly explores edges with probability $\epsilon$, otherwise exploits high $M$-values.
  • $M$-greedy: Strictly selects edges with the highest learned $M$-values.
  • $\alpha$-greedy: Selects edges based on the original, static global heuristic.

Experimental Evaluation

The authors evaluated bandLKH and its variant for routing extensions, bandLKH-3, across standard benchmarks including TSPLIB, National TSPs, and the Uchoa et al. CVRP benchmark.

Performance comparison of bandLKH against VSR-LKH and NeuroLKH variants.

As shown in the table above, bandLKH consistently outperformed modern deep learning-based solvers such as NeuroLKH (which utilizes Graph Neural Networks) and VSR-LKH. Key results include:

  • Gap Reduction: bandLKH reduced the average gap to best-known solutions by approximately 65% compared to standard LKH.
  • Robustness: In 62 hard TSP instances, bandLKH found superior average solutions in 52 cases.
  • Generalization: The framework successfully extended to complex variants, outperforming LKH-3 on 47/82 MTSP instances and 61/100 CVRP instances.

Conclusion

The success of bandLKH demonstrates that dynamic, lightweight reinforcement learning applied during a search can be more effective than heavy neural network predictions made before the search. By using the MAB model as a "smart filter," the algorithm successfully identifies high-quality edges in an expanded search space while ignoring noise. Future work will explore adaptively changing the size of candidate sets during the search to further refine performance on increasingly complex routing problems.

Summary updated

BibTeX
@misc{wanga2025bandit,
  author = {Long Wanga and Jiongzhi Zheng and Zhengda Xiong and Chumin Li and Kun He},
  title = {{Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems}},
  year = {2025},
  eprint = {2505.15862},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.15862},
}
Figure