电动公交车辆调度问题研究综述

沈吟东 陈晨

摘  要：政府大力推动电动公交发展以促进城市节能减排，同时也为公交运营带来了挑战。车辆调度是公共交通运营计划中的一个关键问题，优化电动公交车辆调度方案不仅有助于降低公交企业运营成本，而且可以改善服务水平，让广大出行群众受益。文章首先对电动公交车辆调度问题及其数学模型进行了阐述，然后总结归纳了现有的车辆调度研究及电动公交车辆调度研究的成果，最后展望了电动公交车辆调度未来的研究方向。

关键词：电动车;车辆调度问题;公共交通;综述

中图分类号：F570    文献标识码：A

Abstract： Our government vigorously accelerates the development of electric buses to promote urban energy conservation and emission reduction. It is effective but also brings challenges to bus operations. In public transport， the vehicle scheduling problem is a key issue. Optimizing the electric bus scheduling plan will not only help reduce the operating costs of public transportation companies， but also improve the service level and benefit the passengers. This paper firstly describes the electric bus scheduling problem and its mathematical model， then summarizes the existing vehicle scheduling research and the electric vehicle scheduling research， and finally looks forward to the future research direction of electric vehicle scheduling.

Key words： electric vehicle; vehicle scheduling problem; public transport; review

0  引  言

近年來，随着我国城市化和交通机动化的进程不断加快，能源匮乏、环境污染与经济增长之间的矛盾日益加剧。在此关头，电动汽车以其节能、清洁和环保等优势被各国广泛关注，国内外众多国家与城市都在大力推动其发展以促进城市节能减排。

2012年，在国务院印发的《节能与新能源汽车产业发展规划（2012-2020年）》文件中，明确指出在由汽车需求量增长带来的能源紧张和环境问题日益突出情况下，纯电动汽车是我国新能源汽车和汽车工业转型的主要战略取向[1]。2015年，交通运输部、财政部、工业和信息化部联合印发了《新能源公交车推广应用考核办法（试行）》，直接对各省（区、市）每自然年度内（2015～2019年）新增及更换的公交车中新能源公交车的比重制定了目标，加快了新能源汽车在公交领域的推广应用[2]。2017年，工业和信息化部、发展改革委、科技部联合印发的《汽车产业中长期发展规划》中指出，要加快新能源汽车技术研发及产业化、加大新能源汽车推广应用力度，逐步提高公共服务领域新能源汽车使用比例[3]。2020年，交科院发布的《2019年度中国新能源公交车推广应用研究报告》显示，截至2019年底，全国公交车总量在69万多台，其中新能源车占比59%，并且2019年度新增及更换公交车6.9万辆，其中96%为新能源公交车，电池类型以磷酸铁锂为主。

王雪然等[4]对纯电动公交车基于能源链的全生命周期CO2减排效果研究中得出结论：在相同的运营环境下，纯电动公交车相较于柴油公交车，在能源链全生命周期能够减少61.20%的CO2排放量。其中，直接排放阶段，纯电动车可实现100%减排;间接排放阶段，可实现46.09%减排。公共汽车是城市交通基础设施的重要组成部分，除了中国，世界各地的城市越来越多地将电动公交车视为减少当地空气污染的一种方式，巴黎和阿姆斯特丹等城市也已经设定了在未来几年改用零排放巴士的目标。

然而纯电动车在公交领域的应用有别于传统燃油公交，由于动力电池性能限制，纯电动公交的续驶里程范围和长充电时间特性，以及充电的相关配套设施建设情况使得纯电动公交在车辆调度过程中需要考虑更多的约束，不能简单地去把传统燃油公交的车辆调度方案套用于纯电动公交。因此，有必要针对电动公交展开其车辆调度问题研究，编制出科学合理的车辆调度方案。这不仅有助于降低公交企业运营成本，而且能够改善公交运营和服务水平，让广大出行群众受益。

1  电动公交车辆调度问题概述

