公交车的调度 - 图文

公交车的调度

杜克勤 童颜 李科

摘要：本文解决的是一个公交车调度问题，目的是用尽可能少的车来运送乘客，

同时不能让乘客等待时间过长，也不能超载。

文中提出了一种解决本问题的新颖的模型。通过分析知，一个时区内需要

的车只与该时区内车站的最大转移客流量有关，于是我们对题目所给的数据进

行一系列变换处理，求出每个时段发的车的最大转移客流量，得到一个新的表格。

根据最大转移客流量，用线性规划的方法可以求出我们这个模型需要发车次数的

最小值，然后综合考虑乘客的等待时间等我们可以给出各个时区的发车次数，进

而确定全天发车时间表，由发车时间表，我们同样用线性规划方法求出需要的最

少车辆数。

用我们构造的模型，求出了一个可行的调度计划，并给出了发车时刻表。每

个方向的全天发车次数为237，需要的57辆公交车。通过编程模拟得出平均等

待时间2.17min和平均满载率81.6%，对这个解进行了评价，说明了本模型的特

点，并指出了进一步优化改进的方向。最后用一个模拟搜索方法又求出一个解，

并与第一个解相比较。

一 问题的提出

这是一个公共汽车调度问题。题目给出了来自我国一座特大城市某条公交线路的客流调

查和运营资料。

该条公交线路上行方向共14站，下行方向共13站，题目给出的是典型的一个工作日两

个运行方向各站上下车的乘客数量统计。公交公司配给该线路同一型号的大客车，每辆标准

载客100 人，据统计客车在该线路上运行的平均速度为20公里/小时。运营调度要求，乘客

候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟，车辆满载率不应超过 120%，

一般也不要低于50%。

我们的目标就是根据题目所给的这些统计资料，把调度问题抽象成一个明确完整的数学

模型，并求解，根据我们的解，给公交公司制定一个公交车调度方案和起点站的发车时刻表，

使公交公司能够有效降低成本，但又不能牺牲乘客的利益。

二 基本假设

1. 1. 候车队伍有良好的秩序；即要保证乘客先来先乘车的原则；

2. 2. 忽略其它情况对公交车的影响，即公交车以20公里/小时的速度匀速行驶；不计乘

客上、下车的时间及公交车起动、加速、滑行、制动时间（因为题中给的是平均速度）；

3. 3. 从i:00?(i?1):00时间段内到达某站的乘客数服从均匀分布；

4. 4. 公交公司只对公交车进行调度但在允许的范围内不限制乘客上车；既只要该车乘客

数不大于120则允许乘客上车，直到达到120为止；

5. 5. 每个时间段的发车间隔时间是确定的而且平均的。

三 符号说明与概念引进

3.1 概念引进

1

1 时区-----我们规定两相邻正点之间的单位时间间隔为一个时区，并给之编号

5：00-6：00 1时区 6：00-7：00 2时区 21：00-22：00 17时区

22：00-23：00 18时区

2 跨时区-----当一辆公交车从i时区出发在到达目的地之前已经进入下一个

?

2

i?1时区

时，我们就称为产生了跨时区。

3

4 4 如果一个乘客是在i时区来到j车站乘车的，我们称该乘客来自i时区

3 站间转移客流量M?i,j?-----有多少乘客乘坐i时区发出的车经过j车站到达

j?1车站（包括在j车站上车的乘客，）。

3.2 符号说明

1

l1、l2、l3??l18分别代表各个时区内发车的时间间隔

2 n1n2n3?n16n17n18分别代表各个时区内发车的总次数

3 A?i,j?：在i时区j车站的净上车客流量 4 M?i,j?：站间转移客流量（见上面定义）

5 Ti?1?i,j?：j车站来自i时区的人被发自i?1时区的车运走的数量

6 N?i,j?：i时区内发出的所有车在j车站运走的净乘客数量（上车人数减下车人数）。

四 问题的分析

我们应该在满足乘客的等待时间要求的前提下，合适地安排发车次数，得到发车时刻表，

使得发车次数尽可能的少，而且用到的车辆尽可能少。

