切割路径优化问题的自适应大邻域搜索退火算法  

An Adaptive Large Neighborhood Search-Simulated Annealing Algorithm for Cutting Path Optimization

作　　者：吴哲[1] 徐圣伦 杨春梅[1] 赵帅 秦广义 李超[1] WU Zhe;XU Shenglun;YANG Chunmei;ZHAO Shuai;QIN Guangyi;LI Chao(College of Mechanical and Electrical Engineering,Northeast Forestry University,Harbin 150040,China)

机构地区：[1]东北林业大学机电工程学院,哈尔滨150040

出　　处：《重庆理工大学学报（自然科学）》2020年第9期230-237,244,共9页Journal of Chongqing University of Technology：Natural Science

基　　金：国家自然科学基金项目(31700643,31200434);中央高校基本科研业务费专项基金项目(257572015CB10)。

摘　　要：针对定义为广义旅行商问题(GTSP)的激光切割工艺路径优化问题,提出了一种自适应大邻域搜索算法(ALNS)与改进模拟退火算法相结合的混合算法。该算法提出一种融合最近、最远和随机插入操作的统一插入操作和统一最坏删除操作,通过在算法中反复进行删除和插入操作来优化自适应大邻域搜索算法,再运用改进模拟退火算法接受最优解,求得满足工艺约束的最短切割路径。通过GTSP-Lib数据库中的算例和实际切割案例对算法进行验证。结果表明,提出的算法在准确性上与最优算法的误差只有0.31%,但计算速度提高了12%,证明了该算法在求解小规模切割路径问题上有很强的适用性。Aiming at the laser cutting process path optimization problem defined as generalized travel agent problem(GTSP),a hybrid algorithm based on adaptive large neighborhood search algorithm(ALNS)and improved simulated annealing algorithm is proposed.The algorithm proposes a unified insertion operation and a unified worst-case deletion operation,which combines the nearest,farthest and random insertion operations.The algorithm optimizes the adaptive large neighborhood search algorithm by repeatedly deleting and inserting operations in the algorithm,and then uses the improved simulated annealing algorithm to accept the optimal solution to obtain the shortest cutting while meeting the process constraints.The algorithm is verified by the examples in the GTSP-lib and the actual cutting cases.The results show that the proposed algorithm has only 0.31%error from the optimal algorithm in accuracy,but achieves 12%improvement in computing speed.It is proved that the algorithm has strong applicability in solving small-scale cutting problems.

关 键 词：切割路径 模拟退火 自适应大邻域搜索 最优解 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TG485[自动化与计算机技术—计算机科学与技术]