公交车调度问题

1关于公交车的调度问题摘要：本文主要是研究公交车调度的最优策略问题。我们建立了一个以公交车的利益为目标函数的优化模型，同时保证等车时间超过10分钟（或者超过5分钟）的乘客人数在总的等车乘客数所占的比重小于一个事先给定的较小值。首先，利用最小二乘法拟合出各站上（下）车人数的非参数分布函数，求解时先用一种简单方法估算出最小配车数43辆。然后依此为参照值，利用Maple优化工具得到一个整体最优解：最小配车数为48辆，并给出了在公交车载客量不同条件下的最优车辆调度方案，使得公司的收益得到最大，并且乘客等车的时间不宜过长，最后对整个模型进行了推广和评价，指出了有效改进方向。关键词：公交车调度；优化模型；最小二乘法问题的重述：公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。下面考虑一条公交线路上公交车的调度问题，其数据来自我国一座特大城市某条公交线路的客流调查和运营资料。该条公交线路上行方向共14站，下行方向共13站，第3-4页给出的是典型的一个工作日两个运行方向各站上下车的乘客数量统计。公交公司配给该线路同一型号的大客车，每辆标准载客100人，据统计客车在该线路上运行的平均速度为20公里/小时。运营调度要求，乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟，车辆满载率不应超过120%，一般也不要低于50%。试根据这些资料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益；等等。如何将这个调度问题抽象成一个明确、完整的数学模型，指出求解模型的方法；根据实际问题的要求，如果要设计更好的调度方案，应如何采集运营数据。基本假设1）该公交路线不存在堵塞现象，且公共汽车之间依次行进，不存在超车现象。2）公共汽车满载后，乘客不能再上，只得等待下一辆车的到来。3）上行、下行方向的头班车同时从起始站出发。4）该公交路线上行方向共14站，下行方向共13站。5）公交车均为同一型号，每辆标准载客100名，车辆满载率不应超过120%，一般也不要低于50%。6）客车在该路线上运行的平均速度为20公里/小时，不考虑乘客上下车时间。7）乘客侯车时间一般不超过10分钟，早高峰时一般不超过5分钟。28）一开始从A13出发的车辆，与一开始从A0出发的车辆不发生交替，两循环独立。9)题目所给的数据具有一定的代表性,可以做为各种计算的依据。符号说明Na：从总站A13始发出的公交车的总次数（上行方向）Nb：从总站A0始发出的公交车的总次数（下行方向）T1：上行方向早高峰发车间隔时间T2：上行方向平时发车间隔时间T3：上行方向晚高峰发车间隔时间T4：下行方向早高峰发车间隔时间T5：下行方向平时发车间隔时间T6：下行方向晚高峰发车间隔时间Ta（i，j）：第i辆车到达第j站的时刻N1（i，j）：在j站离开第i辆车的乘客数Ne（i，j）：在j站上第i辆车的乘客数D（j，j-1）：第j站与第（j-1）站间距f1（j）：上行方向第j站的上车乘客的密度函数g1（j）：上行方向第j站的下车乘客的密度函数f2（j）：下行方向第j站的上车乘客的密度函数g2（j）：下行方向第j站的下车乘客的密度函数G：一天内公交公司的总收入A：公交车出车一次的支出，为定值B：公交公司每天的固定支出，为定值i：i=1,2,3,为一小概率事件的概率N（t）：某车站全天的上（下）车乘客数3qt：第t时间段此站的上（下）车人数Q（i，j）：第i辆车到达第j站时的车上人数建模前的准备：1）对问题的初步分析我们考虑三组相关的因素：公共汽车，汽车站与乘客对模型的影响。ⅰ）与公共汽车有关的因素：离开公共汽车总站的时间，到达每一站的时间，在每一站下车的乘客数，在每一站的停留时间，载客总数，行进速度等。ⅱ）与车站有关的因素：线路上汽车的位置，车站间距，乘客到来的函数表示，等车的乘客数，上一辆车离开车站过去的时间等。ⅲ）与乘客有关的因素：到达某一车站的时间，乘车距离（站数），侯车时间等。2）曲线的拟合分析样本数据，可知对于某车站全天的上（下）车乘客数N（t）是时间t的递增函数，N（t）=N（t-1）+qt，其中qt为第t时间内此站的上（下）车人数，我们可以由此来拟合其分布函数。由样本数据知每一车站每天有两次波峰，故根据最小二乘法将分布函数拟合为关于t的五次多项式。分析与建模分析样本数据，在上行方向22：00—23：00和下行方向5：00—6：00的上、下车人数较其它时段偏小，为使模型更好地体现普遍性，我们单独讨论上面的两个时段。易知各站只需一辆车就可以满足需求。由题设要求可知，所求方案须兼顾乘客和公交公司的利益，但实际上，不可能同时使双方都达到最优值。因此我们将公司利益作为目标函数，将乘客利益作为约束条件。公司利益Z=G-(Na+Nb)*A-B（其中G为总收入，因样本数据为典型工作日，因而可以看作定值，(Na+Nb)*A+B为支出。）Na=[1T60*4+260*7T+3T60*2+260*5T]Nb=[5T60*7+460*3T+5T60*4+660*4T]乘客的利益在此处即为侯车时间，由于乘客侯车时间带有随机性，不可能总小于（或大于）某个定值，因而可用概率来描述乘客的利益，得如下模型：I：maxZ=G-(Na+Nb)*A-B4s.t.P{等待时间t10分钟的人}1P{Q（i，j）+Ne（i，j）—N1（i，j）120}2P{Q（i，j）+Ne（i，j）—N1（i，j）50}3或P{等待时间t5分钟的人}1P{Q（i，j）+Ne（i，j）—N1（i，j）120}2P{Q（i，j）+Ne（i，j）—N1（i，j）50}3模型的简化与求解：对于原模型，由于约束条件难以表示为明确的函数表达式，给实际求解过程中带来相当大的困难，因而对其简化。1）发生间距时间的求解分析原目标值Z，易知maxZmaxT其中T为发车间距时间，它因不同的时间段而不同。下面我们就以每小时为一时间段来求解，且假设乘客上下车瞬间完成，即不考虑上下车时间。应题设要求，乘客侯车时间一般不超过10分钟，早高峰时一般不超过5分钟。我们引进概率参数，用以控制侯车时间超过10分钟（或5分钟）的人数在总侯车人数的比重。对于满载率不低于50%，由于目标值为maxZ，则可以忽略不考虑，可得如下模型：Ⅱ:maxT=ts.t.),1(),()(10),1(),()(jiTjiTjijiTjiTidtfdtjfQ(i,j)+),1(,()(jiTjiTidtjf）-),1(),()(jiTjiTidtjg120或),1(),()(5),1(),()(jiTjiTjijiTjiTifdtjf5Q(i,j)+),1(0,()(jiTjiTidtjf-),1(),()(jiTjiTidtjg120t0,i=1,2分析样本数据可以发现：ⅰ）对于上行车道，A13，A12，A11，A10，A9的上车人数下车人数，对于其余站点则相反；ⅱ）对于下行车道，A0，A2，A3，A4的上车人数下车人数，而其余站点则相反；因而对于约束条件，只需取前5个（或4个），对于模型Ⅱ，我们可以根据拟合分布函数Fi，Gi将约束条件转化为T的函数，利用Matlab软件容易求解。分析Ⅱ所得结果，易知在高峰时间段中，结果T有较大误差，是由于拟合函数的误差而引起的。为了减小误差，可以分段拟合分布函数Fi，Gi。为计算方便，可以认为在每小时内，每站的到达人数与时间成正比，每站的下车人数亦与时间成正比，即Fi（t）=ki*t，Gi（t）=pi*t,ki,pi为斜率，令=5%，于是将模型简化为：Ⅲ：maxT=ts.t.19t-2000(或19t-1000)k1*t-1200k1*t+k2*t-p2*t-1200k1*t+k2*t-p2*t+k3*t-p3*t-1200k1*t+k2*t-p2*t+k3*t-p3*t+k4*t-p4*t-1200k1*t+k2*t-p2*t+k3*t-p3*t+k4*t-p4*t+k5*t-p5*t-1200t0（平时及晚高峰取19t-2000，早高峰取19t-1000）当上行时，取所有约束条件，下行时取前5个约束条件。模型Ⅲ为线性规划，利用Matlab求解，结果如下：发车间距时间表（单位皆为分钟）时段5~66~77~88~99~1010~1111~1212~1313~14上行10.522.451.4342.8485.49626.03525.31375.64796.9231下行/6.9292.6162.23393.9516.58747.30228.67478.08时段14~1515~1616~1717~1818~1919~2020~2121~2222~23上行8.17258.26643.37552.59748.026810.52610.52610.526/6下行7.0795.533.27871.99342.97896.59959.2199.302310.5263对模型Ⅱ、Ⅲ进行误差分析在上文中，我们已提及到模型Ⅱ的误差，究其原因主要是由于拟合函数的误差引起的。如上行方向A13站7：00—8：00，发车间距T=5.26分，显然此时的T无法使3626名乘客正常运行，而此时由拟合函数算出来的乘客总数为2023。误差△=3626-2023=1603(人）。为使误差减小，因而可以对函数进行分段拟合。如模型Ⅲ中，以每小时为一段。此时求解的结果，能很好的使样本数据的乘客正常运行。当然此时的解亦有误差，因而T可有一波动范围。在此解的情况下，容易知道客车满载率120%（约束条件）。乘客等待时间过长的概率5%。空载情形，大部分只有在最后一站方出现空载情形（满载率50%）。2）对无滞留乘客条件下的最小配车数初步求解我们对数据作进一步的处理，估算出每一段上、下行所需的最小配车数，从而得出一天内所需配备的最小车辆数。为最小配车数的求解找到一个参照值。我们首先考虑以一小时为时间间距来考查一天的最小配车数（即设公交车在各车站所停的时间为一定值）。分析数据可知满足各站均无滞留乘客，各发车时刻均有车可发的最小配车数应为65辆车。这只是一个初步解，为得到进一步的精确解，我们考虑以44分为一时间间距，通过拟合的分布函数得到各车满载时各时段的所需最小配车数。满足各站无滞留乘客，各发车时刻均有车可发的最小配车数为43辆。3）公交公司调度方案模型的建立与求解ⅰ）我们制订调度方案，应使公交公司和乘客双方的利益达到均衡。一方面公交公司希望配置尽可能少的汽车以降低固定成本，又要在保证接送全部乘客的前提下尽可能减小出车次数，以降低可变成本；另一方面，应实现乘客满意，即规定发车时段必定有车可乘，尽可能缩短等车时间。ⅱ)制订调度方案时，我们发现有下难点：A）一方车站到了发车时间但没有车可发，另一方面却有囤积。此问题有两种解法：一是购置新车，二是调节班次。前者使成本变高，后者引起连锁反应，使整个计算量变大且有可能求不出最优解。B）若迫不得已要改变总车配置数，必须调动各个时间间隔使车优化配置，全局最优化。这是一个最优问题。C）总配置数一定，调节总车班次使总车次数增加越少，总车班次数越小，则求得的解越优。这又是一个极值优化问题。为解决以上难点，我们建立了一个线性规划模型，用Maple优化软件求解。设某j时间段发车数为Xij，车站内车辆总数为Ci。i=下行始发站发车上行始发站发车10m为总配置数，z为总班次minz=18110jjijX7s.t.C0+Ci=mX11=C1-X110X01=C0-X010Xj1=C1+110jmmX-jmmX110Xj0=C0+111jmmX-jmmX1001810mmX=1811mmX1）60分—120人调度方案