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

Dynamic Vehicle Routing Problem with Time Windows and Capacity Constraints Based on Coordinate Firefly Algorithm

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

In order to solve the cost waste caused by the change of urban traffic road information or customer demand,a dynamic vehicle routing problem model and solution algorithm with time window and capacity constraints are proposed.Firstly,a dynamic vehicle routing problem with time windows and capacity constraints is established to minimize the total vehicle cost,and DVRP is decomposed into a set of VRP problems by DVRP solver to solve the dynamic problem.Secondly,the coordinate firefly algorithm is proposed to map the discrete solution of the firefly algorithm to the continuous domain to be suitable for the model.The local search is used to improve the algorithm,including initial population,enhanced path,removing nodes and exchanging nodes.Finally,combined with data sets and examples,Matlab is used to analyze the performance of the algorithm.The results show that the proposed algorithm is significantly better than the classical DVRP algorithm in both solution speed and solution quality,and the practical significance of the algorithm and model is verified by an actual case.