熊 杰，白宸宇，李向楠，陈艳艳

(1. 北京工业大学 北京市交通工程重点实验室，北京100124； 2. 民航机场规划设计研究总院有限公司，北京 100101)

0 引 言

纯电动公交能源利用率高、环境污染小，乘坐舒适，在城市交通中发挥着重要的作用。公交调度计划是公共交通运营的重要依据，直接影响到公交企业的运营效率。行车计划的优化是公交调度过程中的核心问题，关系到车辆资源的优化配置和精细化管理。如何对纯电动公交的行车计划进行科学地编制，是亟待研究和解决的问题。

目前，国内外对于公交行车计划编制问题的研究可根据车场数分为两类：单车场与多车场的行车计划编制。B. GAVISH等[1]和R.FRRELING等[2]将单车场行车计划编制问题表述为指派问题，即在满足特定指派要求条件下，给各个车辆派遣车次任务，使指派方案的总行驶费用最低；M. MESQUITA等[3]和A.LOBEL[4]将多车场行车计划编制问题表述为网络流模型，即在网络中找到满足约束条件的多个网络流，使每个节点有唯一一条流经过，和单车场相比，多车场车辆调度问题的约束条件更多，算法求解难度更高。

公交行车计划编制问题常用的求解算法有拉格朗日松弛启发式算法、列生成算法、分枝定价法等。公交调度问题是NP-hard问题，可行解数量巨大，启发式算法是解决该问题的重要方法。例如M.WEN等[5]以减少公交车辆数和降低空驶成本为目标，采用自适应大规模邻域搜索算法(ALNS)对多场站公交调度问题进行了优化分析；H.GERHARD[6]将公交调度问题描述为含有时间窗的混合车辆路径问题，研究了多种公交车型，并通过分支定价算法以及混合启发式算法得出了车队规模最小和旅客出行成本最低的最优解；R.MATTHIAS等[7]建立了以车辆数最少及充电成本最低为目标的优化模型，比较分析了由单一车型以及混合车型组成的车队对总成本的影响，运用整数线性规划方法和遗传算法(GA)求出了最优行车方案；孟越[8]引入了时空网络的概念，对空驶弧进行简化，采用遗传算法对区域内多条公交线路进行优化调度；ZUO Xingquan等[9]在车辆调度过程中采用了改进的多目标遗传算法，为每个目标分配适当的权重以获得能够平衡不同目标的Pareto最优解；ZHANG Jian等[10]建立了等间隔的单车场车辆调度模型，结合实例对智能公交的运营进行优化；TANG Chunyan等[11]在对单线路的车辆调度过程中运用了逆差函数(DF),采取不同措施对个别行程进行调整从而减少所需车辆数。

此外，也有学者在优化车辆行车计划的同时兼顾了时刻表的调整。C. AVISHAI[12]研究了混合车型下的公交时刻表编制方法，均衡考虑了乘客及公交企业的利益；J. OMAR等[13]构建了以乘客换乘效率最高和车辆数最小为目标的模型，对单场站多线路的公交行车计划和时刻表进行协同优化；LIU Tao等[14]运用逆差函数，在不同客流分配下对时刻表及行车计划进行了同步优化，提升了服务的连续性。

综上，国内外学者对公交行车计划编制问题做了大量的研究，取得了丰硕的成果。然而这些研究大多针对常规公交，对于纯电动公交的研究相对较少。笔者以纯电动公交为研究对象，在整车充电模式下，对区域内多条电动公交线路的行车计划进行优化。纯电动公交调度模型的约束条件更多，求解难度更大。在建模上，考虑续驶里程、时间及车次衔接等约束条件，建立了以减少车辆数和空驶成本为目标的模型。在算法求解方面，笔者利用遗传算法对模型求解，有效改善了交叉和变异算子的设计。最后通过实例分析，验证了该模型的有效性。

1 纯电动公交调度模型构建

1.1 问题描述