我们的目标是求每一个时区内发车的次数，发车的次数由在该时区内发出的车要要运

送的乘客数量决定，那么我们就要求各个时区发出的车分别要运送的乘客数。知道了要运送

的乘客数，就可以用线性规划求发车车次ni。知道了发车车次，我们进而可以列出发车

时刻表，通过时刻表，可以用线性规划求最少车辆。

五 模型的建立和求解 起点 Ak 点

5:00 5.1 模型一

示意图见右。箭头表示车在一定时间内从起点开到终点。

6:00 由于公交车有跨时间段的问题（例：起点到第Ai站要用t(以小

时为单位))的时间，则在i：00到i+t时间内到达Ak站的乘客

可由i-1：00—i：00时间段内发出的公交车运走）。为了方便解决问题，

i:00

在i时区到达车站的这部分乘客将被i-1时区发出的车运走 我们以第i时区(6?i?22)发出的公交车来重新划分乘客， 在i时区到达车站的这部分乘客

找出各个站点上由这些车运送的乘客数量

由i时区发出的车运走

则从第j时区发出的车在Ak站点所要运

走的乘客数量为(假设在i:00到（i+1）:00在Ak点候车的

（i+1）:00 在i+1时区到达车站的这部分乘客由I时区发出的车运走

乘客数量为ui；在i:00到（i+1）:00在Ai点下车的乘客 数量为di)：

当j=1时，上车的乘客数为：u5?u6?t；

下车的乘客数为：d5?d6?t

22:00

当2?j?17时，上车的乘客数为：ui?ui?t?ui?1?t 当j=18时，上车的乘客数为：u22?u22?t

下车的乘客数为：d22?d22?t

我们再引入两个附加假设：

附加假设一： 假设i时区发出的第一辆与最后一辆车到达j车站的时刻分别为t1?j?，

23:00 下车的乘客数为：di?di?t?di?1?t 图 1 t2?j?，在t1?j?到t2?j?这个时间间隔内，乘客的到来服从均匀分布。

（原来假设一个时区里来人是均匀的；当求出在t1?j?到t2?j?内来的人数后，再认为这段时间内来人均匀）

附加假设二： 假设i时区发出的车能够把t1?j?-t2?j?这个时间间隔内来到j车站的乘客全部运走。

下面我们要解决的问题：具体求出i时区发出的车要运多少乘客

命题一： 在考虑车站转移客流量M?i,j?时，在一个站我们分别考虑上下车人数与我们考虑

净上车人数是等价的。

命题二： 每个时区内公交车的发车次数的下限由这个时区内相邻两站间最大转移客流量

maxM?i,j?决定。

证明： maxM?i,j?表示在i时区要经由j车站向下的乘客，我们要保证人能被运走，但又不

能超载，即满载率不能超过120%，那么如果留。

ni?maxM?i,j?120,必然导致该站的部分乘客滞

命题三： 在第i时区来j车站的乘客是被发自i?1时区和发自i时区的车共同运走的，而且

被i?1时区的车运走的乘客Ti?1?i,j?占j车站总乘客的比例由j车站距始发站的

距离决定。

推论： 第i时区内发的车从j车站运走的乘客来自于i时区和i?1时区，运送的i?1时区

的乘客Ti?i?1,j?占总乘客的比例也由j车站距始发站的距离决定。

由这四个命题我们可以得出的一个算法： 1）

1）

计算i时区j车站净上车人数A?i,j?（i=1,2,?17,18；

j?13,12,11,?2,1,0）；

2）

2） 计算Ti?1?i,j?和Ti?i?1,j?（Ti?1?i,j?为在i时区来的乘客被i?1时区发出的车运走的数量，Ti?i?1,j?为从i时区发的车运送的在i?1时区来的乘客）

3）

3） 计算i时区发出的车需从j车站运走的乘客的数量N?i,j?，

N?i,j?=A?i,j?-Ti?1?i,j?+Ti?i?1,j?

4） 5）

4） 计算i时区j车站的转移客流量M?i,j?，M?i,j?=i?13?N?i,j?j（对于上行

方向来说），即i时区内发出的车从起点站到j站的净上车人数之和。

