基于萤火虫算法的动态车辆路径规划

摘要

为解决城市交通道路信息或客户需求改变带来的成本浪费,提出带时间窗和容量约束的动态车辆路径问题模型和求解算法。建立以最小化车辆总成本为优化目标的带时间窗和容量约束的动态车辆路径模型(dynamic vehicle routing problem with time windows and capacity constraints,CDVRPTW),并用DVRP求解器将DVRP分解成VRP问题的集合以解决动态性问题。提出坐标萤火虫算法,使萤火虫算法的离散解映射到连续域以适用于模型求解,运用局部搜索包括初始种群、增强路径、移除节点以及交换节点改进算法。结合数据集和实例,运用Matlab分析算法性能。结果表明,本文所提算法与经典求解DVRP算法相比,不论是求解速度还是解的质量都有明显提升,实际案例验证其现实意义。