<p>Heuristic algorithms for routing problems, for example the Traveling Salesman Problem (TSP) as a representation, usually involve metrics for evaluating the quality of the edges. In this paper, we observe that most routing algorithms utilize a single evaluation metric, limiting the robustness and the ability to escape local optima. To address this issue, we propose a novel approach to associate a hybrid metric, containing local, global, and historical perspectives, with the routing algorithms, where the distance and backbone information are extracted to represent the local and historical information, respectively. Moreover, the combination mechanism of the hybrid metric is adjusted adaptively by a multi-armed bandit (MAB) framework, enabling the algorithm to dynamically select the most appropriate metric by learning from the search process. We apply our methods to the famous Lin-Kernighan-Helsguan (LKH) and LKH-3 algorithms for TSP and its variants. Extensive experimental results demonstrate the effectiveness and generalization of our approach, significantly enhancing LKH’s performance for TSP and LKH-3 for two representative TSP variants, Colored TSP (CTSP) and Capacitated VRP with Time Windows (CVRPTW).</p>