公交车调度方案的优化设计

1、公交车调度公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。下面考虑一条公交线路上公交车的调度问题，其数据来自我国一座特大城市某条公交线路的客流调查和运营资料。该条公交线路上行方向共14站，下行方向共13站，第3-4页给出的是典型的一个工作日两个运行方向各站上下车的乘客数量统计。公交公司配给该线路同一型号的大客车，每辆标准载客100 人，据统计客车在该线路上运行的平均速度为20公里/小时。运营调度要求，乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟，车辆满载率不应超过 120%，一般也不要低于5

2、0%。试根据这些资料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益；等等。如何将这个调度问题抽象成一个明确、完整的数学模型，指出求解模型的方法；根据实际问题的要求，如果要设计更好的调度方案，应如何采集运营数据。某路公交汽车各时组每站上下车人数统计表 上行方向：A13开往A0站名A13A12A11A10A9A8A7A6A5A4A3A2A1A0站间距(公里)1.60.510.732.041.262.2911.20.411.030.535:00-6:00上37168385264545

3、110下5576:00-7:00上199895943308307680下958854282889216157:00-8:00上36266345284479488685239589990下6118187114598:00-9:00上254775492714864390下441327599:00-10:00上17286778143162360下4448310:00-11:00上9235214119212260下105511:00-12:00上9571814138117300下119012:00-13:00上8731411403112260下63256389164111313:00-14:00上77

4、914110897230下2119729738426314:00-15:00上625197585200下915:00-16:00上63512498820下919633912982916:00-17:00上149329924108197490下0055717:00-18:00上2865610下576945739573922879318:00-19:00上6911241382220下3723112542833619:00-20:00上355110下616620413920:00-21:00上35490下841435934464716011721:00-22:00上2529475216282760下

5、411289222:00-23:00上193325535513210下127993221某路公交汽车各时组每站上下车人数统计表 下行方向：A0开往A13站名A0A2A3A4A5A6A7A8A9A10A11A12A13站间距(公里)1.5610.441.20.972.291.320.7310.51.625:00-6:00上22342443331100下396:00-7:00上7951431678471304553160下05195082717:00-8:00上23283855272343331126138450下3744442653739588:00-9:00上274354120153460下3

6、6742823737611679:00-10:00上2523537699270下51149833619927613621955610:00-11:00上9022061280下34632019143811:00-12:00上84774148150下382561751221436812834612:00-13:00上7440120下119659826113:00-14:00上773643130下102091530914:00-15:00上83916519150下3824611834615:00-16:00上11101714190下3516:00-17:00上46325395122340下96175

7、49426978417:00-18:00上38468649388432452157205560下3793414278448124918:00-19:00上19663571289335342122132400下3101019:00-20:00上93974856170下820:00-21:00上642643130下27709531921:00-22:00上6361148295983440120下4319210129022:00-23:00上2944351244658354142151750下8926947603349136公交车调度方案的优化设计摘要本文利用某一特大城市某条公交路线上的客流调查运营

8、资料，以乘客的平均抱怨度、公司运营所需的总车辆数、公司每天所发的总车次数以及平均每车次的载客率为目标函数，建立了的分时段等间隔发车的综合优化调度模型。在模型求解过程中，采用了时间步长法、等效法以及二者的结合的等效时间步长法三种求解方法，尤其是第三种求解方法既提高了速度又改善了精度。结合模型的求解结果，我们最终推荐的模型是分时段等间隔发车的优化调度方案。在建立模型时，我们首先进行了一些必要假设和分析，尤其是针对乘客的抱怨程度这一模糊性的指标，进行了合理的定义。既考虑了乘客抱怨度和等待时间长短的关系，也照顾了不同时间段内抱怨度对等待时间的敏感性不同，即乘客在不同时段等待相同时间抱怨度可能不一样。主

