建模专辑 公交车调度的规划数学模型 ②算法实现 若k(1<k<n)已知,应求分类bA,使它的损失函数最小 由(3)式,如果k>2,找,使L(bm;A)=L(b,-1,k-1)+D(i,n) 于是得到第k类P=1n,n+1,…,n|,然后找-1,使它满足L(b1,+-1) L(b-1,k-2)+D(4-1,-1),得到第k-1类P1=1k-1,j-1+1,…,j-1 依次类推得到所有类(P1,P2,…,PA)=bn,k。由式(2)和(3)可看出b,是最优解 我们应用上面的费歇( Fisher)算法对公交调度峰值曲线进行聚类处理,具体步骤如下: 1)先将各时段客流量转化为其占全线路客流的比例。本题中有18个时间段,即18个 有序样本。 2)计算所有可能类的直径D(,)=8(x-可,其中,可=1岁 3)计算最小损失函数。用b,表示用前i个样品分成j类的最优解,它的最优损失函数 为L(b)。 当巡≤18,2≤j≤8时,利用费歇算法得到上下行方向的最小损失函数值变化曲线图 (1) 上行方向类函 下行方向损类函 分类个敷 分个 图(1)最小损失函数值变化曲线 经分析计算得出:在分类数为5时,损失函数的值为0.004204和0.002762,损失函数已 经下降的足够小了。在分类数为6时,损失函数的值为0.003076和0.00221分为5类与分 为6类,两者之间损失函数的差别不大。从方便调度管理的角度出发,期望划分尽可能少的 类,所以取曲线最优聚类个数为5个。 在聚类个数为5时,可以得出,上行方向的最优分类为5:006:0,.6:00-9:0,9: 00-16:00,16:00-18:00,18:00-23:00;下行方向的最优分类为5:00-7:00,7:00-9 0,9:00-16:00,16:00-19:00,19:00-23:00。 方法Ⅱ确定公交调度发车间隔 我们通过引入时段配车数的概念,来探讨在不同客流状态时如何确定时段配车数和发车 间隔。 定义在某一时间段内需求的车辆数称之为时段配车数。确定原则是,既保证有足够的 服务质量,又保证配车数最小
第19卷 下面给出两种算法模型: 算法模型IP=C Q Q: H 算法模型ⅡP= maxb:XCXL'C= NXL 我们对确定发车间隔的模型采用两种不同的间隔确定方法进行求解,综合评价后得出综 合算法模型:(假设每小时被调查的上车人数基于均匀的达到率) i)参数分析 H1:对上行方向和下行方向分别计算,将每一时间段内每一站点的上车人数减去下车人 数得到该时间段内该站点净上车人数,然后从每一时间段起始站点开始累加得到每一站点的 小时通过量D(i时间段内第j个站点的小时通过量),那么i时间段内的H1=图gx(D),n 是上行或下行方向的车站总数 C:依据定义有C=100×120%=120(人)N L:上行方向L=14.58(km),下行方向L=14.61(km) Q:Q=∑dpDn,a是i时间段内第j个站点与其相邻的前一个站点间的距离 p2:我们对P的估计值是按综合考虑每一时间段内的总客流量在全天的总客流量所占的 比率以及一些可以查到的经验值拟合出p1与H;的分布关系函数:p2=0.0173XH1+ 46.6919 i)结果分析 分别按照算法模型I和算法模型Ⅱ计算每个时间段内的发车次数。对这些数据分析可 知:算法I和算法Ⅱ各自在不同的类时间段会出现不稳定的结果,在每个类时间段单独使用 种算法得出的结果都会具有一定的不可信度。以不同类时间段上的算法模型Ⅰ及算法模型 Ⅱ的适应程度作为评价标准,得出确定发车间隔的综合算法模型 综合算法模型:在两个间隔高峰类时间段:上行方向类时间段2,3,4},12,13及下行 方向类时间段13,4},{12,13,14采用算法I进行求解,而在上下行方向的其余各3个类时 间段则采用算法Ⅱ求解。 优化模型Ⅲ平滑法 为确定相邻两个时段之间的转换段内的发车时间,我们采用平滑法(所谓平滑法就是根 据计算的时段配车数,在前一时段内确定第一辆车的发车时间,在转换段内综合前后两种配 车数,设置平均期望占用量而不是不均匀间隔)。 例如我们所得结果中,上行方向5:00-5:59,6:00-6:59两个时段内(第一辆车为5:00 发车),时段配车数和发车间隔分别为8.4260车次,7.12min;29.9505车次,2,00min。前一 时段所需要的配车数的0.4260车被留在5:57之后与下一时段的0.5740车结合。此外, 0.4260车的期望占用量为N=P1×C,0.5740车的期望占用量为N2+1=P2+1×C,后一时 间段每分钟需求的配车数(斜率)为29.950560,相应的0.5740车要运行0.5740/(26,9505/ 60)=1.17min。因此第二时段内第一辆车的发车时间为6:01:17,其期望占用量为0.4260 N+0.5760×N2+1 通过以上的分析及数据求解,我们制定出上行方向和下行方向两个起点站的发车时刻表 (略),并求出需要的车辆总数(即最小配车数)。我们求得:上行方向为:47下行方向为:
模专辑 公交车调度的规划数学模型 35故所需车辆总数N=max(47,35)=47 根据题意,我们定义i时段内乘客的满意率为 100%W;<5 高峰期 W:≥5 100%W:<10 W→非高峰期公 乘客的平均满意率δ=H·a B,计算得8=92 公交公司的平均满意率7=∑H1·p,计算得7=0.5(7+7m)=76,23 H 其中,上行7=78.36%,下行mn=74.09% 5.问题(2)基本假设 1)某站乘客到达为泊松过程,设上(下)行各站乘客的到达过程为平稳的泊松过程,乘 客到达率为λ,r为第i个乘客到达时刻,则乘客到达的间隔为 r+1-r;<tl= t≥0 (4) 0,t<0 1又设公交车每批运送的乘客数量为k,该系统可变换为一等效的新系统。由爱尔兰分布 与负指数分布之间的关系可得,新系统的乘客到达间隔服从参数A的k阶爱尔兰分布: 5。(x) Pltm+i -tm tl t≥ (5) 0,t<0 式中,cm为新系统第m组乘客到达时刻。 2)公交车对每批乘客服务时间为相互独立的负指数分布,每批服务时间是指公交车从 起始站出发再返回起始站所需的时间为gro设公交车成批服务时间tgr服从参数a的负指 数分布,即 Pirt th 0,t<0 式中,p与的关系为:1==,Tm为运行一个行程的平均时间 6问题(2)模型建立与求解 定理1在G/M/n系统中,设各顾客的服务时间相互独立且具有公共的以p为参数 的负指数分布,则在该顾客等待的时间内,每台服务设施的输出过程(即服务完成离开服务 机构的顾客)是一个以p为强度的泊松过程。(参考文献[1) k阶爱尔兰分布的分布函数A(t)见(5)式,由(5)得到k阶爱尔兰分布的概率密度为 a()=A=(Ax)+-x
19卷 则到达间隔的期望值为: (8) 由(5),(8)得概率密度的拉氏变换为 SdA(t) (s)>0 (9) 由排队理论,可得到公交车服务系统的服务强度: E[v2] TROd EL (10) 其中:k为爱尔兰分布的阶数(公交车每批运送的乘客数),n为公交车数量,E[v]为系统服 务时间的期望值,E[rm+1-rm]为第n+1批乘客与第m批乘客的到达间隔的期望值。 对于服务强度p<1有下面的定理 定理21)设qm为第m个乘客到达时系统的队长,于是队长的分布极限存在且与初始 条件无关,其表达式为: 其中为方程A‘(n(1-0)) +m(1-))在(0,1)之间的唯一解。 利用(7)式将上式化为p的方程 [n(1-ck)-k] (1-e)n(1-0)-k (12) K={1+cm=8 (13) k=1,2,3 (14) EL=A(Lu) lu 2)该系统平稳分布下的平均队长为: Eq]==2t1(b02 (1-an1)U 其中:U1,K,0分别由(12),(13),(14)决定,n1= 0,n>1 3)系统的平均等待队长为: E[qu=(1-0)2 (16)
建模专辑 公交车调度的规划数学模型 4)系统服务台平均占有数 E[L]= E[q]-E[qw] (17) 定理3对GI/M/n系统,在平衡状态下,顾客到达时不需等待的概率为 W(0)=1 (18) 平均等待时间为 W np:(1-0)2 (19) 其中K、分别由(13),(11)式确定。 我们用系统的平均等待队长作为衡量乘客满意度的标准,用系统服务台平均占有数作为 衡量公交公司利益的标准,因此,在任意时间段内都可以建立目标规划模型 2)氰:1一第任款,反可使原重 P2第二 最大 目标:尽量使公司利益最 3)约束条件的制定 i)乘客在非高峰期等待时间不超过10min,在高峰期等待时间不超过5min i)车容量在区间(50,120) 综上我们得到随机规划模型为: min E[qw min ELl]= ELq]-E[ qw] K∈(50,120); W≡xdW(x) K ≤5(或10) 其中K,由式(13),(11)决定 对上述模型进行系统分析得到以下结论 1)基于对模型结果的分析,服务强度p对系统的性能指标起着至关重要的作用。由于 Pn,而采集数据对Tx无影响,故所采集的数据应尽量体现λ的实际情况即某站在某 期间内指定时间段内的到达人数最大值 2)对不同的系统参数下得出的重要指标比较后,得出:系统公交车数量对系统性能的 改善的灵敏度比公交车容量对系统性能改善的灵敏度大。 3)我们所建立的公交车服务系统模型还可应用于系统的优化配置,只要赋予明确的优 化目标函数,就可得到相应的配置参数。同时为计算机仿真提供理论基础。 7模型的推广 考虑约束条件下的间隔确定。例如以下两种约束条件 i)资金有限,应配备的车辆数不足或当日应配车辆发生事故不能上岗又无替补车辆供 给时,调度员应及时考虑时刻表的变动。 i)当运力充足时,可以增加总发车次数,提高对乘客的服务质量