改進(jìn)自適應(yīng)大鄰域搜索算法及其在旅行商問題中的應(yīng)用
打開文本圖片集
Improved adaptive large neighborhood search algorithm and its application to traveling salesman problem
Ao Hongruila， Zhang Jihuila，1bt，Chen Shengzong2 （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）是一個(gè)經(jīng)典的組合優(yōu)化問題。（剩余14649字）