改进自适应大邻域搜索算法及其在旅行商问题中的应用

打开文本图片集

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 Economics& 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）是一个经典的组合优化问题。（剩余14649字）