单线纯电动公交车辆柔性调度优化

唐春艳，杨凯强，邬 娜

(1.大连海事大学交通运输工程学院，辽宁大连116026；2.长安大学运输工程学院，西安710064)

0 引 言

纯电动公交车与燃油公交车动力系统不同，故在运行参数等方面相差较大.燃油公交车的续驶里程一般能满足1 d的运营需求，而纯电动公交车受电池容量影响续驶里程短，且充电时间较长.因此，燃油公交车的运营调度模式不适用于纯电动公交车.

纯电动公交车辆调度主要研究成果有：杨扬等[1]将班次任务、公交场站和充电站作为节点，班次间的空驶作为边，把电动公交车的调度问题转化为网络模型；Li 等[2]对电动公交车的3 种充电方式进行定性分析，探讨不同动力能源下公交车运营成本，分析电动公交车充电对电网的潜在影响；Li等[3]提出新额外成本效益方法，解决多能源动力混合公交车辆调度问题；Wen等[4]研究不同电量状态的纯电动公交车调度，采用自适应大邻域搜索启发式算法(ALNS)进行求解；Tang 等[5]考虑公交车辆运行受城市道路交通状况影响，提出纯电动公交车辆鲁棒性调度模型；Hall 等[6]研究整充、换电池、快充等不同充电方式下，纯电动公交车辆调度模型；Niekerk 等[7]提出电池衰退下的纯电动公交车辆调度模型.现有研究成果侧重纯电动公交车严格执行时刻表准点发车，即刚性调度，这可能因纯电动公交车充电时间长错过最佳接续发车班次，使调度所需要车辆数增加，进而增加公交运营成本.

国内外在燃油公交车柔性调度方面有一定研究，但主要关注公交线路动态调整、实时需求方面的柔性调度，较少涉及允许存在误时发车的柔性调度.刘昱岗等[8]提出基于实时需求的夜间公交柔性调度，通过采集夜间公交出行需求，考虑夜间公交服务水平和运营成本建立多目标优化模型；张飞舟等[9]提出公交车辆动态调度策略与在线调整方法，研究运营车辆出现意外事故、故障及延误等情况时应急调度措施和方案；Ceder[10]研究基于逆差函数方法的柔性车辆调度，以减少车辆使用数量；Nourbakhsh等[11]对低需求地区的运输系统进行研究，以系统成本最小建立模型，并提出柔性路径的选择方法.

综上，本文研究允许存在误时发车的纯电动公交车柔性调度，即允许车辆误时发车情况下，尽可能调度公交车接续最近发车班次.在分析发车延误带来公交运营外部成本的基础上，如乘客放弃乘坐此线路的公交，公交公司声誉受损等成本，构建车辆误时成本函数；考虑更换电池方式补充电能，构建单线纯电动公交的车辆柔性调度优化模型，并设计遗传算法求解.

1 模型构建

1.1 问题描述及基本假设

研究单一公交线路的纯电动公交车调度问题，线路双向运营.车辆运营成本主要包括车辆使用成本、空驶成本和充电成本.因允许误时发车，在运营成本中需考虑误时带来的外部成本，即因发车延误造成公交公司负面影响的成本.

模型基本假设如下：①纯电动公交车采用更换电池方式充电，②发站均有充电设施和车库，③每辆车均从车库驶出，执行完全天班次任务后返回车库，即中途不返回车库，④不考虑道路拥堵等情况.

1.2 符号设定

p——车库序号，p∈{1,2}；

h——纯电动公交车辆编号，h∈H，H为车辆集合；

R——时刻表中的班次集合；

|R|——R中元素个数；

|H|——H中元素个数，0 ≤ |H|≤ |R|；

i,j——班次序号，i,j=0 表示纯电动公交车驶入车库或驶出车库；

L——线路长度(km)；

D——纯电动公交车在一次充满电且保留安全应急电量情况下，正常载客所能行驶的最大距离(km)；

C1——一辆纯电动公交车1 d 使用成本(元/d)，即一辆车购置成本与使用期内的维修成本均摊到每天的固定成本值；

C2——纯电动公交车每千米空驶成本(元/km)；

C3——纯电动公交车更换一次电池成本(元/次)，包括电池充电费用与操作费用；

T——纯电动公交车从开始使用到退役的服务时间(d)；

Ta——载客行驶完一趟班次所需时间(min)；Tb——始发站发车准备时间(min)；

Tc——公交车更换电池所需时间(min)；

