收费站的设计
收费站最佳窗口数问题
摘要:本文讨论了收费站收费窗口设置的数目问题。首先,建立了一个评判最佳的标准:单位时间的全部费用。然后分析了这个问题的特点,采用了排队论中的M/G/K模型。根据评判标准求出了目标函数,建立了无约束规划模型。求解时先对找到的数据进行了分布的检验,检验通过后算出模型需要的相关参数值,再取定车流量,采用了遗传算法进行求解,得出结果为:
当平均车流量0.2辆/秒时,最佳收费窗口数目K*为5;
当高峰时期车流量为0.5辆/秒时,最佳收费窗口数目K*为10.
所以建议收费站设置10个窗口。
本文采用边际分析的方法对上述结果进行了验证,两种方法得到的结果完全相同。而为了验证模型的合理性,对取了20个值进行求解,得到结果非常符合实际。另外也对参数的选取和求解过程中出现的反常结果进行了合理的解释。本文还对模型结果与现实情况进行了比较,当现实情况收费站窗口数为6时,结果如下: 当车流量0.30时,本文模型的结果(即10个窗口)更为有效; 当车流量0.30时,现行情况(即6个窗口)更为有效。
最后,我们对模型进行了评价以及对现行收费系统提出了几条改进建议。 关键词:收费窗口数目 评判标准 遗传算法 边际分析
1. 问题重述:
交通流量大的收费道路一般都是多车道的高速公路,那里总会有很多收费站,司机需要在收费处停车收费。通常情况下,收费站收费窗口的数量会远大于高速公路上的车道数。进入收费站时,车辆分散开,进入各个收费窗口;出站时,这些车辆就要挤回车道上。于是,当交通流量大时,出收费站时往往就会出现交通拥挤。而在交通非常繁忙时,由于每辆车交费都需要一定的时间,这样在收费站入口处也会出现交通拥挤。
当车道数目给定时,若收费窗口较少,就会造成入口处的拥挤,车辆排队等待的时间就会增多;当收费窗口较多时,虽然车辆等待时间会减少,但这样就会在出口处造成拥挤,而且收费窗口的增加会在交通低峰期间造成窗口空闲损失。在这两者之间,必然会存在一个平衡,会存在一个最优解。
这样就需要建立一个模型,来决定对于一个交通繁忙的收费处多少个收费窗口才是最佳数目。另外还考虑每条路只有一个收费站的情况。在什么情况下会比现行的有效,在什么情况下会比现行的效率低。自己找到数据,对模型进行求解并分析。
2. 基本假设及说明:
1)在单位时间内车辆到来的数目服从泊松分布。由于车辆的到来过程服从平稳性、无后效性、普通性这三条性质,所以这一假设必定成立[1]。
2)车辆的数目是无限的。也就是说,当时间足够长时,到来车辆的总数目可以无限的大。由于我们的研究目标是交通流量很大的高速公路,所以这一点自然服从。
3)收费系统的容量无限大。也就是说,即使到来车辆所排的队列相当长,新来的车辆也将排队等待而不会离开,这一点在高速公路收费站也是服从的。
4)通过收费站的车辆将遵守先到先服务,先到先出的原则。
5)多车道,多收费窗口时,驾驶员会自己根据队列的长度来选择最短队列排队,也就是说每个队列的队列长度基本一样。
6)所有车辆都可以在任一车道上行驶,在任一收费窗口交费。
7)假定所有收费窗口收费效率一样,也就是每个窗口服务时间服从同种分布,且参数相同。。
8)车辆的进站等候时间,收费服务时间及出站等候时间相互独立。
3. 符号约定:
t0 : 车辆在收费站的平均停留时间
t1 : 车辆的平均进站等候时间
t2 : 车辆的平均服务时间
t3 : 车辆的平均出站等候时间
: 单位时间车辆到达数目所服从的泊松分布的参数 : 每个收费窗口的服务强度
Lq : 收费站中等待收费的平均排队长度
K : 收费站收费窗口的数目
K*: 收费站最佳收费窗口数
Cs : 收费站每个收费窗口单位时间的成本
Ct : 每辆车在收费站中停留单位时间造成的平均损失
G : 收费站中单位时间的全部费用
4. 问题分析:
我们需要建立模型来决定收费窗口的最佳数目。那么什么才是最佳呢?很显然,这就需要确定一个评判的标准,并以此来确立问题的目标函数。我们把单位时间的全部费用作为目标函数。这主要从两方面来考虑:一是收费站的服务成本;二是收费站中等待的车辆的损失。一般来说,窗口越多,等待车辆的对长越短,单位时间的损失越大,而收费站单位时间的成本就增多;反之则反。我们把这两个目标相加,即得到目标函数。
收费窗口的成本,取决于收费站本身,我们可以直接找到某收费站的窗口成本,将其代入我们的目标函数。至于等待车辆的损失,我们需要对找到的数据加以分析和判断,求出其符合的分布,然后根据排队论理论,求出收费站中等待收费的平均排队车辆数,乘以每一车辆在收费站中停留单位时间的损失。
至于约束条件,从理论上讲,只需要保证窗口数目是正整数也就足够了。当然,实际上对于每一车道,设置的窗口数目显然是不会太多。这样我们就建立了一个无约束规划模型。
5. 模型的建立
很显然,当一辆车到达收费站时,如果所有的收费窗口都正在收费,那么这辆车就必须等待,这样就形成了一个队列,车辆较多时就会形成几个队列。我们可以用排队论的理论来分析这个问题。
一个排队系统能够用下面的形式表示出来2:
X/Y/Z/A/B/C
X: 输入过程一定时间顾客的到达数目服从的分布
Y: 服务时间服从的分布
Z: 服务台的数目
A: 系统容量
B: 顾客的总数目
C: 服务规则
对于本问题,输入过程是泊松过程,服务时间服从的分布未知,服务台(在本题中即收费窗口)的数目有限(一般大于1),而根据我们的假设和说明,系统容量和顾客(即到来车辆总数目)均为无穷大,而服务的规则为先进先出。所以本问题的模型即:
M/G/K///FCFS
这样的收费站的示意图如图1所示:
表示通行车辆
图1:收费站示意图 表示收费窗口
再由M/G/K排队模型的理论2,有:
D(t2t3)E(t2t3)K1(K1)!KE(t2t3)t11Ki2E(t2t3)KE(t2t3)i!E(tt)i023
tt1t2t3 21 (1) (2)
21D(t2t3)E(t2t3)K1(K1)!KE(t2t3)Lq1Ki2E(t2t3)KE(t2t3)i!E(t2t3)i0 (3)
注:D,E分别表示对后面的随机变量取方差和均值。
我们的目标函数即为GKCsCt(LqK)。另外,由于目前对于M/G/K排队模型的研究并没有建立公认的确切理论,在这个模型中,每个收费窗口的服务强度并没有确切的表达式,我们就取目标函数为:
GKCsCtLq (4)
同时把Ct的值适当的增大就可以消除这一改变造成的误差。这样,(3)和 (4)就构成了我们的模型:
Model:
min GKCsCt(LqK),
D(t2t3)E(t2t3)K1(K1)!KE(t2t3)其中Lq1Ki2E(t2t3)KE(t2t3)i!E(t2t3)i021
6. 模型的求解
我们先对找到的数据进行分析,算出(3)式中各参数的值。
在假设中,我们已经知道,在单位时间内车辆到来的数目服从泊松分布。而由排队论理论3,该泊松分布的参数即为单位时间的车流量。另外,由于高速公路往往会有多条车道,我们设第i条车道的车流量为i(i=1,2,„n),由泊松分布
的可加性可以知道,所有车道的总的车流量,也就是到达收费站的车流量为i,根据我们在多篇文献及网上查到的资料显示,高速公路上的平均车流量
i1n
在0.2辆/秒左右,而高峰期的车流量在0.5辆/秒,我们就使用这两个数值对模型进行求解。
下图2是我们找到的某路段收费站窗口服务时间概率的分布图2。
图2:收费窗口服务时间概率分布图
根据我们查得的文献结论以及上图图象,服务时间近似服从对数正态分布或正态分布。下面我们分别对它们进行检验:
我们采用MATLAB工具箱对两个分布进行检验。对于对数正态分布,先将上图横坐标取对数得到新的图象;对于正态分布,图象不变。然后用正态分布检验命令normplot对两者进行检验,分别得到图3和图4。该命令检验结果有如下意义:如果数据来自正态分布,则图形显示出直线性形态。
图3:服务时间对数正态分布检验图
图4:服务时间正态分布检验图
容易看出,图4的图形直线性更明显一些,而且拟合得相当不错,因此我们认为收费站服务时间t2近似服从正态分布。再对t2的分布参数进行极大似然估计得到
Et211.00,Dt26.76(单位分别为秒,秒2),然后我们对t2的分布进行皮尔逊
2检验,在95%的置信水平上检验通过。
图5:离去时间概率分布图
图5是车辆出站时间的概率分布图,近似服从正态分布。同上面一样我们对其进行检验,得到如下检验图:
图6:出站时间正态分布检验图
我们可以看到,直线性形态还是比较明显的。然后我们对t3的分布参数进行极
大似然估计,得到Et34.47,Dt30.59(单位分别为秒,秒2),然后我们对t3的分布进行皮尔逊2检验,在95%的置信水平上检验通过。
由于服务时间和出站时间是相互独立的,所以有:
Et2t3E(t2)Et3
Dt2t3D(t2)Dt3
另外,假定Cs= 0.02,Ct= 0.05(单位为元/秒,关于这两个参数的选取我们会
在后面进行分析),则Cs0.02= 0.4 Ct0.05
这样模型所需要的参数都确定了,我们采用了遗传算法对模型进行了求解,算法的流程图如下:
图7:遗传算法流程图
具体步骤如下:
1.编码初始化:鉴于实际中窗口的数目不可能太大,对于一个收费站来说,能建设到40个窗口的可能性太小了。因为窗口的数目不仅取限于车站的面积,而且还要受经济效益的约束。所以我们选择编码的二进制精度:串长为20,范围为1到40 。
2.评价函数:即为模型的目标函数
3. 选择过程:我们采用的通用的旋转赌轮法。
4.杂交操作:并且根据我们多次试验的经验:取杂交概率为0.95,有更好的全局最优解搜索能力和收敛速度快的优点。然后随机确定杂交位置然两个父本进行交换基因。
5.变异操作:根据我们多次的实验数据,对于我们这个问题取变异率为0.01有更好的全局最优解的搜索能力和收敛速度快的优点。然后随机进行选择父本和变异基因位。
6.确定遗传算法终止条件:大多数研究者认为对于遗传算法的终止条件目前尚无定论,一般都取为遗传代数4。在这里为了增加收敛速度,并且取迭代数为25也有更好的全局最优解的搜索能力。
我们得到的结果为:
当平均车流量0.2辆/秒时,最佳收费窗口数目K*为5;
当高峰时期车流量为0.5辆/秒时,最佳收费窗口数目K*为10.
显然,由于收费站交通繁忙,应该着重考虑高峰时期,倘若只按平均车流量来设置5个收费窗口,在车流高峰时期就会发生严重的堵车现象,所以我们最后的结果为:
收费站应设置10个收费窗口。
7. 模型结果的检验与分析
7.1 模型结果的检验
为了验证这一结果,下面我们采取解析的方法对目标函数进行求解。
由于Cs和Ct是给定的,而收费窗口的数目K为变量,G是K的函数GK,现在要求K*,使得GK* = minGK,K为正整数。
由于K只能取正整数,所以函数GK不连续,这样就不能采用经典微分法。这里采用边际分析方法来求解。
根据GK* = minGK这一点,则有:
GK*GK*1 (5) GK*GK*1 (6)
将(4)代入(5),(6),即得到:
K*CsCtLqK*(K*1)CsCtLqK*1 (7) K*CsCtLqK*(K*1)CsCtLqK*1 (8)
**CtLq*K1Lq*K KK1由(7),Cs**CtLq*K1Lq*K KK1由(8),Cs
也就是: CsLqK*1LqK* Ct
即有: CsLqK*1LqK* Ct
LqK*LqK*1CsLqK*1LqK* (9) Ct根据(9)式,依次求出K1,2,3,„时Lq的值。由于哪个不等式构成的区间就可定出K*的值。
分别代入0.2 ,0.5 计算Lq的值,得到:
Cs已知,根据它落在CtLq(K)的相应差值为0.7496,0.1563,0.0435, 而 Cs0.4 ,根据(9)式 Ct我们取K*= 5;
Lq(K)的相应差值为1.1897,0.3685,0.1445,而 Cs0.4 ,根据(9)式我们Ct取K*= 10.
上面的结果与我们用遗传算法得到的结果完全一样!
7.2 模型参数Cs和Ct的解释
由于我们查不到相关的资料,模型中两个参数的值Cs= 0.02,Ct= 0.05是我们
自己给定的,其意义如符号约定中所述。自然这样的取值会与现实有较大的出入。但从上面分析中可以看到,最佳窗口数目K*只与这两个参数的比值Cs有关,只要Ct
我们取的两个参数的值的比值是合理的,则得到的结果就是合理的。
7.3 模型求解过程中反常结果的解释
在应用(3)式我们发现在有的和K取值的时候,队长Lq会出现负值。经过
观察后,我们发现问题在于(3)式中有的KEt2t3出现了负值,经分析后我们对这一现象作出如下解释:
当队长KEt2t3为负值时,即Et2t3
K1,这表示收费窗口的平均服务
强度大于1,这样当收费站运营一段时间后,在站里排队等待收费的长度将越来越大,最终这一系统将崩溃!
所以在实际求解时我们将队长Lq取负值的情况舍去了。
为了进一步验证我们模型的合理性,我们对从0.05到1.00,步长为0.05进行取值,分别得到的最佳服务窗口数目如下表3所示:
为了更清楚地显示我们的结果,将表3转化为图8(见下页):
从图7中可以清楚地看到:当车流量逐渐增大时,最佳服务窗口的数目也逐渐增大或不变,这个结果显然与实际相符。
7.4 模型的结果与现实情况的比较
考虑每条路只有一个收费站的情况。从表3和图8中可以看到,当取最佳收费窗口数为10时,倘若车流量0.4时,最佳收费窗口数并不为10,由于我们并不能确定现行收费站的窗口数,所以在这里不好对我们模型的结果与现行情况进行比较。这里不妨取K6,从表3和图8中可以得到:
当车流量0.30时,K6并不是最佳收费窗口数,设6个窗口会使得车辆排
队长度过长,显然不是有效的。在这种情况下,虽然随着的变化,最佳收费窗口数也在变化,但设10个收费窗口显然要比设6个收费窗口要有效。
当车流量0.30时,设置6个收费窗口已经足够,而设置10个收费窗口会加大收费站的成本,这表明模型的结果在这种情况下比现行的效率低。
图7:对应每一车流量的最佳收费窗口数目折线图
8. 模型的评价
(1) 在模型的处理中只对单种车型进行了考虑,对于不同的车型我们可以给它们加个权重系数来考虑不同的车型,这样得到一个加权的进站等待时间,服务时间以及出站等待时间,模型的结果就会更精确一些。
(2). 本模型忽略了对车道的考虑,鉴于我们对模型的假设(5)以及泊松分布的可加性,这样的处理应该是合理的。同样根据这两点,我们也可以进行对多车道的推广。
(3). 本模型中有些参数是根据人工选定的,可能跟实际情况会存在一些差别,但是并不影响该模型的适用性。模型的结果非常符合实际,说明我们选取的参数与实际情况还是比较符合的。
(4) 当考虑到各种车型以及各种收费方式时,所改变的也只是几个时间变量,我们只需要相应地改变模型的参数,即可对模型进行求解。这说明该模型具有横强的适用性。
9. 对收费系统改进的思考
(1)建议收费窗口的设置按照高峰时期的车流量来考虑,在平峰时期和低峰时期可以少开一些收费窗口,从而减少收费站的服务成本。
(2)就我们所知,目前我国大多采用都是“人工半自动收费系统(MTC)” ,其出票速度和通行能力有限,推荐使用电子不停车收费系统(ETC),这样可以缩短服务时间,提高通行效率,进而在相同车流量的情况下,减少服务窗口数,减少服务成本。
(3)我们考虑在一条公路的旁边(在我国即在右边)设立多个收费站,在最后一个收费站的后面会有一个探测装置和电子眼。每辆车在该路段只需交一次费。它可以选择在该路段任一收费站交费,在交费之后会发一张卡(或者其它别的方式),没有卡时通过探测装置时间就会发出警报,同时电子眼会拍下其车牌号,这样就可以防止驾驶员逃票。同时在每个收费站的前面,车道的旁边会有一个电子公告版,会显示当前该收费站的各种信息,比如收费窗口数目,各窗口排队长度等,当司机看到排队长度过长时,就会选择继续行驶,到后面的站交费;当排队长度较短时,就可以在该站交费。
参考文献:
[1] 李贤平. 概率论基础(第2版)[M]. 北京:高等教育出版社,2005.
[2] 张智勇等. 基于MGK排队模型的北京地区高速公路收费站通行能力研究[J] 公路.2001年7月,第7期.
[3] 卢向南.主编. 应用运筹学(第1版)[M] . 杭州:浙江大学出版社,2005
[4] 刘宝碇等. 不确定规划与应用(第1版)[M]. 北京:清华大学出版社,2003