公交车调度方案的优化模型

公交车调度方案的优化模型摘要本文通过对某市某条公交线路的客流调查和运营资料分析，建立公交车调度方案的优化模型，使公交公司在满足一定的社会效益和获得最大经济效益前提下，给出了理想公交车调度方案。对于问题一，模型中建立了最大客容量，发车车次数的数学模型，运用决策方法给出了各时间段最大客容量数，在满足客车载满率及载完各时段所有乘客情形下，得出每天最少车次数为462次，最少车辆数为60辆；并给出了整分发车时刻表(见附件四)。模型中，用层次分析法分析乘满意度为mc= ，在公交车最大载客量分别为120、100、50时乘客和公交公司的满意度mc、mg 。拟合得出乘客及公交公司满意度对应的关系式，建立目标函数max=(mc+mg)-|mc-mg|，使双方满意度之和达到最大，同时双方满意度之差最小，得到上下行的最优满意度（0.8688，0.8688），此时公交车调度为474次50辆。对于问题二，交待了综合效益目标函数及整数规划法求解流程。关键词：公交调度 层次分析法满意度整数规划一、问题的重述公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。公交公司制定一个公交车调度方案需要考虑各方面的因素。我国一座特大城市某条公交线路情况，一个工作日两个方向各个站上下车的乘客数量统计表如表1、表2所示。已知运营情况与调度要求如下：（1）公交线路上行方向共14站，下行方向共13站。（2）公交公司配给该线路同一型号的大客车，每辆标准载客100 人，据统计客车在该线路上运行的平均速度为20公里/小时，车辆满载率不应超过 120%，一般也不要低于50%。（3）乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟。需要解决的问题：（1）试根据这些资料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益；等等。（2）如何将这个调度问题抽象成一个明确、完整的数学模型，指出求解模型的方法。二、问题的分析本问题要求我们设计一个公交车调度是要同时考虑到完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益等诸多因素。如果仅考虑提高公交公司的经济效益，则只要提高公交车的满载率，运用数据分析法可方便地给出它的最佳调度方案；如果仅考虑方便乘客出行，只要增加车辆的次数，运用统计方法同样可以方便地给出它的最佳调度方案。显然这两种方案时对立的。于是我们将此题分成两个方面，分别考虑：公交公司的经济利益，记为mg：公司的满意度；乘客的等待时间和乘车的舒适度，记为mc：乘客的满意度。公交公司的满意度取决于每一趟车的满载率，且满载率越高，公交公司的满意度越高；乘客的满意度取决于乘客等待的时间和乘车的舒适度，而乘客等待时间取决于车辆的班次，班次越多等待时间越少，满意度越高；乘客的舒适度取决于是否超载，超载人数越少，乘客越满意。很明显可以知道公交公司的满意度与乘客的满意度相互矛盾，所以我们需要在这个因素中找出一个合理的匹配关系，使得双方的满意度达到最好。三、符号说明aijk：上行或下行第j时段第k站上车人数。bijk：上行或下行第j时段第k站下车人数。lij：上行或下行第j时段最大客流量。zij：上行或下行第j时段平均载客量。cij：上行或下行第j时段的整车次。C：日所需总发车车次。sij：上行或下行第j时段平均发车时差。Fsij：上行或下行第j时段发车时差为小数时，向下取整数。Csij：上行或下行第j时段发车时差为小数时，向上取整数。mci：上行或下行乘客的日平均满意度。mcij：上行或下行第j时段乘客满意度。tij：上行或下行第j时段乘客等车时间。mct：乘客对等车时间的满意度。mcw：乘客对乘车舒适度的满意度。mgi：上行或下行公交公司日平均满意度。mgij：上行或下行第j时段公交公司的满意度。i=1：表示上行运动（此时k=1，2，3，.，14）。i=2：表示下行运动（此时k=1，2，3，.，13）。j=1，2，.，18：表示公交车从5：00到23：00运行的各个时间段。四、模型的假设1)交通情况、路面状况良好，无交通堵塞和车辆损坏等意外情况。2)公交公司在正常营业期间，最迟发车时间间隔不超过20分钟。3)公交车发车时间间隔取整分钟，行进中公交车彼此赶不上且不超车，到达终点站后掉头为始发车。4)乘客在每段时间内到达车站的人数可看作是负指数分布，乘客乘车是按照排队的先后有序原则进行的，且不用在两辆车的时间间隔内等待太久。5)“人数统计表”中的数据来源、可信、稳定、科学。6)乘车票价为2元，不因乘车远近而改变。7)为了便于叙述，本文把公交车运营时间5：0023：00分为18个时间段，分别为1，2，.，18 。五、模型的建立与求解5.1 模型问题1为设计便于操作的公交车调度方案。根据表1、表2中的一个工作日两个方向各个站上下车的乘客数量统计情况，要满足公交车载完每个时间段的乘客数，则必须能载完各个时段乘客人数达到最大时的人数，由此建立模型，来确定发车时刻表，计算需要的车辆数，对问题依次进行分析。(1)上下行各时段的最大客容量，建立模型如下：lij= (j=1，2，.，18)运用模型和表1、表2中的上下乘客数，算出上下行各个时间段内最大客容量。上行方向：701，2943，5018，2705，1528，1193，1355，1200，1040，881，871，2133，2772，897，464，410，275，19。下行方向：27，1039，2752，3223，1822，1093，986，830，891，1017，1302，2196，3612，2417，1091，781，774，337。其对应的各个时间段最大客容量的直方图：（图一） (2)各个时段的发车次：由于公交车每辆标准载客100 人，车辆满载率在50%120%之间，当zij接近120人，由模型： cij= (其中是正整数)C= 可以计算出各时间段的发车次数cij，对于早晚时段，上行22：0023：00最大客容量数为19人、下行5：006：00最大客容量数为27人，但公交公司要满足最迟不超过20分钟发一趟车，于是发车车次依次如下：上行：6，25，42，23，13，10，12，10，9，8，8，18，24，8，4，4，3，4 。下行：3，9，23，27，16，10，9，7，8，9，11，19，31，21，10，7，7，4 。于是得到全天的总最少发车次数C=231+231=462 。(3)安排发车时间间隔：取每个时段60除以车次数，得到该时段的平均发车时间间隔：sij=60/ cij ，依次如下：上行：10 ，2.4 ，1.4 ，2.6 ，4.6 ，6 ，5 ，6 ，6.7 ，7.5 ，7.5 ，3.3 ，2.5 ，7.5 ，15 ，15 ，20，20 。下行：20，6.7，2.6 ，2.2 ，3.8 ，6 ，6.7 ，8.6 ，7.5 ，6.7 ，5.5 ，3.2 ，1.9 ，2.9 ，6 ，8.6 ，8.6， 20 。由sij的值有小数出现，而现实中列车、客车等时刻表的最小单位为分钟，故为了调度方案的实际可操作性，应该调整为整分间隔。当sij取整数时，可直接安排发车cij次；当sij取小数时，不妨设Fsij和Csij间隔的车次为mij ,nij；可知FsijsijCsij，由模型： （i=1，2；j=1，2，.，18）可以求出以Fsij为间隔的班次mij和以Csij为间隔的班次nij，再分别以发车间隔为Fsij和Csij，兼顾发车密度，为了使得安排在同时段线路的车辆不宜过多，我们对调整的整分发车间隔对应发车量的先后顺序作调整，将相邻时间段内发车间隔相等的班次尽量安排在一起，得出了全天（一个工作日）内的公交车调度方案，结果见附件（四）。(4)日需车辆数由汽车平均速度20公里/小时和A0A13的距离14.61公里、A13A0的距离14.58公里，可求得车辆从起点站运行到终点站平均用时为44分钟；又由假设可知车辆到达终点后立即掉头返回。由于早高峰乘客数最多，故此时车辆实际占用数应是当日的上限，若公交公司日派车最少时能达到这个用车上限，则能满足日需车辆数。早高峰段最大用车数：考虑到最少车辆时满足上下行的公交车发车要求，上行方向比下行方向车辆要多发车，我们根据各时段的发车车次cij，调整后的发车间隔Fsij和Csij，公交车单程运行时间44分钟，动态分析每时段A0、A13站可用公交车数量和发车情况如图二。5：006：00上行下行的发车情况：5：006：00下行A0到达A13车辆数起点站车辆数终点站车辆数5：006：00 从A13站发车c11次5：006：00从A0发车c21次5：006：00上行A13到达A0车辆数上行下行6：007：00上行下行的发车情况：6：007：00下行A0到达A13车辆数A13站待发车辆数A0站待发车辆数5：006：00下行A0到达A13车辆数6：007：00从A0发车c22次5：006：00上行A13到达A0车辆数6：007：00 从A13发车c12次上行下行6：007：00上行A13到达A0车辆数由上可分析每段时间的公交车发车情况，得到高峰车辆实际占用为60辆，A13站车辆数需51辆，A0站车辆数需9辆，也即当天共需开动的车辆最少为60辆。5.2模型 1满意度分析根据问题，我们在设计两个起点站的发车时刻表时，应该考虑此时刻表带给公交公司和乘客两方的利益，即公交公司和乘客对应的日平均满意度mgi和mci，各时段的满意度mgij和mcij，我们对影响各自满意度的因素做分析。(1)公交公司的满意度取决于公交车的平均载客量，公交车平均载客量越多，公交公司发车车次就少，对公交公司利益就大。在乘客源一定的情况下，影响mgij的主要因素是车上的乘客数即载客量zij，其中，一般情况下50zij120 。我们取各个时段的平均载客量zij的满意度mgij，mgij= 。则公交公司的平均日满意度为各时段的满意度的加权平均值： mgi= (1=1，2；j=1，.，18)(2)乘客的满意度对于乘客，影响mcij的主要因素是乘客的等车时间tij与车上的平均载客量zij 。设mcitj，mciwj分别是各时段乘客因tij与zij的影响而产生的满意度，则mcij即可以表示为： mcij= (mcitj，mciwj) A其中，A是关于因素tij与zij的权重集。考虑到，对于乘客，mcitj，mciwj对mcij的影响不是相等的 ，上下车的乘客都在动态地变化，但对于车辆而言，车辆的满载率达120%时，最大超载的20%由于缺少座位，而注重舒适度的影响，无暇过分顾及等待时间的影响；100%的乘客因为有座，而无需过分考虑舒适，更多的是考虑等车时间的影响。又设A=，其中， ，分别是因素tij, zij的重要程度，用层次分析中的成对比较法， 可知： ，同时，A应满足归一性和非负性，即+ =1， 0可以解得= , = 因此mcij=(mcitj，mciwj) =mcitj+mciwj我们把mcitj，mciwj满意度函数看着是常见的降半梯形分布。 mcitj= mciwj=由每时段的乘客满意度mcij，每时段的乘客最大客容量lij，一天最大客容量人数为，可以算出乘客平均日满意度为各时段的满意度的加权平均值： mci= （i=1，2；j=1，2，.，18）2、数据分析通过对模型的最大客容量（表一）分析。考虑上行问题，可以得出日平均最大容量z1 =1467人，日平均最大容量的标准差1=1768，根据3检验法，可发现模型中的z118 =19人，不满足，故可以看做是奇异值，不予以考虑。同样，对下行问题中的第一时段（27人）也偏离3检验法的可信区间，故应舍弃。3、合理调度情况分析对于公交公司，当满载120人时公交公司最满意，人数越少，满意度越来越低。对于乘客，可知当等车时间不超过5分钟，车辆满载率不超过100%时，乘客满意度为1，随着等待时间增加和车载率的上升，乘客满意度会逐渐下降。我们取当公交车平均载客人数分别为120人，100人，50人时作分析。考虑上行方向，当zij120人，第18时段的数据19人不予考虑，mgij=，则乘客日均满意度mg1=0.9722 。乘客的满意度由模型的发车车次cij和发车时间间隔sij，算出乘客的满意度mc1=0.7334, 当zij100人时，公交公司满意度mg1=0.8116,此时对应的每个时段的发车车次与平均发车时间间隔：8，30，51，28，16，12，14，12，11，9，9，22，28，9，5，5，3，4。S1j：7.5，2，1.2，2.2，3.8，5，4.3，5，5.5，6.7，6.7，2.77，2.2，6.7，12，12，20，20。此时乘客的满意度为mcij=0.9218 。当zij50人时 ，此时公交公司的利益达到最小，相应的乘客满意度会变大，公交公司满意度mg1=0.4207, 乘客满意度mc1=0.9800 ,对应的公交车调度情况：14，58，100，54，30，23，27，24，20，17，17，42，55，17，9，8，5，4。S1j:4.3 ，1.0 ，0.6 ，1.1 ，2，2.6 ，2.2 ，2.5 ，3.0 ，3.5 ，3.5 ，1.4 ，1.1 ，3.5 ，6.7 ，7.5 ，12.0 ，20 。a、考虑上行问题：根据公交公司的满意度和乘客的满意度的对应关系，(0.9722，7334)( 0.8116，0.9218)( 0.4207，0.9800)，可以利用二次拟合得出公交公司和乘客的函数f(mg1)： mc1=-1.8737mg12+2.1694mg1+0.3953 ()拟合曲线如图三：本题要求我们最大照顾到乘客和公交公司双方的利益，这就要求R=mc1+mg1能尽可能取大，即满足双方的利益最大化；同时我们也要使得双方满意度的差不能太大，即W=| mc1-mg1|尽可能取小.于是我们建立目标函数max=R-W= mc1+mg1-| mc1-mg1|，寻找出满足双方的满意度之和最大同时满足之差最小的最优满意度。联系函数分析，求的上行行驶时乘客和公交公司双方的匹配问题的最优满意度为mc1= 0.8674 , mg1=0.8674 .可以计算出这种情况下，各时段车次与发车时间间隔：c1j：6，25，42，23，13，10，12，10，9，8，8，18，24，8，4，4，3，4 。s1j：10，2.4，1.4，2.6，4.6，6，5，6，6.7，7.5，7.5，3.3，2.5，7.5，15，15，20，20。b、下行问题：此时i=2，同理利用二次拟合的到乘客满意度与公交公司的满意度函数关系：mc2=-1.9617mg22+2.2797mg2+0.3720 ()拟合曲线如图四：故可求得公交公司和乘客的日最优满意度是mc2=0.8702，mg2=0.8702 。所以一天上下行乘客和公交公司的平均满意度为（0.8688，0.8688）运用逆向思维，根据日最优满意度，找出最优的调度方案，可得到下行各时段车次c2j和发车时间间隔s2j。 5.3模型很明显此问题可看做是一个排队随即服务系统，我们把汽车看做是“顾客”，将各个车站看作是“服务台”，则此公交车系统可看作是一个顾客不消失的、单通道多级服务台串联的排队系统。因此，这里所遇到的，主要是排队问题。归纳起来，需要考虑三种活动。(1)首站发车活动：根据发车时刻表确定。(2)到达中途站活动：在中途站主要考虑和计算上下车人数、车上的总人数和上下车时间。(3)到达终点站掉头活动：在终点站根据发车时刻确定。我们先考虑上行时乘客在站的逗留时间，即乘客在A1k站的等待时间，它包括相邻两趟车到达A1k站的时间间隔q1jk（即发车间隔），和乘客上下车的服务时间p1jk。因此假设每个乘客上下车时间 不计，即p1Jk=0，可以得出q1jk=60/ci，sjk=p1jk。故此问题可以转化为：满足下列条件下的公交车公司全天的总利益取最大的规划问题： 乘客等待时间在一般时间段不超过10分钟。 早高峰时间段不超过5分钟。 各个时间段内的最大满载率不超过120%。 各个时间段内的最小满载率不低于50%。又公交车公司全天的总利益为全天所有车辆运行公里数最小，因为线路长度一定，只要考虑发车车次即可得出目标函数：min(z)= s.t.这个模型是整数规划模型，在满足各种约束条件的情形下，寻求全天发车车次的最小值，我们可以用lingo编程求解，算法流程图（如图五）六、模型的讨论与检验6.1模型的讨论一个好的模型用于解决一类问题时与实际的结果不会有太大的出入。模型是从实际问题出发，没有涉及太高深的数学知识，用常规方法做出的结果与实际情况较为统一。模型中涉及公交公司的满意度和乘客的满意度的插值拟合，我们对其合理性进行分析。讨论上行方向，当平均载客量zij75人时 ，根据模型中的算法，得出各时段发车车次和发车时间间隔，及这种情况下的双方的满意度。c1j：10，40，67，37，21，16，19，16，14，12，12，29，37，12，7，6，4 。s1j：6，1.5，0.9，1.6，2.9，3.8，3.2，3.8，4.3，5，5，2.1，1.6，5，8.6，10，15。用此数据算出公交公司的满意度mg1=0.6158 ，乘客的满意度mc1=0.9679 ，而当利用二次拟合函数关系mc1=-1.8737mg12+2.1694mg1+0.3953 推算出的乘客满意度为1，即满意度达到最大。可以看出拟合函数算出的满意度与实际分析的满意度相差=1-0.9679=0.0221，而对拟合函数整体情况作分析，mc1=-1.8737mg12+2.1694mg1+0.3953取得最大值时为1.0256，可知当满意度最大时mc=1,所以曲线误差率=2.56% 。zij75满意度偏差2.21%小于2.56%，在允许的误差范围内。可知用二次拟合处理的满意度曲线能较好的反映真实的情况，也使得分析问题简单合理。6.2 模型的检验模型是把这一类公交车调度问题抽象成数学模型来表达，从考虑发车车次最小出发，满足各项约束条件，寻求最优解，于是可以利用这个模型来分析此问题，对条件分析可知，约束条件满足两方面，一方面要满足乘客的等车时间早高峰不超过5分钟，其余时段不超过10分钟。对于公交公司方面，也要满足客车的载客率在50%120%之。对于题中的客流量，我们筛选出不合要求的时段，如：上行第17时段、第18时段、下行第1时段。于是我们利用lingo编程（见附件六）。得到的发车车次情况：上行：6，25，42，23，13，10，12，10，9，8，8，18，24，8，6，6，5，4 。下行：3，9，23，27，16，10，9，8，8，9，11，19，31，21，10，7，7，6。一天总发车车次为471辆，因此次解法是在满足乘客的情况下求的最优解，所以乘客的等待时间的满意度为100%，但是从舒适度考虑，上行和下行分别有11和9人不满意。此模型的结果为模型和的中间情况，故此模型的建立是合理的。七、模型的评价与推广1、 优缺点普适性，模型三对任意客流量调查和运营资料都可以给出较优的调度方案。模型不仅接触了较优的调度，而且还得出了该方案照顾到乘客和公交车公司双方利益的程度（即灵敏度）。该模型较稳定，不随某一控制量的微小变化而导致方案的较大改变。易操作性，一方面公交公司的时刻表比较合理可行，另一方面驾驶员能容易记住自己的上班时间，以避免时间表混乱而引起误车现象。不足之处是用光滑曲线拟合的方法无法模拟真实的客流量曲线。2、模型推广根据前面的模型所建立的运输系统，可以很好地解决公交线上公交车的调度问题，然而，在建模过程中，简化了许多因素，因而与实际问题有偏差。因此，要想建立更好的调度方案，可以对一条实际运营的公共汽车的运行过程进行计算机模拟，将调查得到的实际数据输入计算机程序，便可以得出更优的调度方案。八、参考文献吴建国等，公交车调度方案的优化模型，建模案例精编，中国水利水电出版社，2005年第一版附件附件一：上行各时段对应的最大客容量（C+程序）：#includeusing namespace std;int main()int i,j;int carray18;int darray18=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;int xarray1814=371,60,52,43,76,90,48,83,85,26,45,45,11,0,1990,376,333,256,589,594,315,622,510,176,308,308,68,0,3626,634,528,447,948,868,523,958,904,259,465,454,99,0,2064,322,305,235,477,549,271,486,439,157,275,234,60,0,1186,205,166,147,281,304,172,324,267,78,143,162,36,0,923,151,120,108,215,214,119,212,201,75,123,112,26,0,957,181,157,133,254,264,135,253,260,74,138,117,30,0,873,141,140,108,215,204,129,232,221,65,103,112,26,0,779,141,103,84,186,185,103,211,173,66,108,97,23,0, 625,104,108,82,162,180,90,185,170,49,75,85,20,0,635,124,98,82,152,180,80,185,150,49,85,85,20,0,1493,299,240,199,396,404,210,428,390,120,208,197,49,0,2011,379,311,230,497,479,296,586,508,140,250,259,61,0,691,124,107,89,167,165,108,201,194,53,93,82,22,0,350,64,55,46,91,85,50,88,89,27,48,47,11,0,304,50,43,36,72,75,40,77,60,22,38,37,9,0,209,37,32,26,53,55,29,47,52,16,28,27,6,0,19,3,3,2,5,5,3,5,5,1,3,2,1,0;int yarray1814=0,8,9,13,20,48,45,81,32,18,24,25,85,57,0,99,105,164,239,588,542,800,407,208,300,288,921,615,0,205,227,272,461,1058,1097,1793,801,469,560,636,1871,1459,0,106,123,169,300,634,621,971,440,245,339,408,1132,759,0,81,75,120,181,407,411,551,250,136,187,233,774,483,0,52,55,81,136,299,280,442,178,105,153,167,5223,385,0,54,58,84,131,321,291,420,196,119,159,153,534,340,0,46,49,71,111,263,256,389,164,111,134,148,488,333,0,39,41,70,103,221,197,297,137,85,113,116,384,263,0,36,39,47,78,189,176,339,139,80,97,120,383,293,0,36,39,57,88,209,196,339,129,80,107,110,353,229,0,80,85,135,194,450,441,731,335,157,255,251,800,557,0,110,118,171,257,694,573,957,390,253,293,378,1228,793,0,45,48,80,108,237,231,390,150,89,131,125,428,336,0,22,23,34,63,116,1088,196,83,48,64,66,204,139,0,16,17,24,38,80,84,143,59,34,46,47,160,117,0,14,14,21,33,78,63,125,62,30,4,41,128,92,0,3,3,5,8,18,17,27,12,7,9,9,32,21;int barray1814;int aarray1814;for(i=0;i18;i+)j=0,j14;dobarrayij=xarrayij-yarrayij;j+;while(barrayij0);barrayij+=barrayij=0;for(i=0;i18;i+)aarrayi0=barrayi0;for(j=1;j14;j+)aarrayij=aarrayij-1+barrayij;for(i=0;i18;i+)for(j=0;jdarrayi)darrayi=aarrayij;carrayi=darrayi;for(i=0;i18;i+)coutmax=carrayi =6;c2=12;c3=12;c4=12;c5=6;c6=6;c7=6;c8=6;c9=6;c10=6;c11=6;c12=6;c13=6;c14=6;c15=6;c16=6;c17=6;50*c1=701;50*c2=2943;50*c3=5018;50*c4=2705;50*c5