基于列生成算法的鲁棒电动车路径问题

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