M?i,j?和需要的发车次数ni的关5） 据i时区内各车站的最大转移客流量max系：

maxM?i,j??ni*120

从而确定ni的最小值。

用以上算法，将原表格变换成为一个新的表格，用来求发车次数。

我们编了一个程序来计算每个车站由i时区出发的车的转移客流量，最后求的结果列表如下：（各个时区的最大转移客流量用粗体标出）

表1：上行方向的各个车站的转移客流量 站名 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 A13 371 1990 3626 2064 1186 923 957 873 779 625 635 1493 2011 691 350 304 209 19 A12 445 2279 4038 2273 1308 1024 1081 969 878 695 734 1716 2265 767 391 337 230 19 A11 512 2514 4326 2445 1396 1093 1180 1057 941 763 803 1875 2444 823 423 362 246 19 A10 556 2620 4485 2505 1423 1123 1227 1090 958 796 834 1938 2495 833 435 373 250 17 A9 679 2996 4912 2667 1519 1211 1346 1190 1042 876 924 2148 2700 886 464 405 265 14 A8 723 2944 4753 2577 1422 1134 1289 1138 1013 861 890 2052 2527 826 440 394 246 5 A7 645 2594 4259 2267 1210 975 1143 1022 922 765 733 1805 2305 726 388 354 219 -4 A6 563 2106 3589 1903 982 774 981 899 804 611 509 1470 2020 575 299 282 167 -16 A5 670 2209 3638 1911 1002 819 1041 945 838 637 548 1557 2099 599 302 277 159 -19 A4 660 2074 3498 1841 960 780 995 915 812 605 513 1476 2031 572 287 264 149 -20 A3 685 2020 3422 1789 925 755 968 899 796 583 476 432 1991 547 276 254 141 -24 A2 718 1908 3245 1682 864 712 932 874 767 555 432 1335 1922 520 263 241 131 -27 A1 44 409 1965 845 289 208 458 483 405 213 -195 292 1289 264 99 111 734 -36 由以上数据，我们可以建立一规划模型来求解minni

目标函数： minni

maxM?i,j??120ni s.t： (j?1,2,3,?17,18)

经过求解，对所得数据进行近似及权衡乘客等待时间，我们得到了以下一组时区车次安排

表2：上行方向的各个时区的车次安排 时1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 区 车6 24 41 23 13 11 12 10 9 次 总共需发车237次

同理我们可以求得下行方向的车次安排

表3：下行方向的各个车站的转移客流量 站点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 A0 22 795 2328 2706 1556 902 847 706 770 839 1110 1837 3020 1966 939 640 636 294 A2 29 869 2416 2809 1603 945 882 726 794 889 1172 1927 3163 2084 957 672 671 301 A3 48 1014 2695 3123 1770 1064 956 805 880 998 1303 2181 3541 2333 1060 756 751 328 A4 56 1062 2763 3193 1812 1087 985 829 897 1018 1322 2223 3595 2384 1089 780 763 332 A5 47 975 2460 2878 1654 1000 914 761 828 930 1225 2045 3318 2114 972 704 687 299 A6 39 878 2143 2607 1468 873 830 688 752 846 1085 1813 3025 1849 864 622 601 262 8 8 18 23 8 6 6 6 4 A7 31 609 1586 2154 1183 693 695 576 628 681 840 1378 2482 1536 711 497 511 227 A8 -3 515 1391 1992 1090 638 641 543 592 633 751 1233 2309 1415 659 456 478 211 A9 17 509 1365 1986 1087 628 626 544 603 653 758 1246 2346 1433 661 453 471 209 A10 -23 299 1053 1740 925 512 534 455 501 541 589 964 2030 1243 563 364 407 189 A11 -38 212 953 1685 888 486 511 435 476 506 550 903 1931 1181 535 337 387 183 A12 -101 -34 623 1445 732 365 415 339 373 389 354 566 1612 994 434 250 327 168

表4：下行方向的各个时区的车次安排 时1 2 3 4 5 6 7 8 区 车6 9 24 27 16 10 9 次 总共需发车237次

