公交车调度方案

公交车调度方案陈爽 刘伟 舒传华摘要： 本文要求在照顾乘客和公交公司双方利益的前提下，给出一个合理的调度方案。我们以乘客的满意率、公交公司的满载率和所需车辆数目为目标函数，求它们的加权和的最大值。由于双方的利益是矛盾的，如何找到一个令双方都能接受的解是问题的关键。我们找出了与双方利益均密切相关的因素发车间隔，通过对发车间隔的寻优，来解决这个问题。在寻找发车间隔的过程中，针对各个时间段内始发站上车人数的不同将发车间隔按早晚高峰期、低谷期、中间期，分成四个时期，采用搜索算法进行求解。结果为早高峰期发车间隔为2分钟、中间期为7分钟、晚高峰期为2分钟、低谷期为10分钟，上行方向和下行方向的对应时期发车间隔相等；根据发车间隔，得到两个始发站的发车时刻表；计算出所需的最多车辆数目为51辆,总车次为575次，乘客满意率为95%，满载率为59.03%；提供了一份详尽的调度方案并对其可行性进行了论证。我们又对模型进行了改进。方案是对原来划分的四个时期加以细化，计算出所需的最多车辆数目为47辆；总车次为432次；乘客满意率为92.24%；满载率为70.49%。接着讨论了各时间段的行驶速度不同的发车方案和加开区间车的方案。另外还进行了参数灵敏度分析，得到了不同的时期的发车间隔变化对于模型的影响程度，其中t1的影响程度最大。一、问题重述公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。下面考虑一条公交线路上公交车的调度问题，其数据来自我国一座特大城市某条公交线路的客流调查和运营资料。该条公交线路上行方向共14站，下行方向共13站，第3-4页给出的是典型的一个工作日两个运行方向各站上下车的乘客数量统计(数据从略)。公交公司配给该线路同一型号的大客车，每辆标准载客100 人，据统计客车在该线路上运行的平均速度为20公里/小时。运营调度要求，乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟，车辆满载率不应超过120%，一般也不要低于50%。试根据这些资料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益；等等。如何将这个调度问题抽象成一个明确、完整的数学模型，指出求解模型的方法；根据实际问题的要求，如果要设计更好的调度方案，应如何采集运营数据。二、问题的假设1、 公交车运行的平均速度为总路程除以总时间，总时间包括行驶时间和乘客上下车的时间。2、 到达任一车站的乘客人数在一个小时内服从均匀分布。3、 每辆车最多可以坐120名乘客，并且乘客对这种情况不会抱怨。4、 公交公司只有一个车库在上行方向的起始站处，每天早上运营开始前所有车辆均集中在上行方向的始发站，晚上所有车均回到车库。但两个方向的始发站各有一个停车场，以共白天停车使用。三、符号的说明 乘客的满意率 P= 满载率 C= （总车次数指一天发多少班次） 第i站全天所经过的车辆数 （i=A0，A1，A2，A13） 第i站全天所经过的车辆中满载率小于50%的数目 空载率 E=n 公交公司进行一天的运营所需的总车辆数四、问题的分析和模型的建立寻找调度方案，首先要找出发车间隔。根据给出的数据，做出每个时间段内始发站上车人数的直方图如下。 （上行方向） （下行方向）从上行方向图中可以看出，一天之内有两个明显的高峰分别是早高峰期6：00-10：00，晚高峰期16：00-19：00；两个高峰的中间10：00-16：00称为中间期；5：00-6：00和19：00-23：00称为低谷期。同理，得到下行方向早高峰期为7：00-10：00、晚高峰期为15：00-19：00、中间期为10：00-15：00、低谷期为5：00-7：00和19：00-23：00。由于题目中对高峰期和非高峰期乘客等待时间的要求不同，我们将这四个时期的发车间隔取为不同的值，分别记为t1：早高峰期发车间隔t2：中间期发车间隔t3：晚高峰发车间隔t4：低谷期发车间隔衡量一个调度方案的好坏，是看该方案是否能使乘客和公交公司双方的利益尽可能达到最大。我们用乘客的满意率来衡量顾客的利益，乘客满意是指乘客的等待时间在早高峰期不超过5分钟，其它时段不超过10分钟；否则，认为乘客不满意。它是t1、t2、t3、t4的函数记为P=P（t1，t2，t3，t4）。我们用满载率和所需车辆总数来衡量公交公司的利益，C、n 均与发车间隔有关，记为C=C（t1，t2，t3，t4）、 n=n（t1，t2，t3，t4）。我们的目标为 s.t P C120%分别是P、C、n的权值。是根据实际情况确定的最小满意度.五、模型的求解1、目标函数的三个组成部分是互相矛盾的,必须相互协调。求解时可先不考虑车辆数目，并将乘客满意率限制在一定范围之内，将其作为约束条件，只对第三个指标求最值。根据实际情况和经验，我们选取P95%。同时可以发现C与发车间隔的变化趋势相同，即发车间隔越大，平均满载率越高。所以问题变为：max C(t1,t2,t3,t4)s.t. P（t1，t2，t3，t4）95%由于在低谷期等车人数很少，不会出现乘客因满载而无法上车的情况，又因为乘客的一般等待时间不能超过十分钟，可令t4=10分钟。因此，我们只要对t1、t2、t3寻找最优值。2、算法流程step1 使得t1、t2、t3在某一范围内变化 step2 模拟一天车辆的运行情况，按照时间间隔t1、t2、t3、t4从上行线站点不断发车。计算车到站时间，按照它所属的时段计算上下车人数，如果所有等车的人都上车，车上会超过120人，则车上人数按120计算，一部分人将继续等候下一辆车。计算在每一站点的车上人数，统计车的总次数。计算在该站点满载率小于50%的车数。求出乘客在每站点的等待时间，判断乘客是否满意，计算满意乘客的人数，并统计所有乘客的人数。step3 求出乘客满意率，客车满载率和空载率。满意率为所有站点满意乘客的人数除以乘客总人数；满载率为所有站点的车上人数除以总车次数再除100；空载率即为所有满载率小于50%的人数除以总车次数。按照满意率大于95%的指标选择使得t1,t2,t3尽可能大的值。 其余步骤与上行线完全相同。六、模型的结果与结果分析在满足一定乘客满意率情况下，分别对上行方向和下行方向使用上面的算法搜索各时期的发车间隔。可以求出在满足顾客满意率大于95%的情况下，上行方向的各时期的最大发车间隔分别为t1=2,t2=7,t3=3,t4=10；下行方向的各时期的最大发车间隔分别为t1=3,t2=8,t3=2,t4=10。可以证明,在一个足够长的时间内,使用不同的发车间隔,比使用相同的较小时间间隔所需要的总车辆数要多。证明过程如下:设两个站点A、B,A站发车间隔为，B站发车间隔为,不妨设3,则在A站就会再次补车，这样+()=2。在两边的发车间隔相等时，发车间隔取,中较小的一个,即t=,这时只需2辆车就可以了。从而证明了我们的结论。分析原因，在总时间足够长时，为保证两边都按各自的时间间隔发车，在发车间隔小的站点要不断的补发车，而在发车间隔大的站点会有车堆积，等待的时间较长。因此这种方法所需的车数多，而且车的利用率比较低。选取上行方向和下行方向对应时间段发车间隔的较小值，即选取t1=2,t2=7,t3=2,t4=10在这种情况下，可以减少每时间段内需要的车辆数，使得调度更方便，同时提高了乘客的满意率，只是在车辆的满载率上有所下降。我们认为，对于公交公司来说，减少车辆数意义更大，所以这样的选取是合理的。得到结果如下表 表1t1t2t3t4CEP2min7min2min10min0.59030.11500.95（一）两个始发站发车时刻表由假设4，上行方向5：00发第1班车，这辆车到达下行方向始发站的时间为5：45，则下行方向始发站在5：45之后有车可供发出，将下行方向发首班车时间定为5：50。当发车间隔不是该时期总时间的约数时,从新的时期开始,以新的间隔发车。由此可得到两边起始站的发车时刻表。上行方向低谷期5:00-6:00早高峰期6:00-10:00中间期10:00-16:00晚高峰期16:00-19:00低谷期19:00-23:00发车间隔(分钟)1027210下行方向低谷期5:00-7:00早高峰期7:00-10:00中间期10:00-15:00晚高峰期15:00-19:00低谷期19:00-23:00发车间隔(分钟)1027210（二）调度方案在上行方向，由于有车库，不存在该发车时没有车可发的情况，而在下行方向由于在每天开始时均无车可发，因此我们的调度系统一定要保证下行方向可以顺利发车。（）上行方向的调度方案。将下行方向车的到达时间与上行方向车的发车时间列出，对照可知有以下几种情况1、早上5：00到6：34期间，下行方向无车到达，在此期间内所发的车均从车库调出。2、6：36到7：46期间，下行车从6：35分开始每10分钟来一辆，它们可作为6：36、6：46、7：46的上行方向车发出，在这期间其它时刻所发的上行车均由车库调出。3、7：48到10：00期间，刚好每来一辆下行1分钟后车就可将其作为上行车发出。4、10：00到10：56期间，每隔7分钟发一辆上行车，下行车每隔2分钟来一辆。将10：07、10：13、10：19、10：27、10：35、10：41、10：45、10：52到达的下行车发出，其余时间到来的20辆下行车休息。5、10：56到15：50期间，每隔7分钟发一辆上行车，下行车每隔7分钟来一辆。每来一辆下行车4分钟后就将其作为上行车发出。6、15：50到16：00期间，15：57要发一辆上行车。下行车从15：47开始每隔2分钟来一辆，将15：57到来的下行车发出。其余5辆车休息。7、16：00到19：00期间，刚好每来一辆下行车1分钟后就可将其作为上行车发出。8、19：00到23：00期间，到来的下行车按时间顺序排入等候车队，当发车时间到来时，将等候车队中的第一辆发出。如果到了23：00等候车队中还有剩余车辆，将这些车辆入库。（）下行方向的调度方案。将上行方向车的到达时间与下行方向车的发车时间进行比较，可知下行方向的调度情况为1、5：50到6：50期间，每来一辆上行车就可将其作为下行车发出。2、7：00到11：00期间，到达的上行车远远大于所要发的下行车，建立等候车队。由于等候车队的车很多，让它们一直排下去会造成时间的巨大浪费，因此，下行方向在10：56将10：03到达的上行车发出，10：05到10：52到达的27辆上行车进入停车场休息，以备在下行方向的高峰期使用。3、11：00到15：00期间，每来一辆上行车4分钟后被发出。4、15：00到19：00期间，进入下行线高峰期。当发车时刻前上行方有来车时，将到达的上行车发出；否则，将停车场上的车辆发出。5、19：00到23：00期间，到来的上行车按时间顺序排入等候车队，当发车时间到来时，将等候车队中的第一辆发出。如果到了23：00等候车队中还有剩余车辆，将这些车全部返回上行方向起点站入库。比较双方的调度情况可以看出,下行方向的晚高峰期比上行方向早1个小时,但它有27辆后备车,刚好可以弥补这一个小时的不足,因此我们的调度方案是可行的。（三）所需车辆数目的计算已知上、下行方向的路程分别为s=14.58公里,x=14.61公里。车的平均速度为20公里/小时。早高峰期、中间期、晚高峰期及低谷期的发车间隔分别为t1、t2、t3及t4分钟。上、下行方向的车从一个始发站到另一个始发站的时间约为45分钟。上行方向发车间隔为ti（i=1，2，3，4）的时期所需车数计算如下： 60/ti-15/tj+45/tj+补发车数其中tj(j=14) 为该时期的第一小时所对应的下行方向的发车间隔，至于补发车数根据实际情况进行简单的运算即可求得。结果如下表：低谷期5:00-6:00早高峰期6:00-10:00中间期10:00-16:00晚高峰期16:00-19:00低谷期19:00-23:00车数651374510由上表看出，早高峰所需车数最多。当有51辆车可调度时，各个时期都可按各自的间隔发车。因此，公交公司进行一天的运营所需的总车辆数为51。总车次数为575。（四）关于数据采集的几点建议1、题目中给出的数据是以一个小时为采集时间间隔，当相邻两个采集时间间隔的人数相差很悬殊时，如下行方向6：00-7：00有795人，7：00-8：00有2328人，很难对此期间乘客人数的分布进行估计，因此影响到问题的求解的精确性。希望在采集数据时，在乘客人数变化较大的时间适当将采集时间间隔缩短，比如以半小时为一个采集时间间隔。2、可将多天的数据取统计平均，减少随机因素的干扰。结果分析调整几个时间段内的发车间隔，观察它们的变化对乘客满意率和满载率、空载率影响。具体调整过程为在求得的发车间隔的基础上（t1=2,t2=7,t3=2,t4=10），固定其中三个发车间隔，只改变一个发车间隔，得到对应的乘客满意率和满载率、空载率。（选定t4=10不变）满载率空载率满意度t1=1,t2=7,t3=2,t4=100.46430.17220.9774t1=3,t2=7,t3=2,t4=100.63110.09520.8799t1=2,t2=6,t3=2,t4=100.59030.11500.9607t1=2,t2=8,t3=2,t4=100.58900.11860.9257t1=2,t2=7,t3=1,t4=100.44670.16150.9600t1=2,t2=7,t3=3,t4=100.64060.10410.9381分析数据，调小发车间隔会提高满意率，但是满载率会下降，空载率会上升，这是一对相互矛盾的指标，分别反映了乘客和公交公司的利益。其中调整t1对两个指标的影响最大，其次为t3，t2影响最小。七、模型的改进在原模型的基础上对时间段划分进行细化，由数据可以看到，上行方向的早高峰期中乘客最多的时间在7：008：00，下行方向的晚高峰期中乘客最多的时间在17：00-18：00，而在上行和下行方向的最后一个小时乘客很少，因此可以把这些时段分离出来单独考虑。而且由于比起两个总站之间的行驶时间，一小时的时间不够长（60453），即不符合我们前面证明的结论，所以使得上下行方向在这一个小时内可以采用不同的发车间隔而不会使车辆总数很大。经过搜索，给出改进后的时间段划分和对应的发车间隔如下表：上行方向发车时段5:00-6:0019:00-22:006:00-7:008:00-10:0016:00-19:007:00-8:0010:00-16:0022:00-23:00发车间隔1032730下行方向时间段5:00-7:0019:00-20:007:00-10:0015:00-17:0018:00-19:0010:00-15:0017:00-18:0022:00-23:00发车间隔 1037220A13的发车时间为5：00，A0的发车时间为5：50。在这种发车方案下，得到的乘客满意率，公交公司的满载率和空载率分别为：总车次总车数乘客满意率满载率空载率432470.92240.70490.0603 在每个时间段内需要的总车数如下表低谷期5:00-6:00早高峰期6:00-10:00中间期10:00-16:00晚高峰期16:00-19:00低谷期19:00-23:00车数641374710 在这种发车方案下，乘客的满意率有所下降，而对于公交公司来说，既减少了车辆总数，也提高了满载率，抑制了空载率。因此这种发车方案对于公交公司很有利，但是同时也增加了调度的复杂性。如果在乘客满意率要求不是很高的情况下，这不失为一种好的发车方案。同时我们发现，由于所给上下车人数在按照这种分段方案划分后，在本时段内相邻两个小时的上下车人数很接近，所以没有必要再继续划分成更小的时段，即使再划分也不会有明显的效果。八、模型的进一步讨论题中给出客车在该线路上运行的平均速度为20公里小时，我们认为这是一天里的速度平均值。实际考虑在车辆的运行过程中，速度会随着装载人数的不同而有所变化，是装载人数的一个减函数。我们设在某一段内的平均速度v=-kx,其中表示车空载时的速度,x表示在一个时间段内的平均到一个小时的载客数,即用这个时间段的总载客数除以时间段长度，k表示载客数对速度的影响。假定25公里/小时，由客车在该线路上运行的平均速度为20公里小时的条件可以求出k0.1288。对应求出在四个时间段内的平均速度(公里/小时),从而求出在四个时间段内所需要的车数，见下表：早晚时段早高峰期中午时段晚高峰期平均速度24.07616.32221.87619.34所需车数8563445分析得到的数据,在考虑每一时间段内速度不同的情况下, 比较不考虑