近日，南方科技大学机械与能源工程系教授杨再跃团队在智能交通领域取得多项研究成果，两篇论文被该领域期刊之一IEEE Transactions on Intelligent Transportation Systems接收。

目前，交通物流行业已大量采用电动汽车作为运输工具。然而，与传统燃油车不同，电动汽车充电需要花费相当长的时间，势必会影响车辆的调度安排。因此，我们需要同时考虑电动汽车路径规划和充电的联合调度问题(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级博士生姚灿棋，通讯作者为杨再跃、机械与能源工程系研究助理教授陈士博，南科大是论文第一单位。以上论文由科技部重点研发计划、国家自然科学基金、深圳市科创委等资助。