计算机应用研究2025，Vol.42Issue(6)：1713-1718,6.DOI:10.19734/j.issn.1001-3695.2024.11.0445
改进自适应大邻域搜索算法及其在旅行商问题中的应用
Improved adaptive large neighborhood search algorithm and its application to traveling salesman problem
摘要
Abstract
This study enhanced the traditional adaptive large neighborhood search algorithm(ALNS)to address the challen-ges 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,elimi-nating 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 conver-gence speed,indicating its potential for handling large-scale instances.关键词
改进自适应大邻域搜索算法/近邻算子/RRT接受准则/旅行商问题Key words
improved adaptive large neighborhood search algorithm/neighbor operator/RRT acceptance criteria/traveling salesman problem(TSP)分类
信息技术与安全科学引用本文复制引用
敖弘瑞,张纪会,陈晟宗..改进自适应大邻域搜索算法及其在旅行商问题中的应用[J].计算机应用研究,2025,42(6):1713-1718,6.基金项目
国家自然科学基金项目(61673228,62072260) （61673228,62072260）
青岛市科技计划项目(21-1-2-16-zhz) （21-1-2-16-zhz）
