公交车调度的运作模型

1、公交车调度的运作模型【摘要】 由题可知，本问题是 多目标规划求解问题 。该问题要求我们 设计一个公交车调度方案， 同时照顾公交公司和乘客的利益。 我们首 先对基本数据进行分析， 得出上下行方向可独立优化 ，并通过 立方插 值找到了各站乘客到达的分布。 载客率和乘客等待时间是其核心 ，载 客率与公交公司利益相关，乘客等待时间与乘客利益相关。 (合理大 胆的假设的重要性) 我们将其作为两个目标 分解 形成多目标规划。 通 过分析各客车运行状态， 推导出了 平均载客率和平均乘客等待时间的 准确计算公式 ，从而得到原问题的一个明确、完整的数学模型，按多 目标规划的方法求解， 即化多目标为单目标求解。

2、在数值求解中我们 用非线性规划中的网格法和模矢法原理找到了本客车调度问题的满 意解。其典型解的有关指标为： 载客率为： 82.5% ；平均等待时间为： 2.55 分；所需客车为 57 辆。思维分析 ：公交车的调度问题，我们的切入点是 尽量使 乘客和公交公司 双赢。 对数据的处理：先取出上行数据进行分析，下行可以通过同理可得J1) 乘客到达的分布连续性2) 乘客下车的分布离散型对离散型数据进行进一步的分类，分析J考虑平均载客率公交公司的满意度:考虑平均等待时间 T 乘客的满意度: 建立综合模型：上行+下行模型的检验编码问题的提出： （已知条件）上行方向共 14站 ，下行方向共 13站，每辆标准载

3、客 100人，据统计客车在该 线路上运行的平均速度为 20公里/ 小时。乘客候车时间一般不要超过 10分钟 ，早 高峰时一般不要超过 5分钟 ，车辆满载率一般 50%120%。二基本假设：（理想状态下）1：乘客上车是按先到先上车的原则。 2：汽车到达终点站后排队等待发车，乘客上下车时间不计（可认为该时间已并 入客车正常时速）。3：客车在各站准点发车，客车平均时速为 20km/h 。4：车辆满载率不应超过 120%，一般也不要低于 50%。 5：所给原始数据是在车辆宽松的情况下得到的， 能很好的反映乘客来去的规律。 6：乘客候车时间一般不要超过 10分钟，早高峰时一般不要超过 5分钟。 7：对全

4、天而言客车公司应基本把所有的顾客运完。三模型的建立：（一）问题分析制定公交车调度方案时，必须考虑 公司和乘客 两方面的 利益，这两方面的利 益是 不可能同时满足 。所以，最后的数据牵扯到 权的问题。后面解释 （二）模型建立1 乘客到达的分布（本质上是连续型） 上行首发站各时间段上车的乘客人数已知为：371 1990 3626 2064 1186 923 957 873 779 625 635 1493 2011 691 350 304 2Q9 a9表示客流量。F1 （5） =0H | l|>R 4 1 I V 4 I «« I 4I< i|>H «

5、;> I 14/"O口 + C 了 » 4= /耳（0 = i*L七k匸 ar = 23LT（形成连续性函数）此分布函数是离散型，matlab软件能很好的用插值法得到连续型分布函数，不妨用表示0到t时刻本站到达 乘客的总数。依次类推对其它各站也同样可得到乘客到达的分布。2乘客下车的分布（本质上是 离散型）假设p为乘客在每站可能下车的概率（在t时段第i站上车的人在第j站下车的概率），每个时段的Pij（t）可组成一 n阶上三角矩阵。）（黑板画）3. 乘客、车辆运行规律（此表对于上行方向）仃辆车在n个站的行车时刻表t=（t ij ） n x m第i站到第1站的距离：xx1

