Abstract: Aiming at multi-objective vehicle routing problem with time windows, proposes Differential Evolution algorithm integrating Mutation Strategy and Adjacent Information (DE-MSAI). First, four mutation operators are devised by employing elitist sampling strategy to increase algorithm search breadth. Second, customer adjacency information matrix is established to guide g targeted neighborhood search, improving local optimization efficiency. Finally, simulated annealing criterion is adopted to accept inferior solutions with certain probability. If Pareto non-dominated solution set remains unimproved beyond preset iterations during optimization, elite fragment protection strategy is activated to perturb a randomly selected solution from non-dominated set, maintaining population diversity. Simulation experiments based on Solomon benchmark instances show that proposed algorithm controls solving error within 0.07 compared to hybrid crow search algorithm, and outperforms clustering-based large neighborhood search algorithm in most cases, achieving an average reduction of 4.51 in route deviation metrics, verifying its effectiveness.

Key words: vehicle routing problem, multi-objective optimization, Differential Evolution &#40, DE&#41, algorithm

摘要： 针对多目标带时间窗车辆路径问题，提出了一种融合变异策略与邻接信息的差分进化算法(Differential Evolution Algorithm Integrating Mutation Strategy and Adjacent Information, DE-MSAI)。首先，利用精英抽样策略设计四种变异操作，增加算法搜索的广度；其次，结合客户邻接信息矩阵引导个体进行邻域搜索，提升局部优化效率；最后，基于模拟退火准则以一定的概率接受劣解。如果在迭代过程中，Pareto非支配解集连续未被改善的次数超过阀值，则启动精英碎片保护策略，随机选择一个非支配解集中的解进行扰动，维持种群的多样性。基于Solomon标准库中的算例仿真实验表明，所提算法相较于混合乌鸦算法的求解误差控制在0.07；相较于基于聚类的混合大邻域搜索算法，所提算法在绝大多数算例上结果较优，路线偏差指标平均降低4.51，验证了算法的有效性。

关键词: 车辆路径问题, 多目标优化, 差分进化算法, 邻接信息矩阵, 精英碎片保护策略