Bi——班次i的发车时间(min)；

si——班次i的发车站点；

ei——班次i的到达站点；

Lei,sj——班次i到达点和班次j发车点之间的行驶里程，若为同一站点Lei,sj=0 ，否则为空驶，Lei,sj=αL，其中，α为同等耗电量下空驶距离与正常载客行驶距离的折算系数，0<α<1；

Tei,sj——班次i到达点和班次j发车点之间的行驶时间，若为同一站点Tei,sj=0 ，否则为空驶，Tei,sj=βTt，其中，β为同等运行里程下空驶时间与正常载客行驶时间的折算系数，0<β<1；

σ——允许误时发车的最大延误时间(min)，将班次延误发车时间限制在合理范围内；

——从车库p出发的车辆h在执行完班次i时，累计行驶里程数，与决策变量有关；

——从车库p出发的车辆h在执行完班次i时剩余电量所能行驶里程数，与变量有关；

——从车库p出发的车辆h在执行完班次i时，需要更换电池，否则为0，与变量有关；

1.3 模型目标函数

以公交车辆总运营成本最小为目标函数，即每天总运营成本(由车辆使用成本Z1，总空驶成本Z2，总换电成本Z3和总误时成本Z4组成)乘以纯电动公交车使用年限T.

(1)车辆使用成本.

车辆使用成本为每天使用车辆数与车辆使用成本之积.

(2)空驶成本.

空驶成本是1 d 车辆总空驶里程与空驶单位距离成本的乘积.

(3)换电成本.

换电成本是1 d 换电总次数与纯电动公交车更换一次电池成本的乘积.

(4)误时成本.

发车误时对公交运营企业造成负面影响，包括乘客放弃乘坐此线路公交，公交企业声誉受损等，将负面影响量化，构建误时成本函数.延误时间tj为公交车执行j班次实际发车时间与时刻表中规定发车时间之差，班次j的误时时间tj为

tj≤0 时，不存在误时，C(tj)=0；tj＞0 时，误时成本C(tj) 随延误时间变化与已有误时成本成正比，设比例为k，即

求解式(6)可得

误时成本C(tj)为

随tj增大，误时成本呈指数增加.表明，k值越大，公交公司越看重误时发车带来的负面影响.

纯电动公交车运营1 d的总误时成本为

1.4 约束条件

式(10)和式(11)表示每个班次有且仅被一辆公交车执行一次；式(12)表示每辆公交车最多从车库驶出一次；式(13)表示从车场出发公交车的班次链；式(14)～式(16)分别表示公交车h在执行完某班次时，累计行驶里程数，剩余电量所能行驶里程数，是否需要更换电池；式(17)表示同一辆公交车执行班次i后执行班次j时，其延误时间不高于允许的最大延误时间σ(σ=0 时，不存在延误发车，为刚性调度模型；σ＞0 时，允许误时发车，为柔性调度模型)；式(18)表示是取值约束.

2 求解算法

纯电动公交车柔性调度为NP-hard问题，采用遗传算法求解，根据模型特征设计算法求解初始种群、适应度函数、交叉和变异操作.

2.1 染色体

染色体编码需包含纯电动公交车的3 部分信息：①执行哪些班次，②执行班次的先后顺序，③所属发车站.为满足上述信息，需构造3条染色体.实际上，公交车先执行班次的时间必定早于后执行班次，故将班次按发车时间先后顺序从小到大排列，使用重新排序的时刻表后，仅需构造2 条染色体包含①③信息即可，极大地缩小了解空间.如图1所示：染色体1为纯电动公交车对应班次基因段，班次1由编号9#的公交车执行，班次114由编号6#的公交车执行；染色体2为公交车所属发车站基因段，编号1#的公交车属于1发车站，编号22#的公交车属于2发车站.

2.2 适值函数

染色体适值函数定义为

式中：Cmax是一个较大正数，保证适应度值非负.适应度值越大，其保留下来的概率越高.

图1 染色体表达方式Fig.1 Chromosome expression

2.3 交叉与变异

选择两点交叉，随机设置两个交叉点对父代染色体进行两两配对，然后对部分基因进行交换得到新染色体，如图2所示.选择换位变异，随机生成两个基因索引值，然后交换两个索引值位置上的基因，如图3所示.

3 实例分析

以上海市金山区莘金专线进行数值分析，如图4 所示，线路为双向运行，上行线路自金山汽车站起，至莘庄地铁南广场站；反之为下行线路.

3.1 基本数据

