基于双重交叉策略的多元宇宙优化算法求解带时间窗车辆路径问题

Multi-verse Optimization Algorithm Based on Double Crossover Strategy for Solving Vehicle Routing Problem with Time Windows

提出了一种基于双重交叉策略的多元宇宙优化算法求解带时间窗车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW)。该算法利用访问概率在满足车辆最大载重的约束条件下构造算法的初始解,提高初始宇宙群的优良性;引入动态交叉算子,在当前宇宙的基础上交叉重组生成新的宇宙,提高算法的局部探索能力,同时采用基于最优片段的交叉策略更新白洞位置,加强各个宇宙间信息的交互;并引入随机交换搜索、2-opt和3-opt相结合的邻域搜索方法对最优解进行局部优化,扩大算法搜索空间。实验结果表明:所提算法能够有效解决带时间窗车辆路径问题,有较强的寻优能力,求解质量优于所对比算法。

In this paper,a multi-verse optimization algorithm is presented based on double crossover strategy to solve the vehicle routing problem with time windows(VRPTW).The access probability is used to construct the initial solution of the algorithm under the constraint of satisfying the maximum load of the vehicle,which can improve the superiority of the initial cosmic group.A dynamic crossover operator is introduced to cross-recombine a new universe based on the current universe and improve the local exploration ability of the algorithm;and the crossover strategy of the optimal segment is used to update the white Hole,the interaction of information between the universe is introduced;the algorithm introduces random exchange search,2-opt,3-opt neighborhood search strategy to expand the search space of the algorithm.The ex-perimental results show that the proposed algorithm can effectively solve the VRPTW,and has a strong optimization ability,the quality of the solution is better than the compared algorithm.