Improved adaptive large neighborhood search algorithm and its application to traveling salesman problem

Ao Hongruila， Zhang Jihuila，1bt，Chen Shengzong² （1.aScholofutomaindongKeybotoryfdstralControlTologingdoUnesityQingdaSd China；2.School of Economicsamp; Management，Beihang University，Beijing 10o191，China）

Abstract：Thisstudyenhancedthetraditionaladaptivelargeneighborhoodsearch algorithm（ALNS）toaddressthechallngesof initial temperaturesetingandlowaccuracywhensolving large-scaletravelingsalesman problems.Firstly，this paper proposedtwoadditional directionalremovaloperators basedonnearestneighborinformation：thenearest neighborremoval operator forregionalsolutionremovalandthenonnearestneighborremovaloerator forsinglepointremoval，which improved search efciency.Secondly，Itreplacedthetraditional Metropolis criterion withanimprovedRRTaceptance criterion，eliminatingtheneedforinitialtemperatureparametersandenhancingthealgorithm’suniversalityFinally，experimentalesults fromvarious testcases in the TSPLIBdatabase showthattheimprovedALNS performs wellin termsof acuracy andconvergence speed， indicating its potential for handling large-scale instances.

Keywords：improved adaptive large neighborhood search algorithm；neighbor operator；RRTacceptance criteria；traveling salesman problem（TSP）

0 引言

旅行商问题（TSP）是一个经典的组合优化问题。该问题可以描述为：给定一组城市以及它们之间的距离，目标是找到一个最短的路径，使得从某个起始城市出发，访问每一个城市恰好一次，并最终返回到出发点。众所周知，TSP是经典的NP难题，具有广泛的应用背景，如物流运输、车辆路线规划和管道铺设等，针对不同的实际应用场景，存在多种TSP问题的变体和扩展模型。近年来，智能优化算法的快速发展为解决TSP提供了新的视角和方法，如模拟退火算法[1]、蚁群算法[2]、遗传算法[3]和布谷鸟算法[4]等。高海昌等人[5]讨论了几种求解TSP热门的启发式算法和元启发式算法，指出2-opt和3-opt等局部启发式优化算法单独使用时虽然操作简单但是易陷入局部最优，元启发式算法通过特定策略赋予算法跳出局部最优的能力，提高求解精度。陈晟宗等人[提出了一种波动温控模拟退火算法，将退火过程中的降温函数替换为波动函数，使得整个算法在总体上温度逐渐降低，且实现多次的温度升降，减少算法陷入局部最优解的情况。陈科胜等人[7]提出了一种自适应升温模拟退火算法，通过升温控制因子使得算法在求解过程中自适应地升高温度，防止陷入局部最优。Wei等人[8]提出了一种具有反复升温和降温的模拟退火算法，根据历史最优解定义最佳温度，通过在最佳温度附近反复升温降温实现跳出局部最优。王育洁等人提出结合评估奖惩机制和邻域动态退化的协同蚁群算法，通过路径评估值将路径分为活跃路径和舍弃路径，对活跃路径进行信息素奖励，对舍弃路径进行信息素惩罚，加快算法的收敛速度。……