9、要思想是通过逐步改变发车时间间隔用计算机模拟各个时间段期间的系统运行状态，确定最优的发车时间间隔，但计算量过大，对初值依赖性强。等效法是基于先来先上总候车时间和后来先上的总候车时间相等的原理，通过把问题等价为后来先上的情况，巧妙地利用“滞留人数”的概念，把原来数据大大简化了。很快而且很方便地就可求出给定发车间隔时的平均等待时间，和在给定平均等待时间的情况下的发车间隔，但该方法只能对不同时段分别处理。结合前两种方法的优点提出等效时间步长法，即从全天时段内考虑整体目标，使用等效法为时间步长法提供初值，通过逐步求精，把整个一天联合在一起进行优化。通过对模型计算结果的分析，我们发现由于高峰期乘车人数在

10、所有站点都突然大量增加，而车辆调度有滞后效应，从而建议调度方案根据实际情况前移一段适当的时间。在模型的进一步讨论和推广中，我们还对采集运营数据方法的优化、公共汽车线路的通行能力以及上下行方向发车的均衡性等进行了讨论。在求具体发车时刻表时，利用等效时间步长法，较快地根据题中所给出的数据设计了一个较好的照顾到了乘客和公交公司双方利益的公交车调度方案，给出了两个起点站的发车时刻表（见表二），得出了总共需要49辆车，共发440辆次，早高峰期间等待时间超过5分钟的人数占早高峰期间总人数的0.93%，非早高峰期间等待时间超过10分钟的人数占非早高峰期间总人数的3.12%。引入随机干扰因子，使各单位时间内等

11、车人数发生随机改变。在不同随机干扰水平下，对推荐的调度方案进行仿真计算，发现平均抱怨度对10%的随机干扰水平相对改变只有0.53%，因此该方案对随机变化有很好的适应性，能满足实际调度的需要。1问题的提出公共交通是城市交通的重要组成部分，做好公交车的调度对于完善城市交通环境、改善市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。下面考虑一条公交线路上公交车的调度问题，其数据来自我国一座特大城市某条公交线路的客流调查和运营资料。该条公交线路上行方向共14站，下行方向共13站，题中给出了典型的一个工作日两个运行方向各站上下车的乘客流量统计。公交公司配给该线路同一型号的大客车，每辆标准载客1

12、00人，据统计客车在该线路上运行的平均速度为20公里/小时。运营调度要求，乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟，车辆满载率不应超过120%，一般也不要低于50%。试根据这些资料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益。 2模型假设与说明1 题目中所给出的一个工作日的乘客流量统计数据是具有代表性的；2 工作日每天同一时间的乘客流量大致相等；3在任何时刻车辆上的人数不能多于120人；4每个乘客都严格遵守先到先上车的规则；5在公交线路上所有车辆总能正常通

13、行，不考虑诸如堵车、交通事故等意外情况；6不考虑公交车在各站的停车时间，即乘客上下车均在瞬间完成；7公交车在公路上行驶速度处处相等，都等于题目中给出的平均速度；3符号系统l上：公交路线上行方向的总路程；l下：公交路线下行方向的总路程；v：客车行驶的平均速度； ：上行车辆第i段时间内的发车时间间隔；：下行车辆第i段时间内的发车时间间隔；：乘客的抱怨度；N：一共需要的车辆数；S：一天总的发车次数；：平均每车次的载客率；：在第i时间段内上车的总人数；：一天的乘车总人数；4问题分析与模型的建立4.1 问题分析 本题要求设计全天(工作日)的公交车调度方案，这里需要考虑乘客和公交公司两方面的利益，是一个多

