纯电动公交时刻表和车辆排班计划整体优化

滕 靖, 林 琳, 陈 童

(1. 同济大学 道路与交通工程教育部重点实验室, 上海 201804; 2. 同济大学 城市交通研究院, 上海 200092;3. 上海电科智能系统股份有限公司, 上海 200063)

我国城市公交车辆已经进入电动化时代,按照交通运输部的部署,到2020年年底,我国重点区域的直辖市、省会城市、计划单列市建成区公交车全部更换为新能源汽车[1].在新能源公交车辆中纯电动公交车具有零排放、零污染、噪音小等优点,纯电动公交车辆靠车载电池电力驱动,非常适合城市交通环境中车辆低速行驶和频繁起停.然而不同于化石燃料公交车,受电池技术等限制,目前纯电动公交车辆电池容量夜间一次充满后,其电能还不能完全满足公交线路的日间运营需求.

公交运行计划的编制既需要满足乘客出行需求,达到规定服务水平,也需要控制运营成本,为企业增加效益.时刻表和车辆排班计划是公交运行计划的两个重要组成部分,两者整体优化能够兼顾乘客和企业利益,是运输管理领域研究的热点内容.国内外关于时刻表和车辆排班计划整体优化方面的研究主要针对化石燃料的公交车,研究可分为两类:第一类是先确定时刻表或给定初始时刻集合,在此基础上优化车辆排班计划,如果排班计划无法满足约束则在时刻表优化约束范围内继续寻找次优方案,进而不断反馈直至排班计划满足约束.Ceder[2]较早提出先时刻表后车辆排班计划的优化方法,提高了时刻表和车辆排班计划的协同性;其在2011年[3]又进一步设计了交互式的启发式算法,求解考虑多车型、兼顾载客均衡和发车间隔均衡目标的时刻表以及运营费用最低的车辆排班计划.第二类是联合求解,即采用一个模型同时得到两个计划.如刘志刚等[4]按照区域公交调度模式,建立集成时刻表生成和车辆排班的双层规划模型,产生最佳车辆调度方案及与之对应的符合满意度评价标准的公交时刻表.Rojas等[5]提出了面向区域网络的双目标模型,双目标分别为乘客换乘成功率最大和车辆使用成本最低,较好地解决了区域多线路协同调度模式下的车辆排班问题和时刻表协同优化问题.

关于纯电动公交车运行计划的研究主要集中在车辆排班计划方面.在整车充电模式下,Zhu等[6]基于单线路的纯电动公交的运行特点建立了使公交运营企业以及充电站运营成本最小的PE-VSP模型.Van Kooten[7]和Posthoorn[8]提出了三个模型来解决纯电动公交车车辆排班问题,第一个为线性规划模型(LP),基于电池的充电速度是线性的假设,只适用于小规模问题;第二个模型是混合整数规划模型(MIP),和第一个模型的区别在于车辆充电不是一个针对班次的连续变量,即车辆可以在每个班次结束后充电,这样可以考虑不同时间段的充电价格;第三个模型适用于大规模问题,用列生成算法求解.周斌[9]基于纯电动公交续航里程、充放电时间等运营特点,以电动车续驶里程和充电时间约束为基础,建立了以车辆数最小和空驶距离最小为目标的纯电动公交车调度模型.孟越[10]研究了纯电动公交多车场区域行车计划编制模型,统筹考虑所需车辆数、空驶时间和等待时间,以及纯电动车行驶里程限制、充电时间约束、车场容量等约束.

综上,既有的时刻表和车辆排班整体优化问题研究多针对于化石燃料公交车,对纯电动公交车排班计划优化的研究多是在时刻表给定的前提下开展的.纯电动公交排班与化石燃料公交排班的最大差异在于其必须将进场充电过程与线上运行过程统筹考虑.纯电动公交车辆由于续航里程的限制,在运营周期内需要多次往返场站进行充电,在运行计划编制过程中需要考虑更多约束条件.可见,化石燃料运行计划整体优化理论成果无法套用于纯电动公交运行计划编制中.为此,本文尝试研究电动公交车时刻表和车辆排班计划整体优化方法.首先对纯电动公交时刻表和车辆排班计划的影响因素进行分析,然后凝练问题形成优化逻辑,进而构建模型并设计求解算法,最后举例实证方法与模型的有效性.

