一种用于确定电动公交车线路最小车队规模的新型动态规划方法

《European Journal of Operational Research》：A novel dynamic programming approach for minimum fleet size in electric bus transit lines

　　•我们将电动公交车队的规模规划问题建模为时空混合整数规划模型，并证明峰值同时发车数量严格限制了车队规模的上限。•一种启发式动态规划算法能够以更低的计算量解决基于权重调度的子问题，从而得到近乎最优的车队规模。•通过真实数据与模拟数据的实验验证，该方法在多种场景和扩展条件下都能实现更优的车队规模与运营效率。

引言
电动公交车对于城市交通系统的绿色可持续发展具有重要意义，它有助于减少污染物和温室气体排放、优化能源结构以及降低运营成本（Pei等人，2024）。在全球推动可持续交通发展的背景下，中国及欧盟国家纷纷加大力度，加速城市公交车的电气化进程。中国在这方面取得了显著进展：2024年，纯电动公交车已占全国公交车总数的74.1%，实际运营数量达487,500辆（中国交通运输部，2025）。深圳、北京等城市也已实现或承诺实现公交车队的全面电气化（X. Wang等人，2023）。在欧洲，包括电动公交车在内的零排放公交车占据了城市公交市场的三分之一。尽管电动公交车具有显著的环境优势，但其续航里程较短，充电时间较长，相比传统柴油公交车存在更大挑战（Dolgui等人，2025；Hiermann等人，2016；Wang等人，2024），这给运营管理带来了诸多难题。根据不同的替换策略和调度安排，在保持原有时刻表的前提下，运营电动公交车所需的车辆数量大约是传统柴油公交车的1.3到2倍（Xue等人，2019）。此外，性能相当的电动公交车的价格通常是柴油公交车的两倍（Lu等人，2021；Y?ld?r?m和Y?ld?z，2021）。如此较大的车队规模和较高的单辆成本，在公交系统电气化过程中给运营方带来了沉重的财务负担。因此，研究为满足固定时刻表要求而需要的最小车队规模至关重要，这有助于减少初期投资并提升资源利用效率。该问题不仅涉及确定所需电动公交车的数量，还需为每辆公交车制定高效的行程分配与充电计划，以满足电池电量约束，避免行程与充电操作之间的冲突。

近年来，学术界对优化电动公交车运输系统的运营管理产生了浓厚兴趣。研究人员提出了多种复杂的优化模型与算法，用于解决电动公交车队配置与调度问题。一些研究聚焦于在固定车队规模下优化电动汽车调度问题，以降低运营成本（de Vos等人，2023；Rinaldi等人，2020）；另一些研究则将车辆购置成本纳入考量，将电动公交车队配置问题融入电动汽车调度模型中（Cui等人，2023；Wen等人，2016；Y?ld?r?m和Y?ld?z，2021）。然而，电动公交车的购置成本属于一次性前期支出，在德国约占其总拥有成本的35%–40%（Jefferies & G?hlich，2020），在波兰则约为49%（Ghotge等人，2025），而日常运营成本则是重复性且相对稳定的，因为它主要取决于固定的时刻表。实际上，车队采购决策通常在运营阶段之前做出，即便减少一辆电动公交车也能带来可观的资本节省。这种顺序决策特性凸显出，开展专门的舰队规模优化工作十分必要，这是降低初期投资、提升电动公交车应用经济可行性的前提。据我们所知，仅有少数研究探讨了电动公交车线路的最小车队规模问题（Diefenbach等人，2023；Janovec和Koháni，2019；C. Wang等人，2023）。不过，现有研究大多依赖商业求解器或启发式算法，未能深入挖掘问题的结构特征，导致在处理大规模问题时难以兼顾计算效率与解决方案质量。为填补这一空白，我们分析了问题的结构特征，将其重新构建为动态规划模型，进而开发出一种启发式算法，可高效获得高质量解决方案。

在本研究中，我们探讨了在预定路线两端站点之间运行的电动公交车线路的最小车队规模问题。时刻表规定了从各站点出发的时间，而两站点间的行驶时间则是固定且已知的。在这些运营约束条件下，我们的首要目标是确定满足整个时刻表要求所需的最少电动公交车数量，以及每辆公交车的相应调度方案（包括行程分配与充电计划）。为解决这一问题，我们首先构建了一个时空网络模型，进而建立了混合整数规划模型，该模型可同时优化行程分配与充电计划。随后，我们基于时刻表的特征从理论上分析了问题的结构属性。利用这些属性，我们将问题重新构建为动态规划模型，并开发出一种高效的基于动态规划结构的启发式算法。该算法会逐步向公交线路上添加电动公交车，为每新增的一辆公交车确定行程分配与充电方案，不断重复此过程，直至所有新增公交车能够覆盖时刻表中的所有行程。通过对真实数据集与模拟数据集进行的大量数值实验表明，与现有基准方法相比，所提出的方法更具有效性。本研究的主要贡献如下：
•我们将最小车队规模问题构建为基于时空网络的混合整数规划模型，该模型明确考虑了部分充电的灵活性、每辆电动公交车必须返回起始站点的要求，以及站点充电设施的有限供应情况。基于这一模型，我们还证明了在每个时间点正在执行的行程数量直接决定了正在运行的电动公交车数量。这一结构特征为分析问题属性以及设计高效解决方案提供了重要的理论基础。
•我们利用已发现的 problem结构特征，将混合整数规划模型重新构建为动态规划模型，在该模型中，电动公交车会依次被添加到公交线上，每新增一辆公交车都会对应确定其行程分配与充电计划。随后，我们基于这一结构开发出一种启发式的顺序决策算法。在每一阶段，我们会根据剩余待执行行程的数量以及各站点在对应时间点的充电设施使用情况所确定的权重，来解决电动公交车的调度子问题。此外，我们还引入了多步前瞻机制，以减少单步决策的短视效应，进一步提升解决方案的整体质量。
•我们使用了来自中国大连三条电动公交车线路的真实数据，以及具有不同发车频率的随机模拟数据集，进行了大量数值实验。实验结果表明，所提出的HDP方法在多种场景下都能实现具有竞争力的车队规模优化效果，且计算效率更高。我们还通过对与电力相关的参数进行敏感性分析来评估该方法的表现，进一步将模型扩展为包含充电成本和不同类型电动公交车参数的形式，并研究了其在随机运营条件下的稳定性。

需要指出的是，本文提出的时空网络建模框架、所分析的问题结构特征以及HDP方法框架并不局限于此处研究的线路级场景。它们可以自然地扩展到多线路电动公交车网络，以及那些同时优化车队配置与运营成本的更一般场景。这种通用性凸显了所提出方法在电动公交车运输运营领域的广泛适用性与实际价值。

本文的其余结构如下：第2节对研究问题相关的文献进行了综述。第3节明确了本研究要解决的具体问题，第4节介绍了相应的模型构建方法。第5节将问题重新构建为动态规划模型，并设计了对应的求解算法。第6节针对多个真实公交线路进行了大量数值实验，同时还基于模拟数据测试了算法的性能。第7节对全文内容进行了总结。为便于理解与查阅，技术性证明内容放在附录A中，附录B详细介绍了各类基准方法，附录C则汇总了在模拟数据集上进行的实验所得的补充结果。