近年来，电动车辆由于具有噪音小和零排放的特点而在公共交通中广泛采用[1]．公交车辆调度对于节约运营成本和保证服务质量具有重要意义．电动公交车辆调度具有续驶里程、充电时间等约束，比传统燃油车辆调度更为复杂[2-3]．公交车辆调度是NP难题[4]，求解方法包括精确方法和启发式方法[5-6]．精确方法能获得问题的最优解，但当求解大规模问题时计算时间过长，启发式方法可在合理时间内得到满意解．邻域搜索是解决公交车辆调度问题的常用启发式方法，其关键是如何产生邻域解．删除-插入和交换[7-10]是两种常用的邻域解产生算子．删除-插入算子随机删除当前调度解中的某些行程，再将这些行程随机插入到其他车辆块中，来产生当前解的邻域解．交换算子随机交换任选的两个车辆块中的两个行程．删除-插入和交换算子具有随机性，无法保证邻域解的质量．文献[9]设计了一种插入操作，该操作插入不同的行程到不同的车辆块中，然后评价产生的邻域解来选取较好邻域解．这种插入操作需要大量的评价计算，导致算法计算时间较长．文献[6]设计了块移动操作来插入和删除若干连续的行程．某些连续的行程适合被同一车辆执行，而该操作保证了这些行程被同一车辆执行，提高了搜索效率．文献[10]中，若一个车辆的所有行程都可插入到其他车辆块中，则删除该车辆，从而减少车辆数目．文献[11]针对多车场车辆调度问题设计了5种邻域搜索算子，分别是插入-删除、交换、块移动、两元素优化和转换车辆．当前，已有较多传统燃油公交车辆调度的研究，但电动公交车辆调度的研究还较少[12]．文化基因算法是一种结合进化算法与局部搜索的优化算法，既具有进化算法的全局搜索能力，又具有较强局部搜索能力．本研究提出一种基于文化基因算法的电动公交车辆调度方法(memetic algorithm based electric bus scheduling approach，MAEBS)．首先，设计了初始个体生成算法用来构造初始群体；然后，设计了一种针对公交车辆调度问题的交叉操作用于全局搜索．改进和设计了3种邻域搜索算子，将其与已有的删除-插入、交换算子和块移动算子[6]构成6个邻域搜索算子用于邻域搜索．1 电动公交车辆调度方法一条公交线路通常包括两个控制点(control point，CP)，即主站和副站，分别用CP1和CP2表示．每个控制点有一个发车时刻表．一辆车从一个CP行驶到另一个CP称为一个行程，所花费的时间为单行程驾驶时长．每辆车一天的行车计划由多个行程组成，称为车辆块．若车辆的剩余电量不足以完成剩余的行程，则须充电．公交车辆分为长班车、短班车和高峰车三种类型．短班车需一个司机完成；长班车需两个司机完成，其工作时间是短班车的两倍；高峰车和短班车的工作时间相同，在车辆块中存在一段较长的时间间隔．电动公交车辆调度问题为：已知发车时刻表，安排车辆完成发车时刻表中的行车计划，使时刻表中每个发车时刻点都被唯一的车辆行程所覆盖．1.1　调度流程基于文化基因算法[13-14]的电动公交车辆调度方法流程如图1所示．首先，构造一个初始种群；然后，从种群中随机选取两个个体S1和S2进行交叉操作，生成新个体Snew；最后，对新个体Snew施加邻域搜索以更新Snew．若种群中不存在和Snew相同的个体，且Snew优于种群中的最差个体，则用Snew替换种群中的最差个体，形成下一代种群．重复以上步骤，直至达到给定的最大世代数Gmax．DOI：10.13245/j.hust.220102.F001图1基于文化基因算法的电动公交车辆调度流程1.2　评价函数设计的评价函数中，每个车辆块j对应一个评价函数Fj，有Fj=∑i=16ωiCij，式中：ωi为权重系数；C1j为车辆块j的固定成本；C2j为车辆块j中行程数目与标准行程数目的差值，避免由于过短车辆块导致的车辆利用率低；C3j为车辆块j中的空驶次数；C4j为车辆块j的工作时间和标准工作时间的差值；C5j为车辆块j中的长时间间隔的数目；C6j为车辆块j中与预设的最小充电次数的差值．合成所有车辆块的评价函数，得到整个调度解的评价函数F，有F=ω0M+Fj，式中：ω0为对应的权重系数；M为车辆调度方案中未覆盖的时刻点数目．1.3　生成初始种群设计两种初始个体产生算法，各生成初始种群中的一半个体，以保持种群的多样性．算法1 第1种初始解产生算法步骤1 初始化．发车时刻表中每个发车时刻点对应一个行程，所有行程的集合为Ta；令初始解S=∅；初始解中的车辆块数目nb=0．步骤2 产生一个新车辆块．产生一个新的空车辆块Bt=∅，从Ta中随机选取一个发车时刻小于该车辆第一个行程的最晚发车时间(tlast)的Tt作为该车辆块的第一个行程，令Bt=Bt∪{Tt}，令该车辆块中的行程数量nt=1．步骤3 向车辆块中添加行程．令tb为车辆块Bt中的最后一个行程的结束时间，trelax为司机的最小休息时间，twait为司机休息后车辆的最长等待时间．从集合Ta中随机选取出一个发时间位于(tb+trelax，tb+trelax+twait)区间的行程Tt，加入到Bt中，即Bt=Bt∪{Tt}．令nt= nt+1，转到步骤3．若集合Ta中没有行程在区间(tb+trelax，tb+trelax+twait)中，或nt等于一种类型车辆块中允许的最多行程数目，则转到步骤4．步骤4 车辆块加入到解中．令S=S∪{Bt}，nb=nb+1．步骤5 算法终止．若nb等于允许产生的最大车辆块数目，则该算法停止；否则，转到步骤2．算法2 第2种初始解产生算法步骤1 初始化．所有行程的集合为Ta；令初始解S=∅；初始解中的车辆块数目nb=0．步骤2 产生一个新车辆块．产生一个新的空车辆块Bt=∅，从Ta中随机选取一个发车时刻小于tlast的Tt作为该车辆块的第一个行程，令Bt=Bt∪{Tt}，Ta=Ta\{Tt}，\为集合相减，令该车辆块中的行程数量nt=1．步骤3 判断是否向车辆块中加入行程．若nt等于一种类型车辆块中允许的最多行程数目或者Ta中没有发车时间晚于(tb+trelax)的行程，则转到步骤5；否则，令nle=1，转到步骤4．步骤4 向车辆块中添加行程．若集合Ta中存在发车时间位于区间(tb+trelax，tb+trelax+nletwait)内的行程，则从中随机选取一个行程Tt，令Bt=Bt∪{Tt}，Ta=Ta\{Tt}，nt=nt+1，转到步骤3；否则，令nle=nle+1，转到步骤5．步骤5 将车辆块加入到解中．令S=S∪{Bt}，nb=nb+1．步骤6 算法终止．若Ta中没有发车时间小于tlast的行程，则算法停止；否则，转到步骤2．1.4　交叉操作不同于传统交叉操作，本研究设计了基于车辆块选取的交叉操作：对于两个个体S1和S2，由这两个个体中所有的车辆块构成一个车辆块集合Ba；然后，从Ba中选取若干车辆块构成新个体Snew，作为交叉操作产生的个体．交叉操作见算法3．算法的每次迭代向Snew中加入一个车辆块．希望该车辆块覆盖那些未被覆盖的时刻点，同时不会引起重复覆盖．为此，设计了一个冲突值nc=u1-u2，以评估加入一个车辆块引起的冲突，其中：u1为该车辆块中包含的已存在于Snew中的行程的数目；u2为该车辆块中包含的不存在于Snew中的行程的数目．u2越大表示加入该车辆块可覆盖越多的时刻点，因此nc越小越好．每次向Snew中加入车辆块时，从Ba中选取nc最小的车辆块加入．算法3 交叉操作步骤1 随机从种群中选取两个个体S1和S2，由S1和S2中的所有车辆块构成集合Ba，令交叉产生的新个体Snew=∅．步骤2 加入新车辆块．遍历集合Ba，选择nc最小的车辆块Bt，S=S∪{Bt},Ba=Ba\{Bt}．步骤3 算法终止．若Ba中存在Bt，nc小于0，则转到步骤2；否则交叉操作终止．1.5　修复操作初始个体产生算法和交叉操作可能产生具有重复覆盖和未覆盖发车时刻点的个体．为此，设计了修复操作，使得个体不包含重复覆盖和未覆盖的发车时刻点．修复操作包括删除和插入行程操作．首先，执行删除行程操作，即遍历个体中所有的车辆块包含的行程，若某个行程同时存在于多个车辆块中，则将该行程保留于一个随机选择的车辆块中，而将该行程从其他所有车辆块中删除．然后，提出一种组合三种插入操作的方法，依次将未覆盖的时刻点对应的行程插入到个体中．第一种为随机插入操作[7]，即从待插入的行程集合中随机选取一个行程，将该行程插入到一个随机选择的车辆块中．第二种为行程最优位置插入操作，即从待插入的行程集合中随机选取一个行程，然后遍历当前解中所有的车辆块，把该行程插入到某一车辆块，使得解的改善程度最大．第三种为文献[9]中的插入操作，即分别计算待插入的行程集合中每个行程插入到不同车辆块后对解的影响，然后选取某一行程插入到某一车辆块中，使得插入后对其他行程插入的影响最小．这种组合插入操作的方法每次向个体中插入一个行程，通过计算个体中未被覆盖的时刻点与所有时刻点数目的比值来确定采用哪种插入操作：当比值大于20%时，采取第一种插入操作；当比值小于5%时，采取第三种插入操作；当比值在5%~20%之间时，采用第二种插入操作．通过这种方式兼顾计算效率和解的质量．1.6　邻域搜索邻域搜索过程见算法4，包括以下6个邻域搜索算子．N1(删除-插入算子)：随机选取若干车辆块中的若干行程予以删除，然后用1.5节的插入方法再将这些行程插入到车辆块中．N2(交换算子)：随机选取两个车辆块，然后从中各随机选取一个行程进行交换．N3(块移动算子)：采用文献[6]提出的块移动方法，即选取某个车辆块中若干连续行程予以删除，再将其插入到其他车辆块中．N4(删除空驶算子)：遍历所有车辆块，若车辆块中存在空驶行程，则用插入方法将空驶行程之前或之后的任一行程插入到其他车辆块中，以消除空驶行程．N5(拆分-合并算子)：对于充电时间过短的长班车，将其拆分为两个短班车；然后再选取若干长班车进行拆分；最后，合并拆分后的短班车，形成具有合理充电时间的长班车．N6(删除车辆块算子)：删除评价函数值最低的车辆块，再用插入方法将该车辆块中所有的行程插入到其他车辆块中．采用多个邻域搜索算子用于提高搜索过程中解的多样性，以提升全局搜索能力．算法4 邻域搜索步骤1 假设对解S施加邻域搜索，令当前最好解S*=S；当前解S'=S．令邻域搜索算子集合Na={N1,N2,N3,N4,N5,N6}．步骤2 选择邻域搜索算子．从Na中随机选取一个邻域搜索算子Ni施加于S'，得到S''．若F(S'')F(S*)，则令Na={N1,N2,N3,N4,N5,N6}；否则令Na=Na/{Ni}．步骤3 更新最好解和当前解．若F(S'')F(S*)，则S*=S''．若F(S'')(1+r)F(S*)，则令S'=S''；否则令S'=S*．其中r为比例系数，是(0，1)内的实数．步骤4 算法终止．若Na=∅，则算法停止，输出解S*；否则，转到步骤2．1.7　充电操作电动公交车辆续航里程有限，在一天的驾驶中须中途充电．对于邻域搜索算子产生的邻域解，通过在其中插入充电时间块的方式来确定电动车辆的充电时间．假设车辆电池的总容量为Vmax，允许的最低电量为Vmin，车辆执行第i个行程后的剩余电量为Vi．车辆完成车辆块中的所有行程所需电量为D0．车辆执行第i个行程后，完成剩余行程所需电量为Di，由剩余行程驾驶时长和充电速率的乘积确定．第i个行程间隔的可充电量为Ri，由行程间隔时长和充电速率的乘积确定．第i个行程后的间隔内的充电量为min(Vmax-Vi,Ri,Di)．每台车辆的最小充电次数为nr，nr=D0Vmax-Vmin-1．设计以下充电策略．从一个车辆块nt-1个行程间隔中选取nr个行程间隔用于充电．若能保证每个行程执行后的剩余电量不小于Vmin，则按这种方式充电；否则，再选取其他nr个行程间隔用于充电．若找不到nr个行程间隔满足充电要求，则令nr=nr+1，重新寻找nr个行程间隔用于充电．若还找不到nr个行程间隔满足充电要求，则给评价函数中C6j一个较大值作为惩罚，以引导算法搜索能满足充电要求的车辆块．2 实验结果将MAEBS用于某市三条实际公交线路，即60路、K1路和803路，并与人工调度结果比较．用C++实现MAEBS，运行在带有2.30 GHz CPU，8GiB RAM的PC机上．2.1　问题实例这三条公交线路各有一个主站和一个副站，即CP1和CP2．60线路中，CP1和CP2的发车时刻表中最早和最晚发车时刻分别为6:00和21:00，共有120个发车时刻点．K1线路中，CP1的发车时间范围为5:40—21:30，CP2的发车时间范围为5:40—21:00，共有196个发车时刻点．803线路中，CP1的发车时间范围为5:20—21:40，CP2的发车时间范围为5:50—22:00，共有158个发车时刻点．每个司机的最长驾驶时间为6.5 h，最长工作时间为8 h，行程间的最小休息时间为2 min．车辆电池的总容量Vmax=133.79 kW·h，允许最低电量Vmin=40.14 kW·h．车辆单位时间耗电速率Eu=15.6 kW/h，单位时间充电速率Ec=30 kW/h．2.2　算法参数种群规模取为20，算法在40世代已收敛，因此最大世代数Gmax取为40．邻域搜索中，用于接受较差解的比例系数r在[0.2，0.3]均可得到较好结果，此处设置r=0.2．评价函数中各惩罚系数根据经验给定，系数ω0=500，ω1=200，ω2=50，ω3=100，ω4=50，ω5=100，ω6=200．2.3　比较结果将MAEBS生成的车辆调度方案和人工调度方案进行对比．人工调度方案中存在较多未覆盖的时刻点．为了与人工调度方案进行合理比较，人工调度方案中，若车辆的发车时间和发车时刻表中的发车时刻点间相差不超过3 min，则认为该发车时刻点被覆盖．对于每条路线，MAEBS运行30次．MAEBS调度方案与人工调度方案对比见表1．由表1可看出：MAEBS得到的车辆调度方案中不存在未覆盖的时刻点；对于60路、803路和K1路，MAEBS得到的车辆调度方案比人工调度方案平均分别减少1.4辆车、5.7辆车和7.2辆车．MAEBS的计算效率高，可在15 s内得到高质量的调度方案．DOI：10.13245/j.hust.220102.T001表1MAEBS调度方案与人工调度方案对比线路编号MAEBS人工平均未覆盖时刻点数平均车辆数平均运行时间/s未覆盖时刻点数车辆数60路012.67.2014803路015.39.82521K1路027.814.23435图2为MAEBS生成的60路的一个车辆调度方案的甘特图．其中：灰色矩形表示充电；绿色、蓝色和粉色矩形分别表示短班车、长班车和高峰车的行程；行程间的空白表示休息时间．纵坐标车辆1~12均从主站发车．右侧为每个车辆块的利用率，其计算公式为：利用率=车辆的驾驶时长/13 h．DOI：10.13245/j.hust.220102.F002图2MAEBS产生的60路车辆调度方案的甘特图人工调度方案采用车辆随到随充的方式，这种充电方式会造成频繁充电，损耗电池寿命．MAEBS生成的车辆调度方案中，每辆车充电1~2次，避免了车辆频繁充电．此外，MAEBS得到的充电安排可保证电池在最小电量前充电，避免了过度放电，可提高电池使用寿命．MAEBS产生的车辆调度方案中的车辆利用率普遍大于人工调度方案中的车辆利用率．这意味着MAEBS生成的车辆调度方案中，一台车辆可执行更多行程，因此所用车辆数更少．MAEBS采用了6个邻域搜索算子，其中N1~N3是已有邻域搜索算子，N4~N6为提出或改进的算子．为了验证N4~N6的有效性，让MAEBS的邻域搜索仅使用N1~N3算子，构造方法MAEBS-3．将MAEBS和MAEBS-3各运行30次，结果见表2．DOI：10.13245/j.hust.220102.T002表2MAEBS与MAEBS-3运行结果对比线路编号MAEBSMAEBS-3平均评价函数值平均车辆数平均空驶次数平均运行时间/s平均评价函数值平均车辆数平均空驶次数平均运行时间/s60路3 281.312.70.007.24 717.018.10.14.5803路4 134.015.30.069.85 794.720.80.97.2K1路6 696.327.80.1014.28 612.731.02.310.8由表2可见：相比MAEBS-3，MAEBS得到的平均评价函数值更小，车辆调度方案中的平均车辆数明显更少，空驶数目也有所降低．这说明N4~N6邻域搜索算子能有效减少车辆数和空驶次数，提升解的质量．3 结语提出一种基于文化基因算法的电动公交车辆调度方法(MAEBS)．设计了两种初始个体生成算法用来构造初始种群．提出一种交叉操作用于全局搜索，并设计和改进了3种邻域搜索算子与已有3种搜索算子一同进行邻域搜索．设计一种基于车辆块的评价函数，用于引导邻域搜索算子进行邻域搜索．将MAEBS用于某市三条实际的公交线路，并与人工调度方案对比．实验结果表明：MAEBS能够生成覆盖所有发车时刻点的调度解，解中不存在重复覆盖和未覆盖的发车时刻点，在所用车辆数和发车时刻点覆盖率方面明显优于人工调度方案．