1 纯电动公交时刻表和车辆排班计划问题解析

首先,时刻表是车辆排班计划的前提,规定了各客流特征时段的发车班次数和行车间隔,发车班次数与投放的运能有关,需要满足各时段的客流需求,且最大行车间隔需要满足行业服务水平要求.时段间的行车间隔还应尽量平滑,以提升乘客候车感知效果.

其次,车辆排班计划编制时要安排有限的车辆资源尽可能接续更多的班次.上一阶段行车间隔调整必然会影响车辆执行班次的接续情况,从而影响车辆使用数量,影响企业效益.

第三,对于纯电动公交车辆,受限于电池续航里程,车辆的全日运营过程中还必须考虑进场充电时间.纯电动车辆的充电时长和所在的充电时段会影响充电费用,显然尽可能避开高峰时段充电会降低企业运营成本.因此,在纯电动车辆排班过程中,需要特别考虑车辆在场内的充电时长和充电起、终时刻.

综上可见,对于纯电动公交线路,时刻表、车辆排班计划和进场充电计划之间互相影响,其编制过程涉及如图1所示的两步编制、三项内容.优化目标方面需要综合考虑发车间隔标准差、车辆数量和充电费用三类指标,约束条件则涉及不同时段发车间隔水平、纯电动公交车续航里程、充电设施资源条件等.本文尝试在特征时段内线路发车班次数确定的情况下,在发车间隔范围内对纯电动公交时刻表和车辆排班计划进行整体优化,模型的优化过程就是车次任务之间的最佳接续关系调节过程.

图1 纯电动公交时刻表和车辆排班计划整体优化内容范围

2 问题优化过程

2.1 时刻表优化

(1) 考虑客流聚类的分时段发车频率优化

基于客流调查数据获得公交线路全日的断面客流数据,将单位小时高断面客流量按时间顺序组成一组有序样品,通过建立有序样品聚类的Fisher模型,划分特征时段.该模型已有较好的研究基础[11],不再详述.利用式(1)来计算各时段内的发车班次数nf,其中f表示特征时段的编号,F表示特征时段总数,f∈[1,F].对于分上下行的公交线路,车辆从首站出发再回到首站作为一个班次.

(1)

(2)

(3)

这个过程将划分出客流特征时段,计算出各时段内的发车班次数,以作为下述优化过程的前提.

(2) 发车时刻表优化

根据实际运营要求,时刻表应该在满足乘客需求的条件下使发车间隔应且尽可能平滑,这里用发车间隔的标准差Z1来刻画发车间隔的平滑性.

时刻表优化部分将各班次间的发车间隔作为决策变量,即tsfi-tsf(i-1),i=2,3,…,nf.其中,tsfi为f时段内i班次的发车时刻,tsf(i-1)为f时段内i-1班次的发车时刻.

(4)

(5)

约束条件为

hfmin≤tsfi-fsf(i-1)≤hfmax,i=2,3,…,nf

(6)

(7)

(8)

式(6)表示各时段发车间隔需要落在最大发车间隔和最小发车间隔之间.式(7)和式(8)要求各时段首末班次发车时刻介于特征时段跨度内.

2.2 纯电动公交车辆排班计划优化

2.2.1 纯电动公交车充放电过程分析

由于电动公交车的驱动电能由动力电池提供,动力电池的性能指标决定了车辆的性能,也会影响车辆的充放电过程.电池性能指标主要有电池容量(C)、电池荷电状态(Cs)和放电深度(Dd).

充满的电池在一定条件下放电到终止电压时所释放的电量为电池容量C,其值通常由制造商标明,也称为电池额定容量.

