改進(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）是一個經(jīng)典的組合優(yōu)化問題。（剩余14649字）