计算机应用研究

作者：敖弘瑞,张纪会,陈晟宗,

单位：1.青岛大学a.自动化学院;b.山东省工业控制技术重点实验室,山东青岛266061；2.北京航空航天大学经济管理学院,北京100191；

关键词：改进自适应大邻域搜索算法,近邻算子,RRT接受准则,旅行商问题,

基金：国家自然科学基金项目(61673228,62072260)；青岛市科技计划项目(21-1-2-16-zhz)；；

为了克服自适应大邻域搜索算法（ALNS）在解决大规模旅行商问题时面临的初始温度设定困难及求解精度不足的问题，对传统ALNS进行了改进。首先，基于最近邻信息，提出了近邻移除算子和非近邻移除算子两种更具指向性的移除算子。前者负责区域性地移除解的部分，而后者则专注于单点移除，从而提高了搜索效率。其次，采用改进的RRT（record-to-record travel）接受准则替换了传统的Metropolis准则，这一改变不仅消除了对初始温度参数的需求，还增强了算法的通用性。最后在TSPLIB数据库中不同规模的多个测试算例上进行实验，并将结果与新型启发式算法进行比较，发现改进后的ALNS在求解精度和收敛速度方面均表现出色，并显示出处理大规模问题的潜力。

来源：2025年第6期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2025年第6期