14、目标的优化问题。其中可以供选择的目标函数主要有：1)乘客候车时间要尽量短；2)候车时间超过5分钟乘客数要尽量少；3)公交公司所需的总车辆数尽量少；4)全天范围内，发车的总次数尽量少；5)平均每车次的载客率尽量高等等。以上的目标可以用乘客利益和公司利益分为两类，这两类目标是相互冲突的，不可能同时达到最大。工作日的早高峰正是多数乘客上班的时间，也是一天中乘坐公交车人数的高峰期，所以这段时间里所需的车辆数也是最多的。从乘客的方面考虑，早上上班迟到对他的利益的损失相当大，因此乘客希望候车时间一般不要超过5分钟。这时应以乘客的抱怨程度尽量小为主要目标，求得公交公司在早高峰期间的所需的最少车辆数。在其余时

15、间段里，乘客候车时间一般不要超过10分钟，这时考虑到公交公司的利益使其在这段时间内所发的总共发车的车次总数最少，以及提高每车次的载客率为主要目标。因此我们首先确定出早高峰期，针对早高峰期的数据，在一定的乘客抱怨水平下，求出共需多少辆车，然后再根据全天其它时段的数据，并综合其它指标求出两个起点站的发车时刻表。由于题目中所给出的仅是各站一个小时上下车人数的数据，对于我们的计算而言太过粗糙。首先想到的是运用题中的数据对每一车站在各时段上车和下车的人数进行分布拟合，但这样做也有很大的缺点，因为各时段每个站点上下车人数受上下班时间以及道路沿线工厂等因素影响很大，从而导致各时段前后相关性很小。而对各时段上

16、车和下车的人数进行分布拟合就人为的增加了各时间段的上下班人数的相关性，与实际情况不符。实际中如果把统计做的更细致或者知道那些影响上下车人数分布的因素，就可以较好的求出这些分布；由于缺乏我们对这些情况得了解，所以我们假设各站的上下车人数在各个时间段（一小时）内分布是均匀的，即Enumik（t，ti）=（ti）= numik/ti其中numik（t，ti）表示在t，ti内上车的人数。4.2模型的建立为了更好的建立模型，首先要明确下面几个问题：1）时间段的划分：假设在题目中给出的各时段（一小时）内，各车站上下车的乘客人数分布均匀，这样就可将全天分为18个时间段，分别对每一个时间段进行考虑，并认为每个

17、时间段内的发车间隔时间ti上和ti下分别为常数，但两者不一定相等。2）对下行方向的处理：从题中数据可以看出上行方向比下行方向多一个车站A1，我们对此的处理是在下行方向同样也补上一个车站A1，并且令这个车站在任何时段上车和下车的人数均为0。3）对乘客平均抱怨度的定义：考虑到一个人的抱怨程度是一个模糊的表述，它与候车时间的长短有关，候车时间越长，抱怨程度越大，但候车时间足够短时又不会抱怨。经过分析可以定义第i个时间段上行的（或下行的）第j个乘客的抱怨度为： 或 式中，表示当此乘客不同等待时间wij对应不同的抱怨度。可以看出抱怨度不仅与等待时间的长短有关，而且还会与所在的时间段i有关。很明显，早高峰

18、期间和平时时段里等待同样长的时间，前者给乘客造成的损失可能更大些，因此抱怨度也会相应大一些。有了每个乘客抱怨度的定义，第i时间段的平均抱怨度为：一天内的平均抱怨度为：式中i表示第i段时间内区间的平均抱怨度对总平均抱怨度的权重，可取。其中wij 是由ti上或ti下及numik（t，ti）决定的，其中numik（t，ti）是一个随机量，故wij也是一个随机量，从而一天内的平均抱怨度也是一个随机量，可表示为f（ti上，ti下）。4)总车辆数的确定: 一天所需的总车辆数N等于各时段所需的总车辆数Ni中的最大值，即N=g（ti上，ti下）=maxN1，N2，N18，而每一时段所需的总车辆数由上行车辆数、