电池剩余容量占额定容量的百分比为电池的荷电状态Cs,%.用数学公式可以表示为

(9)

式中:C1为电池现有剩余容量.

电池已使用的电量与额定电量之间的比值为放电深度Dd,它与电池功率密度相关.

靳莉[12]采用线性拟合的方法研究了纯电动公交车整车充电的充放电过程,结果表明,在充电过程中,Cs呈线性增长趋势,且每个充电过程中Cs曲线基本平行,即Cs增长率相同;在放电过程中,公交车已行驶的里程和放电深度Dd也呈线性变化的关系.结合该研究,本文引入充电速率k1,%·h-1,即充电过程中单位时间内电池Cs增长量;和电池电量利用效率k2,km·%-1,即使用单位电量公交车可行驶的距离.两者的取值和车型及电池种类相关, 根据公交企业纯电动公交车充电记录计算可得到.另外高峰期时段道路交通运行整体环境的恶化会导致公交车车速下降、启停车次数增加,电池利用效率降低[13],本文基于不同时段周转时间的差异性区分了平峰与高峰期的电池电量利用效率参数.

根据已有研究对磷酸铁锂蓄电池在不同的放电时间、放电深度和充电速率下的实验[14],电池循环寿命随放电深度的变化而变化,完全放电对于电池循环寿命损耗较严重.因此,为不至于对电池造成较大的损伤,结合现场考察的实际应用经验,本文设定电池的放电深度上限为80%,即Cs≥20%.

充电深度和充电时间的关系可表示为

ΔCs=k1·tc

(10)

ΔCs=Csa-Csb

(11)

式中:ΔCs为充电深度,%,即充电的电量与额定电量之间的比值,也等于充电后的荷电状态Csa减去充电前的荷电状态Csb;tc为充电时间,h.

放电深度和充电时间的关系为

r=k2·Dd

(12)

式中:Dd为放电深度,%;r为电动公交车已行驶里程,km;假设电动公交车充电和放电深度相等,可以得到电动公交车充电时间与已行驶里程之间的关系方程如式(13):

(13)

车辆在这段时间所补充的电量c,kwh,为

c=ΔCs·C=tc·C·k1

(14)

2.2.2整合充电过程的车辆排班优化模型

纯电动公交车辆排班优化的目标函数为车辆数和充电费用最小.

(15)

(16)

式中:Xk为0-1变量,表示车辆k是否运营;tckij为车辆k在班次i和班次j之间的充电时间,min;ph为现有充电时段的单位分钟电价,min-1.

纯电动公交车辆排班问题的约束条件可分为常规公交车辆排班问题约束和纯电动公交充电约束.

常规约束[15]有

(17)

(18)

(19)

(20)

(21)

Xkij={0, 1}

(22)

式中:Xkij为0-1变量,表示车辆k执行完班次i后执行班次j,i,j=1,2,…,n;XxOi表示车辆k从车场出发执行班次i,XkjO表示车辆k执行完班次j后回到车场,下标O代表车场;m为该公交线路可投入运营的最大车辆数.

式(17)和(18)为班次衔接约束,保证每个班次均有车辆执行且被执行一次;式(19)保证从车场出发的车辆最终回到车场;式(20)表示如果车辆k执行了某一班次,则Xk=1;式(21)表示执行班次任务的车辆数小于等于可供调度的车辆数.

为了更好地描述纯电动公交车辆排班过程,本文对模型中对纯电动公交充电的相关假设及对应的约束条件如下:

条件1:车辆一次连续行驶里程不超过续航里程,如果车辆剩余运行里程不足以执行一个班次并返回车场,则该车辆必须进行充电,此时的剩余里程称为充电限制里程.如果车辆的剩余里程大于充电限制里程也可进行充电,充电时间仅和已行驶的距离有关.车辆开始充电后,必须充满才能执行下一班次.相关约束条件为

(23)

Cki·(Rk-rki)≤L+L′+L0

(24)

Cki={0, 1}

(25)

(26)