6、x2 x3 x4 xix（n -1）第1辆车到第i站的时间：t t11t12t13t14 t1i t1n第1辆车经过第i站时站上等待的人数：F F11F12 F13 F14F1iF1n第1辆车经过第i站时下车的人数：B B 11 B 12 B 13 B 14B1Bn第1辆车在第i站到第i+1站车上的人数：S S11S12S13S14S1iS1n第1辆车经过后第i站剩余的人数：F- a等待人数-上车的人数F11- a 11F1n- a 1易知:上车人数1：一车人数哎打=% =0（当等待的人数F,超过可以车上的空位数b的时候）F车人数：pi=00LJ =乞叫珂毎）1*1（P每个车上的人在每站可能下

7、车的概率）其中：虬-120 - 22 A）（车上空位数，很好的控制120%） bii=120车上人数（车上的人数=前面上的总人数一前面下的总人数）显然当已知时，通过各站乘客到达分布函数可计算站上等车人数Fn=F1（t11）,从而可知an，因乘客下车分布pj（t）已知，从而可导出B 12= anp12, b12=120-（ aB 12）由前面数据和Fl2=F2（tl2）可得a12，对应的可算出Sli，依次类推我们可得到第 一辆车运行状态的有关数据。第二辆车类似的有这一状态：但在第2辆车经过的 第i站时站上所有等待的人数F21F22 F2iF2n 分别等于：F11 - a11+?F21 F12 -

8、 OI2+?F22 F1i - a1i+?F2i 其中?F2i =Fi（t2i） -Fi（t1i） Fi（t）为第i站乘客到达的分布；其它类似于第1辆车的情况，依次类推可导出各车的运行情况。以上分析是彻底解决本题 的关键。4. 平均载客率第k辆车的平均载客率为I 刊1fl1毎=（而Jg/町曲d = 2 （临的tO兀川）（车上的人数/路程X）总平均载客率:m丸总车次5. 平均等待时间对于第一个车站：Y1为本站人数达到a1时的时刻Y1为本站人数达到a1+ 021时的时刻Y1为本站人数达到011+021+031时的时刻为本站人数达到三磅时的时刻r-lmatlab软件能很好的用 插值法得到y，其它的车

9、站也有类似的定义。设 e为第i 辆车所运乘客总的等待时间，hi为第i辆车所运的总人数，由于在Y-i）j和Y这个 小时间段到站的人a可看作平均是在* S +兀于是可得:ei二旳厲-今）+%缶?-牛）+叫（心-今）十叫-尸；°）沁）心也02i心考察原始数据，我们定义上行方向早高峰期为6:00 9:00，下行方向早高峰期为7:00 10:00。则早高峰期的平均等待时间 为：+勺心） +號5(5)（总等待时间/总人数）正常期的平均等待时间为:l =右1 二"（G） + 勺1 5（4）十十冷1 一 （5）2松1 - $（站）+爲卩-21 ）H十饥1- §（%）正常期的平均等

