2500
2000
1500
1000
500
0
0
2
4
6
8
10 12 14 16
18 20
（下行方向） 从上行方向图中可以看出，一天之内有两个明显的高峰分别是早高峰期 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）。 我们的目标为
t= t1 ,这时只需
N 2 >2
t0 t1
辆车就可以了。从而
3
证明了我们的结论。分析原因，在总时间足够长时，为保证两边都按各自的时间间隔发车，在发车间隔小
的站点要不断的补发车，而在发车间隔大的站点会有车堆积，等待的时间较长。因此这种方法所需的车数 多，而且车的利用率比较低。 选取上行方向和下行方向对应时间段发车间隔的较小值，即选取
上行方向
低谷期 早高峰期 中间期
晚高峰期 低谷期
5:00-6:00 6:00-10:00 10:00-16:00 16:00-19:00 19:00--23:00 发车间隔(分钟)
下行方向
10 低谷期
2
7
早高峰期 中间期
2 晚高峰期
10 低谷期
5:00-7:00 7:00-10:00 10:00-15:00 15:00-19:00 19:00--23:00 发车间隔(分钟)
t2 ,为保证A站的车仍旧能Fra bibliotek照间隔t1
发出,在
t0
时间内要补发
t0 t1
− t0 t2
辆车。这时需要的总车数 N1 ≥
t0 t1
+
t0 t2
+( t0 t1
− t0 t2
)。如果
T>3
t0
,则在
A
站就会再次补车，这样
N1
＞
t0 t1
+
t0 t2
+( t0 t1
− t0 t2
)=2 t0 t1
。
在两边的发车间隔相等时，发车间隔取 t1 , t2 中较小的一个,即
i= A0
n
公交公司进行一天的运营所需的总车辆数
四、问题的分析和模型的建立
寻找调度方案，首先要找出发车间隔。根据给出的数据，做出每个时间段内始发站上车人数的直方图
如下。
4000
3500
3000
2500
2000
1500
1000
500
0
0
2
4
6
8 10 12 14 16 18 20
（上行方向）
3500
3000
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 等候车队中还有剩余车辆，将这些车辆入库。 （Ⅱ）下行方向的调度方案。
t1=2,t2=7,t3=2,t4=10 在这种情况下，可以减少每时间段内需要的车辆数，使得调度更方便，同时提高了乘客的满意率，只是在 车辆的满载率上有所下降。我们认为，对于公交公司来说，减少车辆数意义更大，所以这样的选取是合理
的。得到结果如下表 表1
t1 t2 t3 t4
C
E
P
2min 7min 2min 10min 0.5903 0.1150 0.95
公交车调度方案
陈爽 刘伟 舒传华 摘要： 本文要求在照顾乘客和公交公司双方利益的前提下，给出一个合理的调度方案。我们以乘客 的满意率、公交公司的满载率和所需车辆数目为目标函数，求它们的加权和的最大值。由于双方的利益是 矛盾的，如何找到一个令双方都能接受的解是问题的关键。我们找出了与双方利益均密切相关的因素—— 发车间隔，通过对发车间隔的寻优，来解决这个问题。 在寻找发车间隔的过程中，针对各个时间段内始发站上车人数的不同将发车间隔按早晚高峰期、低谷 期、中间期，分成四个时期，采用搜索算法进行求解。结果为早高峰期发车间隔为 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%。 试根据这些资料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个 起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益； 等等。 如何将这个调度问题抽象成一个明确、完整的数学模型，指出求解模型的方法；根据实际问题的要求， 如果要设计更好的调度方案，应如何采集运营数据。 二、问题的假设 公交车运行的平均速度为总路程除以总时间，总时间包括行驶时间和乘客上下车的时间。 到达任一车站的乘客人数在一个小时内服从均匀分布。 每辆车最多可以坐 120 名乘客，并且乘客对这种情况不会抱怨。 公交公司只有一个车库在上行方向的起始站处，每天早上运营开始前所有车辆均集中在上行方向的始 发站，晚上所有车均回到车库。但两个方向的始发站各有一个停车场，以共白天停车使用。 三、符号的说明
10
2
7
2
10
（二）调度方案
在上行方向，由于有车库，不存在该发车时没有车可发的情况，而在下行方向由于在每天开始时均无
车可发，因此我们的调度系统一定要保证下行方向可以顺利发车。 （Ⅰ）上行方向的调度方案。
将下行方向车的到达时间与上行方向车的发车时间列出，对照可知有以下几种情况
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 分 钟后就将其作为上行车发出。
意率限制在一定范围之内，将其作为约束条件，只对第三个指标求最值。根据实际情况和经验，我们选取 P≥95%。同时可以发现 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 尽可能大的值。 其余步骤与上行线完全相同。