基于列生成算法的鲁棒电动车路径问题
来源：计算机集成制造系统杂志2023年第7期北京时间：
作者：胡剑鹏, 罗霞, 甘易玄
单位：1.西南交通大学交通运输与物流学院2.西南交通大学综合交通运输智能化国家地方联合工程实验室
摘要：为解决旅行时间不确定和柔性时间窗下的电动车车辆路径问题,建立了以配送成本最小为目标的混合整数规划模型。引入虚拟节点把电动车的车辆路径问题转化为网络模型,利用列生成方法进行求解,将模型转化为基于路径的主问题和有限资源约束条件下求解最短路径的子问题,并构建了基于蒙特卡洛仿真方法的鲁棒模型。针对子问题设计了改进Bellman-Ford算法,引入了路径扩充机制加速模型求解速度获得模型近似解,并结合动态路径查找算法获得最优解。最后,对多组算例进行计算,结果表明:所提出算法可以在保证结果精度的同时提高问题的求解速率;时间窗约束对配送成本影响最为显著;鲁棒情形和确定情形下配送成本受续航里程约束、汽车载重约束和时间窗约束影响的变化规律具有一致性。
关键词：公路运输,电动汽车,旅行时间不确定性,列生成算法,最短路径,整数规划
基金资助：四川省科技厅科技计划资助项目(2020YJ0255)。
