公交公司车辆调度方案设计林大海,徐文溢,赖清文一、问题的提出优先发展公共交通的交通政策是解决城市交通问题的根本途径，不论是在我国或者是在外国都是如此。
公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。
要求考虑一条公交线路上公交车的调度问题，其数据来自我国一座特大城市某条公交线路的客流调查和运营资料。
该条公交线路上行方向共14站，下行方向共13站，已经给出的是典型的一个工作日两个运行方向各站上下车的数量统计。
公交公司配给该线路同一型号的大客车，每辆车标准载客100人，据统计客车在该线路上运行的平均速度为20公里/小时。
运营调度要求，候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟，车辆满载率不应超过120%，一般也不要低于50%。
根据提供的资料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个起点站的发车时刻表；一共需要多少辆车；以使这个方案更大程度上照顾到了顾客和公交公司双方的利益。
二、问题的分析一辆公交车在整个的行驶过程显然会涉及许多的因素，如1、与公共汽车有关的因素主要有离开公共汽车总站的时间、到达每一汽车站的时间、在每一汽车站下车的乘客数、在每一汽车站停留的时间、载客总数、最大容量、行进速度、交通条件等；2、与乘客有关的因素主要有到达某一车站的时间、乘车距离（站数）、等车的时间、总的旅行时间等；3、与车站有关的因素主要有线路上汽车站的位置、从上一辆车离开车站后过去的时间、乘客到来的频率、下一辆车到来时正在等车的乘客数、车站之间的距离。
这些因素相互之间互为联系、互相影响甚至可以互相转化，经过仔细分析不难发现，这些因素无非只有两个指标：时间和人数。
图（1）上行方向各站点上车乘客数量累积图图（2）上行方向各站点乘客每分钟上车乘客数图（1）是上行方向各站点全天上车乘客数量的累积图，由于乘客上车受公交车运行间隔时间的影响，因此，我们将每小时上车的乘客数认为是到达车站的乘客数是合理。
从理论上说，乘客到达车站是随机的、离散的，但在很小的时间间隔内，比如1分钟内，乘客到达车站的数量是近似于连续变化的，即在相邻的两分钟内，到达车站的乘客数不会相差很大。
问题提供的是一小时乘客上下车的人数，而公交车的运行是以分为单位的，因此如何求出乘客到达车站的规律是解决问题的关键。
虽然图（1）是由直线连成，但看起来仍然相当光滑，因此本文利用数值方法求出每个车站的上下车的流量函数，由于假定客流量连续变化，流量函数应二阶连续可微，我们采用三次样条插值的方法求流量函数。
并仍使用数值方法求出客流密度。
顾客的不满意度：作为顾客，他们所关心的主要是两个方面的问题：等待时间和所乘汽车的拥挤度.如果能保证顾客在十分钟内能搭上车（早高峰时5分钟内能搭上车），顾客一般比较满意，但如果要等的车来了，却搭不上则会使顾客很不满意。
我们认为当车上的人数超过100时顾客感到拥挤，并且规定当车上的人数超过120时，顾客宁愿等下班车。
为了量化顾客的满意度，我们将一人次搭不上车作为一个单位，求出全天搭不上车的次数，即误车次数，同时把汽车经过各站后车上人数超过100的部分累加得出全天的拥挤程度。
由于误车是有车来了而乘客上不了车，不满意程度更大，因此我们定义顾客的不满意度=0.4拥挤的不满意度+ 0.6误车次数的不满意度公交公司的不满意度：作为公交公司由于顾客的总量一般不会发生变化，即收益不会发生变化，所以其所追求的是发出车次及使用车辆数的极小化（但必须保证将所有的顾客运送至目的地），即成本的极小化。
根据实际情况一辆汽车的买价大约为发出一趟车所需费用的10000倍，因而，我们用所需的车辆数乘以10000加上发车的次数来衡量公交公司的不满意程度。
客流密度：在较短的单位时间内（如1分钟内）上车（到站）或下车的人数；流量：指从初始时刻到某时刻的上车（到站）或下车的乘客的累积人数。
三、模型的假设我们作如下假设：1、不存在交通堵塞；2、大客车按匀速20公里/小时行驶，乘客上下车的时间以及大客车在各个站上的停留时间忽略不计；3、大客车到终点站后的调头时间忽略不计，司机和售票员的换班时间也忽略不计；4、客流量是连续变化的，并且客流量的变化率也连续变化；由于在该线路上的客流量相当大，每天的客流量达到十万余人，因此可以认为在相邻的单位时间内到达车站的人数应该近似于连续变化，这是合理的。
5、顾客一般会按先来后到上车；6、乘客不会因为等待时间过长而改乘其它交通工具（例如出租汽车等）；7、表中数据的上车人数为到站人数（由于不改乘其他交通工具，因此上车人数就是到站人数）；8、每车次的费用相同，与乘客的数量无关；9、为便于操作，发车的时间间隔为整分钟。
即不会安排在类似于6时12分24秒的时间发车；10、所给的数据能近似代表一般情形；11、 在线路的两端都设有停车场，且容量足够使用；12、 候车时间在早高峰时不超过5分钟，其他时刻不超过10分钟时认为顾客满意。
四、符号说明在本文中将出现以下重要符号：b a ,：公交车的头班车和末班车发车时间M ：大客车的限制载客量；j t ∆：表示从起点站至第j 站大客车运行的时间，01=∆t ；m ：采集的样本容量；n ：单条线路上的车站数量；ij a ：表示第j 站第i 时段上车乘客的人数；ij b ：表示第j 站第i 时段下车乘客的人数；ij x ：表示第j 站第1至第i 时段上车乘客的流量；ij y ：表示第j 站第1至第i 时段下车乘客的流量；)(t f j ：表示第j 站t 时刻上车乘客的流量；)(t g j ：表示第j 站t 时刻下车乘客的流量；)()()(1--=∆i j i j i j t f t f t f ：表示时刻i i t t 至1-第j 站新增加的乘客人数；)()()(1--=∆i j i j i j t g t g t g ：表示时刻i i t t 至1-第j 站的下车人数；ij c ：表示第i 次发出的车在停靠第j 个车站时第j 站正在候车的人数，这批乘客应尽量乘坐该次车；ij d ：表示第i 次发出的车在离开第j 个车站时该车站尚未上车的人数；)(i S j ：表示第i 次发出的车在离开第j 个车站后车上的乘客数；)(t p j ：表示第j 站t 时刻上车乘客的客流密度；)(t q j ：表示第j 站t 时刻下车乘客的客流密度；五、模型的建立和求解在问题分析中已经指出，解决这个问题之间必须先了解乘客上下车及到达车站的规律，可以用常见的随机模型来表示这种规律，如可认为每小时段的乘客数呈均匀分布，也可认为乘客数呈指数分布等等，但是问题中要求提供调度方案，并指出提供的数据是典型的，因此我们认为先不需要考虑数据的随机性，而是要求出各车站的流量函数。
从初始时刻至i 时段在第j 个车站要求上车的累积人数为ij x ∑==ik kj a 1 m i ,,2,1 =，n j ,,2,1 = ------------------（1）从初始时刻至j t 时段在第i 个车站下车的累积人数为ij y ∑==ik kj b 1 m i ,,2,1 =，n j ,,2,1 = ------------------（2）在问题的分析中我们已经知道，乘客上车或下车的流量变化可近似看作是连续变化的，并且乘客的客流密度也可以近似看作是连续变化的，因此如果分别作ij x ，ij y （m i ,,2,1 =）的三次样条插值，可得第j 个车站在任意时刻t 的上车流量函数)(t f j 和下车流量函数)(t g j ，并且相应的客流密度函数分别为)(t p j )(t f j '= n j ,,2,1 = ------------------（3）)(t q j )(t g j '= n j ,,2,1 = -------------------（4）以上结果适用用于任意个车站和任意组采集的数据的情形。
用MA TLAB 软件可以得到上行方向和下行方向各车站上下车的流量和客流密度的数值解，本文取步长为1分钟，图（3）和图（4）分别上行方向起点站A13上车的流量和客流密度曲线。
图（2）是所有车站的客流密度曲线。
图（3） 上行方向起点站A13的上车流量 图（4） 上行方向起点站A13的上车客流密度模型一（即时需求法）即时需求法的意思是哪个站点的候车人数达到指定的上限即有车准时到达，故称为即时需求法。
假定问题给出的各时段上车人数近似为相应时段到达车站的人数，为了使乘客尽快上车，假设发车条件为：（1）只要始发站的候车乘客数累积达到120人即发车；（2）只要某车站的候车乘客数累积达到120人即增发一辆空车到该站；（3）或者距离上次发车时间达到10分钟；（4）5时整和23时整发首班车和末班车。
为了求解的简便，假定在各整点时间之间到达车站的人数为问题所给定的相应时段的上车人数。
给出数据时假定了上车人数为到达车站的人数，求出需要多少车次才能运走始发站的乘客及相应的发车时间。
然后在此基础上，求出需要追加多少车次才能运走后面车站的乘客及相应的发车时间。
如此反复，直到求出最后一站所需追加的车次及相应的发车时间。
模型设计及求解步骤为：1、首先考虑始发站点A13，按照时间顺序，当站点A13的累计候车人数达到120人，或发车时间间隔达到10分钟时，发出一辆公交车。
根据乘客到达车站的时间可以求出发车时间；2、对于站点A12，由于站点A13发出的车基本上是满载（客流量较少时例外），而在A12下车的乘客留出的空位很难满足A12要上车乘客的需求，因此可以求出当A12的候车累积人数到达120人的时间，以便提前从A13向A12直接发出空车运送A12的乘客，以使A12的乘客候车时间不要太长；3、依此类推，求出增发至A11至A1各站的发车时间，并按此方案设计出全天的公交 车调度方案；4、 下行方向也类似处理。
利用MATLAB 软件编写求解模型一的程序，部分结果如下（程序参见附录2）：全天共需发车总次数为459次，其中上行方向由A13发出233次，下行方向由A0发出 226次；上行方向发出的233车次中，有51车次需要直接加发至其他站点，有191车次是严重满载，发车时即为120人；下行方向发出的226车次中，有31车次需要直接加发至其他站点，有196车次是严重满载，发车时即为120人；为了保证模型一设计出的调度方案能顺利实行，全线路至少需要62辆大客车，其中在站点A13处停放57辆，在站点A0处停放5辆。
模型一的顾客不满意度为：41021314.8⨯,公交公司的不满意度为：4100459.62⨯模型二设第i 次发车的时间为i t ，根据符号系统的定义不难得到第j 站要求上第i 次车的乘客数 )()1(j i j j i ij t t f d c ∆+∆+=-)()(1)1(j i j j i j j i t t f t t f d ∆+-∆++=-- --------（5）第j 站要求下第i 次车的乘客数)()()(1j i j j i j j i j t t g t t g t t g ∆+-∆+=∆+∆- ------------(6)第i 次车停靠第j 站经过下车后的车上剩余乘客数)()(1j i j j t t g i S ∆+∆--第i 次车停靠第j 站经过上下车后的车上乘客数⎪⎩⎪⎨⎧≤+∆+∆-≤+∆+∆-≤+∆+∆->+∆+∆-=----0)()()()(0)()()()()(1111ij j i j j ij ij j i j j ij j i j j ij j i j j j c t t g i S c M c t t g i S c t t g i S M c t t g i S M i S -----(7)第i 次车离开第j 站时第j 站尚未上车的人数=≤ij d 0)]()()([1j i j j j ij t t g i S i S c ∆+∆+--- ----------------(8) ,2,1=i ,n j ,,2,1 =,并且规定,0)(,000=∆+=j j j t t f d 0)(,0)(00=∆+=j j t t g i S . 在给定了数据后，(3)~(8)式可以描述全天这条线路的运行情况，包括车站和车上的乘客数量的动态变化过程。