莘金专线基础数据来自中国公交信息网(http://www.bus-info.cn/)与8684 公交查询网(https://www.8684.cn/).上行线路始发时间为04:35，06:05-06:55 发车间隔为10 min，最后一班车18:30 发车，与上一班车间隔20 min，其他时段发车间隔均为15 min；下行线路始发时间为06:00，06:00-07:00发车间隔为20 min，08:45-09:15 发车间隔为10 min，最后一班车20:00 发车，其他时段发车间隔为15 min.对上行线路始发时间从早至晚依次进行编号，如上行路线04:35 编号为1，04:50 编号为2，18:30编号为57；下行线路始发时间编号接续上行线路编号，并从早至晚进行编号，06:00 编号为58，20:00 编号为114，共114 趟班次.L=52.4 km，Ta=80 min.T=1 825 d，即5年，每辆纯电动公交车购置成本为100万元(车辆售价160万元，政府每辆车补贴60万元)，平均每辆车使用期内的维修成本为20 万元，则C1=657.53 元/d.α=0.80，β=0.80，k=1.20，Tc=5 min，Tb=5 min，σ=5 min，公交车充电电价为0.82 元/(°)，平均耗电率1 (°)/km，则C2=0.66 元/km ；D=220 km ，更换电池的操作费用取10元/次，则C3=180 元[12-13].

图2 交 叉Fig.2 Cross

图3 变 异Fig.3 Variation

图4 莘金专线Fig.4 Shenjin bus line

3.2 结果分析

使用Python 语言编程，选用处理器Inter(R)Core(TM)i5-4200U，内存为4 G 的计算机.遗传算法种群规模为200，交叉概率0.70，变异概率0.02，算法终止条件为最优个体的适应度和群体适应度不再变化.计算得到不同车辆数的总成本值，车辆数为24时总成本最小，收敛图如图5所示，计算结果如表1 所示，最小总成本为3 653.99 万元，1 d 运行中产生25 次空驶，更换电池16 次，延误时间16 min.

图5 收敛图Fig.5 Convergence graph

表1 柔性调度结果Table 1 Flexible scheduling results

表2给出24辆车的执行班次链及每辆车所属发车站，其中，1 代表金山汽车站车库，2 代表莘庄地铁南广场站车库.如编号11的车辆从1始发，依次执行班次15、25 与85 后进行更换电池操作，再依次执行班次43、99与112，返回2.

3.3 柔性调度与刚性调度对比

式(17)的误时上限σ=0 时，模型为刚性调度模型.求得刚性调度车辆数为27辆时总成本最小，计算结果如表3 所示，总成本为3 983.69 万元，在1 d运行中产生29次空驶，更换电池17次.与刚性调度相比，柔性调度节约用车3 veh，总成本减少329.70万元，可见柔性调度优于刚性调度.

表2 柔性调度班次链Table 2 Flexible scheduling trip chain

表3 刚性调度结果Table 3 Inflexible scheduling results

3.4 灵敏度分析

对σ进行灵敏度分析，不同σ值对应的车辆使用数量及总误时如图6 所示. 计算发现，σ＜2 min 时，车辆使用数量不变且几乎不存在误时发车，其调度结果接近于刚性调度结果.

图6 误时上限σ 与最优车辆数及总误时Fig.6 Delay time upper limit σ-optimal number of vehicles and total delay times

如图7 所示，随着σ增大，车辆使用数与总成本整体呈下降趋势.当σ＜4 时，总成本下降速度最快；σ＞4 时，总成本下降速度变慢.表明延误上限取值小于一定阀值时，对运营成本影响较大.

图7 误时上限σ 与总成本Fig.7 Delay time upper limit σ-total cost

4 结 论

本文研究允许误时发车的单线纯电动公交车辆柔性调度优化模型，设计遗传算法求解，并以上海市莘金专线进行数值实验.结果表明，与刚性调度相比，允许误时发车的柔性调度能够减少纯电动公交车辆使用数量及总运营成本，进而提高公交车辆使用效率.此外，当误时上限取值小于2 min时，车辆使用数量不变且几乎不存在误时发车，柔性调度结果接近于刚性调度结果；随误时上限取值增大，车辆使用数与总成本整体呈下降趋势，当误时上限取值少于一定阀值时，对运营成本影响较大.

本文以单条线路为基础研究纯电动公交车辆柔性调度模型，未考虑多线路的区域性纯电动公交车辆柔性调度，将在下一步研究中体现.