基于列生成算法的鲁棒电动车路径问题
作者:胡剑鹏; 罗霞; 甘易玄
更新时间:
为了解决具有不确定行程时间和灵活时间的窗下电动汽车路径问题,建立了以配送成本最小化为目标的混合整数规划模型。引入虚拟节点将电动汽车车辆路径问题转化为网络模型,采用列生成法求解。将该模型转化为基于路径的主问题和有限资源约束下求解最短路径的子问题,构建了基于蒙特卡罗仿真方法的鲁棒模型。子问题设计对bellman-Ford算法进行了改进,引入了路径扩展机制,加快了模型的求解速度,获得了模型的近似解,并结合动态路径搜索算法获得了最优解。最后,对对多组算例进行了计算。结果表明,该算法在保证结果准确性的同时,提高了求解速度。时间窗约束对分销成本的影响最大。在稳健和确定性情况下,里程约束、车辆荷载约束和时间窗约束对配送成本影响的变化规律是一致的。