作为公共交通运营计划中的一个关键问题，公交车辆调度问题（Vehicle Scheduling Problem，VSP）的目的是以运营时刻表为基础，制定覆盖所有单程的有序的行车计划。要求每个单程被且仅被某一辆车执行一次，其目标通常是最小化总运营成本。由于国内的城市公交车逐渐被电动公交车取代，而传统燃油公交的车辆调度方案不能直接套用于纯电动公交运营中，因此新的挑战涌现出来了。相较于传统的基于燃油公交的车辆调度问题，由于电动汽车存在低续驶里程和长充电时间两个特性且实际充电站相关配套设施建设有限，因此电动公交车辆调度问题（Electric Vehicle Scheduling Problem，EVSP）将更加复杂。

1.1  问题分析

电动公交车辆调度问题基于给定每日发车时刻表（其中包含每个单程的发车时刻、起点站、终点站等信息）、电动公交的车型信息（其中包含额定载客量，整备质量，电池总储电量等信息）等，目标是求解得到总运营成本最小的车辆调度方案。电动公交车辆调度方案的制定需满足以下限制：

（1）每个单程任务都必须被执行，被且仅被一辆车执行一次;

（2）同一辆车的两个相邻单程任务之间允许空驶和等待，但是会产生相应的连接成本;

（3）车辆电量低时，需及时去充电站补充电量，绝对不能使公交车在路上耗完电量;

（4）车辆从车场出发开始执行一天的任务，执行完所有的任务后返回车场。

燃油车辆续航高，在公交车辆调度问题中通常忽略加油过程。然而纯电动公交车电池容量有限不足以满足城市一整天的运营需求，白天运营过程中电量不足时需及时补充电量。一般，电动车补充电量的方式主要分为以下三种：

（1）整车慢充。采用低电流对电动车进行充电，技术成熟，建设成本低，且对电池的损害小，但是所需时间长。

（2）整车快充。采用高电流为电动车进行充电，所需时间较短，但是建设成本较高，并且高电流充电对电池损害大。

（3）更换电池。采用专业的操作装置，取下车上储电不足的电池，换上充好电的备用电池，整个过程在十分钟左右。所需时间最短，但是技术要求高且建设成本高。

目前，公交运营企业的主流充电方案是夜间慢充将车辆充满电，白天运营过程中在需要时采用快充模式补充电量。换电模式需配备若干备用电池以及配备专用的操作设备，虽耗时最短，但由于成本高昂，很少采用。慢充模式则耗时过长，仅适合夜间充电，若用于运营过程中充电则会导致车辆资源不能很好的利用。

1.2  问题建模

为了尽可能地将问题描述清楚，对如下术语给出定义：

（1）单程：对应时刻表上的一趟发车任务，应具有首末站地点、发车时间、单程服务时间、单程耗电量等属性。

（2）车次链：一辆车的全天行车计划，包括从车场出发，然后按照发车时间先后执行完全部单程任务，最后返回车场。

（3）空驶：车辆在非运营路段的行驶，包括某单程终点与下一单程起点不同时两衔接车次间的空驶、首末站与车场的空駛。

（4）等待：车辆完成前一单程任务后，在下一单程的出发地点停留等待再发车的时间。

本文将车辆调度问题常重构为网络流模型，表示为一个有向图G=N，A。节点的集合N包含车场节点集合D和单程节点集合T。弧的集合A包含五种弧：出场弧DO=i，j|i∈D， j∈T;返场弧DI=i，j|i∈T， j∈D;直接连接弧TL

=i，j|i∈T， j∈T，且中途不返回车场;返场连接弧DR=i，j|i∈T， j∈T，且中途返回车场d∈D等待;充电连接弧RL

=i，j|i∈T， j∈T，且中途去充电站充电。

现实情况中，当一条单程链中的两个衔接单程间的时间跨度过长（如两个小时以上），任务车辆会被要求返场等待，因此存在返场连接弧。当车辆电量不足时，需要去充电站补充电量后才能继续执行后续单程任务，因此也存在充电连接弧。电动公交车辆调度问题的网络流模型表示见图1。

图1表示了电动公交车辆调度问题的网络流模型，其中圆柱形表示车场节点，椭圆表示单程节点。对于车场节点集合D

