Liu Songzuo, Sun Jian, Duan Xiaohong, Liu Guofang
Faculty of Information Engineering, Shandong Huayu University of Technology, Dezhou, 253034, China.
College of Computer Science and Engineering, North Minzu University, Yinchuan, 750021, China.
Sci Rep. 2024 Oct 11;14(1):23809. doi: 10.1038/s41598-024-74432-2.
Aiming at the multi-objective vehicle path planning problem with time windows (VRPTW), a Spark-based parallel Adaptive Large Neighborhood Search algorithm (Spark-ALNS) is proposed to solve it. The main design of the 4-point strategy: (1) Design a new simulated annealing algorithm cooling strategy to achieve a better jump out of the local optimal solution. (2) Adopt CW initialization to accelerate the convergence speed. (3) Use three destruction operators and three repair operators to implement local path optimization. (4) A new parallel strategy is proposed to improve the algorithm's accuracy and reduce the running time. To illustrate the algorithm's effectiveness, the arithmetic example in Solomon is used as an example. The experimental results show that the proposed Spark-ALNS can find better solutions, get the known optimal solutions for 41 out of 56 instances, and find new optimal solutions for 31 algorithms, which outperforms other evolutionary algorithms. The runtime is 3-5 times better than other parallel algorithms and is able to solve VRPTW effectively.
针对带时间窗的多目标车辆路径规划问题（VRPTW），提出了一种基于Spark的并行自适应大邻域搜索算法（Spark-ALNS）来求解该问题。4点策略的主要设计：（1）设计一种新的模拟退火算法冷却策略，以更好地跳出局部最优解。（2）采用CW初始化以加快收敛速度。（3）使用三种破坏算子和三种修复算子来实现局部路径优化。（4）提出一种新的并行策略，以提高算法的精度并减少运行时间。为说明该算法的有效性，以Solomon中的算例为例。实验结果表明，所提出的Spark-ALNS能够找到更好的解，在56个实例中有41个得到了已知最优解，为31个算法找到了新的最优解，优于其他进化算法。运行时间比其他并行算法快3至5倍，能够有效地求解VRPTW。
