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

作者：吴秀芹; 刘铁良

来源：长春理工大学学报(自然科学版), 2021, 44(04): 111-118.

• VRPTW
• 访问概率
• 动态交叉算子
• 最优片段
• 邻域搜索

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

• 单位
  东北石油大学