19、下行车辆数，加开车辆数三部分组成，有Ni=Ni上+Ni下+ Ni加其中 这里表示对括号内的数取整。5)对平均每车次的载客率的定义：考虑到每车次的运营成本基本不变，这样平均每车次的载客数目的多少就能反映公司的利益。于是我们定义平均每车次载客率定义为：=num总/S 即： 式中代表第i时段在第j车站到上车人数（包括上行和下行）；代表第时段的时间间隔；第i时段上行或下行的发车时间间隔。平均每车次的载客率的高低直接反映了一个调度方案对于公交公司的收益率。一般地乘坐公交车是按次计费的，所以总上车人数即反映了公交公司一天的收入，而总发车次数则反映了公交公司一天的支出。6）据以上分析，我们建立如下模型：目标

20、：min E=Ef（ti上，ti下）min N=g（ti上，ti下）min 这里表示对括号内的数取整max =num总/S调度要求：1 每辆车上承载的人数不超过120人；2 在给定时间段Ti60（分）内ti上，ti下为定值。5模型的求解5.0 解法分析在我们建立的模型中的多个目标中，总共需要的车辆数N 涉及到公司建立一条公交线路的初始投资，每辆车所需的资金巨大，应被首先考虑。而要确定总共需要的车辆数，只需求出早高峰期（我们根据题中给出的数据，假设早高峰期为7：008：00和8：009：00两个时段）内所需的车辆数即可。 考虑到实际求解过程中，对于前面模型中所定义的抱怨度在各个时间段内对于不同等

21、待时间长度取值问题，可以通过实际的调查数据得到；简化地想，如果对应所有的区间，顾客等待时间长度大于5分钟时都取1，而小于5时都取0，那么这是所定义的抱怨度直观意义就是指所有时间内等待时间超过5分钟的人数占总人数的比值，但显然着这种定义太粗糙；由于缺乏实际的调查，我们在以下求解过程中对抱怨度在各个时间段内对于不同等待时间长度取值作以下假定：早高峰期间i1-i4分别取0 0.3 1 1.5 2.4；而其它时间段内i1-i4分别取0 0.15 0.5 0.75 1.2。 5.1 解法一：时间步长法总体思路：在给定的假设原则下，通过逐步改变发车时间间隔用计算机模拟各个时间段期间的系统运行状态，确定最优

22、的发车时间间隔。为简化计算，可以设定每个车站单位时间内上下车人数分别正比于该车站在这个时间段上下车的总人数，即numik（t，ti）=（ti）= numik/ti。运行步骤：1)初始发车时间间隔，i=1,2,18；2)设置初始状态。模拟时钟、终点时间 3)设置每个车站等车人数以及待发车辆的最初状态，将每个车站的等车人按其等待时间的长短分为以下几类：、； 4)判断是否需要发车以及是否有车到站，并更改一次各车站等车人数及运行车辆的状态。其中运行车辆的状态包括实际承载人数和空余座位数。判断是否到了终点时间？若是，转5）；否则转2）； 5)统计整个过程中各区间等车时间超过5分钟以上的人数，对这些人加权

23、求和，然后除以该过程总的上车人数得到平均抱怨程度。判断是否大于给定的目标抱怨度？若大于给定值则转1），并改变发车时间间隔ti；否则，给出结果并转6）。 6)结束。5.2 解法二：等效法总体思路：由于不同上车规则所对应的所有乘车人员的等待时间之和T总是相等的，可以把先到先乘车这个规则所对应的T总等效成后到先乘车规则的情况求出来。由T总除以总乘车人数可以得到乘客的平均等待时间T平，对乘客而言，T平当然越小越好，即可以把T平作为一个目标；当然也可以这样解释：通过对乘客等待时间的统计，可得到等待时间位于各个时间区间内的乘客人数。通过拟合有如下图所示的分布，图中虚线代表T平，那么图中阴影所示的面积就反映

