对公交车调度问题的研究
数学建模论文
——对公交车调度问题的研究
摘要:本文根据所给的客流量及运营情况排出公交车调度时刻表以及反映客运公司和乘客的利益有多个指标,建立了乘客的利益及公司的利益两个目标函数的多目标规划数学模型。基于多目标规划分析法,进行数值计算,从而得到原问题的一个明确、完整的数学模型,并在模型扩展中应用已建立的计算机模拟系统对所得的结果和我们对于调度
的想法进行分析和评价。
首先通过数据的分析,并考虑到方案的可操作性,将一天化为:引入乘客的利益、公司利益作为两个目标函数,建立了两目标优化模型。通过客运能力与运输需求(实际客运量)达到最优匹配、满载率高低体现乘客利益;通过总车辆数较少、发车次数最少表示公司利益建立两个目标函数。应用matlab中的fgoalattain进行多目标规划求出发车数。
一、问题的重述
1、路公交线路上下行方向各24站,总共有L 辆汽车在运行,开始时段线路两端的停车场中各停放汽车m辆,每两车可乘坐S人。这些汽车将按照发车时刻表及到达次序次发车,循环往返地运行来完成运送乘客的任务。建立数学模型,根据乘客人数大小,配多少辆车、多长时间发一班车使得公交公司的盈利最高,乘客的抱怨程度最小。假设公交车在运行过程中是匀速的速度为v。
一、问题分析
我们分析该问题为一带软时间窗的单车型运输问题。由已知条件无法确定是单车场问题还是多车场问题,故我们分别建立两个模型:双车场模型和单车场模型。其中,双车场模型认为车站A13和车站A0分别有车场A和B存车,即均可作为始发站和终点站,上行和下行路线独立运行;单车场模型认为A0同时为上行终点和下行起点,它有转运能力但没有存车能力,这样实际上可将单车场方式理解为环线行驶。
三、模型的建立与求解
?双车场模型
?模块一:发车时刻表的确定
依据前面的分析,兼顾乘客与公交公司双方的利益,分别对单程的上行路线和下行路线建立如下的多目标规划模型:
目标函数 ? 供求的最优匹配 min?(Qi×β i
2-Vi)
? 各时段的发车车次均最小 min{Ni}
约束条件 ? 各时段的平均满载率限制 0.5?β?1.2 i
? 供求匹配比限制 α?k 1.1 符号说明:
Ni 第i时段发车次数
β 第i时段的平均满载率 i
β=Ri/(c×Ni) Ri为第i时段的总上车人数, c=100人/车i
次
α 供求匹配比 α=(?Vi)/(?Qi)
k 控制参数
Qi 第i时段运客能力(人×公里)
Qi=第i时段发车次数Ni×每辆车
载客量c×单程(上行或下行)总运行距离L
其中,上行时,L= 14.58公里; 下行时,L=14.61 公里 Vi 第i时段的需要运客量(人×公里)
Vi= j?(13,12„,1,0) ,上行方向;j?(0,2,3,„(x,y)Ljijij,j
13) ,下行方向。
其中,x 为第i时段内Aj站的上车人数;y 为第i时段内jijiAj站的下车人数
L为Aj站距该单程方向上终点站的距离。 j
即认为上车乘客的运载距离为正,下车乘客的运载距离为负。
1.2 目标函数说明:
目标函数?使第i时段的运客能力Qi与运输需求(实际客运量)Vi达到最优匹配,β反映满载率高低的影响。 i
目标函数?使高峰期所发车次,即单位时段所发的最大车次,在满足约束条件下尽可能少,以使总共需要的车辆数较少。
1.3 约束条件说明:
条件?是限制满载率满足运营调度要求,是考虑了乘客的利益。
条件?是限制供求匹配比α小于常数k。我们根据参数k的变动量
分别进行模拟,从而筛选最恰当的k值。
注:为使始发站车场的每天起始时刻的车辆数保持不变,需使总
发车次数与总收车次数相等,即必须使单程车次总数达到匹配
(N1=N2),而N1不能减少(受满载率限制),因此我们在求解下
行方向的Ni时增加约束?Ni2=N1. 在增添约束条件?Ni2=N1之
后,用二次规划求得各时段发车次数Ni1和Ni2. ?模块二 运营过程的模拟
在这部分,我们采用时间步长法,根据假设一个时段内发车间隔时间t相等,则t可由Ni确定,从而得到发车时刻表。按此发车时ii
刻表模拟实际运行过程,目标是确定满足时刻表的最小车辆数n,统计各项运营指标,搜索最优调度方案。
2.1 模拟子程序一:确定最小车辆数目n
根据“按流发车”和“先进先出”的原则,对起点站,在发车时刻应至少有一辆车可以发出(处于等待发车状态)。若有多辆车,则先进站者先发车,其余车辆“排队”等候;若无车可发,则出现“间断”。完整的运营过程应保证车辆严格按时刻表发车,不发生间断。
设A13站和A0站分别有车场A和B,从车场中不断有车发出,同时接受车进场,则车场中的车的数目是随时间变化的状态量。用Na和Nb来描述车场A和车场B中要满足车流不间断所需的最小数目,分别搜索其在运行过程中的最大值,则所需最小车量数目
n=Na+Nb。
2.2 模拟子程序二:统计各项运营指标
确定各项运营指标,采用模拟统计的计算方法,对不同的运营指标进行定量计算,主要功能是通过定量分析运营指标来检验方案的可行性,以确定方案调整。
注:由于车次与发车时刻一一对应,而车辆的队列顺序是不发生改变,因而对所需车辆进行统一编号,则对每一车次,与其对应的车辆编号是确定的,故我们直接对第k次车进行考察。
我们统计的指标及其定义如下:
平均满载率 上行方向 β= ,,,(,k,j(N1,J1)01,,kj
下行方向 β= ,,,(,k,j(N2,J2)02,,kj
满载率分布 可以由β(k,j)确定。
平均候车时间 上行方向T1= ,,,(Tk,j(N1,J1),,kj
下行方向T2= ,,,(Tk,j(N2,J2),,kj
滞留乘客候车时间分布:
假设乘客在第i站有k次滞留到k+1次,他增加的等候时间为:ti(k),
其概率为(1-(B(k,i)-B(k,i-1))/(D(k,i)+C(k-1,i)),有k次滞留到更后的车次的概率可由此递推,那么我们就可以得到滞留时间的分布。 符号说明:
B(k,j) 第k次车离开第j站时车上的人数;
D(k,j) 第k次车到第j站时上车与下车的人数之差;
C(k,j) 第k次车离开第j站时站台上的滞留人数;(由于车已达最
大满载率以至乘客不能上车,故称“滞留”)
T(k,j) 为第k次车离开第j站时站台上滞留者的滞留时间;
β(k,j)为第k次车离开第j站时的满载率,β(k,j)=B(k,j)/100 ;
N1,N2为一天单程所发的车次总数;J1,J2为单程站台总数; 2.3 模拟结果及统计指标分析
我们选取参数k=0.8,0.85,0.9进行模拟运行,所得结论如表一。(表中只给出上行方向值):
表一:模拟上行方向所得营运指标值 参数k 平均满载率平均候车时所需总车辆总发车次数
β间T n N1 0
0.8 68.7% 3.88 63 270 0.85 72.8% 3.88 63 255 0.9 76.4% 4.24 62 243 0.95 80.4% 7.23 62 231 综合考虑以上参数,当k,0.9时,各项指标比较适当,平均满载率较高,平均候车时间较短,所需车辆与总发车次数适中,所以我们选取k=0.9.
下面我们给出k=0.9时的具体模拟结果及统计指标。
结果:
?各时段内单程发车次数(见表二)
总车次N1=N2=243。
表二:k,0.9时各时段中的发车次数
时5~6 6~7 7~8 8~9 9~10 10~111~112~113~1段 1 2 3 4 上7 28 41 23 13 11 13 11 11 行
下3 12 21 26 16 11 10 9 10 行
时14~115~116~117~118~119~220~221~222~2段 5 6 7 8 9 0 1 2 3 上9 9 19 24 8 5 5 4 2 行
下11 13 19 30 19 11 9 8 5 行
?各时段单程发车时间间隔
由于一个时段内的发车间隔已假设为等距,所以由所得的车次很容易确定发车时间间隔。
?单程发车时刻表(数据量太大,故略)
?总车辆数 n=62 ,其中场A 存车57辆,场B存车5辆。 统计指标:
?平均满载率 上行方向 β=76.4% 下行方向 β01
=70.9% 02
?平均候车时间 上行方向 T1=4.24 下行方向 T2=3.48
3. 调度方案
我们由不同的理解得到两种调度方案,其共同点是都必须形成完整的运营过程,使车流不发生间断。
3.1静态调度方案:
认为在该路线上运行的总车数固定不变,形成序贯流动的车流,依照“按流开车”和“先进先出”的原则,按发车时刻表发车。 所需总车辆数目为62,其中从A13站的车场A始发的车数为57,从A0站的车场B始发的车数为5 。
3.2动态调度方案:
考虑高峰期与低谷期实际需要的车辆数目不同,为了满足高峰期而求得的车辆数目必然大与其他时间需要的车辆数,即62辆车只在高峰期得到充分利用,造成资源浪费。我们认为公交公司可进行车辆动态调度,让一些车辆可以在特殊原因下进行修理调整,并节约运营成本。由此我们在保证车流不间断的条件下,计算得出各个时段内实际所需的最小车辆数。如表三所示:(同时给出A、B车场的存车状态,可以自由支配的车辆数目)
表三:动态调度中各时段的车辆数 时段 5~6 6~7 7~8 8~9 9~10 10~111~112~13~1
1 2 13 4 车数 9 34 56 48 38 22 20 19 18 A场 51 28 2 0 0 11 12 11 9 B场 2 0 4 14 24 29 30 32 35
时段 14~115~16~117~118~119~220~221~22~2
5 16 7 8 9 0 1 22 3 车数 17 20 29 42 41 25 17 14 10 A场 9 10 9 5 6 25 37 43 48 B场 36 32 24 15 15 12 8 5 4 由上表我们得出:在总车辆数目可变动的情况下,所需的最大车辆数为7:00~8:00间的56辆,在非高峰期时所需车辆数目都较小,A车场和B车场都有较多车辆库存着,可以根据实际情况挪作它用。公交公司只需按表中所给的每个时段的所需车辆数进行调度,按发车时刻表发车即可。
?单车场模型
1. 模型的建立
根据问题分析,公交营运方式按单车场组织后我们建立如下的带软时间窗口的单车型运输问题的多目标优化模型:
目标函数? y1=min {n}
? y2=min ?Ni
? y3=min (P(Ti))(R,K,M),,,jkr
约束条件? 平均满载率限制50%?β?120%
k,? 发车间隔时间限制t ?5 +5k; 0 i为早高峰期i
时;
1 i为非早高峰
期时。
? t?{1,2,3„} i
注: 1.目标函数说明: 目标函数?使总车辆数目最小,即使公司的投资成本达到最小。
目标函数?使总车次数最小,即使公司的运营成本达到最小。
目标函数?是使所有顾客的平均不方便程度达到最小。
2.约束?主要是考虑到可操作性,发车间隔划分到秒一级,公交司机是没法把握的,故最小只能划分到分一级,那么发车间隔就应是1分的整数倍
2.模型的求解
本模型是多目标、多约束的优化模型,很难求出全局最优解,所以我们先将多目标规化简,再仿真模拟运营过程求解。
转化为单目标的求解思路如下:
给出初始发车时刻表 ? 模拟
客运数据 ? 运营 ? 统计指标 ? 结论?人工分析
客流分布(平均分布) ? 数据
2.1 模型化简
化简多目标问题,我们可以有三个出发点:?分析各目标之间相关联的数学关系,减少目标函数数目或约束条件数目。?依限定条件,
针对具体数据挖掘隐含信息以降低求解难度。?分析各目标权重,去掉影响很小的目标函数,从而达到简化目的。
分析目标?与?存在数学关联,发现总车次越多,乘客不方便程度越小。因此y2与y3不能同时取最小值。我们认为?为主要目标,故主要考虑目标函数?。从具体数据可知,在上行方向7:00~8:00,A13
站上车人数达3626人,平均每分钟到达60人,A12站上车634人而下车仅205人,为客流量最大的时段,发车间隔时间至少需要2分钟。由平均速度20公里/小时及环行距离,可得到此时至少需45辆车。.
由以上分析将原模型简化为:
目标函数:y1= min (P(Ti))(R,K,M),,,jkr
y2=min M
s.t. 同上
2.2 运营过程模拟
?初始时刻表的产生方法
原则上初始时刻表可以随机产生,然后模拟判断搜索出较优解,但这样搜索量太大,且很难保证有一个收敛结果。因此我们采用人机交互的方式,首先分析数据得出比较合理的发车时间间隔的近似值,再在其附近搜索,产生初始时刻表。
表四为初始发车时间间隔
表四:初始发车时刻表
时5~6 6~7 7~8 8~9 9~10 10~111~112~113~1段 1 2 3 4
t 10 3 2 3 8 8 8 8 8 i
时14~115~116~117~118~119~220~221~222~2段 5 6 7 8 9 0 1 2 3 t 8 8 3 2 3 10 10 10 10 i
?模拟运营过程,统计各指标
由于模拟运营过程与双车场模型大同小异,故我们在此不再详述。
2.3 结果及统计分析
对仿真产生的多组发车时刻表进行模拟获得最小的Y=5.6分,我们把这一组解做为我们的局部最优解,其结果(其中统计指标用来描述我们以怎样的程度照顾双方利益)如下:
?总车数
理想处理平均速度得总车数为45辆,加2辆应急,为47辆;
考虑高峰期车速小于20km/h,高峰期人流量大,是造成高峰期速度稍低于20公里/小时的主因,那么通过人流量数据和20公里/小时就可大致推算7:00-8:00速度约为18公里/小时。这样高峰期的最小总车数45修正为50辆,加2辆应急最终为52辆。 ?全天总车次 M=253×2=506次
?发车时刻表见表五 (用各时段发车间隔时间简述)
表五:单车场各时段的发车间隔 时5~6 6~7 7~8 8~9 9~10 10~111~112~113~1段 1 2 3 4
t 10 2 2 2 4 6 6 6 8 i
时14~115~116~117~118~119~220~221~222~2段 5 6 7 8 9 0 1 2 3 t 8 6 3 2 3 7 10 10 10 i
注:5:00-6:00只是一种统计划分,首发车可以在5:00之前,也可在5:00之后。当然当不知道其它原则时可以假设首发车为5:00发。对单车场下行线始发为5:45与数据相吻合。5:00-6:00 上行线共855人上车;下行线共50人。其可能原因之一就是上行在5:00-6:00都有车可统计;而下行只在5:45-6:00中有车可统计 统计指标:?乘客平均候车时间 y3=5.6分
?平均满载率 β=66.4% 0
结论分析:由上面两个图表可见我们的调度方案基本上能满足乘客候车时间的限制,高峰期乘客在5分钟内等到车的概率为92.9%,非高峰期乘客在10分钟内等到车的概率为89.7%.
调度方案:(见表六)
表六:单车场动态调度方案 时5~6 6~7 7~8 8~9 9~10 10~111~112~113~1段 1 2 3 4 所10 46 52 46 24 16 16 16 14 需
车
辆
数
时14~115~116~117~118~119~220~221~222~2段 5 6 7 8 9 0 1 2 3 所14 16 30 46 30 14 10 10 8 需
车
辆
数
五、模型的进一步讨论
1.关于采集运营数据的讨论
由于我们假设乘客到站服从均匀分布,而实际中乘客到站时间不可能都服从均匀分布。特别是在高峰期的情况下,乘客到站时间的不均匀分布就会使模型结论误差较大。我们建议以下几种改进采集方式的方法:
?采取不等的统计人数的间隔时间
在高峰期的情况下,为削弱乘客到站时间的不均匀分布带来的影响,可适当减小统计的间隔时间但统计时间加密应有一定限度。对客流量很小的时段,我们可适当增大统计的间隔时间,不必要每小时都统计一次。
?增加能反应有关滞留人数的统计数据。
?按相等到站人数来区分时间段的统计
方法是统计达到一定到站人数时的时间点,即可由此判断乘客到站的大概分布情况,有利于按其分布的疏密进行车辆调度,以更好的满足乘客的需要。其缺点是不易确定相等人数间隔的大小,可操作性不高;其优点是能较为准确地反映客流量的变化情况。 2.对调度方案的进一步讨论
我们依据假设:各时段内乘客到站时间服从均匀分布,从而认为各时段内的发车时间间隔相等。我们在模型的改进中,可考虑对不等的发车时间间隔进行模拟,并与等间距的结果进行比较。 3.单车场调度方案与双车场调度方案的选用
由结果分析可知单车场调度方案减少了公司的前期投资成本;双车场调度方案的运营成本小,更好的兼顾到乘客与公司双方的利益。我们建议,在有双车场的条件下选取双车场调度方案更好。当需进行路线规划,需要选取单车场或双车场时,建议根据实际所需成本来选取方案。
六、模型的评价
本文的优点如下:
1( 模型的主体是采用时间步长法,模拟生成的发车时刻表的实际
运行过程,准确性高,容量大,逻辑性严格,计算速度快,具有
较强的说服力和适应能力。
2( 定义了能定量衡量我们的调度方案对乘客和公交公司双方利
益满足程度的统计指标。
3( 在求最少车辆数时,将两个车场看作两个发射源,通过对两个
车场的存车状态的实时模拟,形成不间断的运营过程,从而求得
所需车辆数目。