7 9 8 10 11 12 13 14 15 16 17 18 9 12 19 31 20 10 7 7 6 公交车时刻表的安排

由于我们假设在各个时区内发车间隔相等，所以由以上的发车次数我们很容易得到始发站的

发车时刻表（具体见附录）

需要车辆数的求解

知道了具体的发车时刻，我们就可以去求至少需要多少辆车

设D1为A13站必须的车辆数，D2为A0站必须的车辆数

din?i?为A13站在i时刻发车前由A0已经开到的车次数，dout?i?为A13站在i时刻发车前

开出的车次数

fin?j?为A0站在j时刻发车前由A13已经开到的车次数，fout?j?为A0站在j时刻发

车前开出的车次数

目标函数： min D1+D2

s.t：. D1+din?i?-dout?i??1 D2+fin?j?-fout?j??1

（i，j分别是已经确定的两个始发站的发车时刻）

通过对这个线性规划求解，我们可以得出需要的最少车辆D=D1+D2 D=57

5.2 模型二：模拟搜索

我们又用模拟的方法编了一个搜索程序去搜索可行的车次（程序清单见附录2.b）

我们尽可能地去模拟每步的情况，对各种情形做出分析

用这种方法我们得出上行情况的一组车次安排（下行情况略） 时1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 区 车7 26 41 23 13 10 13 10 9 8 9 18 23 8 6 6 6 6 次

总共需发车242班

比较这两种方法得出的结果可以看到相差并不大，用模拟搜索总数要大一点，这是由于两种

方法处理乘客等待时间时要求不一样造成的

六 模型的评价及改进方向

6.1 评价

我们对这种发车车次安排进行了评价，我们用平均等待时间和最长等待时间来评价乘客的满

意度，用平均满载率来评价公交公司的利益。 平均等待时间t-----所有乘客等待时间的平均值，

?(t*m)以上行为例，可以证明 t? 2*?m，

iii其中 ti是第i时区发车间隔，

mi第i时区发出的车在全程运载的总人数。

平均满载率?-----在这一天中，发出的车的载客能力利用率

同样以上行为例， ? = B*100*13 ， 其中B为全天中上行方向总的发车班数。

用编程方法算得t=2.17分钟，?=81.58%，程序见附录。

1） 于我们模型严格的时间控制，使得在整个运送过程中，没有乘客等待时间超过10分钟，

并且平均等待时间t达到一个很小的值，对乘客来说，是非常满意的，这也有利于提高公

司的社会效益。

2） 但是对于公交公司来说，虽然车的载客能力利用率?=81.58%已经较大，在早晨与晚上

的时区内，我们安排的车的满载率远远低于50%，因此我们可以适当地减少早上，晚上

的发车班数，以提高车的利用率。严格保证乘客的利益，是需要总的车辆数较大的主要原因。

?mi6.2 改进

1） 按照经验，在早高峰期间一般还存在着一个超高峰，我们可以增加高峰期间的发车班数；

2）减少某些时区的发车次数；

3）为了便于调度，我们还可以在不影响载客的前提下对一个小时内的发车次数进行微调，

考虑到实际情况是一天的总客流量，向上的与向下的应该是相等的，为了不跑空车，我

们还应保证一天中上行的总发车次数与下行的总发车次数相等；

根据以上几点原则，我们可以进行手调，得到以下的发车方案

表5：改进后的上行方向发车方案 时1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 区 车6 24 40 24 15 10 10 10 8 次 表6：改进后的下行方向发车方案 时1 2 3 4 5 6 7 8 9 区 8 8 15 24 8 5 3 3 2 10 11 12 13 14 15 16 17 18 车5 8 24 30 15 8 次 每个始发站共需发车223次

8 6 8 8 10 20 30 20 8 6 6 3 6.3 进一步改进的方向

1） 每一个站点都可以看作是一个服务系统，可以近似看作是一个排队问题，整个问题就可

以看作一个多服务系统的排队问题；

2） 找到一个更好的评价函数，能够同时对公司的利益与乘客的满意度进行比较；

3） 求发车次数时可以考虑的时间长一点，即把不同的时区合在一起，可以减少发车次数；