24、了等车时间超过5分钟的比重。由图可看出，T平的值越小，抱怨度也会越小。图一等效法求解T平的计算原理及方法：利用等效的概念求解是基于这样一种结论：只要每个乘客到达的车站的时间和发车的间隔确定，那么先到先上车的规则和后到先上车的规则两种情况下所有人员的等车时间总和总是相等的。例如：甲在一个车站等待，过了一个周期来了一辆车和乙，但车只有一个座位；又过一个周期，又来了一辆车和丙，也是只能一个人上。那么，这段时间里如果按照先来先上规则，甲和乙的等车时间都是一个周期；如果按照后来先上规则，则甲的等车时间是两个周期，而乙可以不等待，但是两人的等待时间之和是一样的。如果沒有更多的空位如果没有更多的空位，甲将被

25、“滞留”在那里。这种现象可解释为：如果出现等待，先到先上规则是每个乘客都得等一段时间，而后到先上规则却是先到的人员一直在等，后来得人反倒可以即来即上。相当于后来人员的等待时间被折合到先到人员身上的缘故。先到的乘客担当了全体人员的“替罪羊”，从而形成了在整个时间隔内永远上不了车的滞留情况。这样就可以只通过计算这些滞留人员的滞留时间之和，得到全体的平均等待时间。定义 第i个时段内，第j个车站的净上车人数aij为该车站在这一时段内的上车人数减去下去车人数。用以上定义对数据进行预处理，即得到每个车站在各时间段内的的净上车人数aij。考虑在ti内，一辆本来已经满载的车经过第j个车站的情况：如果这个车站的

26、净上车人数大于0，则这个站滞留的乘客人数为ti内的净上车人数aijti/Ti；若净上车人数小于等于0，则这个车站可以为后面的车站提供空位置，从而使得下面站点的滞留人数减少，即可等效为它能提供的滞留人数为一负值，用来对消后面车站的滞留人数；但是如果其后面所有车站的净上车人数之和为负的话，它所提供的空位永远也不会有人来坐，负的滞留人数就没有实际意义。这时就可令它和它之后的所有车站所能提供的滞留人数都为0。按照以上方法可求得每个时段上只有前面若干个车站会出现滞留人数，即可简化计算；同时对第i时段的始发站而言，它所提供的滞留人数为：。图二给出的是7：008：00段各站上行方向上的净上车人数）。图二按上

27、述等效原理，算出各时间段内各站的净上车人数，即滞留人数，而滞留的人从到站起就一直等待到时间段结束，其等待时间成一个等差数列。由此可得总的等待时间的计算公式为：而平均等待时间Ti平=Ti总/下面给出上行方向各段平均等待时间Ti平的目标，求得结果如下：表一：上行方向各段平均等待时间Ti平的目标Ti平732244444443344447ti9.72.51.462.584.55.64.85.56.16.973.22.65711.312.315.337.3误差讨论：该方案计算时，当一个人的等待时间时，他的等待时间就被忽略了，导致结果偏小，这里应对平均等待时间T平加上一个ti/2的修正；5.3解法三：等效

28、时间步长法时间步长法虽然将全天的数据作为一个整体来处理，充分考虑到各时间段的数据对相邻时间段的影响，可以较好的模拟出全天公交车的运营情况，并且给出对乘客抱怨度较为精确的描述；但ti是一个18维的向量，我们对于初值的确定缺乏依据，而导致大量盲目的搜索。另一方面，等效法可方便快捷的给出在平均等待时间T平约束下各段的发车时间间隔；但其根本缺陷在于只对每个时间段内的数据进行处理，而没有考虑到上一时间段遗留下来的人对本时间段的影响及本时间段遗留的人对下一时间段的影响。因此算出的结果对于全天来说是就不见得特别好了。结合前面两种算法，我们想到可以首先用等效法算出几组ti的初值，然后将这些初值带入时间步长法中

29、进行计算，得出平均抱怨度最小的一组ti作为我们的结果。5.4模型的结果：按解法三求得结果如下： 1 两个起点站的发车时刻表如下：表二：公交车全天调度方案发车时间间隔上行下行5：006：006：007：007：008：0093030002306501302408：009：009：0010：0024022043042010：0011：0011：0012：0054065045074085012：0013：0013：0014：0053061082014：0015：0065072015：0016：0071055033016：0017：0031017：0018：0024021018：0019：007003

