基于ALNS改进的蜣螂优化算法求解带时间窗的车路径问题

Improved Dung Beetle Optimization Algorithm Based on ALNS for Vehicle Routing Problem with Time Windows

摘要: 针对带时间窗的车辆路径问题(Vehicle Routing Problems with Time Windows, VRPTW)，提出一种混合大规模领域搜索的改进蜣螂优化算法(Improved Dung Beetle Optimization of ALNS, ALSN-IDBO)进行求解。本文主要的改进点为：1) 设计新的编码解码方式实现连续蜣螂位置向量向离散客户序列的转化；2) 对于蜣螂优化算法的初始化采用随机、贪婪、最邻近而策略；3) 在ALNS中设计了3个移除算子和3个重插算子；4) 在传统的DBO中针对繁育的蜣螂和小蜣螂分别改进为螺旋搜索策略和三角游走策略。通过在标准Solomon数据集的部分算例进行实验，将本文算法与GA、DBO、ALNS算法进行对比，实验结果表明，本文所提出的混合大规模领域搜索的改进蜣螂优化算法能找到更好的解，并且寻优能力和稳定性均优于对比算法。

Abstract: For the Vehicle Routing Problems with Time Windows (VRPTW), an Improved Dung Beetle Optimization of ALNS (ALSN-IDBO) with hybrid large-scale domain search is proposed to for solving. The main improvements in this paper are 1) designing a new encoding and decoding method to realize the transformation of continuous dung beetle position vectors to discrete client sequences; 2) adopting random, greedy, and nearest-neighbor while strategies for the initialization of the dung beetle optimization algorithm; 3) designing three removal operators and three re-insertion operators in ALNS; and 4) improving the traditional DBO for the breeding dung beetles and the small dung beetles with a spiral search strategy and a triangular wandering strategy. The algorithm in this paper is compared with GA, DBO, and ALNS algorithms by conducting experiments on some arithmetic cases in the standard Solomon dataset. The experimental results show that the improved dung beetle optimization algorithm for hybrid large-scale domain search proposed in this paper can find better solutions, and the optimality finding ability and stability are better than the compared algorithms.