研究区域内包含一个充电站、若干发车场站与若干条公交线路。车辆可在任意场站与充电站之间空驶以执行不同线路的车次，从而实现公交跨线调度。一套行车计划涵盖了所有车辆在一天内的车次安排，其表示方法是若干条车次链，每条车次链即每辆车在一天内按时间顺序排列的行车计划。

纯电动公交行车计划的优化问题可描述为：给定发车时刻表及其他相关信息，在符合一系列约束条件的前提下，指派各个车辆执行时刻表中的班次，使全部车次都被覆盖，且每个班次任务有唯一车辆执行。

在编制纯电动公交行车计划时，要以区域发车时刻表为基础，将各场站与充电站之间的空驶距离及其他相关信息作为输入数据；并选取合适的调度模型及算法进行求解，最终输出各条车次链。

1.2 模型假设

在问题的模型化过程中，笔者对实际情况做如下说明和假设：

1)场站内的电动公交车为单一车型，车辆不存在延误。

2)在一天的运营周期内，车辆在执行车次期间需及时整车停靠充电，车辆每次充电的时间和电价为定值，且充电桩数量充足。

1.3 目标函数

目标函数包含车辆购置成本Wf和空驶成本Wd。其中，车辆成本为一次性投资，而空驶成本为持续性成本损耗，需将两者按照复利公式转化为年值。目标函数表示为：

(1)

式中：μd为空驶成本的权重系数；μf为车辆成本权重系数；p为资金年回收率；m为车辆使用年限。

车辆购置成本Wf表示为：

(2)

式中：k代表纯电动公交车；i代表车次；N为车次集合；V为车辆集合；uf为单位车辆购置成本；xkoi为0～1变量；o代表场站。

空驶成本Wd包含两类：场站与充电站之间的空驶Wd1与不同场站之间的空驶Wd2。分别表示为：

(3)

(4)

式中：ud为单位里程的空驶成本，其中包含了单位里程空驶所耗费的电量、人力成本以及车辆的折损成本等，为一个固定常数；lc,oi为充电站至车次i发车场站的空驶距离；ldj,c为车次j终到场站至充电站的空驶距离;ldi,oj为车次i终到场站至车次j发车场站的空驶距离；xij为0～1变量。

1.4 约束条件

模型的约束条件分为车次衔接约束、车次时间约束和电量约束3类。

1.4.1 车次衔接约束条件

(5)

(6)

(7)

(8)

式中：xkij和xkoi为0～1变量；式(5)、式(6)表示每个班次均有且仅有一辆车执行；式(7)为车次链的网络连通性约束；式(8)表示从场站发出的车辆在执行完一系列班次后必须返回场站。

1.4.2 车次时间约束条件

(9)

(10)

1.4.3 电量约束条件

Ej≤(ERi-hij)·xij+E0(1-xij),∀i,j∈N

(11)

式中:Ej为车次j消耗的电量；ERi为车辆执行完车次i后的剩余电量；hij为车辆在车次i，j之间的电量消耗；E0为初始电量；Ej、ERi和hij均为百分比电量，三者均在[0,1]之间；式(11)表示车辆在执行车次j前的电量水平应不低于车次j消耗的电量。

2 纯电动公交行车计划优化算法

遗传算法模拟了生物在自然中优胜劣汰适者生存的进化过程，是基于进化论发展起来的一种随机全局优化搜索算法。算法从一个随机初始化的种群出发，经过逐代的选择、交叉和变异等遗传操作，使种群不断进化直到产生最优解。

2.1 编码方式设计

编码方式如下：假设时刻表中一共有n个车次，每条染色体以从1到n的不同排列来表示行车计划，其中插入C表示充电事件(Charge),V表示新增一辆车(Vehicle)。例如染色体 [1 8 V 2 32 C 59 V 3 16…]表示车辆1执行了任务1、8，车辆2依次执行了任务2、32、59，并在执行完车次32之后进行充电，车辆3依次执行了任务3、16。

2.2 初始可行解的生成

在种群初始化之前，要根据车次信息生成一个n×n的0～1矩阵，表示在时间约束上每个车次之后所能连接的车次。在安排每辆车的后续车次时，需考虑以下两个判定条件：

