基于双层规划的公交调度模型研究

基于双层规划的公交调度模型研究

1公交调度的系统模型对于公共交通公司来说，他们的基本任务是协调和充分利用公共交通资源，更好地满足城市居民的需求。公交区位规划模式是实现这一目标的好途径。该公交区位规划利用不同线路和不同季节的最大客运量在方向和时间上的不平衡，实现不同部门之间交通的动态组合，节约劳动力、物资和财力，提高车辆使用效率，增加不同路线的协调目标。由于公交调度问题的复杂性,现有的研究通常将该问题依次划分为四个部分:公交线网设计及优化、时刻表编制、车辆调度和人员调度,且前一部分的解决方案是后一部分实施的前提和基础.其中,公交时刻表是公交企业组织线路运营的具体作业计划.它指导着公交线路运营的全过程,是公交企业管理的基础工作.而车辆调度工作的好坏又直接影响着公交企业的成本支出,是公交企业重点关注的运营环节之一.国内外众多学者对以上这两个问题都进行过深入的研究[1,2,4,5,6,7,8,9,10,11],他们或利用数学、运筹学等精确的方法,或利用现代启发式优化算法对这两个子问题进行了求解,且取得了较好的运算结果.然而,上述研究都未能从系统的角度来考虑公交调度系统整体优化的问题.由于公交时刻表的生成与车辆调度之间存在着有机的联系,因此,虽然按照这些既有的模型算法可以得出上述公交调度问题较好的解决方案,但是却不能够保证系统的解决方案从总体上讲是最优的.本文的研究重点就是要基于既有研究成果中的上述主要不足,根据公交调度问题自身的特点,借助双层规划的基本原理,按照区域公交调度的模式,建立一个可行而有效的区域公交调度系统中时刻表生成和车辆调度双层规划模型.2适用时间区间的数学模型较之传统单线公交调度模式,区域调度的最大优势就在于能够更有效地利用企业的车辆资源,更好地满足乘客的出行需求.那么,在公交线路和车辆参数既定的情况下,如何实现这种优势就成为了考核公交调度质量的重要标准之一.而双层规划正是解决这类双层系统优化决策问题的有效方法.因此,区域公交调度问题可描述为一类双层规划问题,即上层规划是以实现公交企业综合运营成本最小化为目标的多车场多线路且同一车场服务多条线路、线路之间存在换乘节点的车辆时序指派问题,而下层规划是以实现乘客换乘时间最小化为目标的若干条公交线路协同发车问题.通过建立双层规划模型,将时刻表生成模型由只产生最优解变为产生一组满意解供车辆调度模型比选,进而产生出最佳车辆调度方案及与之对应的符合满意度评价标准的公交时刻表.上层配车模型所要解决的问题就是使得时刻表中每一个车次都能得到执行.建立模型之前,需要知道以下参数:p(车次数),K(车场数),tl,P(车场l到第p条线路起点的走行时间),ti,j(两条线路起点间的走行时间),tP(各条线路的走行时间),C(一台车辆的固定成本),c(一台车辆在单位时间内的可变成本),Dmaxlmaxl(车场l所能容纳的最大车辆数),dminlminl(执行完所有任务后车场l最少车辆数),Tmax(车辆最大续驶时间)以及[TB,TE](调度计划的适用时间区间).由于是区域化调度,所以无须考虑车辆执行完任务后必须回到原车场的情况,只要保证任务全部执行完毕后,车场车辆存量不低于某一数值即可.在不考虑车辆容量约束、车型差异、车速差异以及每个车次有且仅有一辆车来执行这四条假设的前提下,设上层模型的目标函数为:(U.){S(X)→YF(Y)=min{Cm+n∑i=1n∑j=1Cijyij+k∑l=1[n∑i=1Ci,n+lyi,n+l+n∑l=1Cn+l,jyn+l,j]}.(U.)⎧⎩⎨⎪⎪⎪⎪S(X)→YF(Y)=min{Cm+∑i=1n∑j=1nCijyij+∑l=1k[∑i=1nCi,n+lyi,n+l+∑l=1nCn+l,jyn+l,j]}.其约束条件为:p+Κ∑j=1yi,j=1,i=1,2,\∑j=1p+Kyi,j=1,i=1,2,\:,p,(1)p+Κ∑i=1yi,j=1,j=1,2,\∑i=1p+Kyi,j=1,j=1,2,\:,p,(2)d0l-Τ′∑t=0yp+l,j+Τ′∑t=0yi,p+l≤Dmaxl,Τ′∈[ΤB,ΤE],l=1,2,\:,K,(3)d0l-ΤE∑t=0yp+l,j+ΤE∑t=0yi,p+l≥dminl,l=1,2,\:,K,(4)yp+l,j-zj,l≤0,j=1,2,\:,p;l=1,2,\:,K,(5)yi,p+l-zi,l≤0,i=1,2,\:,p;l=1,2,\:,K,(6)zi,lyi,j-zj,l≤0,i,j=1,2,\:,p;l=1,2,\:,K,(7)Κ∑l=1zi,l=1,i=1,2,\:,p,(8)yi,j∈{0,1},i,j=1,2,\:,p+K;(i,j)≠(p+l,p+l′);l,l′=1,2,\:,K,(9)zi,l∈{0,1},i=1,2,\:,p;l=1,2,\:,K,(10)tl,i+ti,i′+ti′i″+\:+tin-1,in+tin,l′≤Tmax,xl,ixi,i′xi′,i″\:xin-1,inxinxin,l′=1,(11)这里,S(X)——公交时刻表生成的所需完成的任务班次序列.yi,j——如果运行完车次i接着直接运行车次j,则为1,否则为0;i,j=1,2,…,p.yi,p+l——如果车次i运行完之后,车辆直接回到车场Dl则为1,否则为0;i=1,2,…,p;l=1,2,…,K.yp+l,j——如果车次j是车场Dl发出的车辆运行的第一个车次,则为1,否则为0;l=1,2,…,K;j=1,2,…,p.zi,l——如果车次i是由车场Dl发出的车辆执行的,则为1,否则为0;i=1,2,…,p;l=1,2,…,K.Ci,j——线路间空驶成本.Ci,j=ci,j×ti,j.d0l——初始时刻车场Dl的车辆数.m——完成车辆调度任务所需车辆总数.映射S(X)→Y表示下层时刻表生成的任务班次按照自然数编码形成上层车辆调度模型的可行输入解.例如S(X)为下层模型生成的5个班次的时刻表,那么Y即为1、2、3、4、5组成的任意排列,即12345.条件(1)保证每一辆车完成车次i之后回到车场或执行下一个车次j,其中,i,j=1,2,…,p.条件(2)使得每一个车次都能分配到车辆,或者从车场出发,或者是从上一个车次完成之后接着执行新的车次.条件(3)保证每一个车场在T0时刻的车辆数不超过它的最大容量.条件(4)保证每一个车场在TE时刻的车辆数不小于它的最小存量.条件(5)将车场Dl的车辆分配给j,并且j是车辆从Dl开出后执行的第一个车次.条件(6)说明的是车场Dl的车辆分配给i,并且i是车辆回到车场Dl前执行的最后一个车次.条件(7)说明车辆执行完车次i直接执行车次j,如果车次i是车场Dl分配的,那么车次j也是由车场Dl分配的.条件(8)保证每一个车次i仅有一个车场分配车辆.条件(9)和(10)分别给出了yi,j和zi,l的定义.条件(11)是车辆续驶时间约束.由于实际各种可获得信息的随机性过大,得出精确的针对公交客流规律性的量化关系具有相当大的难度,所以在建立下层时刻表生成模型之前不妨做以下假设:①每位在站点等车的乘客只等一条线路的车;②各条线路均不许超车行走;③车辆全部采用“全程全站”的运行方式;④同一条线路上行和下行两个方向的乘客在换乘节点无换乘;⑤客流需求不受发车频率的影响;⑥各条线路的公交车会在误差允许范围内,在规定时间准时入站.在以上六条假设的前提下,根据区域内各条线路各个时段的最大发车间隔和最小发车间隔,考虑乘客在线路换乘站点的换乘来最终确定发车时刻表.本文将在文献研究的基础上,将以乘客换乘时间最少为目标的区域时刻表编制问题归结为一类特殊的0-1背包问题.该问题没有容量的约束(设定其容量为无穷大),且通过协同系数βn的引入,将“0-1”的含义进行了泛化,使得模型可以刻画三条及以上线路在同一换乘节点相交的情形.定义1(协同系数)对于某一公交线路间的换乘节点来说,同时有车辆到达该换乘点的线路数与所有经过该换乘点的线路总数的比值称为该换乘节点的协同系数,记作βn.设下层模型的目标函数为:(L.){f(X)=max∑n∈AkqαnβnXnf(X)→S(X)其约束条件为:W1k≤Ηmaxk,1≤k≤Μ,(12)WFkk≤Τ,1≤k≤Μ,(13)Ηmink≤(W(i+1)k-Wik)≤Ηmaxk,1≤i≤Fk-1,1≤k≤Μ,(14)βn=2∑xk,lnΝ′(Ν′-1).(15)Xn=max{xk,ln|k∈Μ,l∈Μ,k≠l,k和l不能同时分别为2n′-1和2n′‚1≤n′≤Μ}(16)其中,S(X)——公交时刻表所生成的一系列需完成的车次序列集,它可按照某一规则由f(X)得出;T——表示一个时间段;M——线路的总条数;n′——经过某换乘节点的单向线路条数;N——换乘节点的个数;Wik——表示时间段T内第k条线路的第i车次的发车时间;Tkj——线路k的起点站到换乘节点j的行驶时间;Hmaxk——第k条线路在时间段T内的最大发车间隔;Hmink——第k条线路在时间段T内的最小发车间隔;αn——换乘节点n的权重系数,依换乘站点换乘量而定;βn——换乘节点n的协同系数;Xn——表征该换乘节点是否同时有车到达的二进制变量;N′——经过节点n的双方向线路条数;xk‚jn——考察k和j两条线路在换乘节点n是否有车同时到达的0-1变量;Akq={n:1≤n≤N,Tkn≥0,Tkj≥0}.映射f(X)→S(X)表示根据模型产生的可行解X,来确定各条线路的发车间隔,进而生成一组可行任务班次,即时刻表.在约束条件中,(12)式表示从时段T的起始时间到第一个发车时间不超过该时段的最大发车间隔;(13)式表示时段T内的最后一个班次的发车时间在该时段的终止时间之内;(14)式表示发车间隔在该时段最大发车间隔和最小发车间隔之内;(15)式给出了βn的计算方法;(16)式定义了目标函数中的Xn值.3上层规划密度目标函数本文模型中的上下两层规划均采用禁忌搜索算法进行求解.先从下层规划着手,生成符合满意度指标的可行任务班次列,比较上层规划的目标函数在各个可行任务班次的值,进而找到该双层系统的最优解.3.1表的生成和求解对于上层车辆调度模型,用0表示车场,其它自然数表示所需完成的班次任务.首先产生一组自然数序列,再根据约束条件插入车场00.因为是多车场问题,所以在生成有00插入的自然数列以后,再分别考虑00具体代表的实际车场.例如:初始解可表达为012300450067890.这个初始解中存在3条任务链,0代表可能的车场,如果这里的第2个0和第5个0代表同一个车场且可以形成0123067890链的时候,则完成整个调度任务只需2辆车即可.初始解可以依照上述规则随机产生.对于下层时刻表生成模型,其每次迭代产生的解(包括初始解)可依据文献中设计的启发式算法求得,具体步骤如下:Step2当kn∉E且xkn‚k⋅n=1,则转入Step1;当kn∈E时,如果Hk1=Hk2,则xkn1‚kn2n=1,否则xkn1‚kn2n=0.其它情况下,则算法继续.Step3计算Xn的值,得出解向量XNow.Step4计算βn的值,得出目标函数f(X).Step5记录当前最优解及所对应的目标函数值.Step6计算r(X)的值.若r(X)≥R,则X∈S.其最终输出的可行任务班次列可依照生成方案满意度指标来确定.定义2(方案的满意度)方案X所对应的目标函数值f(X)与最优方案X*所对应的目标函数值f(X*)之比称为该方案的满意度,记作r(X).上下两层模型均采用2-opt作为邻域操作方法.对于上层车辆调度模型,每变换一次,则根据各个约束条件,重新插入车场编号00,得到随机一组自然数对位置交换后的新数列.例如:原解为012300450067890,如果对3、7进行邻域交换操作,则可能会依规则变为01270045006003890.对于下层时刻表生成模型则直接将解向量中的0变换成1.例如,解向量X=(1,1,0,0),则将解向量中的两个0分别用1来代替,再根据产生初始解的方法得其邻域为{(1,0,1,1),(0,1,0,1)}.3.2输出当本文的终止原则采用确定迭代次数和频率控制相结合的方式.即如果在一个给定的步数内,当前最优值没有变化,那么就终止计算,输出当前最优解;如果在规定的迭代次数内没有达到频率控制的要求,那么也终止搜索,输出当前最优解.本文将既有最优值出现的次数与总迭代次数之比作为记忆频率,记为J={Count(¯XBest)G,G≥Gmax20,else.3.3生成挡墙空间本文将每次迭代产生的使得目标函数值最大/最小的解作为禁忌对象,将候选集合确定为随机产生的解的部分邻域空间,给被禁对象Xn一个数t作为禁忌长度,设上下两层模型的评价函数均为p(x)=f(¯XBest)-f(XΝow).4总体计算时间每一个组合最优化问题都可以通过枚举的方法求得最优解,于是对于有N个换乘节点,M条公交线路,K个车场的情况来说,1)如果有P个车次任务需要完成,那么依照上文提出的上层模型的可行解的表示方法,要生成能够满足所需车辆数和车辆空驶时间最小的配车计划,则需P!次枚举;2)如果每条公交线路都有H个发车间隔(或发车频率)可供选择,那么要生成一个使得总换乘时间最小的发车时刻表,则需要HM次枚举.随着公交线路的增多、发车间隔(取离散值)取值范围的增大,况且公交调度所需执行的任务班次数通常都是几十次,甚至是上百次,对于这上下两层都属于NPC问题的二层规划模型而言,其计算时间是令人无法忍受的.然而,如果依照本文所设计的算法,上层模型产生最优解的总计算量仅为O(P2K),下层模型的可行解的启发式生成算法的计算量为O(M2N+N2),生成下层模型的最优解的总计算量也仅为O(M4N2+M2N3+N4).这相对于枚举法,在理论上来讲,问题的求解速度必将得以显著提高.这里需要说明的是:1)虽然在下层模型中,应用一种启发式算法来产生可行解的做法会导致算法整体计算量的增加,但是这一启发式寻优过程的引入,必然会使收敛速度加快.因此,总体来说,算法的总计算时间不仅不会延长,反而很可能会更短.2)通过引入满意度r(X)作为二层规划算法的过滤器,这就在不增加计算量的前提下,进一步保证了整体模型输出结果的最优性.3)当然,本文所设计上层模型的算法依然没有克服禁忌搜索算法固有的对于初始解选择过于依赖和串行算法计算时间相对较长等主要不足,这需要在今后的研究中继续探讨.5算法计算满意方案作者用C++语言程序实现了上述算法,并对如下随机产生的实例在CPU为AMD2500+、内存为256M的计算机上进行了实验计算.对于下层模型,假设区域内双向8条公交线路,即M=8,如图1所示.单向4条线路间有三个换乘节点Ⅰ、Ⅱ、Ⅲ,即N=3.设定所制定时刻表的时间段为9:00～11:00.各条线路的发车间隔取值范围分别给定为:,,,,,,和.三个换乘节点的权重分别设定为:αⅠ=1,αⅡ=1,αⅢ=2.设定满意度评价指标R=0.85.运用本文所给出的启发式算法计算,经过50次迭代计算(计算时间均在2秒钟以内),最终得到两组满意方案.具体计算结果如表1所示.这两组满意方案分别如下:方案一,1、2、6、7、8路车的发车间隔为20分钟,3、4、5路车的发车间隔为15分钟;方案二,1、3、4、5、7路