式(23)~(26)中:np为同一放电过程中车辆已执行班次的集合;Cki为0-1变量,表示车辆k在执行完班次i后是否需要充电;Rk为车辆k的续航里程,km;rki为车辆k执行完班次i后已行驶的里程,km;L,L′分别表示线路上、下行的行驶里程,km;L0表示线路从首站到车场的行驶里程,km.

式(23)表示为续驶里程约束,保证每辆电动公交车在一个放电过程中行驶的里程数小于等于其续航里程;式(24)表示车辆剩余运行里程不足以执行一个班次并返回车场,则该车辆必须进行充电;式(26)为充电时间的计算方法,在式(13)中已有表述.

条件2:车辆充电后,与下一班次的接续时间必须满足式(27),即下一班次的发车时间必须大于等于上一班次的到达时间加进出车场的时间再加充电时间.

tsfj-tefi≥tkij·Xkij

(27)

(28)

条件3:当车辆到达车场后立即开始充电,保证车辆周转效率.本文研究的是单线路公交,在车场内一般不固定充电桩使用,可设充电桩充足.

条件4: 车辆充电时间应该避开用电高峰时段和客流高峰时段,不影响城市电网的使用,从而保证社会效益.

3 整体优化建模及求解

将第2节优化过程中的目标函数和约束条件整合,建立多目标优化模型,采用多目标粒子群算法求解,得到该问题的Pareto最优解集,考虑到在实际运营过程中三个目标函数之间优先级关系,提出最优解的选择方法.

3.1 模型公式

由于发车间隔平滑度、使用车辆数和充电费用三个目标函数的量纲差别较大,且三者之间难以用权重系数衡量.因此,本文建立了纯电动车时刻表和车辆排班计划整体优化的多目标规划模型,目标函数为式(4)、(15)、(16);约束条件为式(6)~(8)、式(17)~(28);Xkij和Cki为0-1变量.

3.2 模型求解

本问题为典型的多目标优化问题(MOP),使用多目标粒子群算法[16](Multi-objective particle swarm optimization, MOPSO)求解. MOPSO算法是基本粒子群算法和Pareto支配方法结合的基于随机优化技术的进化的求解方法.算法的关键步骤为选取个体的极值,建立外部储存器以储存迭代过程中的Pareto最优解,外部存储器中的解集就是全局极值的候选解,运用轮盘赌方法从外部存储器中选取,个体极值则根据Pareto支配关系进行选择.针对时刻表和车辆排班整体优化模型,对算法中的关键步骤进行说明.

(1) 粒子编码方式

采用实数编码方式,定义粒子的长度为2n-1,前n位的取值在0~m之间,m为最大车辆数,表示每个班次对应的车辆编号,若车辆编号相同,则说明这些班次均由该车辆执行;粒子的后n-1位的值为相邻班次间的发车间隔,取值范围根据班次所处特征时段的具体要求而定.

(2) 适应度值的计算

模型共有三个目标函数和众多约束条件,由于目标函数均为求最小值,所以可以直接作为适应度值.对约束条件的处理是将其作为罚函数加入目标函数.如客流高峰时段和城市用电峰时段的电价设置为一个较大的正数,则在计算充电费用时,目标函数会增大,产生较大的适应度值.

3.3 实际运营最优解的选择方法

多目标优化问题不存在唯一的全局最优解,所以求解多目标优化问题实际上是寻找一个解集合,称为Pareto最优解集.但是在公交实际运营过程中,由于运营成本等原因,运营者对三个目标的考虑会有先后顺序,通常车辆数最小的目标优先考虑,在这个前提下再合理安排车辆充电,使充电费用较低,最后在此基础上去优化发车间隔的平滑度,给乘客更好的体验.按照该顺序,本文提出了一个最优解的选择方法,其步骤如表1所示.

表1 选取实际运营最优解的步骤

4 案例研究

4.1 案例参数

选取上海市某纯电动公交线路,线路运营和所使用的纯电动公交车辆及单位电价的相关参数如表2所示.

表2 参数含义及取值