1)上一班次的结束时间+相应的空驶时间<下一班次的开始时间；

2)剩余电量-空驶电量>下一班次消耗电量+返回场站消耗的电量。

若两个条件都满足，可从符合条件的车次集合中随机选择一个车次连在该车辆当前完成的最后一个车次之后；若只满足条件1不满足条件2，可对该车辆充电，若同时符合上一任务的结束时间+空驶时间+充电时间<下一任务开始时间，可给该车辆继续安排车次；若两个条件均不满足，则需要新增车辆。

初始可行解生成的算法流程如表1。

表1 初始可行解的生成算法

2.3 适应度函数的设计

遗传算法依据个体的适应度高低进行搜索。个体目标函数值越小，代表该个体的适应度越高，被选择的概率越大。可将目标函数的倒数作为适应度函数。

求解目标函数时，染色体中所含V的个数代表车辆数，再乘以单位车辆成本即可得到车辆成本；将染色体中每两个相邻车次之间的空驶距离从头至尾累加求出总空驶里程，再乘以单位里程的成本可得出总空驶成本。两项成本之和为目标函数W。适应度函数f(i)表示为:

(12)

2.4 遗传操作

2.4.1 选择

选择是指从种群中选择优质个体作为繁殖后代的父代的过程。选择操作常见的方法有轮盘赌法、随机遍历抽样法、无放回随机选择等。笔者采用了轮盘赌法。

在选择之前，需确定种群规模Nind和代沟GGAP。代沟指每代种群中有Nind×(1-GGAP)个父代直接进入下一代种群，即在选择中加入了精英保留策略，将适应度最高的个体保留了下来。

每个个体被选择的概率p(i)表示为：

(13)

选择策略如下：

Step1:每转一次轮盘会产生一个在[0,1]之间服从均匀分布的随机数;

Step2:在种群中遍历搜索，直至选中p(i)大于该随机数的个体，该个体落入选择区间，本次转轮盘结束;

Step3:继续下一次转轮盘，直到选出Nind×GGAP个染色体。

2.4.2 交 叉

交叉模拟了生物在进化过程中的基因重组，指按照一定的概率从父代种群中随机选择染色体，以某种方式交换染色体的部分基因从而产生新个体的过程。交叉是遗传算法的核心内容，提高了算法的全局搜索能力。

在交叉过程中，包含了两个主要操作：重复车次的删除以及未涵盖车次的重新插入。在车次的重新插入过程中，以染色体中的V和C为节点，将其划分为若干个区块(block)，每个区块都代表着一个满足电量要求、期间不需充电的车次序列。

对于每一个待插入的车次，经最初计算和筛选后，有若干个符合时间和续航里程约束的区块可作为备选方案。笔者随后采用了模糊综合评价方法对这些备选方案进行了综合评价，最终决策产生一个最佳方案。需要考虑的决策指标分别为：①车次插入区块之后的总电量消耗；②车次插入区块之后产生的空驶里程；③待插入车次与block中车次的时间间隔。

该3项指标均为负指标，且分别占有不同的权重。通过计算每个方案的加权相对偏差距离，可得出一个最优方案。

对车次的重新插入的过程如表2。

表2 交叉算子中的重新插入算法

交叉的整体策略如下：

Step1:从种群中随机选取两个染色体作为父代；

Step2:任选一条车次链作为交叉点，父代1与父代2在交叉点的基因序列分别记为cross1和cross2；

Step3:将父代1中所含的交叉基因cross1与cross2中的车次序号删去；

Step4:将cross2插入父代1的交叉点位置；

Step5:将cross1中的每个车次重新插入到父代1中，得到一个新的子代；

Step6:以同样的步骤对父代2进行交叉。

交叉算子的具体过程如表3。

表3 交叉算子

2.4.3 变 异

变异模拟了生物在遗传进化中的基因突变过程，是生成新个体的辅助方法，提高了遗传算法的局部搜索能力。变异策略如下：