由于时间紧张，我们没能继续深入这些

七 模型的推广及应用

7.1 为了更好地设计调度方案，我们采集数据可用下面几种方法

1） 我们可以连续二或三天进行调查，在全天的运营调查中，调查各站所有乘客的下车地点

和他们分别坐了几站；

） 调查节假日的客流情况；

3） 各站下车乘客他们分别是从哪些车站上车的；

7.2 应用

实际在公交系统中，是多条路线在运营的，每条路线都可以用这种方法来考虑，只是要多

考虑一下各条路线之间的联系，因为它们有的路线是重合的。

参考文献

1 1 同济大学，《城市道路与交通》，中国建筑工业出版社，1979 2 2 Eva part-enander，《MATLAB 5 手册》，机械工业出版社，2000

附录

附录1．两个始发站的发车时刻表：

A13站点的发车时刻表 5:00:00 7:26:24 9:09:14 5:10:00 5:20:00 5:30:00 5:40:00 5:50:00 6:00:00 6:02:30 6:05:00 6:07:30 6:10:00 6:12:30 6:15:00 6:17:30 6:20:00 6:22:30 6:25:00 6:27:30 6:30:00 6:32:30 6:35:00 6:37:30 6:40:00 6:42:30 6:45:00 6:47:30 6:50:00 6:52:30 6:55:00 6:57:30 7:00:00 7:01:28 7:02:56 7:04:24 7:05:52 7:07:20 7:08:48 7:10:16 7:11:44 7:13:12 7:14:40 7:27:52 7:29:20 7:30:48 7:32:16 7:33:44 7:35:12 7:36:40 7:38:08 7:39:36 7:41:04 7:42:32 7:44:00 7:45:28 7:46:56 7:48:24 7:49:52 7:51:20 7:52:48 7:54:16 7:55:44 7:57:12 7:58:40 8:00:00 8:02:37 8:05:14 8:07:51 8:10:28 8:13:05 8:15:42 8:18:19 8:20:56 8:23:33 8:26:10 8:28:47 8:31:24 8:34:01 8:36:38 8:39:15 8:41:52 8:44:29 9:13:51 9:18:28 9:23:05 9:27:42 9:32:19 9:36:56 9:41:33 9:46:10 9:50:47 9:55:24 10:00:00 10:05:27 10:10:54 10:16:21 10:21:48 10:27:15 10:32:42 10:38:09 10:43:36 10:49:03 10:54:30 11:00:00 11:05:00 11:10:00 11:15:00 11:20:00 11:25:00 11:30:00 11:35:00 11:40:00 11:45:00 11:50:00 11:55:00 12:00:00 12:06:00 12:12:00 12:18:00 12:24:00 12:30:00 12:36:00 13:26:40 13:33:20 13:40:00 13:46:40 13:53:20 14:00:00 14:07:30 14:15:00 14:22:30 14:30:00 14:37:30 14:45:00 14:52:30 15:00:00 15:07:30 15:15:00 15:22:30 15:30:00 15:37:30 15:45:00 15:52:30 16:00:00 16:03:20 16:06:40 16:10:00 16:13:20 16:16:40 16:20:00 16:23:20 16:26:40 16:30:00 16:33:20 16:36:40 16:40:00 16:43:20 16:46:40 16:50:00 16:53:20 16:56:40 17:00:00 17:02:37 17:23:33 17:26:10 17:28:47 17:31:24 17:34:01 17:36:38 17:39:15 17:41:52 17:44:29 17:47:06 17:49:43 17:52:20 17:54:57 17:57:34 18:00:00 18:07:30 18:15:00 18:22:30 18:30:00 18:37:30 18:45:00 18:52:30 19:00:00 19:10:00 19:20:00 19:30:00 19:40:00 19:50:00 20:00:00 20:10:00 20:20:00 20:30:00 20:40:00 20:50:00 21:00:00 21:10:00 21:20:00 21:30:00 21:40:00 21:50:00 22:00:00

7:16:08 7:17:36 7:19:04 7:20:32 7:22:00 7:23:28 7:24:56