？哿N，车场中的车辆可以在任意时刻，从所属车场出发，并最终返回所属车场。对于单程节点集合T？哿N，每一个单程包含计划出发时间、起点站、终点站，以及单程服务过程的电量消耗等信息。对于弧的集合A，每一条弧包含出发地、目的地、空驶时间、等待时间，以及对应的电量变化等信息。在时空网络中，通过五种类型的弧，单程节点集合被串成若干条车次链，每一条车次链被一辆车执行。

1.3  数学模型

网络流模型中，通过流量守恒公式和决策变量的取值共同约束单程任务的覆盖（即约束每个单程都被执行，且仅被执行一次）。给定一组节点N=D∪T和一组弧A=DO∪DI∪TL∪RL∪DR，以及一组充电站R，可以将电动公交车辆调度问题建模为：

2  车辆调度研究综述

目前针对电动公交车辆调度问题的研究相对较少，但是国内外学者已经对城市常规公交的车辆调度问题进行了大量的研究，并且取得了许多优秀的研究成果。考虑到电动公交车辆调度问题是车辆调度问题的扩展，可以采用相同的求解思路，本文分别从车辆调度研究和电动车辆调度研究这两部分展开文献综述。

2.1  车辆调度研究

自20世纪60年代起，交通与运筹优化等领域的学者们就开始了对车辆调度问题的研究。根据停放车辆的车场数，可以将车辆调度问题划分为单车场车辆调度问题（Single Depot Vehicle Scheduling Problem，SD-VSP）和多车场车辆调度问题（Multi Depot Vehicle Scheduling Problem，MD-VSP）。早期的研究工作集中在单车场车辆调度问题[5-8]上。单车场车辆调度问题即只有一个车场，所有车辆从该车场出发并最终返回该车场，通常被重构为指派模型[5]，最小分解模型[7]或网络流模型[8]。单车场车辆调度问题可以看作是多车场车辆调度问题的一种特例，自90年代起，更多的研究开始关注于多车场车辆调度问题[9-12]。多车场车辆调度问题即有多个车场，每个车场有自己的车辆，一般规定所有车辆从所属车场出发并最终返回所属车场，通常被重构为多商品网络流模型[9]或集合分割模型[11]。与此同时，学者们对于车辆调度问题的研究，都是从不同角度、不同方向开展，各有侧重。例如，考虑燃料约束[13-14]，考虑多车型[15-17]，考虑多目标[18-19]，将车辆—调度问题与时刻表问题集成求解[20-22]，将车辆调度问题与驾驶员调度问题集成求解[23-25]，考虑方案准点率水平[26-28]等。

公交车辆调度问题作为一个整数规划问题，已被证明为是NP难问题[9]，其求解方法主要分为两大类：

（1）整数规划（Integer Linear Programming， ILP）方法，通常辅助以启发式方法。Bertossi等[29]使用了松弛拉格朗日启发式算法对多车场调度问题进行求解，同时证明了该问题是一个NP难问题。Ribeiro等[30]建立了带有限制约束的集分割模型，并用列生成算法进行了求解，算例结果表明求解算法具有很好的鲁棒性。Amar等[31]提出了一种改进的列生成算法以求解具有高度退化特性的大规模实例。Oukil等[32]致力于在线性规划框架内加速列生成，将列生成、变量预处理、稳定变量结合起来以求解大规模的多车场车辆调度问题。作为精确算法的一种，ILP算法求解效果好，但是在求解速度上，以及在大规模问题上的求解能力具有较大局限性。

（2）智能优化方法（如启发式方法和超启发式方法等）。智能优化算法虽然不能保证求得整数规划问题的最优解，但是却能在短时间（通常多项式时间）内给出一个较好的可行解，结合领域知识能够很好地应用于大规模组合优化问题的求解[33]。张飞舟等[34]采用遗传算法的一点和二点交叉方式，求解了三种不同规模的车辆调度方案。Shen and Xia[35]应用2-opt策略，设计了基于禁忌搜索的车辆调度方法。姚艳君[36]将禁忌搜索算法独有的记忆思想引入到遗传算法的搜索过程中，从而对车辆调度问题进行求解，实验结果表明该混合算法的求解质量优于遗传算法。Pepin等[37]对比分析了分支定界算法、拉格朗日启发式算法、列生成法、大规模邻域搜索算法、禁忌搜索算法五种算法在求解车辆调度问题中的应用，发现其中列生成法的求解质量最优，但求解时间较长，而基于大规模邻域搜索的启发式方法求解速度快且质量不错。