30、2070092093019：0020：00112020：0021：00122021：0022：00150022：0023：00300020002 总共需要N=49辆车；3一天内总的发车次数为S=440 次，其中下行方向为202次，上行方向为 238次；4.平均每次车载客率P=246人/车次5抱怨度=0.2831表三：各等车时间区间等车人数等待时间(分)455667788991010等待人数811278945739933745.5 方案模拟不同工作日同一时段乘客到达总数基本相同，但由于种种随机因素的影响，它总是有一定的上下波动。于是在单位时间内到达乘客数均值m上引入随机量，它服从均值为0正态分布

31、，其均方差与m成正比关系，即N(0，()2 )于是实际到达人数，其中可以通过调整来控制波动的程度。在不同水平下的对上行方向调度方案仿真，同一水平下作100次仿真然后取均值得到一天不同候车时间w占全天乘车人数的比值及最后总的抱怨度。表四：不同随机水平上行方向调度方案仿真结果5667788991010=00.06880.050.01370.01270.01580.02970.2826=0.010.06880.050.01370.01280.01560.02970.2827=0.020.06880.05010.0140.01290.01560.02970.2830=0.050.06870.05010

32、.01390.01290.01510.03020.2835=0.10.06870.05080.01470.01390.01510.02950.2841可以看出，调度方案对即对于数据的波动不敏感。最大随机水平=0.1时，抱怨度相对变化只有0.53%，此方案有较大的适用范围。5.6 结果分析与模型改进通过对上面所得到的结果进行分析可以看出高峰期及高峰期前各时间段等车时间较长的人数较多，而高峰期后各时间段等车时间较长的人几乎没有。其原因是我们的模型是在第i段的起点时刻才开始启用第i段的时间间隔，而在第i段发出第一辆车的时刻，各站的上下车人数均已按第i段的数据开始出现了，但已在路上运行的车还是按第i-

33、1段的时间间隔发出的，这样车就明显的与乘客的需求不相符合。当第i段的上下车人数大于第i-1段的上下车人数时，乘客的等待时间显然会变长，增加乘客的抱怨；我们的结果中高峰期及高峰期前各时间段等车时间较长的人数较多就是这种情况；反之，乘客的等待时间显然会变短，同时也使车辆的满载率过低，不符合公司的利益。对此我们可对我们的模型作如下调整：在第i段的起始时刻之前Tr时刻开始的Ti=60（分）时段内按第i段的时间间隔ti发车，针对不同的Tr值进行搜索，得出使得平均抱怨度最小的Tr。得到结果如下：6模型的进一步讨论 1对数据处理时出现的现象讨论：同一方向同一时段内上下车人数之差通常不等于零，大于0说明这个时

34、段内上车的乘客，有一部分要到下一时段才能下车；小于0说明有一部分在这个时段内下车的人时在上一个是段上来的；而为0，说明出现这两种情况的机会相等。整个线路上全天的净上车人数不为44，数据不等，可能是输入错误或者随机误差。对每个车站一整天的净上车人数的物理意义：如果净上车人数接近于0，说明此地没有别的交通工具大的干扰，该处的乘客多会在一天之内返回然来地点；如果净上车人数大于0，说明此处可能是一个大的中转站，有别的交通工具或公交路线为这个站点提供源源不断的净上车人数，这种地方适合作为一个公交线路的起始点。 2采集运营数据方法的优化由于题目中给出的数据过于粗糙，因而我们进行了适当的简化。如果要更好的对公交车进行的调度，就需要知道运行方向各车站上下车人数更细致的数据，比如说各站每10分钟上下车的人数，甚至每分钟上下车的人数。我们可以对运营数据的采集的统计时间间隔按一定的规律进行调整，一般来说，在高峰期时对数据进行统计的间隔较小的，而在一般时段对数据进行统计的间隔较大