Step1:生成一个在[0,1]之间服从均匀分布的随机数，若该数小于变异概率，则进行变异，否则继续下一次循环;

Step2:随机选取一个染色体作为变异对象，任选一条车次链作为变异的基因片段;

Step3:将变异基因从染色体中删去;

Step4:将染色体划分为若干个区块(block);

Step5:在符合时间和电量约束的前提下，采用模糊综合评价方法进行比较后，将变异基因中包含的车次逐个重新插入到某一个区块中；

Step6:更新每个区块的开始、结束时间；

Step7:按照时间的先后顺序，连接若干个区块，得到一条新染色体。

2.5 终止原则设计

经过选择、交叉和变异后产生的新种群又重新开始了下一代的遗传操作，直至达到最大的迭代次数，算法流程结束。在设计终止原则时，算法迭代次数一般在100～500之间取值。在整个进化过程中，种群规模不变，群体性能经过若干代进化后逐渐趋于最佳，最终得到的种群即为最优群体。

3 实例分析

3.1 实验参数

以在北京鲁谷场站充电的472路、473路和79路3条线路作为研究对象。472路、473路的发车场站在鲁谷场站，79路的发车场站在廖公庄站。3条线路全天共352个车次，车辆续驶里程为60 km，每次充电时间为30 min。在当前方案下，车辆未实行跨线调度，3条线路共使用86辆车，线路基本信息如表4。

表4 线路基本信息

运用MATLAB求解时，为方便计算及算法操作，充电事件C和新增车辆V需用不同于车次序号(1～352)的数字来赋值。笔者令V=0，C=0.1。各场站间的空驶距离如表5。

表5 各场站间的空驶距离

实验运行的相关参数设置如表6。

表6 实验参数

3.2 结果分析

利用遗传算法对3条线路全天352个车次的行车计划进行优化求解，使用MATLAB2016a在Win10环境中运行，得到了目标函数值的迭代曲线如图1。

优化结果中，车队规模为70辆。每辆车在执行完当天一系列车次后，最终返回场站进行充电。经过优化后的车辆行车计划可表示为如下车次链(部分)：

车辆1:车次1→60→134→充电→186→211→298→充电

车辆2:车次2→101→189→227→充电

车辆3: 车次3→84→160→221→充电

车辆4: 车次4→58→110→充电→153→238→276→303→充电

车辆5: 车次5→29→138→263→充电

车辆6: 车次6→217→348→充电

车辆7: 车次7→175→213→291→充电

车辆8: 车次8→94→充电→130→158→194→243→317→充电

……

……

车辆65: 车次83→128→177→充电→226→284→325→充电

车辆66: 车次86→133→165→202→充电→247→296→335→充电

车辆67: 车次90→167→203→充电

车辆68: 车次102→131→241→充电

车辆69: 车次106→155→192→250→充电

车辆70: 车次141→174→228→271→充电

将经过算法优化后的结果与现状进行对比如表7，投入使用的公交车由原先的86辆降为70辆，空驶成本也降低了。表明对车辆实行区域跨线优化调度，可以使行车安排更加合理，车辆资源得到更好的利用。运营总成本由16 325万元降至14 312万元，降幅约12%，提高了公交企业的运营效率。

表7 优化结果与现状的对比

4 结 语

笔者结合纯电动公交车的特性，将纯电动公交行车计划编制问题转化成了增加续驶里程和充电时间等约束的常规公交调度问题，对多场站多线路的电动公交车辆实施区域跨线调度。在运用遗传算法求解的过程中有所创新，采用独特的混合整数编码方式对行车计划进行描述，并引入了区块的概念，在区块的层面上来实施交叉和变异等遗传操作，且在交叉决策过程中采用了模糊综合评价方法，提高了该复杂优化问题的解决效率和交叉算法的科学性。最后对472路、473路和79路3条公交线路进行案例分析，算法优化结果相比现有行车方案减少了16辆车，总成本降低了约12%。证明笔者构建的模型及算法可有效解决公交行车计划编制问题，对纯电动公交的优化调度具有重要的现实意义和指导作用。