基于超级时空网络的公交车辆调度模型及3M进化算法.pdf

Sep.,2023Vol.27No.3Operations Research Transactions2023年9 月第2 7 卷第3期运筹学学报DOI:10.15960/ki.issn.1007-6093.2023.03.005基于超级时空网络的公4车辆调度模型及3M进化算法何胜学1,t摘要，针对在时刻表给定条件下如何减少空驶车次和实现具有工作时间公平性的公交车辆调度问题，建立了基于超级时空网络的模型，并设计了一种具有混生、变异和成长三种基本操作的进化求解算法。首先利用超级网络理念，将出场弧、入场弧、接续、实际车次和空驶车次在时空上整合为一个连通的有向超级时空网络。基于超级网络中流量守恒概念，建立了公交车辆调度模型，并通过合理转化将工作时间公平性约束变为具有简单加和特征的目标函数项。利用可行车次覆盖集合的拓扑结构特征，设计了将多个可行解混合后生成新解的混生算子；通过搜索具有回路特征的接续，实现对可行解构成元素的变异操作；通过构建指派网络、计算指派网络中联接的费用，并利用匈牙利算法求解对应指派问题，实现对可行解的成长操作。以上述操作为基础提出了一种新的“3M”进化算法。通过实证分析，验证了模型的合理性与算法的有效性。研究发现：减少空驶车次与平衡车次链之间的实际车次运行时间之间存在相互制约的矛盾，但是与所需的公交车总数不存在必然联系。关键词公共交通，车辆调度，超级网络，智能优化，自适应中图分类号U491，T P39 12010数学分类号90 B06,90B20,90C10Transit vehicle scheduling model and 3M evolutionaryalgorithm based on super spatiotemporal network*HEShengxuel.tAbstractIn order to reduce the number of deadheading trips and realize theequality of working hours with the given bus timetable,this paper formulated a superspatiotemporal based transit vehicle scheduling model and designed an evolutionary algo-rithm including mixed creation,mutation and mature operators.Firstly,this study usedthe super-network conception to combine pulling out arcs,pulling in arcs,connectors,ac-tual trips and deadheading trips into a super spatiotemporal network.Based on the fowconservation conception in the super-network,this study built a vehicle scheduling modeland transformed the constraint of working time equality into an addable item of objec-tive.In view of the topological feature of the set of trip coverings,this paper designed amixed creation operator to generate new solution with several known feasible solutions.By searching the connectors with loop feature,this paper realized the mutation operatorto the elements of feasible solution.The mature operator consists of formulating an as-signment network,computing the cost of links in the assignment network,and obtainingthe optimal match by Hungarian algorithm.Based on the above three operators,thispaper proposed a new“3M evolutionary algorithm.The numerical analysis verified the收稿日期：2 0 2 1-0 3-10*基金项目：国家自然科学基金(Nos.71801153，7 18 7 1144)，上海市自然科学基金(No.18ZR1426200)1.上海理工大学管理学院，上海2 0 0 0 93;Business School，U n i v e r s i t y o f Sh a n g h a i f o r Sc i e n c e a n dTechnology,Shanghai200093,China+通信作者E-mail:C69基于超级时空网络的公交车辆调度模型及3M进化算法3期rationality of the new model and the effectiveness of the new algorithm.This researchdiscovers that there is a mutual restriction relationship between reducing deadheadingtrips and equalizing the actual trip times among trip chains,but the both have no obviousconnection with the fleet size.Keywords public transportation,vehicle scheduling,super-network,intelligent op-timization,self-adaptationhinese Library ClassificationU491,TP3912010 Mathematics Subject Classification 90B06,90B20,90C10公交车辆调度问题是公交运营管理的核心问题之一。当公交时刻表确定以后，如何安排车辆运行与时刻表对应的所有车次就成了公交运营必须解决的首要问题。合理的车辆调度体现在完成所有车次的公交车数目合理、无载客的车辆空驶时间最小化和车辆或乘务组公平合理的工作安排。尽管研究者对于公交调度已进行了大量研究，但是由于该问题本身较大的规模和问题约束的复杂性，使得构建具有较强解释性的优化模型和设计有效的求解方法成为研究的难点。本文尝试从超级时空网络的角度对该问题加以分析，利用网络元素与元素间的关联关系梳理公交调度问题所涉及的各种对象及关系，从而构建具有较强解释性的优化模型。同时基于超级网络，分析问题可行解的拓扑表现，从而设计出更具实效的模型求解方法。公交车辆调度问题一直是公交优化邻域的一个研究热点。下面从一般化公交车辆调度、电动公交车调度、半自动和无人驾驶公交调度以及车辆与乘务组合调度四个方面对当前的国内外相关研究作简述。在一般化公交车辆调度研究方面，针对交通拥堵等随机因素对车辆运行计划的影响，文献 1 提出了一个三阶段解决方法。首先在拥挤发生后生成车辆备选集的集合；然后基于上述集合利用遗传算法生成无占优的车辆运行计划；最后通过调整车辆发车时间进一步优化结果。针对给定的乘车需求的降低，文献 2 建立相应的线性优化模型在多种车辆条件下确定最小的车辆数，并给出求解模型的对应列生成算法。在假设司机开始工作时间无限制和休息时间不固定条件下，文献 3 建立了公交车辆和乘务调度的量和混合整数规划模型，并给出了一种求解模型的邻域搜索算法。在多车场条件下，文献 4 提出通过微调部分车辆的发车时间进一步提升公交车辆的利用率。该文给出了两阶段启发式方法，即首先生成车辆运行方案，然后针对上述运行方案调节时刻表中部分车辆发车时间。文献 5 在多车场条件下比较了数种启发式车辆调度方法，并给出了一种修复不可行解的方法。与传统的基于车场的问题分解不同，文献 6 提出在利用列生成算法求解多车场车辆调度问题时改用基于车次的分解方法，从而提高算法的效率。为了减少由于时刻表制定与车辆调度分开决策而可能增加的车辆需求，文献 7 建立了将两者统一决策的优化模型，并给出了一种启发式求解算法。基于实时乘客需求信息，文献 8 提出利用跳站策略在减少乘客等车时间和车辆数目条件下协同决策自动驾驶班车的时刻表和车辆的调度，并在单车场具有上下行的环线条件下对其方法进行了验证。以班次时间接续、乘务组劳动强度、车场能力等为约束条件，以最小化乘务组的车场驶入与驶出成本、停留等待成本和空驶成本为目标函数，文献 9 建立了多车场公交乘务排班问题的数学模型，并给出了求解模型的改进的禁忌搜索算法。针对一般性的车辆路径问题，文献 10 提出通过交换两条已定车辆路线来恢复和处理多车场条件下的两类扰动，即车辆的延误和额外增加的任务。近年来一些研究者也针对电动公交车调度进行了深入研究。文献 11 从最小化电动公交车数目和最小化充电器数目两个角度分析了电动公交车辆的调度问题，主要考虑的电7027卷何胜学动公交的行驶里程和充电需求约束。在给定多种车辆运行时刻表条件下，考虑电动公交车的行驶距离和充电需求约束，文献 12 建立了相应的优化模型，给出了搜索最优解的启发式方法。考虑电动公交车在一定容量约束下需要馈线充电，文献 13 设计了一种改进的双中心粒子群算法对电动公交车充电进行优化调度，从而可以获得最大的电动公交车运营数量。以公交车辆运营总成本最小为目标，文献 14 构建允许存在误时发车的纯电动公交车辆柔性调度优化模型。通过最大可能地增加一辆公交车可执行班次的数量，减少车辆使用数量及运营成本，文献 14 的研究表明：与纯电动公交车辆刚性调度相比，柔性调度能够极大地减少车辆使用数量。在半自动和自动驾驶公交车调度方面，在考虑到需求的变化条件下，文献 15 提出了模块化拼接自动驾驶公交车辆的柔性调度策略。建立了提高车辆利用率和服务水平的双目标优化模型。以车辆运营成本和乘客候车时间成本之和为目标，以车辆编组大小和发车时刻为决策变量，文献 16 建立半自动驾驶公交车辆调度优化模型。该研究的实证分析表明：与传统人工驾驶公交的车辆调度相比，基于半自动驾驶公交的车辆调度能有效降低车辆运营成本和乘客的候车时间。文献 17 提出利用驻车和调速两种方式实施调整无人驾驶公交车的行车计划，从而满足实时变化的公交需求。文献 17 利用仿真验证了其方法的可行性。文献 18 从实证角度分析了无人驾驶公交对公交车辆调度系统的影响，比较了有人驾驶与无人驾驶条件下系统的各项成本与资源的利用情况。超级网络理论的基本思路是利用虚拟节点和路段描述研究对象所包含的各种抽象关系，形成一个网络拓扑结构，随后在网络中解释系统的运行规则，最后利用图论和各种优化技术解决相关问题。作为一种有效的研究方法，超级网络很早就被应用在交通分配研究的交通方式选择建模 19,2 0 。后来通过对相关理论进行了总结，研究者将该方法应用于交通行为分析、交通方式整合、供应链物流优化、金融网络优化、在线广告定价分析和无人机巡视路线优化等众多领域 2 1-2 5。超级时空网络是将超级网络与时空网络结合，利用超级网络理论来处理具有时空特征的研究问题 2 4。与研究目标相关，目前处理超级网络的理论方法主要包括：各种图论方法、变分不等式、投影动态系统和非线性规划理论等 19-2 5。就作者所知，尽管在车辆调度问题处理中常会利用网络的拓扑特征对问题加以描述，但很少有研究者明确相关的超级网络概念，并利用它对问题加以深入分析。与现有研究相比，本文具有如下特色：a）从超级时空网络的角度对公交车辆调度问题进行网络拓扑刻画和模型构建，拓展相关研究的分析和解释视角；b）通过建立类似随机变量方差形式的目标项来替代常见的工作时长约束和工作时间公平性约束，从而大幅降低模型求解的难度；c）基于超级时空网络，结合可行车次链在网络中的拓扑特征，设计了具有混生、变异和成长三个基本操作的群体型新进化算法。1超级时空网络构建1.1参变量介绍下面简单介绍建模所需的基本参变量。相关的集合包括：D为车场集合；S为所有发车站点的集合；P为所有车次的集合：V表示所有公交车辆的集合；C表示接续集合；PO为所有出场弧构成的集合；PI为入场弧集合。相关的上下标参量包括：dED表示一个车场；sES表示公交线路的发车站点；pEP表示一个车次；V表示一辆公交车；（p,q）EC表示联接车次p与q的一个可行接71基于超级时空网络的公交车辆调度模型及3M进化算法3期续；（d,p）EPO 表示联接车场d与车次p的车辆出场弧；（p,d）EPI表示联接车次p与车场d的车辆入场弧。相关的主要变量有三个。其中，(p）E(0,1)为接续是否被利用的指示变量，当车辆利用接续(p,)时，其值为1；否则，为0。Lu.(d.g）(0,1)为出场弧是否被利用的指示变量，当车辆利用出场弧(d,g)时，其值为1；否则，为0。w.(p,a)）E（0,1)为入场弧是否被利用的指示变量，当车辆利用入场弧(p,d)时，其值为1；否则，为0。除了上述集合、上下标和变量，下面简单介绍建模需要的主要参数。tp,start为车次p从其始发站sp,start发车的时间。tp,end为车次p到达其终点站sp,end的时间。tp表示车次p的跨越时长，其值等于tp,end-tpstart。t(p,g)）表示接续(p,g)的跨越时长，其值等于tg.start二tpend。0,T】表示线路运行的时间段，0 和T分别为运行时段的始末时间。tdstart 表示可以从车场d发车的最早时间，一般情况假设其值等于0。td,end表示车辆最晚可以进入车场d的到达时间，一般情况下假设其值等于T。t(d,g）表示出场弧(d,q）的跨越时长，其值等于tastart一tdstart。t(p,a)）表示入场弧(p,d)的跨越时长，其值等于ta.endtp,end。t i a y o v e r为车辆的最小留站时间，也称最小站停时间，其间可进行必要的车辆维护检查。ts1,s2表示从发车站点si到发车站点s2的空驶车次的行驶时间。td,s表示车辆从车场d到发车站点s的出场行驶时间。ts,表示车辆从发车站点s到车场d的入场行驶时间。t(p,g）表示在接续(p,q)上车辆的行驶时长，即当该接续包含空驶车次时等于该空驶车次的跨越时长，否则其值为0。td,p表示出场弧(d,p)上车辆从车场d到车次p的始发站s的出场行驶时间，其值为td,s。t p,表示入场弧(p,d)上车辆从车次p的终站s到车场d的入场行驶时间，其值为ts,d。1.2超级时空网络构建超级网络是利用网络拓扑结构解决工程和管理问题一种技术手段。超级网络中一般应包含非物理上实际存在的名义节点或弧段来描述相关问题的抽象逻辑关系。下面以常见的单车场、具有上下行两个发车站的公交线路为例，对如何构建相应的超级时空网络加以说明。对应的超级网络中包含两类时空节点。第一类是由车场d形成的时空网络的总的起止点(d,0)和(d,T)。一个时空节点由一个有序数对表示，其中第一个数字表示时空节点的位置，第二个数字表示节点在时空网络中所处的时刻。第二类时空节点是由线路的发车站点sES形成的。已知tp,start为车次p从其始发站sp,start出发的时刻，在时空网络中对应的发车时空节点为(sp.start,tp,start)。而由车次p到达其终点站sp,ena的时间tp,ena可得到时空网络中对应的车次终止时空节点(sp,end,tp,end)。为了表述简洁，用(s,t)表示一个典型的第二类时空节点。公交车辆调度对应的超级网络具有5类时空弧段，均为依循时间增加的有向弧段。第一类是由联接(d,0)和一个(s,t)形成的出场弧。出场弧的头节点(s,t)必须为车次的起始节点。第二类是由联接一个时空节点(s,t)和(d,T)形成的入场弧。入场弧的尾节点(s,t)必须为车次的终止节点。第三类时空弧段是联接两个第二类时空节点(s,t)的接续。显然接续的尾节点(s,t)必须为车次的终止节点，而头节点(s,t)必须为车次的起始节点。第四类时空弧段为与给定实际车次对应的车次弧。实际车次的起止时空节点已在前面定义。第五类时空弧段为与空驶车次(Deadheading Trip-DH)对应的空驶车次弧。空驶车次是为了充分利用有限车辆资源来覆盖所有实际车次而产生的车辆在发车站点之间空驶的车次。由于任一给定DH均包含在一个接续中，其在时空网络中的起止节点具有一定的变动性，我们在后续分析中主要关注DH的行驶时间特征。在5类时空弧段中，除了车次弧为实际给定，其他4类需要按照一定的规则生成。下面7227卷何胜学介绍具体生成其他4类时空弧段的条件。设p,qEP为任意的两个相异实际车次。如果条件tayover tg,start-tp,end宁和sp,end=Sg,start 成立,那么可生成一个可行接续(p,q)C。如果条件tiayover+tsp.end,sg,startta,start-tp,endT和sp,end Sq,start成立，那么可以生成一个可行接续(p,Q）C，同时生成包含于该接续的一个空驶车次。T和为给定的时间长度，用于控制生成接续的最大跨越时长。设dED和qEP为一个车场和任意的一个实际车次。如果条件ta.S.tg.start-ta.startT成立，则可生成可行的出场弧段(d,q)EPO。如果条件tg,end-td,startT成立，则可生成可行的入场弧段(q,d)EPI。根据前面的设定可知一般情况下车场的起始时刻tdstart=0。T 和T为给定的时长，分别用于限定最晚的出场弧段结束时间和最早的入场弧开始时间。图1给出了一个简单超级时空公交车次关联网络。车场在该超级网络中根据其起止时间分化为网络中车次链的起点和终点。车场与车次之间为出场弧和入场弧，而车次之间为接续。7 个车次的序号在图中相应车次的上方标示。图中下方的水平带箭头直线为时间轴。沿时间轴从左向右，时间逐渐增大。时间轴的起点时间应早于车辆的最早出车时间，而右端的可标示时间应大于车辆的最晚入场时间。为便于观察，时间轴上标示了各车次的起止时间点。其中车次3和7 的起止时刻已在下方的时间轴上明确标出。为了使网络更加清晰且便于理解，图中各元素(如车场和车次的发车点)的实际地理位置并不与图中的点的纵向位置对应。通过将车场分解为起止两个时空节点，将线路的起止站点分解为各个车次的时空起终点，并添加接续、出场弧和入场弧，超级时空网络使得详细刻画车辆的时空运行轨迹成为可能，也便于后续的建模分析。36247dd,T5t3,startt3.endtr,starttr.end车次一接续出场弧/人场弧图1关联车次的超级时空网络2公交车辆调度优化模型基于上文给出的超级时空网络和参变量，可以构建公交车辆调度的基本的模型如下：min f()=t(p,g)v,(p,q),(1)vEV(P,q)ECs.t.Cu,(q,p)+Cu,(d,p)v,(p,d)+u,(p,),Vu E V,p E P,(2二(q,P)EC(d,p)ePO(p,d)EPI(P,q)ECCu,(d,p)=1,Vu E V,(3)dED(d,p)EPOucv(P,aerl733期基于超级时空网络的公交车辆调度模型及3M进化算法au,(p,d)=1,Vu E V,(4)Cv,(p,g)=1,Vp E P,(5)VaEO.au,(p,q)E(0,1),Vu E V,pE P,qE P,(6)av,(d,g)E 0,1),Vu E V,d E D,q E P,(7)Cv,(p,d)E 0,1,Vu E V,p E P,d e D。(8)其中的优化目标f()表示所有接续包含的空驶车次的总行驶时间。是由式(6)(8)中的变量(c)、(d,)和a.(p.a)构成的决策变量。为了便于理解，可以将视为一种特殊的网络流量。如as,(p.c)可视为流经接续(p,Q)的类流量。以式(1)为目标函数，即希望得到可以覆盖所有实际车次的公交车辆运行车次链，使得所需的空驶车次行驶时间最短。约束(2)表示流经任意车次pEP的第EV类网络流量守恒，即流入量等于流出量。约束(3)表示流出所有车场的第EV类网络流量之和等于1。约束(4)表示流入所有车场的第V类网络流量之和等于1。集合O=(gl(p,q)C,pEP)表示通过可行接续与给定车次pEP后向相连的所有车次的集合。约束(5)表示流出任意给定车次pEP的所有类别的网络流量之和等于1。一般将约束(5)称为车次的唯一覆盖约束。约束(6)(8)是对决策变量的取值范围的限制。如果定义集合Ip=gl(q,P)C,pE P)，唯一覆盖约束(5)也可用式DuVDaco(a.D)=1peP加以替换。如果将约束(3)和(4)用下面的约束(9)代替，则表示不是所有车辆必须去执行实际车次：,(d,)=Cu,(p,d)1,Vu E V。(9)deD(d,q)ECdeD(p,d)EC当用约束(9)代替约束(3)和(4),并且将目标函数(1)改为：min f()=av,(p,d),(10)vEV dED(p,d)EC或者min f()=u,(d,p),(11)vEV dED(d,p)EC则优化问题转化为求解执行所有车次所需的最小公交车辆数目。而确定最小车队规模问题也是公交车辆调度中非常重要的基本问题。在实际车辆调度中，常常需要考虑人车固定模式，即乘务组与特定车辆固定搭配，所带来的工作时间约束。设t为车辆u总的实际有效服务时间，而Tmax为任意车辆允许的最大实际有效服务时间。具体的车次开行计划确定后，t，的计算公式如下：Cu,(p,g)(tg+tp)+au,(d,p)tp+au,(p,d)tp)(12)(P,q)EC(d,p)EPO(p,d)EPIe27卷74何胜学实际车辆调度一般会要求下面两个条件成立：tuTmax,VuEV,(13)maxtu-min(tu Taif,(14)UEVUEV式(14)中的Tair是一个事先设定的最大有效工作时间绝对差。条件(13)一般称为工作强度约束，条件(14)一般称为工作时间公平性约束。令Ttotal和Taverage分别表示所有车辆的总有效工作时长和平均有效工作时长，计算公式为：Ttotal=(15)UEVTtotalTaverage(16)nv式(16)中nv表示车辆集合V包含的公交车辆总数。在车次给定条件下，易知Ttotal和Tavera的值为定值。工作时间公平性约束(14)也可利用下式替代：Duev(t,-Taverage)2Tdif,(17)nV约束(17)与(14)相比，去除了求取最大最小值的运算，同时在考虑减少最大与最小的实际工作时间之差的同时，兼顾了各个车辆实际有效工作时间的分布。利用约束(17)替代常见的约束式(14)将为随后设计求解相关问题的算法提供便利。考虑到在车次给定条件下总的工作时长为定值，因此当车辆中最大与最小的实际工作时间之差足够小时，约束(13)就会自动满足。基于上述考虑，后面我们将仅考虑工作时间公平性约束(14)或(17)。当利用启发式方法对模型求解，可以将约束(14)或(17)转化为目标函数的惩罚项，从而便于构建模型的可行解。相应的带有惩罚项的具体目标函数为：min f(a)=wi Z.Zt(p,a)av,(p,g)+w2F(p),(18)vEV(p,q)EC式(18)中wi和w2为正的权重系数，=max(tu一min(tu)或p=(t-Taverage)，而函UEVUEVUEV数F(c)=+，其中，为给定的参数。一般的公交车辆调度问题可以转化为等价的集合覆盖问题。但由于实际调度问题的规模都较大，确定对应集合覆盖问题的精确最优解将变得非常困难。具有类似约束(13)和(14)的公交车辆调度问题已被证明具有NP-hard特征，因此需要设计有效的启发式方法进行求解。33M进化算法本文提出的3M进化算法主要包括三种操作，即混生、变异和成长。方法借鉴了经典遗传算法的变异思想，同时基于超级时空网络的拓扑特征提出了混生与成长算子。下面首先对算法的主要操作加以介绍，随后给出3M进化算法的具体步骤。75基于超级时空网络的公交车辆调度模型及3M进化算法3期3.1可行解的生成、混生、变异与成长公交车辆调度的可行解集由满足约束(2)(8)的决策向量的值构成。一个可行解对应覆盖所有车次且每个车次仅被覆盖一次的nv条车次链。车次链中相邻车次间的接续(p,q)与该车次链的车辆之间的关联关系与具体的决策变量a(p,g)对应。基于上述对应关系，模型可行解的生成等价于生成覆盖所有车次的nv条车次链。具体的生成过程为：首先将所有车次按其发车时间加以升序排列；然后逐一考虑排序后的车次，从当前空闲的车辆中任选一辆覆盖当前的车次，并更新车辆的状态；执行上述操作直到所有车次被覆盖，从形成的nv条车次链析出对应的模型可行解。上述的车辆状态更新包括车辆空闲与运行状态的更新和与车辆相关车次链的变化。与遗传算法中的交又算子对应，本文提出了一种基于问题网络结构特征的“混生”算子。由于公交车辆调度解的集合覆盖特征，将两个可行解简单地进行类似遗传算法的交又操作都会使得到的新解违背约束(2)(5)。因此，为了有效利用已有可行解的特征，有必要设计新的操作实现产生带有已知可行解特征的新可行解。具体的“混生”操作思路为：首先将指定数量的已知可行解对应的已选择的接续、出场弧和入场弧标记为具有优先被选择权利的网络元素；然后按照生成一般可行解的步骤，在选择具体车辆与车次匹配时，以一定的概率优先选择与已知可行解对应的接续、出场弧或入场弧；最后，判断新生成的可行解是否与已知的原可行解相同，如果相同，重复上述步骤，否则输出新的可行解。上述的混生算子既保留了部分已有可行解的特征，又在不违背约束条件下实现了新可行解的生成。下面以图2 为例对算法中的“变异”操作进行解释。图2 中带数字标示的圆圈表示具有相应序号的车次；带箭头的实线表示被当前车次链集合所采用的接续，其中接续(1,2)假设为当前被考察的接续；带箭头的虚线表示未被采用的接续。对一个给定的可行车次链进行变异操作就是逐一对其实际采用的出场弧、入场弧和接续进行是否实施变异操作的判断，并在需要变异时进行合理的改变。以对图2 中接续(1,2)的变异操作为例，首先以车次1为起始车次，在超级时空网络中找出与之后向相接的其他车次，即车次3和4；然后在上述车次中任取一个，如车次4，在当前可行车次链集合中找到与该车次前向相连的车次5；最后判断车次5与接续(1,2)的终止车次2 之间是否存在可行的接续，这里存在可行接续(5,2)，于是结束上述的对具有回路特征的接续的搜索与判断，并用新的接续(1,4)和(5,2)替换原来的接续(1,2)和(5,4)。当在上述操作中，未发现连通的具有回路特征的接续时，需返回前面步骤重新选择可能的路线，如在第二步选择车次3，而不是车次4继续进行分析。变异操作需要注意两点：a）经过上述的遍历也可能没有找到可以替换的新接续，在这种情况下，保持原有接续即可；b）如果存在可行替换，经接续替换后得到的新车次链依然满足可行性约束条件。对一个可行解的“成长”操作实质上是对其进行一种类似邻域搜索的操作。但与一般的邻域搜索不同，每一次的“成长”操作都将改善当前可行解，使其对应的目标函数得以持续优化。在具体介绍成长操作前，需定义一些新的变量。令P表示车辆对应的车次链所包含的按时间升序排列的车次序列。显然，P,与车辆的实际有效工作时间t,对应。令Pu,-p表示P,中排列在车次p前包含车次p本身的部分车次序列，而tu,-p为对应Pu,-p的车辆的部分实际有效工作时间。考虑到车辆的同质性，一般可将to,-p简记为t-p。令Pu,p-表示P,中排列在车次p后包含车次p本身的部分车次序列，而to,p-(或tp-)为对应Pu,p-的车辆的部分实际有效工作时间。成长操作主要包括三个步骤，即指派网络构建、指派联接费用计算和指派问题的匈7627卷何胜学图2变异操作示意图牙利算法求解。下面以图3为例加以说明。图3中带数字标示的圆圈代表具有相应序号的车次；而有向线段表示联接车次的接续。如果为实线，表示该接续为当前可行解所采用的接续；如果接续用短划虚线表示，则表示未被当前可行解所采用的可行接续；如果接续用点划虚线表示，则表示实际不可行的接续。指派网络构建遵循如下步骤：a）确定与当前接续(1,2)的尾车次1后向相接的所有车次，构成前端车次集合(包含车次2、3和4)；b)确定与上述前端车次集合中各个车次利用当前可行车次链前向相接的所有车次，构成后端车次集合(包含车次1、5和6)；c)逐一判断后端车次集合中各个车次是否存在至少两个可行接续与前端车次集合中的车次相接，如果不存在，则删除对应的车次和前端车次集合中的与之相接的车次；d）在剩余的后端与前端车次集合之间添加所有可行接续，如前后两个车次间不存在可行接续时，添加联接费用为无穷大的不可行接续。6图3“成长”操作示意图通过上面的指派网络构建得到了一个具有指派特征的车次匹配网络。下面以最小化各车次链的有效工作时间差异（tT a v e r a g e)2 为例，对如何确定指派网络中车次间联vEV接的费用加以说明。在上述的指派网络中如果一个接续被选用，意味着该接续所联接的两个部分车次链将形成一个新的车次链。假设选用的接续为(p,9)，且该接续为可行接续，则对应联接的费用c(p,g)按下式计算：c(p,q)=(t-p+ta-Taverage)2。(19)如果该接续为不可行接续，则对应的联接费用为无穷大。按上述规则可以确定指派网络所有联接的费用。有了指派网络和相关联接的费用，即可调用匈牙利算法对所形成的指派问题加以求解。指派问题求解的结果将最终确定前后车次之间的最佳匹配。式(19)的联接费用仅针对公平性工作时间的优化，如果需要考虑减少空驶车次，则需对目标函数(18)中相关的参数W1、W 2、进行合理赋值。显然式(19)对应参数W1=0、W 2=1、=1、=1、=1。基77基于超级时空网络的公交车辆调度模型及3M进化算法3期3.23M进化算法于上一小节对3M操作的介绍，可以构建相应的3M进化算法。该算法的流程简图如图4所示。异法的兵体水少球如：步骤0 初始化。给定初始可行解群体规模M、混生新解数量N、变异系数e、成长系数以及最大迭代次数K。令当前选代次数为T=1。步骤1生成规模为M的初始可行解集合。步骤2 通过混生操作生成N个新的可行解。通过轮盘赌或锦标赛法，从可行解集合得到指定数目的可行解，利用“混生”操作生成一个新的可行解。重复上述操作，直到生成N个新解。步骤3对N个新的可行解实施变异操作。对N个新解逐一实施如下操作：生成一个 0,1 间均匀分布的随机数；如果该随机数小于变异系数，对当前新的可行解实施变异操作。步骤4形成新的可行解集合。从原有可行解集合中利用轮盘赌或锦标赛法选取M-N个可行解；将上述M-N个解与前面新生成的N个解组成规模为M的新可行解集合；步骤5随机对部分解进行成长操作。对M个解逐一实施如下操作：生成 0,1 间均匀分布的随机数；如果该随机数小于成长系数，对当前可行解进行成长操作。初始可行解集生成混生操作变异操作成长操作是满足终止条件输出最优结果图43M算法的流程简图步骤6 终止判断。如果TK，输出最优解；否则，令T：=T+1，转步骤2。3M进化算法的混生和变异操作的主要目的是对已有的可行解加以调整，增加搜索的随机性，扩展搜索空间；而成长操作主要目的是通过对解的结构内容加以调整使得对应的调度目标值得以优化。因此，3M进化算法的良好整体收敛表现可说明成长操作能有效提升算法效率。4实证分析本节将通过对一个实例的计算验证新模型的合理性与3M算法的有效性。公交线路车次的基本信息在表1、表2 和表3中给出。表1总结了不同时间段内从起点站发出的车次的运行时间。表2 给出了分别从主副发车站点在不同发车时间段内的发出车次的数量与发车间隔，合计的车次数目为2 16 次。表3给出了车场与主副发车站点间的出场、入场和站间空驶的时间(时间单位：min)。表1发车站点发车的起止时间与站间车次运行时间序号开始时间结束时间运行时间/min106:3007:3070207:3014:3085314:3019:0090419:0022:00807827卷何胜学表2 发车站点发车间隔信息主站S1副站S2开始时间结束时间最优间隔/min发车数开始时间结束时间最优间隔/min发车数06:3007:008406:3007:3012507:0007:489507:3008:1010407:4808:308508:1009:108608:3009:007409:1009:307209:0009:407509:3010:107509:4011:0081010:1011:0010611:0012:0010711:0013:00101312:0013:0010713:0014:0010713:0014:0010714:0015:2081214:0015:2081015:2016:3071115:2016:307916:3017:3061016:3018:0081117:3018:007418:0018:408518:0018:408518:4020:0010918:4020:0010820:0021:0012520:0021:0012521:0022:0012521:0022:00125大忆上出左址上酒穴种行种叶问表3车场与发车站点间的车辆空驶行驶时间车场d主站s1副站2d01520S115030S220300表4给出了以最小化空驶车次的行程时间为优化目标的优化结果。车辆的数目为31，为覆盖所有车次所需的最小车辆数目。计算结果表明通过优化，线路可以在无空驶车次条件下被31辆公交车全覆盖。形成的31条车次链、车次链的实际车次运行时间TripChainTime-TCT)和出入场车辆行驶时间(Pulling Time-PT)在表4中列出。表中时间的单位为分钟(min)。从表中数据可知：为了减少空驶车次，各条车次链包含的实际车次的总行驶时间变化幅度较大。各车次链的实际车次运行时间从430 min到7 6 0 min不等。表5给出了以平衡各个车次链的实际车次运行时间为目标得到的3M算法优化结果。以w=Vuev(t-Taverage)/nv表示车次链运行时间的标准偏差，对应的w值为13.12 9。从表5中的数据可知大多数的车次链的实际车次运行时间均在595min左右。与前面最小化空驶车次时间相比，新的结果出现了大量的空驶车次，各车次链中对应的空驶车次运行时间(DeadheadingTime-DT)在表5中列出，时间的单位为min。在设定nv=31，M=3,N=2，=0.15、=0.15以及最大迭代次数K=40的条件下，图5给出了有31辆公交车时以车次运行时间偏差最小为目标时3M算法的迭代表现。利用Java1.8.0程序语言实现本文的3M算法，在NetBeansIDE8.0.2开发环境下运行，采用的计算机处理器为Intel，Co r e i 3-312 0 M CPU。在上述参数条件下，一次求解的计算时间约为50 s。图5中最终的目标函数值为13.12 9。如果将可行解集的规模增大，如从上面的M=3变为M=10，算法一般只需要送代4到5次即会收敛。但是对于不同迭代次数下79基于超级时空网络的公交车辆调度模型及3M进化算法3期表4以减少空驶时间为目标的车次链优化结果编号车次链TCT/m