Abstract: To study the electric vehicle routing problem with travel time uncertainty and soft time window constraints,a mixed integer programming model was established with the minimum distribution costs as the objective.The virtual node was introduced to construct the routing network model,and the column generation algorithm was used for solving.The model was converted to a linear master problem and the shortest path subproblem with limited resource constraints.Shortest path search method based on improved Bellman-Ford algorithm and dynamic path planning algorithm was designed,and a path expansion mechanism was introduced to improve the efficiency of model solution.Through the calculation of several groups of examples,the proposed algorithm could effectively improve the solving rate of the problem.In addition,the sensitivity analysis results showed that the maximum allowable delay time had the most significant effect on the distribution cost,followed by the load capacity of the electric vehicle.

Key words: road transportation, electric vehicles, travel time uncertainty, column generation algorithm, shortest path, integer programming

摘要： 为解决旅行时间不确定和柔性时间窗下的电动车车辆路径问题,建立了以配送成本最小为目标的混合整数规划模型。引入虚拟节点把电动车的车辆路径问题转化为网络模型,利用列生成方法进行求解,将模型转化为基于路径的主问题和有限资源约束条件下求解最短路径的子问题,并构建了基于蒙特卡洛仿真方法的鲁棒模型。针对子问题设计了改进Bellman-Ford算法,引入了路径扩充机制加速模型求解速度获得模型近似解,并结合动态路径查找算法获得最优解。最后,对多组算例进行计算,结果表明:所提出算法可以在保证结果精度的同时提高问题的求解速率;时间窗约束对配送成本影响最为显著;鲁棒情形和确定情形下配送成本受续航里程约束、汽车载重约束和时间窗约束影响的变化规律具有一致性。

关键词: 公路运输, 电动汽车, 旅行时间不确定性, 列生成算法, 最短路径, 整数规划