10、待时间为：z = acl + l-a）z1（高峰期和非高峰期，平均等待时间的 权）其中(ru) + M(rsl) + + hS(tA显然乘客希望 Minzl , Minz2 , Minz6.乘客满意度按决策论中效用函数的方式归一化，因早咼峰期等待时间一般不要超过5分 钟，正常期一般不要超过10分钟，可定义早高峰时段平均等待时间为 0分钟时乘 客满意度为1;平均等待时间大于5分钟时满意度为0,正常时段平均等待时间为0 分钟时乘客满意度为1;平均等待时间大于10分钟时满意度为0,故zi, Z2如下进 行归一化：早高峰期的平均等待时间 归一化为：3 = 1-（ Z1-0）/（ 5-0）（若31<

11、;0则取心=0）正常期的平均等待时间 归一化为：3 = 1-（Z2-0）/（ 10-0）（若3<0则取32=0）3,32两者合二为一的目标函数为：（画图）Max 込（町=aw+ （1 即血（权）a前面已经定义，u=（t 11,t 21,tmi）为发车时刻表向量,7 .客运公司满意度设载客率120%寸，客车公司的满意度为1； 50%寸满意度为0。贝fir 1 50 zb.徃7T9（町弋0时丁规定轻® = 0）1 上（J% = 3（Ju'o表示客车公司的满意度，显然公司要求（w） D8.模型本问题为多目标规划，按多目标规划求解原则，首先将双目标合二为一。其表达式为：傾町=P

12、叭価）亠Q 凸（町 0<< 1（权）B为权重系数，由于全天最后一小时所到乘客很少，所以 末班车到终点站时, 其余各站所余人数的合计数近似为：（一天不能上车的人数）nI-（«>=- %）从我们的解法和实际要求，我们可看出对于全天来讲客车公司应基本把所有的乘客运完。则对于上行方向的模型为:皿工砍討）二（it） + （1-旳叭仗）z（li） < £（通常要求E比较小）lf = 01了二1十*5切1陆3，仍5）由于- 均为明确完整的数学表达式，所以多目标规划（线性加权法）是一个明确完整的数学模型若其上行方向的载客率为 q上，下行方向的载客率为 q下，则总的载

13、客率二鞋叫 X卜饷烦卜为匕行的发车次航 耕下为下廿的扯车枕数）m卜+叭下若其上行方向的等待时间为Vh，下行方向的等待时间为Vf,则总的等待时间卜+卩下盘卩丘上+阳（Rt为上行方向的总人数，F下为下行方向的总人数，已知数据）。考虑到上行和下行客车循环运输的作用， 和单程所花时间各为T1,T2，当- 方车辆与另一方车辆衔接不上时额外增加一辆车，如此下去计算出最少所需车辆 数即为所求，用计算机编程很容易实现。9.下车分布的计算:5:00-6:00上371602437690188385264545110下0913204845S13218242585576:CO-7:O0上199037633325689

14、594315622510176308S&7630下099IQo164239&8842800初203300238921615上表为上行方向5:00 7:00两个时段的数据，A13为第1站，我们希望得出乘客F车准确的分布，先看5:00 6:00，共上1035人，下465人，余570人在车上。A13 已下车的人数=(371 /1035) *465=166.7,则A13上车的人在 A12下车的概率p12(t)=8/166.7, A12 已下车的人数=(60/1035)*465=27 , A13上车的人在 A11 下 车 人 数 =9*(166.7 8)/(166.7 8+27)=7.7

15、, 则 在 A11 下 车 概 率p13(t)=7.7/(166.7 8) , A12在A11 下车的人数=9*27/(166.7 8+27)=1.3,则在A11下车的概率p23(t)=1.3/27 ，依次类推我们可以得到所有的下车概率。对6:00 7:00乘客下车的概率分布同样可以仿照上面的计算方式，不过要 首先排除上一时段上车而到本时段下车的人数干扰， 我们认为上一时段上车的人 是按照上一时段下车规则在本时段下车， 这假设是合理的。 对其它时段依次类推， 按照以上方法导出的乘客下车概率分布是忠实于原数据并且合理的概率分布。五模型的求解：本模型为多目标规划，可通过非线性规划中的网格法和模矢法

16、原理搜索，结合matlab编程求解，选取不同的权重系数B,可以得到不同满意解。也可用简 明一点的方法， 如根据起始站的数据和题目要求， 找到一个我们认为较满意的行 车时刻表，以此为初值对此多目标规划进行模矢搜索，寻找更好的解。当B=0.5时，借助 matlab 编程计算(程序见附录二) ，我们找到上行方向的一组满意解：? (u)=0.6215 ，对应的时刻表(首发站)简写为 6.9 2.4 1.5 2.5 5 5.1 4.5 5.5 8.5 6.59 2.8 2.8 7.2 9.6 9.6 9.6 30， (此时的最后余下的人数 z(u)=36) 。第一个数字 6.9表示在第一个时间段 5:0

17、06.00中每6.9分发一辆车 ;第二个数字 2.4表示在第二个时间段 6:007.00中每2.4分发一辆车 ;其余依次类推对应的载客率为： 85.99%；其客运公司的满意度为： ? 1(u)=0.5142 ，乘客的满意度为： ? 2(u)=0.7288 ， 对应的平均等待时间为： z=2.71 分钟；当萨0.5时，下行方向的一组满意解：？(u)=0.5788对应的时刻表(首发站)简写为 26 6 2.4 2.1 3.7 5.9 6.7 8.4 7.5 6.5 5.43 1.9 2.76.3 8.2 8.2 11其客运公司的满意度为： ? 1(u)=0.4161 ， 对应的载客率为： 79.1

18、2%；乘客的满意度为： ? 2(u)=0.7620 ，对应的平均等待时间为：z=2.38分；因上行车次为：235,下行车次为：233;所以由模型所给的公式可得 上下行方向合并载客率为： 82.5%；因上行总乘客为： 57101,下行总乘客为： 51305； 类似可得上下行方向合并平均等待时间为：2.55分；比较上下行双方时刻表， 经计算得共需客车57辆，A13站放55辆车，A0站放2辆车，判断收班时起点站和终点 站车数与早班时相同的方法很简单， 即来回车数相同就可， 我们的解来回车数分 别为235和233，只须很小的调整即可，比如 235减少1车，而233增1车就可。对于 双方利益调节只需改变

19、B的值，这样就可以类似解出相应的指标(见附录一)。六模型的检验：利用仿真思想对模型进行检验，得到的结果与理论计算基本相吻合，载客率为： 81.6%；平均等待时间为： 2.67分；所需客车为 58辆。从而验证了本模型的正确性。七.模型的评价与推广:1.本模型有较大的通用性，有明确完整正确的数学模型。 对乘客下车的分布推导很巧妙，通过研究客车运行的状态推导出准确的载客率和乘客等待时间公式，此公式具 有一般性。此模型也很容易推广，对计算影响客车公司和乘客利益的其它指标也容易推广计 算，如:W tt-1、r淨缶Lt .1为 < 500气 > 50低于50%的运行总公里数台台 u 廿+逐、总

20、运厅公里数其中：&為2上小节典翌行车时刻表所对应的0=0丄678 ,鼻=03339 , =0 2506分析模住雀立中平均等待时间的计專方法.我们同样町计卽等持时间越时的人散比例;m h1设叫）早尙岬为5|分坤勺岛朝为M分钟c超时等待的总人8（ §§总人数"一Fi° 冷£ ?*0-1 +m）幵-卩1。） E （儿（JT） - 'Yf + 眞Q首）比咕-7心7+ 霭Cq（）h工F* +用（訂2 .从我们的解法中易知采集运营数据应遵守的最重要的原则是：（1）调查数据阶段应多密度发一些客车，以保证乘客到达分布和离去分布 的准确性。若发车

21、太少会影响乘客到达流和离去流的数据统计。（2）按原统计时间为一小时统计人数，这样误差较大，可改为按半小时时间段统计人数。这样能更好的反映乘客到达和离去的概率分布。当然若选太小的 时间段统计也不现实，且统计稳定性会变差。纵观全文，可以看出我们彻底揭开了客运调度问题的神秘面纱，本模型可作为解决客运调度问题的完美经典的解法。参考书目：1.周义仓，数学建模实验，西安交通大学岀版社2.运筹学教材编写组，运筹学，清华大学岀版社附录一（权重不同时各满意解的情况）3=0.75乘客平均等待时间（分钟）乘客满意度客车载客率公司满意度车次平衡度上行方向4.51350.54870.92310.60452180.590

22、5下行方向3.28200.67180.81770.45392250.5084全天综合3.93070.60700.86960.52804430.5477备注所需车数:55起始点分布:A0: 10 A13: 453=0.25乘客平均等待时间（分钟）乘客满意度客车载客率公司满意度车次平衡度上行方向1.7350.82650.76670.38112620.7151下行方向1.79050.82090.703390.29062620.6883全天综合1.76140.82380.73500.33585240.7018备注所需车数:62起始点分布:A0: 4 A13: 583=0.25乘客平均乘客满意客车载客公

23、司满意车次平衡度等待时间度率度（分钟）上行方向2 .7120.72880.85990.51422350.6215下行方向2.380.76200.79120.41612330.5891全天综合2.55490.74450.82570.46544680.6049备注所需车数:57起始点分布:A0: 2 A13: 55附录二:（主要程序）程序一 :JM2001B1.m (上行方向的发车时刻表)time=0;z=0.01;peo=zeros(1,14);bb=2;b=1;peo2=zeros(1000,14);peo 1= peo2;hh=1;Mx=;PE=;wait=0;Tx=zeros(1,14);

24、c=1;x=0.5;TX仁6.9 2.4 1.5 2.5 5 5.1 4.5 5.5 8.5 6.5 9 2.8 2.8 7.2 9.6 9.69.6 30;A13A0;jm2001T1;for h=5:22b=1;TTx=TT(13*(h-5)+1:13*(h-4),:);for t1=(h+z):z:h+1peo=peo+P(rou nd(t1-5)/z),:);PE=PE;peo;if t1<(23-0.729)if abs(t1-h-(TX1(hh)/60)*b)<=zif peo(1)<=120 peo1(c,1)=peo(1);peo(1)=0;else peo(

25、1)=peo(1)-120;peo1(c,1)=120;e ndTx(c,:)=t1,tt+t1; c=c+1; b=b+1;endendif abs(t1-23+0.729)<=zif peo(1)<=120 peo1(c,1)=peo(1);peo(1)=0;else peo(1)=peo(1)-120;peo1(c,1)=120;endTx(c,:)=t1,t1+tt;endTx1=; Tx1=Tx;bb0=;cc0=;Tx1=(round(Tx-t1)*100);bb0=ceil(find(Tx1')/14);cc0=find(Tx1')-14*(bb0-1

26、);for i=1:size(bb0,1)bb=bb0(i);cc=cc0(i);if cc>=2for jj=2:ccpeo2(bb,cc)=peo2(bb,cc)+peo1(bb,jj-1)*TTx(jj-1,cc); . endif peo(cc)>(120-sum(peo1(bb,1:cc-1)+sum(peo2(bb,1:cc)peo1(bb,cc)=120-sum(peo1(bb,1:cc-1)+sum(peo2(bb,1:cc);else peo1(bb,cc)=peo(cc); endMx(bb,cc)=sum(peo1(bb,1:cc-1)-peo2(bb,1:c

27、c-1);peo(cc)=peo(cc)-peo1(bb,cc);endendtime=time+z*sum(peo);endhh=hh+1;endTxa=Tx;程序二 :JM2001B2.m ( 下行方向的发车时刻表 )time=0;z=0.01;peo=zeros(1,13);bb=2;b=1;peo2=zeros(1000,13); peo1=peo2;hh=1;Mx=;PE=;wait=0;Tx=zeros(1,13);c=1; x=0.5;TX2=26 6 2.4 2.1 3.7 5.9 6.7 8.4 7.5 6.5 5.4 3 1.9 2.7 6.3 8.28.2 11;A0A1

28、3;jm2001T2;for h=5:22b=1;TTx=TT(12*(h-5)+1:12*(h-4),:);for t1=(h+z):z:h+1peo=peo+P(round(t1-5)/z),:); PE=PE;peo;if t1<(23-0.7305)if abs(t1-h-(TX2(hh)/60)*b)<=zif peo(1)<=120 peo1(c,1)=peo(1);peo(1)=0;else peo(1)=peo(1)-120;peo1(c,1)=120;endTx(c,:)=t1,ttt+t1; c=c+1; b=b+1;endendif abs(t1-23+0.7305)<=zif peo(1)<=120 peo1(c,1)=peo(1);peo(1)=0;else peo(1)=peo(1)-120;peo1(c,1)=120;en