2.2  电动车辆调度研究

纯电动公交车辆调度问题可以看作是带有续航里程约束和充电需求的车辆调度问题。其研究起步较晚，多数研究开始于近十年。按照补充电量的模式主要分为三类：基于换电模式的电动公交车辆调度、基于整车充电模式的电动公交车辆调度，以及基于混合充电模式的电动公交车辆调度。

2011年，靳莉[38]在对电动公交车电池状态与运营匹配关系的研究中，根据车载系统的实时监控数据，对纯电动汽车的续驶里程、充放电特性等进行了分析， 基于混合充电模式对单车场电动公交车辆调度问题建立了一个以车队规模最小化和总空驶距离最小化的两目标模型，并采用遗传算法对实例问题进行求解，验证了模型和算法的适用性。随后在2012年，周斌[39]将遗传算法与模拟退火算法相结合，对混合充电模式下的单车场电动公交车辆调度问题进行了求解。2013年，Zhu and Chen[40]基于换电模式研究了单车场的电动公交车辆调度问题，建立了一个以车队规模最小化和总换电次数最小化的两目标模型，并采用非支配排序遗传算法的基本思想，设计了一种改进的多目标优化方法。2015年，孟越[41]基于换电模式研究了多车场的电动公交车辆调度问题，统筹考虑车队规模、空驶时间、等待时间，且通过转化为各种费用将该多目标问题转化单目标问题，并建立了以单程链为变量的集分割模型，应用遗传算法进行了求解。2016年，Wen等[42]基于允许部分充电的整车充电模式，研究了多车场的电动公交车辆调度问题，首要目标是车队规模尽可能的小，其次是空驶距离尽可能小，并采用了自适应大规模邻域搜索算法对问题进行求解，实验结果表明，该算法可以为大规模实例提供很好的解，也可以为小规模实例提供最优或接近最优的解。2017年，徐刚[43]利用IC卡数据和GPS数据的时间同步性转换得到客流数据，从而建立了一个乘客出行成本最小化和公交企业收益最大化的多目标优化模型，并采用了改进的遗传模拟退火算法基于整车充电模式对模型进行求解。2018年，高佳宁[44]将分时电价纳入考虑，即将用电成本纳入考虑，基于改进的遗传算法分别求得了整车充电模式和换电模式下综合成本最小的车辆调度方案。

值得注意的是，上述研究均将单程服务时间视为固定常数，即在已知每一个单程的出发和到达时间的基础上展开调度方案的编制。然而，实际的道路交通情况千变万化，因此编制出的调度方案在实际运营中难以获得令人满意的准时性。此外，电动公交车的能耗与道路交通状况有关，如果电动车在行驶过程中耗尽电量无法前行，其对公交公司的负面影响将非常大。最近，Tang等[45]基于不确定的交通情况展开了在整车充电模式下对單车场电动公交车辆调度问题的研究，提出了一个静态模型和一个动态模型，并基于分支定价算法对两个模型进行求解。其中，静态模型引入了一种缓冲距离策略来规避出行时间的不确定性带来的不利影响，而动态模型则将一天划分为若干个时段，利用不断更新的道路交通状况和车辆运营情况，动态优化下一时段的车辆调度方案。

3  总结与展望

相较于燃油公交车辆调度，电动公交车辆调度需要额外考虑续航里程约束和充电需求，给公交运营带来了挑战。并且，电动公交车辆调度方案在现实中执行时涉及的影响因素非常多且关系复杂，涉及到路面交通情况、客流量、电池的充放电效率、电池容量衰减等问题。因此，电动公交车辆调度问题的建模和求解方法上仍有很大的研究空间，将来可以考虑在以下方向上扩展这项研究：首先，可以从问题角度考虑多车型、更灵活的充电方案，或是与时刻表问题或驾驶员调度问题集成求解，或是如何在不确定的交通情况下提高方案的准点率水平等。其次，可以从算法角度研究电动公交车辆调度问题更好的下限。

参考文献：