车辆进/出车场的时间除单程行驶时间外,还包括例行的车厢卫生环境及安全状态检查时间等.上海市非居民用电峰时段单位电价为1.167元·min-1,在模型计算中取值为1 000,作为惩罚项;平时段单位电价为0.697元·min-1;谷时段单位电价为0.352元·min-1.

对案例公交线路工作日以小时为单位的高断面客流量采用有序样品聚类的Fisher模型对客流量进行分析[11],分类结果如表3所示,其中各时间段的周转时间通过对车辆运行时间历史数据的分析得到.

结合问题规模,设置不同的学习因子和惯性权重,使用Matlab2014b在Win10环境中求解,运行结果显示,当多目标粒子群算法参数如表4所示时,结果最优.

表3 案例线路分时段发车班次和周转时间

表4 多目标粒子群算法参数

4.2 结果分析

案例公交线路时刻表和车辆排班计划的Pareto最优解集如图2所示,根据3.3 节提出的符合实际运营最优解的选择过程,得到模型结果,如表5所示.公交线路全日运营使用的车辆数为14,比线路现有方案中的减少了3辆;发车间隔标准差也相对较小,各班次发车更加平滑;充电费用也比线路现有运营方案降低了约19%;车辆全日总充电次数也有所减少.

表5 各目标结果比较

比较线路现有运营方案和模型得到的车辆排班计划,如表6所示,表中空驶里程指不载客里程.和线路现有运营方案的结果相比,在总运营班次相同的条件下,由于总充电次数较少,模型得到的排班计划中空驶里程和日运营总里程较小,同时由于车辆数的减少,车均运营里程比线路现有运营方案增加了约20%,提高了车辆利用率,但也增加了每辆车的使用强度.

表6 车辆排班计划比较

进一步比较线路现有运营方案和模型得到的车辆排班计划中的充电情况,如图3和图4所示,线路现有运营方案的计划中总充电时间为2 965 min,其中高峰时段充电时间占总充电时间的17.8%,充电费用占总费用的36.5%,说明在峰时段充电对总充电费用的影响较大.而模型通过对用电价格的控制,使车辆利用白天平时段和夜间低谷时段充电,有效地避开了城市用电高峰期,有利于减少城市用电峰谷差.

模型结果中平均每次充电时间为127.64 min·次-1,车辆日平均充电时间为200.57 min·车-1,两者与现有方案相比都较大.由于充电时间和车辆已行驶的里程相关,说明模型结果中车辆的平均使用强度较大.同时,车辆日平均充电时间的增大会加大充电桩使用强度,因此需要公交企业合理安排停车场内充电桩的使用.

由以上结果,可以得出以下结论:

(1) 模型可以优化各班次发车间隔,提高发车平滑度,同时减少使用车辆数、充电费用和充电次数,进而降低空驶里程,有效降低公交企业成本.

图4 充电费用比较

(2) 模型通过对城市用电价格的控制,使车辆利用白天平时段和夜间低谷时段充电,从而减少充电费用,均衡城市用电.

(3) 纯电动公交车线路在运营过程中使用车辆数的减少会增加车辆的使用强度,增加车辆平均每次充电时间,因此公交企业需要协调好车场内充电桩的使用,同时做好纯电动公交车辆日常维护和保养工作.

5 结语

本文运用多目标优化理论,构建纯电动公交车运营的单线路的时刻表和车辆排班计划的整体优化模型,综合考虑了线路发车时刻平滑性、线路所使用的车辆数和充电费用,在约束中考虑了各时段发车间隔范围、纯电动公交车的续航里程、充电时间和充电条件,采用多目标粒子群算法求解.案例结果表明,时刻表和车辆排班计划的整体编制模型相比两阶段独立编制模型增大了优化空间,不仅可以改善班次发车间隔平滑度,减少线路所使用的车辆数,而且可以使纯电动公交车的充电时间避开城市用电高峰期,从而减少充电费用.下一步,将在此基础上开展跨线调度模式下的纯电动车辆排班问题研究.