5:00:00 5:10:00 5:20:00 5:30:00 5:40:00 5:50:00 6:00:00 6:06:40 6:13:20 6:20:00 6:26:40 6:33:20 6:40:00 6:46:40 6:53:20 7:00:00 7:02:30 7:05:00 7:07:30 7:10:00 7:12:30 7:15:00 7:17:30 7:20:00 7:22:30 7:25:00 7:27:30 7:30:00 7:32:30 7:35:00 7:37:30 7:40:00 7:42:30 8:47:06 8:49:43 8:52:20 8:54:57 8:57:34 9:00:00 9:04:37 12:42:00 12:48:00 12:54:00 13:00:00 13:06:40 13:13:20 13:20:00 17:05:14 17:07:51 17:10:28 17:13:05 17:15:42 17:18:19 17:20:56 22:10:00 22:20:00 22:30:00 22:40:00 22:50:00 23:00:00 A0站点的发车时刻表 8:19:57 11:26:40 8:22:10 8:24:23 8:26:36 8:28:49 8:31:02 8:33:15 8:35:28 8:37:41 8:39:54 8:42:07 8:44:20 8:46:33 8:48:46 8:50:59 8:53:12 8:55:25 8:57:38 9:00:00 9:03:45 9:07:30 9:11:15 9:15:00 9:18:45 9:22:30 9:26:15 9:30:00 9:33:45 9:37:30 9:41:15 9:45:00 9:48:45 9:52:30 11:33:20 11:40:00 11:46:40 11:53:20 12:00:00 12:08:35 12:17:10 12:25:45 12:34:20 12:42:55 12:51:30 13:00:00 13:07:30 13:15:00 13:22:30 13:30:00 13:37:30 13:45:00 13:52:30 14:00:00 14:06:40 14:13:20 14:20:00 14:26:40 14:33:20 14:40:00 14:46:40 14:53:20 15:00:00 15:05:00 15:10:00 15:15:00 16:22:10 16:25:20 16:28:30 16:31:40 16:34:50 16:38:00 16:41:10 16:44:20 16:47:30 16:50:40 16:53:50 16:57:00 17:00:00 17:01:56 17:03:52 17:05:48 17:07:44 17:09:40 17:11:36 17:13:32 17:15:28 17:17:24 17:19:20 17:21:16 17:23:12 17:25:08 17:27:04 17:29:00 17:30:56 17:32:52 17:34:48 17:36:44 17:38:40 18:15:00 18:18:00 18:21:00 18:24:00 18:27:00 18:30:00 18:33:00 18:36:00 18:39:00 18:42:00 18:45:00 18:48:00 18:51:00 18:54:00 18:57:00 19:00:00 19:06:00 19:12:00 19:18:00 19:24:00 19:30:00 19:36:00 19:42:00 19:48:00 19:54:00 20:00:00 20:08:34 20:17:08 20:25:42 20:34:16 20:42:50 20:51:24 21:00:00 7:45:00 7:47:30 7:50:00 7:52:30 7:55:00 7:57:30 8:00:00 8:02:13 8:04:26 8:06:39 8:08:52 8:11:05 8:13:18 8:15:31 8:17:44

9:56:15 10:00:00 10:06:00 10:12:00 10:18:00 10:24:00 10:30:00 10:36:00 10:42:00 10:48:00 10:54:00 11:00:00 11:06:40 11:13:20 11:20:00 15:20:00 15:25:00 15:30:00 15:35:00 15:40:00 15:45:00 15:50:00 15:55:00 16:00:00 16:03:10 16:06:20 16:09:30 16:12:40 16:15:50 16:19:00 17:40:36 17:42:32 17:44:28 17:46:24 17:48:20 17:50:16 17:52:12 17:54:08 17:56:04 17:58:00 18:00:00 18:03:00 18:06:00 18:09:00 18:12:00 21:08:34 21:17:08 21:25:42 21:34:16 21:42:50 21:51:24 22:00:00 22:10:00 22:20:00 22:30:00 22:40:00 22:50:00 23:00:00

本文来源：https://www.bwwdw.com/article/xib7.html