目前，交通物流行业已大量采用电动汽车作为运输工具。然而，与传统燃油车不同，电动汽车充电需要花费相当长的时间，势必会影响车辆的调度安排。因此，我们需要同时考虑电动汽车路径规划和充电的联合调度问题（electric vehicle routing problem, EVRP），最大化运输收益、最小化用车成本。该问题是一类NP-hard的混合整数规划（mixed integer programming, MIP）问题，采用常规方法非常耗时。研究团队提出了一种计算时间复杂度低的两阶段算法（TLP），利用线性规划松弛的精确性、并提出消除耦合项方法，将原始问题转化为两个线性规划，故可以在多项式求解时间内获得近似最优解。为了进一步提高解的质量，课题组又提出了一种基于两阶段算法的迭代算法（ILP）。图1展示了两种算法既可保证近似最优解，又能将计算时间降低了4个数量级。

以此为基础，研究团队进一步针对在线的EVRP 以及未来信息的不确定性，提出了一种利用滚动优化框架和虚拟节点生成的快速算法。如图2所示，相较于商用的求解器，如CPLEX、GUROBI和分支定价算法，研究团队提出的MBD 算法将计算速度提高了3~4个数量级；此外，算法对内存需求小，可求解350个节点和35辆车的算例，从而验证了提出算法的优越性。

图1左：最优间隔的比较；右：算法计算时间的比较

图2左：不同算法的计算时间比较；右：大规模算例的计算时间比较

以上论文由南方科技大学和哈尔滨工业大学共同完成。两篇论文的第一作者为南方科技大学与哈尔滨工业大学联合培养的2018级博士生姚灿棋，通讯作者为杨再跃、机械与能源工程系研究助理教授陈士博，南科大是论文第一单位。以上论文由科技部重点研发计划、国家自然科学基金、深圳市科创委等资助。

论文链接：

1、https://ieeexplore.ieee.org/document/9713755

2、https://ieeexplore.ieee.org/document/9430759

内容装载于南科大官网：南科大杨再跃课题组在智能交通领域取得多项新进展 - 南方科技大学新闻网 (sustech.edu.cn)