1、公交车的调度杜克勤 童颜 李科摘要：本文解决的是一个公交车调度问题，目的是用尽可能少的车来运送乘客，同时不能让乘客等待时间过长，也不能超载。文中提出了一种解决本问题的新颖的模型。通过分析知，一个时区内需要的车只与该时区内车站的最大转移客流量有关，于是我们对题目所给的数据进行一系列变换处理，求出每个时段发的车的最大转移客流量，得到一个新的表格。根据最大转移客流量，用线性规划的方法可以求出我们这个模型需要发车次数的最小值，然后综合考虑乘客的等待时间等我们可以给出各个时区的发车次数，进而确定全天发车时间表，由发车时间表，我们同样用线性规划方法求出需要的最少车辆数。用我们构造的模型，求出了一个可行的调
2、度计划，并给出了发车时刻表。每个方向的全天发车次数为237，需要的57辆公交车。通过编程模拟得出平均等待时间2.17min和平均满载率81.6%，对这个解进行了评价，说明了本模型的特点，并指出了进一步优化改进的方向。最后用一个模拟搜索方法又求出一个解，并与第一个解相比较。一 问题的提出这是一个公共汽车调度问题。题目给出了来自我国一座特大城市某条公交线路的客流调查和运营资料。该条公交线路上行方向共14站，下行方向共13站，题目给出的是典型的一个工作日两个运行方向各站上下车的乘客数量统计。公交公司配给该线路同一型号的大客车，每辆标准载客100 人，据统计客车在该线路上运行的平均速度为20公里/小时
3、。运营调度要求，乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟，车辆满载率不应超过 120%，一般也不要低于50%。我们的目标就是根据题目所给的这些统计资料，把调度问题抽象成一个明确完整的数学模型，并求解，根据我们的解，给公交公司制定一个公交车调度方案和起点站的发车时刻表，使公交公司能够有效降低成本，但又不能牺牲乘客的利益。二 基本假设1. 1. 候车队伍有良好的秩序；即要保证乘客先来先乘车的原则；2. 2. 忽略其它情况对公交车的影响，即公交车以20公里/小时的速度匀速行驶；不计乘客上、下车的时间及公交车起动、加速、滑行、制动时间（因为题中给的是平均速度）；3. 3. 从时间段
4、内到达某站的乘客数服从均匀分布； 4. 4. 公交公司只对公交车进行调度但在允许的范围内不限制乘客上车；既只要该车乘客数不大于120则允许乘客上车，直到达到120为止；5. 5. 每个时间段的发车间隔时间是确定的而且平均的。三 符号说明与概念引进3.1 概念引进1 1 时区-我们规定两相邻正点之间的单位时间间隔为一个时区，并给之编号5：00-6：00 时区6：00-7：00 时区 21：00-22：00 17时区22：00-23：00 18时区2 2 跨时区-当一辆公交车从时区出发在到达目的地之前已经进入下一个时区 时，我们就称为产生了跨时区。3 3 站间转移客流量-有多少乘客乘坐时区发出的车
5、经过j车站到达车站（包括在车站上车的乘客，）。4 4 如果一个乘客是在时区来到车站乘车的，我们称该乘客来自时区3.2 符号说明 1 分别代表各个时区内发车的时间间隔 2 分别代表各个时区内发车的总次数 3 ：在时区车站的净上车客流量 4 ：站间转移客流量（见上面定义） 5 ：车站来自时区的人被发自时区的车运走的数量 6 ：时区内发出的所有车在车站运走的净乘客数量（上车人数减下车人数）。四 问题的分析我们应该在满足乘客的等待时间要求的前提下，合适地安排发车次数，得到发车时刻表，使得发车次数尽可能的少，而且用到的车辆尽可能少。我们的目标是求每一个时区内发车的次数，发车的次数由在该时区内发出的车要要
6、运送的乘客数量决定，那么我们就要求各个时区发出的车分别要运送的乘客数。知道了要运送的乘客数，就可以用线性规划求发车车次。知道了发车车次，我们进而可以列出发车时刻表，通过时刻表，可以用线性规划求最少车辆。五 模型的建立和求解 起点 Ak 点5:005.1 模型一示意图见右。箭头表示车在一定时间内从起点开到终点。6:00由于公交车有跨时间段的问题（例：起点到第Ai站要用t(以小时为单位)的时间，则在i：00到i+t时间内到达Ak站的乘客可由i-1：00i：00时间段内发出的公交车运走）。为了方便解决问题，i:00在i时区到达车站的这部分乘客将被i-1时区发出的车运走我们以第i时区()发出的公交车来
7、重新划分乘客，在i时区到达车站的这部分乘客由i时区发出的车运走找出各个站点上由这些车运送的乘客数量（i+1）:00则从第j时区发出的车在Ak站点所要运走的乘客数量为(假设在i:00到（i+1）:00在Ak点候车的在i+1时区到达车站的这部分乘客由I时区发出的车运走乘客数量为；在i:00到（i+1）:00在Ai点下车的乘客数量为)：22:00当j=1时，上车的乘客数为：；下车的乘客数为：23:00当时，上车的乘客数为： 下车的乘客数为： 图 1当j=18时，上车的乘客数为：下车的乘客数为： 我们再引入两个附加假设：附加假设一： 假设时区发出的第一辆与最后一辆车到达车站的时刻分别为，在到这个时间间
8、隔内，乘客的到来服从均匀分布。（原来假设一个时区里来人是均匀的；当求出在到内来的人数后，再认为这段时间内来人均匀）附加假设二： 假设时区发出的车能够把-这个时间间隔内来到车站的乘客全部运走。下面我们要解决的问题：具体求出时区发出的车要运多少乘客命题一： 在考虑车站转移客流量时，在一个站我们分别考虑上下车人数与我们考虑净上车人数是等价的。命题二： 每个时区内公交车的发车次数的下限由这个时区内相邻两站间最大转移客流量max决定。 证明： max表示在时区要经由车站向下的乘客，我们要保证人能被运走，但又不能超载，即满载率不能超过120%，那么如果,必然导致该站的部分乘客滞留。命题三： 在第时区来车站
9、的乘客是被发自时区和发自时区的车共同运走的，而且被时区的车运走的乘客占车站总乘客的比例由车站距始发站的距离决定。 推论： 第时区内发的车从车站运走的乘客来自于时区和时区，运送的时区的乘客占总乘客的比例也由车站距始发站的距离决定。由这四个命题我们可以得出的一个算法：1） 1） 计算时区车站净上车人数（=；）；2） 2） 计算和（为在时区来的乘客被时区发出的车运走的数量，为从时区发的车运送的在时区来的乘客）3） 3） 计算时区发出的车需从车站运走的乘客的数量，=-+4） 4） 计算时区车站的转移客流量，=（对于上行方向来说），即i时区内发出的车从起点站到j站的净上车人数之和。5） 5） 据时区内各
10、车站的最大转移客流量max和需要的发车次数的关系： max*120 从而确定的最小值。用以上算法，将原表格变换成为一个新的表格，用来求发车次数。我们编了一个程序来计算每个车站由时区出发的车的转移客流量，最后求的结果列表如下：（各个时区的最大转移客流量用粗体标出）表1：上行方向的各个车站的转移客流量站名A13A12A11A10A9A8A7A6A5A4A3A2A113714455125566797236455636706606857184421990227925142620299629442594210622092074202019084093362640384326448549124753425
11、935893638349834223245196542064227324452505266725772267190319111841178916828455118613081396142315191422121098210029609258642896923102410931123121111349757748197807557122087957108111801227134612891143981104199596893245888739691057109011901138102289994591589987448397798789419581042101392280483881279676
12、74051062569576379687686176561163760558355521311635734803834924890733509548513476432-195121493171618751938214820521805147015571476432133529213201122652444249527002527230520202099203119911922128914691767823833886826726575599572547520264153503914234354644403882993022872762639916304337362373405394354282
13、277264254241111172092302462502652462191671591491411317341819191917145-4-16-19-20-24-27-36由以上数据，我们可以建立一规划模型来求解min目标函数： min s.t： ()经过求解，对所得数据进行近似及权衡乘客等待时间，我们得到了以下一组时区车次安排表2：上行方向的各个时区的车次安排时区123456789101112131415161718车次624412313111210988182386664总共需发车237次同理我们可以求得下行方向的车次安排表3：下行方向的各个车站的转移客流量站点A0A2A3A4A5A
14、6A7A8A9A10A11A12122294856473931-317-23-38-101279586910141062975878609515509299212-34323282416269527632460214315861391136510539536234270628093123319328782607215419921986174016851445515561603177018121654146811831090108792588873269029451064108710008736936386285124863657847882956985914830695641626534511
15、415870672680582976168857654354445543533997707948808978287526285926035014763731083988999810189308466816336535415063891111101172130313221225108584075175858955035412183719272181222320451813137812331246964903566133020316335413595331830252482230923462030193116121419662084233323842114184915361415143312431
16、1819941593995710601089972864711659661563535434166406727567807046224974564533643372501763667175176368760151147847140738732718294301328332299262227211209189183168表4：下行方向的各个时区的车次安排时区123456789101112131415161718车次692427161097891219312010776总共需发车237次公交车时刻表的安排由于我们假设在各个时区内发车间隔相等，所以由以上的发车次数我们很容易得到始发站的发车时刻表（具
17、体见附录）需要车辆数的求解知道了具体的发车时刻，我们就可以去求至少需要多少辆车设为A13站必须的车辆数，为A0站必须的车辆数为A13站在时刻发车前由A0已经开到的车次数，为A13站在时刻发车前开出的车次数为A0站在时刻发车前由A13已经开到的车次数，为A0站在时刻发车前开出的车次数目标函数： min +s.t：. +-1 +-1 （，分别是已经确定的两个始发站的发车时刻）通过对这个线性规划求解，我们可以得出需要的最少车辆=+=575.2 模型二：模拟搜索我们又用模拟的方法编了一个搜索程序去搜索可行的车次（程序清单见附录2.b）我们尽可能地去模拟每步的情况，对各种情形做出分析用这种方法我们得出上
18、行情况的一组车次安排（下行情况略）时区123456789101112131415161718车次726412313101310989182386666总共需发车242班比较这两种方法得出的结果可以看到相差并不大，用模拟搜索总数要大一点，这是由于两种方法处理乘客等待时间时要求不一样造成的六 模型的评价及改进方向6.1 评价我们对这种发车车次安排进行了评价，我们用平均等待时间和最长等待时间来评价乘客的满意度，用平均满载率来评价公交公司的利益。平均等待时间-所有乘客等待时间的平均值，以上行为例，可以证明 ，其中 是第i时区发车间隔，第i时区发出的车在全程运载的总人数。平均满载率-在这一天中，发出的车
19、的载客能力利用率同样以上行为例， = ， 其中为全天中上行方向总的发车班数。用编程方法算得=2.17分钟，=81.58%，程序见附录。1） 于我们模型严格的时间控制，使得在整个运送过程中，没有乘客等待时间超过10分钟，并且平均等待时间达到一个很小的值，对乘客来说，是非常满意的，这也有利于提高公司的社会效益。2） 但是对于公交公司来说，虽然车的载客能力利用率=81.58%已经较大，在早晨与晚上的时区内，我们安排的车的满载率远远低于50%，因此我们可以适当地减少早上，晚上的发车班数，以提高车的利用率。严格保证乘客的利益，是需要总的车辆数较大的主要原因。6.2 改进1） 按照经验，在早高峰期间一般还
20、存在着一个超高峰，我们可以增加高峰期间的发车班数；2）减少某些时区的发车次数；3）为了便于调度，我们还可以在不影响载客的前提下对一个小时内的发车次数进行微调，考虑到实际情况是一天的总客流量，向上的与向下的应该是相等的，为了不跑空车，我们还应保证一天中上行的总发车次数与下行的总发车次数相等；根据以上几点原则，我们可以进行手调，得到以下的发车方案表5：改进后的上行方向发车方案时区123456789101112131415161718车次624402415101010888152485332表6：改进后的下行方向发车方案时区123456789101112131415161718车次582430158
21、8688102030208663每个始发站共需发车223次6.3 进一步改进的方向1） 每一个站点都可以看作是一个服务系统，可以近似看作是一个排队问题，整个问题就可以看作一个多服务系统的排队问题；2） 找到一个更好的评价函数，能够同时对公司的利益与乘客的满意度进行比较；3） 求发车次数时可以考虑的时间长一点，即把不同的时区合在一起，可以减少发车次数；由于时间紧张，我们没能继续深入这些七 模型的推广及应用7.1 为了更好地设计调度方案，我们采集数据可用下面几种方法1） 我们可以连续二或三天进行调查，在全天的运营调查中，调查各站所有乘客的下车地点和他们分别坐了几站；） 调查节假日的客流情况；3）
22、各站下车乘客他们分别是从哪些车站上车的；7.2 应用实际在公交系统中，是多条路线在运营的，每条路线都可以用这种方法来考虑，只是要多考虑一下各条路线之间的联系，因为它们有的路线是重合的。参考文献1 1 同济大学，城市道路与交通，中国建筑工业出版社，19792 2 Eva part-enander，MATLAB 5 手册，机械工业出版社，2000附录附录1两个始发站的发车时刻表：A13站点的发车时刻表5:00:007:26:249:09:1413:26:4017:23:335:10:007:27:529:13:5113:33:2017:26:105:20:007:29:209:18:2813:40
23、:0017:28:475:30:007:30:489:23:0513:46:4017:31:245:40:007:32:169:27:4213:53:2017:34:015:50:007:33:449:32:1914:00:0017:36:386:00:007:35:129:36:5614:07:3017:39:156:02:307:36:409:41:3314:15:0017:41:526:05:007:38:089:46:1014:22:3017:44:296:07:307:39:369:50:4714:30:0017:47:066:10:007:41:049:55:2414:37:301
24、7:49:436:12:307:42:3210:00:0014:45:0017:52:206:15:007:44:0010:05:2714:52:3017:54:576:17:307:45:2810:10:5415:00:0017:57:346:20:007:46:5610:16:2115:07:3018:00:006:22:307:48:2410:21:4815:15:0018:07:306:25:007:49:5210:27:1515:22:3018:15:006:27:307:51:2010:32:4215:30:0018:22:306:30:007:52:4810:38:0915:37
25、:3018:30:006:32:307:54:1610:43:3615:45:0018:37:306:35:007:55:4410:49:0315:52:3018:45:006:37:307:57:1210:54:3016:00:0018:52:306:40:007:58:4011:00:0016:03:2019:00:006:42:308:00:0011:05:0016:06:4019:10:006:45:008:02:3711:10:0016:10:0019:20:006:47:308:05:1411:15:0016:13:2019:30:006:50:008:07:5111:20:001
26、6:16:4019:40:006:52:308:10:2811:25:0016:20:0019:50:006:55:008:13:0511:30:0016:23:2020:00:006:57:308:15:4211:35:0016:26:4020:10:007:00:008:18:1911:40:0016:30:0020:20:007:01:288:20:5611:45:0016:33:2020:30:007:02:568:23:3311:50:0016:36:4020:40:007:04:248:26:1011:55:0016:40:0020:50:007:05:528:28:4712:00
27、:0016:43:2021:00:007:07:208:31:2412:06:0016:46:4021:10:007:08:488:34:0112:12:0016:50:0021:20:007:10:168:36:3812:18:0016:53:2021:30:007:11:448:39:1512:24:0016:56:4021:40:007:13:128:41:5212:30:0017:00:0021:50:007:14:408:44:2912:36:0017:02:3722:00:007:16:088:47:0612:42:0017:05:1422:10:007:17:368:49:431
28、2:48:0017:07:5122:20:007:19:048:52:2012:54:0017:10:2822:30:007:20:328:54:5713:00:0017:13:0522:40:007:22:008:57:3413:06:4017:15:4222:50:007:23:289:00:0013:13:2017:18:1923:00:007:24:569:04:3713:20:0017:20:56A0站点的发车时刻表5:00:008:19:5711:26:4016:22:1018:15:005:10:008:22:1011:33:2016:25:2018:18:005:20:008:
29、24:2311:40:0016:28:3018:21:005:30:008:26:3611:46:4016:31:4018:24:005:40:008:28:4911:53:2016:34:5018:27:005:50:008:31:0212:00:0016:38:0018:30:006:00:008:33:1512:08:3516:41:1018:33:006:06:408:35:2812:17:1016:44:2018:36:006:13:208:37:4112:25:4516:47:3018:39:006:20:008:39:5412:34:2016:50:4018:42:006:26:
30、408:42:0712:42:5516:53:5018:45:006:33:208:44:2012:51:3016:57:0018:48:006:40:008:46:3313:00:0017:00:0018:51:006:46:408:48:4613:07:3017:01:5618:54:006:53:208:50:5913:15:0017:03:5218:57:007:00:008:53:1213:22:3017:05:4819:00:007:02:308:55:2513:30:0017:07:4419:06:007:05:008:57:3813:37:3017:09:4019:12:007
31、:07:309:00:0013:45:0017:11:3619:18:007:10:009:03:4513:52:3017:13:3219:24:007:12:309:07:3014:00:0017:15:2819:30:007:15:009:11:1514:06:4017:17:2419:36:007:17:309:15:0014:13:2017:19:2019:42:007:20:009:18:4514:20:0017:21:1619:48:007:22:309:22:3014:26:4017:23:1219:54:007:25:009:26:1514:33:2017:25:0820:00
32、:007:27:309:30:0014:40:0017:27:0420:08:347:30:009:33:4514:46:4017:29:0020:17:087:32:309:37:3014:53:2017:30:5620:25:427:35:009:41:1515:00:0017:32:5220:34:167:37:309:45:0015:05:0017:34:4820:42:507:40:009:48:4515:10:0017:36:4420:51:247:42:309:52:3015:15:0017:38:4021:00:007:45:009:56:1515:20:0017:40:362
33、1:08:347:47:3010:00:0015:25:0017:42:3221:17:087:50:0010:06:0015:30:0017:44:2821:25:427:52:3010:12:0015:35:0017:46:2421:34:167:55:0010:18:0015:40:0017:48:2021:42:507:57:3010:24:0015:45:0017:50:1621:51:248:00:0010:30:0015:50:0017:52:1222:00:008:02:1310:36:0015:55:0017:54:0822:10:008:04:2610:42:0016:00:0017:56:0422:20:008:06:3910:48:0016:03:1017:58:0022:30:008:08:5210:54:0016:06:2018:00:0022:40:008:11:0511:00:0016:09:3018:03:0022:50:008:13:1811:06:4016:12:4018:06:0023:00:008:15:3111:13:2016:15:5018:09:008:17:4411:20:0016:19:0018:12:00
