摘要
为了克服自适应大邻域搜索算法(ALNS)在解决大规模旅行商问题时面临的初始温度设定困难及求解精度不足的问题,对传统ALNS进行了改进。首先,基于最近邻信息,提出了近邻移除算子和非近邻移除算子两种更具指向性的移除算子。前者负责区域性地移除解的部分,而后者则专注于单点移除,从而提高了搜索效率。其次,采用改进的RRT(record-to-record travel)接受准则替换了传统的Metropolis准则,这一改变不仅消除了对初始温度参数的需求,还增强了算法的通用性。最后在TSPLIB数据库中不同规模的多个测试算例上进行实验,并将结果与新型启发式算法进行比较,发现改进后的ALNS在求解精度和收敛速度方面均表现出色,并显示出处理大规模问题的潜力。
This study enhanced the traditional adaptive large neighborhood search algorithm(ALNS)to address the challenges of initial temperature setting and low accuracy when solving large-scale traveling salesman problems.Firstly,this paper proposed two additional directional removal operators based on nearest neighbor information:the nearest neighbor removal operator for regional solution removal and the non-nearest neighbor removal operator for single point removal,which improved search efficiency.Secondly,It replaced the traditional Metropolis criterion with an improved RRT acceptance criterion,eliminating the need for initial temperature parameters and enhancing the algorithm’s universality.Finally,experimental results from various test cases in the TSPLIB database show that the improved ALNS performs well in terms of accuracy and convergence speed,indicating its potential for handling large-scale instances.
作者
敖弘瑞
张纪会
陈晟宗
Ao Hongrui;Zhang Jihui;Chen Shengzong(School of Automation,Qingdao University,Qingdao Shandong 266061,China;Shandong Key Laboratory of Industrial Control Technology,Qingdao University,Qingdao Shandong 266061,China;School of Economics&Management,Beihang University,Beijing 100191,China)
出处
《计算机应用研究》
北大核心
2025年第6期1713-1718,共6页
Application Research of Computers
基金
国家自然科学基金项目(61673228,62072260)
青岛市科技计划项目(21-1-2-16-zhz)。
关键词
改进自适应大邻域搜索算法
近邻算子
RRT接受准则
旅行商问题
improved adaptive large neighborhood search algorithm
neighbor operator
RRT acceptance criteria
traveling salesman problem(TSP)
