多臂老虎机与背骨信息提升Lin-Kernighan-Helsgaun算法解决旅行商问题

本研究针对Lin-Kernighan-Helsgaun（LKH）启发式算法在旅行商问题中未充分利用历史信息及局部最优解困境的问题，提出了一种动态提取背骨信息的新方法。通过将背骨信息、α值与距离结合以评估边缘质量，并引入多臂老虎机模型动态选择评估指标，实验结果表明该方法显著改善了LKH及其扩展版本LKH-3在旅行商问题和车辆路径问题中的性能。