[1] 国务院. 《节能与新能源汽车产业发展规划（2012-2020年）》国发（2012）22号[Z]. 2012.

[2] 交通运输部，财政部，工业和信息化部. 《新能源公交车推广应用考核办法（试行）》交运发（2015）164号[Z]. 2015.

[3] 工业和信息化部，发展改革委，科技部. 《汽车产业中长期发展规划》工信部联装（2017）53号[Z]. 2017.

[4] 王雪然，刘文峰，张龙文，等. 基于能源链的纯电动公交车全生命周期CO2减排效果研究[J]. 交通运输系统工程与信息，2019，19（1）：19-25.

[5]  Saha J L. An Algorithm for Bus Scheduling Problems[J]. Journal of the Operational Research Society， 1970，21（4）：463-474.

[6]  Freling R， Wagelmans A P M， José M. et al. Models and Algorithms for Single-Depot Vehicle Scheduling[J]. Transportation Science， 2001，35（2）：165-180.

[7]  Equi L， Gallo G， Marziale S， et al. A combined transportation and scheduling problem[J]. European Journal of Operational Research， 1997，97（1）：94-104.

[8]  Billington L. Routing and scheduling of vehicles and crews[J]. Computers & Operations Research， 1983，10（2）：63-67.

[9]  Bertossi A A， Carraresi P， Gallo G. On some matching problems arising in vehicle scheduling models[J]. Networks， 2010，17（3）：271-281.

[10]  Kliewer N， Mellouli T， Suhl L. A time-space network based exact optimization model for multi-depot bus scheduling[J]. European Journal of Operational Research， 2006，175（3）：1616-1627.

[11]  Pepin A S， Desaulniers G， Hertz A， et al. A comparison of five heuristics for the multiple depot vehicle scheduling problem[J]. Journal of Scheduling， 2009，12（1）：17-30.

[12]  Haghani A， Banihashemi M. Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints[J]. Transportation Research Part A， 2002，36（4）：309-333.

[13]  Wang H， Shen J. Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints[J]. Applied Mathematics & Computation， 2007，190（2）：1237-1249.

[14]  Baumann B M， Washington G， Glenn B C， et al. Mechatronic design and control of hybrid electric vehicles[J]. Mechatronics IEEE/ASME Transactions on， 2000，5（1）：58-72.

[15]  Ralf Bornd？觟rfer， Andreas L？觟bel， Weider S. A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit[C] // Hickman M， Mirchandani P， Voss S. Computer-aided Systems in Public Transport. Springer Berlin Heidelberg， 2008：3-24.

[16]  Ceder A A. Public-transport vehicle scheduling with multi vehicle type[J]. Transportation Research Part C Emerging Technologies， 2011，19（3）：485-497.

[17] 李細霞. 公交线路车辆调度优化模型研究[D]. 武汉：华中科技大学（硕士学位论文），2007.

[18]  Zuo X， Chen C， Tan W， et al. Vehicle Scheduling of an Urban Bus Line via an Improved Multiobjective Genetic Algorithm[J]. IEEE Transactions on Intelligent Transportation Systems， 2015，16（2）：1030-1041.

[19]  Zhi-gang LIU， Jin-sheng SHEN. Regional Bus Operation Bi-level Programming Model Integrating Timetabling and Vehicle Scheduling[J]. Systems Engineering-Theory & Practice， 2007，27（11）：135-141.

[20] 刘志刚. 城市公共交通区域运营调度系统协同优化问题研究[D]. 北京：北京交通大学（博士学位论文），2009.

[21]  Schiewe P. Integrating Timetabling and Vehicle Scheduling[C] // Integrated Optimization in Public Transport Planning， 2020.

[22]  Freling R， Huisman D， Wagelmans A P M. Models and Algorithms for Integration of Vehicle and Crew Scheduling[J]. Journal of Scheduling， 2003，6（1）：63-85.

[23]  Haase K， Desaulniers G， Desrosiers J. Simultaneous Vehicle and Crew Scheduling in Urban Mass Transit Systems[J]. Transportation Science， 2001，35（3）：286-303.

