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

摘要

针对定义为广义旅行商问题（GTSP）的激光切割工艺路径优化问题,提出了一种自适应大邻域搜索算法（ALNS）与改进模拟退火算法相结合的混合算法。该算法提出一种融合最近、最远和随机插入操作的统一插入操作和统一最坏删除操作,通过在算法中反复进行删除和插入操作来优化自适应大邻域搜索算法,再运用改进模拟退火算法接受最优解,求得满足工艺约束的最短切割路径。通过GTSP-Lib数据库中的算例和实际切割案例对算法进行验证。结果表明,提出的算法在准确性上与最优算法的误差只有0.31%,但计算速度提高了12%,证明了该算法在求解小规模切割路径问题上有很强的适用性。