电动汽车路径规划模型与算法研究进展

电动车技术的发展为物流企业提供了一种配送车辆的新方案。电动车具有低污染、低噪音等优点，其续航短、充电站有限等特性也带来了新的挑战。电动车路径问题(electric vehicle routing problems，EVRPs)在交通运输、物流管理等领域得到了广泛应用，受到了众多学者的关注。整理了电动车路径问题及其主流变体的问题描述，分析了其各自的提出背景与适用场景。对EVRPs的求解方法和技术做了归类，分析了各方法的优劣，并介绍了相关实际应用。给出了EVRP基准数据集与带时间窗的电动车辆路径问题的基准数据集的基本信息和部分节点分布图，对比分析了已对EVRP基准数据集应用的算法。展望了EVRPs的发展前景。 化石燃料燃烧产生的温室气体是造成气候变 化与全球变暖的主要原因[1] 。交通运输产业是全球 第二大碳排放源，减碳降耗是当前城市交通策略 的主要目标之一[2] 。近十余年来，电动汽车技术快 速发展，受到了越来越多的关注。国际能源组织 分析了多个国家的电网，认为使用电动汽车能够 有效减少全球碳排放[3] 。研究发展电动汽车也是我 国一个长远的、意义重大的战略目标[4] 。 电动汽车送货是物流公司的新趋势[5] 。由于 充电站点少、续航里程较短等特性，传统车辆路 径问题(vehicle routing problem, VRP) [6] 被扩展为电 动车路径问题(electric VRP, EVRP)。VRP 描述了 如何使用一组有限数量的货车以最小的代价将给 定的货物全部运输到客户手中去的问题。城市加 油 站 设 施 完 善 ， 且 燃 油 汽 车 续 航 里 程 充 足 ， VRPs 通常不考虑中途加油的代价。电动汽车路 径 问 题 源 于 Erdoğan 等 提 出 的 绿 色 车 辆 问 题 (GVRP) [7] 。电动汽车仅靠电池续航往往无法完成 完整的一趟送货，中途可能需要充电是EVRPs与 VRPs的主要区别。 EVRP 虽然是 VRP 的直接变体，但由于充电 约束的存在，VRPs 的求解方法通常不能直接用 于求解 EVRPs[8] 。EVRP 相比 VRP 复杂得多，其 发展具有明确的理论和现实意义，故本文将对 EVRP 及其变体的模型、求解方法和应用场景作 一概述。