[24]  Shen Y， Xia J. Integrated bus transit scheduling for the Beijing bus group based on a unified mode of operation[J]. International Transactions in Operational Research， 2009，16（2）：227-242.

[25]  Yan S， Tang C H. An Integrated Framework for Intercity Bus Scheduling Under Stochastic Bus Travel Times[J]. Transportation Science， 2008，42（3）：318-335.

[26]  Yindong Shen， Jia Xua， Jingpeng Li. A probabilistic model for vehicle scheduling based on stochastic trip times[J]. Transportation Research Part B， 2016，85：19-31.

[27]  He F， Yang J， Li M. Vehicle scheduling under stochastic trip times： An approximate dynamic programming approach[J]. Transportation Research Part C Emerging Technologies， 2018，96：144-159.

[28]  Huisman D， Freling R， Wagelmans A P M. Multiple-Depot Integrated Vehicle and Crew Scheduling[M]. INFORMS， 2005.

[29]  Bertossi A A， Carraresi P， Gallo G. On some matching problems arising in vehicle scheduling models[J]. Networks， 2010，17（3）：271-281.

[30]  Ribeiro C C， Fran？觭ois Soumis. A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem[M]. INFORMS， 1994.

[31]  Amor H M T B， Desrosiers J， Frangioni A. On the Choice of Explicit： Stabilizing Terms in Column Generation[J]. Discrete Applied Mathematics， 2009，157（6）：1167-1184.

[32]  Oukil A， Amor H B， Desrosiers J， et al. Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems[J]. Computers & Operations Research， 2007，34（3）：817-834.

[33] 王凌. 智能優化算法及其应用[M]. 柏林：施普林格出版社，2001.

[34] 张飞舟，晏磊，范跃祖，等. 智能交通系统中的公交车辆调度方法研究[J]. 中国公路学报，2003（2）：83-86.

[35]  Shen Y， Xia J. Integrated bus transit scheduling for the Beijing bus group based on a unified mode of operation[J]. International Transactions in Operational Research， 2009，16（2）：227-242.

[36] 姚艳君. 智能公交车辆调度系统的设计与优化[D]. 沈阳：沈阳工业大学（硕士学位论文），2010.

[37]  Pepin A S， Desaulniers G， Hertz A， et al. A comparison of five heuristics for the multiple depot vehicle scheduling problem[J]. Journal of Scheduling， 2009，12（1）：17-30.

[38] 靳莉. 电动公交车电池状态与运营匹配关系研究[D]. 北京：北京交通大学（硕士学位论文），2011.

[39] 周斌. 基于改进遗传算法的电动公交车行车调度研究[D]. 长沙：长沙理工大学（硕士学位论文），2012.

[40]  Zhu C， Chen X. Optimizing battery electric bus transit vehicle scheduling with battery exchanging： Model and case study[J]. Procedia-Soc. Behav. Sci， 2013，96：2725-2736.

[41] 孟越. 纯电动公交车区域行车计划编制模型及算法研究[D]. 南京：东南大学（硕士学位论文），2015.

[42]  M Wen， E Linde， S Ropke， et al. An adaptive large neighborhood search heuristic for the Electric Vehicle Scheduling Problem[J]. Computers and Operations Research， 2016，76（12）：73-83.

[43] 徐剛. 城市纯电动公交车调度优化问题研究[D]. 南京：南京理工大学（硕士学位论文），2017.

[44] 高佳宁. 考虑分时电价的纯电动公交行车计划编制方法研究[D]. 北京：北京交通大学（硕士学位论文），2018.

[45]  Xindi Tang， Xi Lin， Fang He. Robust scheduling strategies of electric buses under stochastic traffic conditions[J]. Transportation Research Part C， 2019，105（8）：163-182.

收稿日期：2021-01-15

基金项目：国家自然科学基金项目“基于随机运营时间的公交鲁棒车辆调度研究”（71571076）

作者简介：沈吟东（1965-），女，安徽合肥人，华中科技大学人工智能与自动化学院，教授，博士生导师，研究方向：运筹与优化、公共交通规划与调度、智能公交系统;陈  晨（1997-），女，湖北黄冈人，华中科技大学人工智能与自动化学院硕士研究生，研究方向：运筹与优化、电动公交车辆调度。