基于NSGA算法的公交车辆调度优化模型

基于NSGA算法的公交车辆调度优化模型宋晓鹏，韩印，姚佼（上海理工大学管理学院，上海200093）摘要：公交车辆调度方案的优化对于提高公交服务水平，促进公交事业的快速发展至关重要。在乘客与公交公司利益博弈的基础上，基于极小极大思想，考虑公交车车辆容量的限制及城市道路信号控制的干扰因素建立公交发车间隔优化模型，并利用非支配排序遗传算法（NSGA）进行模型的求解。以河南省焦作市的公交线路为例进行验证，优化结果显示乘客的平均等车时间相对减少48.3%，公交车的全日平均满载率下降了3.8%，公交服务水平有所改善。关键词：城市公交；发车间隔；等车时间；非支配排序遗传算法中图分类号：U491文献标志码：ABasedontheNSGABusSchedulingOptimizationModeloftheAlgorithmSONGXiao-peng,HANYin,YAOJiao(BusinessSchool，UniversityofShanghaiforScienceandTechnology，Shanghai200093，China)Abstract:Optimizedbusesschedulingschemeisessentialtoimprovetransitservicelevelsandpromoterapiddevelopmentofpublictransport.Onthebasisoftheinterestsofgamebetweenpassengersandthebuscompany,consideringbusvehiclecapacityconstraintsandconfoundingfactorsofurbanroadsignalcontrol,wehavebuiltthebusdepartureintervaloptimizationmodelbasedontheMinimaxideas,andthenusethenon-dominatedSortingGeneticAlgorithm(NSGA)tosolvethemodel.IllustratedbythecaseofbuslinesinJiaozuo,HenanProvince,thetransitservicelevelshavebeenimprovedwiththeoptimizationresultsshowthattheaveragewaitingtimeofpassengersrelativereducedby48.3%andbusesfulldayaverageloadfactorsfellby3.8%.Keywords:urbanpublictransport;departureinterval;waitingtime;non-dominatedsortinggeneticalgorithm优先发展城市公共交通是提高交通资源利用效率、缓解交通拥堵的重要手段。作为城市交通的主要通行方式，公共交通服务水平与居民出行需求和城市交通运行状态息息相关。优化发车间隔是公交调度的主要技术手段。准确和高效率的发车调度对提高公交线路的服务能力，减少居民的出行延误，提高乘客满意度有着重要意义。Huisman[1]等提出了用于描述多场站调度问题的动态模型，并应用“聚类再生成”启发式算法，基于数学规划模型得出优化的结果，但对公交车容量未作考虑。孙芙灵[2]根据乘客需求来确定发车间隔，用数学规划的思想建立调度模型，并用时间步长法、等效法进行求解，得出仿真结果，但对公交公司利益收稿日期：2013-08-08基金项目：上海市一流学科资助项目（S1201YLXK）；国家自然科学基金资助项目（51008196）第一作者：宋晓鹏（1987-），男，硕士研究生.研究方向：智能交通、交通规划与管理.E-mail：[e-mail]通讯作者：韩印（1964-），男，教授.研究方向：智能交通、交通规划与管理.E-mail：[e-mail]考虑不足。陈芳[3]根据客流变化规律，对发车间隔采用多时段处理思想，建立了以乘客与公交企业运营费用最小为目标的公交车辆调度模型，对于信号控制的干扰没有进行考虑。刘志刚等[4]根据区域公交调度模型，把公交车容量作为理想状态，不受信号控制的干扰,建立了公交调度系统双层规划模型。本文综合考虑乘客与公交公司利益，并基于极小极大思想，考虑公交车车辆容量的限制及城市道路信号控制的干扰因素建立公交发车间隔优化模型，并利用非支配排序遗传算法（NSGA）进行模型的求解。1优化模型的建立1.1模型假设公交车辆的运营受很多因素的影响，本文为建立公交调度优化模型作出以下假设：a.线路上的公交车辆为同一型号，公交车会按照调度表准时到站和出站；b.全程票价统一；c.公交车辆行驶过程中不存在阻塞现象及突发情况，且公交车之间依次行进，不存在超车及越站现象；d.各站点乘客上下车的时间、公交车在各站点停留时间均被考虑在公交车的平均速度之内；e.仅考虑沿线信号延误干扰，沿线交叉口具有相同的信号延误；f.各交叉口有足够大的通行能力，仅考虑单行方向公交车运行。1.2模型的构建公交车运行调度模型的建立是一个复杂过程，根据极小极大思想，为使服从相同规律的受控群体的性能指标在总体上最小，其充分条件就是使群体中性能指标值最大的个体值最小。作为乘客希望获得便捷、舒适、车辆间隔小、等待时间短的公交服务，这样势必造成空驶率过高，并且公交公司的利益得不到保证而影响其服务质量。而公交公司希望发车间隔增大，发车次数少且载客量大，以获取更大利益，这与乘客的需求相违背。因此，综合考虑公交公司与乘客的利益，使乘客最大广义费用最小及公交公司最大广义费用最小。maxmaxmin()min().1stffBMCf(1)式中，M为公交车的最大发车间隔，为一正常数；f为发车间隔，f∈整数，min；C(f)为在时间段T内，乘客的广义费用，元；B(f)为在时间T内，公交公司广义费用，元。在时间段T内出行者的广义费用W1in2T()=()+CfFfFF(2)式中，δ为与乘客有关的时间费用转化系数；FW(f)为乘客等车时间，min；γ1为相对于等车时间费用的在车时间费用权重系数；γ2为相对于等车时间费用的换乘惩罚费用权重系数；Fin为与在车时间相关的费用；FT为与换乘相关的惩罚费用。关于乘客等车时间有W()FfSn(3)式中，FW(f)为所有出行者等待时间，min，n为所有等待的乘客数量，人次；S为乘客等待时间的均值，min。对于某一站点，记W(t)为在t时刻在节点等待的乘客数量，等待的乘客包含在下一辆车到达之前陆续来到站点做等待的乘客及在上一运次滞留的乘客。t时刻为某一公交车进站时刻。并且设定公交车的容量为C，则在该站点，乘客上车的数量为P(t)。()()()()()()()WtWtCOtPtCOtWtCOt其中其中(4)式中，O(t)为在某站点处，公交车上已有的乘客数量。对于滞留的乘客，其需要在等待下一运次才能乘上公交车，假定不存在3次等车，而保证一定的服务标准。对于滞留的乘客需要再次等待一个ti时间才能上车。若对于上一时刻存在乘客滞留，则滞留人数为D(t-ti)。(t)()()iiiDtWttCOtt(5)=+ijjItfd(6)式中，ti为相邻运行公交的平均车头时距，min；d在T时间段内，公交车由于遇到交叉口信号控制的干扰引起的平均延误，min；dj为公交车所遇到某一交叉口j引起的平均延误；I为公交车所沿该线路中交叉口数量，I∈整数。由于公交车按照行车时刻表运营，因此，乘客到达公交站点会产生等车时间，根据Bowman等[5]提出的等车时间模型，乘客期望等待时间的均值为2V()(1)2HEtC(7)式中，E(t)为乘客期望等车时间，min；H为平均车头时距，min；CV为车头时距协变参数。如果排除外界干扰，公交车平均车头时距应与发车间隔相等。由于公交车运行受交叉口信号控制的干扰，车头时距发生波动，则平均车头时距为ti。iHt(8)而对于t时刻，等候车辆的总人数为n，引起乘客等待公交车的状态有m种，分别为没有滞留的乘客平均等待时间和滞留乘客平均等待时间这两种方案，即m=2。根据熵权决策法原理[6]得出乘客等待时间的均值。12()[()]j=1,2,3jSwEtwEttn……(9)式中，w1为没有滞留的乘客等待时间权重；w2为滞留乘客等待时间权重。出行者等待时间W()FfSn(3)由于乘客在车时间只与路段的不同而不同，因此定义在车时间费用是只与路段相关的常数。对于惩罚费用同样与发车频率无关，取决于路段，同样可以作为常数处理[7]。对于在车时间费用与惩罚费用相应权重可以通过实际调查统计得到[8]。在时间T内，相应公交车运营的广义费用为3F3V()=()+1-)()BfBfBf（(10)式中，γ3为公交公司所支出的固定费用的相应权重；BF(f)为在时间T内公交公司所支出的固定费用，元；θ为每公里运营费用(与百公里燃油有关)，元/km；BV(f)为在时间T内与发车间隔相关的公交车辆行驶里程，km。其中固定费用主要包含公交车的保养维修费用、公交公司的管理费用及员工工资在T时间段内[9]。可得到相应固定费用Fsemw()=(++)BfNBBB(11)式中，Bse为在T时段内，平均每辆车的保养维修费用，元；Bm为在T时段内平均每辆车的管理费用，元；Bw为在T时段内相对于每辆车的人均工资费用，元。在T时间段内运营了N辆车TNf(12)式中，N为一整数，运算中中括号为取整运算，表示N为不超过T/f的最大整数。所有车辆行驶里程V2()=[(-)+(-2)++(-(-1))]2=()2BfvTTfTfTNfNTNfNfv(13)式中，v为公交车的平均行程速度，在某条干线上为一常数，km/h。公交车辆的运行势必受到红绿灯的干扰而影响正常运营，为保障公交车服务标准，相邻运行中的公交车车头时距因交叉口信号干扰需保持在一个发车间隔内。公交车遇到交叉口引起的延误是随机的[10]，因而根据Miller提出的随机延误理论。oo2(1-/)=[(1-/)+]2(1-/s)exp[-1.33(1-)]=2(1-)QgcdcgcqqsgxxQx(14)式中，d在T时间段内，公交车由于遇到交叉口信号控制的干扰引起的平均延误，min；c为周期时长，min；g为有效绿灯时长，min；x为饱和度；q为到达率；QO为平均饱和排队车辆数，辆。公交车遇到交叉口引起的总的延误满足如下约束jjIdf(15)基于公交公司与出行者综合广义费用最小。公交车发车间隔与信号控制之间存在相互影响，交通信号控制影响着车头时距的波动程度，约束发车间隔的确定；发车间隔的合理性又反映了信号控制的优化程度，信号控制得以优化可减少公交车运行时由于交叉口的干扰引起的延误，提高通行能力。则根据以上分析，建立如下公交车运行调度模型maxmaxmin()min().1jjIstfMdfCfBf(16)对于公共交通，当交通需求增加时，提高发车频率，可使乘客的等车时间减少[11]。为保持公交服务的优化品质，相邻运行公交车不发生超车或前后相接的现象。2模型的求解乘客广义费用和公交公司的广义费用这些目标并不是彼此独立，二者耦合在一起，互为矛盾，互为竞争。某子目标的改善可能引起其它子目标性能的改变，而同时使所有子目标达到最优往往是不可能的。要找到这些目标的最佳设计方案，就要解决多目标与多约束的优化问题，即多目标优化[12]。对于模型的求解引进非支配排序遗传算法(NSGA)。可以定义为在一组约束条件下，极小化这两个目标函数[13]，令[C(f)]max=u1(X)，[B(f)]max=u2(X)，形式如下：12min[(),()].()01,2,()01,2,jkuustgjJhkK