收费站的设计

收费站最佳窗口数问题摘要：本文讨论了收费站收费窗口设置的数目问题。首先，建立了一个评判最佳的标准：单位时间的全部费用。然后分析了这个问题的特点，采用了排队论中的//MGK模型。根据评判标准求出了目标函数，建立了无约束规划模型。求解时先对找到的数据进行了分布的检验，检验通过后算出模型需要的相关参数值，再取定车流量，采用了遗传算法进行求解，得出结果为：当平均车流量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.符号约定：0t：车辆在收费站的平均停留时间1t：车辆的平均进站等候时间2t：车辆的平均服务时间3t：车辆的平均出站等候时间：单位时间车辆到达数目所服从的泊松分布的参数：每个收费窗口的服务强度qL：收费站中等待收费的平均排队长度K：收费站收费窗口的数目*K：收费站最佳收费窗口数sC：收费站每个收费窗口单位时间的成本tC：每辆车在收费站中停留单位时间造成的平均损失G：收费站中单位时间的全部费用4.问题分析：我们需要建立模型来决定收费窗口的最佳数目。那么什么才是最佳呢？很显然，这就需要确定一个评判的标准，并以此来确立问题的目标函数。我们把单位时间的全部费用作为目标函数。这主要从两方面来考虑：一是收费站的服务成本；二是收费站中等待的车辆的损失。一般来说，窗口越多，等待车辆的对长越短，单位时间的损失越大，而收费站单位时间的成本就增多；反之则反。我们把这两个目标相加，即得到目标函数。收费窗口的成本，取决于收费站本身，我们可以直接找到某收费站的窗口成本，将其代入我们的目标函数。至于等待车辆的损失，我们需要对找到的数据加以分析和判断，求出其符合的分布，然后根据排队论理论，求出收费站中等待收费的平均排队车辆数，乘以每一车辆在收费站中停留单位时间的损失。至于约束条件，从理论上讲，只需要保证窗口数目是正整数也就足够了。当然，实际上对于每一车道，设置的窗口数目显然是不会太多。这样我们就建立了一个无约束规划模型。5.模型的建立很显然，当一辆车到达收费站时，如果所有的收费窗口都正在收费，那么这辆车就必须等待，这样就形成了一个队列，车辆较多时就会形成几个队列。我们可以用排队论的理论来分析这个问题。一个排队系统能够用下面的形式表示出来2：/////XYZABC:X输入过程一定时间顾客的到达数目服从的分布:Y服务时间服从的分布:Z服务台的数目:A系统容量:B顾客的总数目:C服务规则对于本问题，输入过程是泊松过程，服务时间服从的分布未知，服务台（在本题中即收费窗口）的数目有限（一般大于1），而根据我们的假设和说明，系统容量和顾客（即到来车辆总数目）均为无穷大，而服务的规则为先进先出。所以本问题的模型即：/////MGKFCFS这样的收费站的示意图如图1所示：表示通行车辆图1：收费站示意图表示收费窗口再由//MGK排队模型的理论2，有：12123232310232323()()(1)!()12()()!()KKiiDttEttKKEtttEttKEttiEtt（1）123tttt（2）1212323230232323()()(1)!()12()()!()KqKiiDttEttKKEttLEttKEttiEtt（3）注：,DE分别表示对后面的随机变量取方差和均值。我们的目标函数即为()stqGKCCLK。另外，由于目前对于//MGK排队模型的研究并没有建立公认的确切理论，在这个模型中，每个收费窗口的服务强度并没有确切的表达式，我们就取目标函数为：stqGKCCL（4）同时把tC的值适当的增大就可以消除这一改变造成的误差。这样，（3）和（4）就构成了我们的模型：:Modelmin()stqGKCCLK，其中1212323230232323()()(1)!()12()()!()KqKiiDttEttKKEttLEttKEttiEtt6.模型的求解我们先对找到的数据进行分析，算出（3）式中各参数的值。在假设中，我们已经知道，在单位时间内车辆到来的数目服从泊松分布。而由排队论理论3，该泊松分布的参数即为单位时间的车流量。另外，由于高速公路往往会有多条车道，我们设第i条车道的车流量为i（i=1，2，…n），由泊松分布的可加性可以知道，所有车道的总的车流量，也就是到达收费站的车流量为1nii，根据我们在多篇文献及网上查到的资料显示，高速公路上的平均车流量在0.2辆/秒左右，而高峰期的车流量在0.5辆/秒，我们就使用这两个数值对模型进行求解。下图2是我们找到的某路段收费站窗口服务时间概率的分布图2。图2：收费窗口服务时间概率分布图根据我们查得的文献结论以及上图图象，服务时间近似服从对数正态分布或正态分布。下面我们分别对它们进行检验：我们采用MATLAB工具箱对两个分布进行检验。对于对数正态分布，先将上图横坐标取对数得到新的图象；对于正态分布，图象不变。然后用正态分布检验命令normplot对两者进行检验，分别得到图3和图4。该命令检验结果有如下意义：如果数据来自正态分布，则图形显示出直线性形态。图3：服务时间对数正态分布检验图图4：服务时间正态分布检验图容易看出，图4的图形直线性更明显一些，而且拟合得相当不错，因此我们认为收费站服务时间2t近似服从正态分布。再对2t的分布参数进行极大似然估计得到2211.00,6.76EtDt（单位分别为秒，秒2），然后我们对2t的分布进行皮尔逊2检验，在95%的置信水平上检验通过。图5：离去时间概率分布图图5是车辆出站时间的概率分布图，近似服从正态分布。同上面一样我们对其进行检验，得到如下检验图：图6：出站时间正态分布检验图我们可以看到，直线性形态还是比较明显的。然后我们对3t的分布参数进行极大似然估计，得到334.47,0.59EtDt（单位分别为秒，秒2），然后我们对3t的分布进行皮尔逊2检验，在95%的置信水平上检验通过。由于服务时间和出站时间是相互独立的，所以有：2323()EttEtEt2323()DttDtDt另外，假定sC=0.02，tC=0.05（单位为元/秒，关于这两个参数的选取我们会在后面进行分析），则0.020.05stCC=0.4这样模型所需要的参数都确定了，我们采用了遗传算法对模型进行了求解，算法的流程图如下：图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模型结果的检验为了验证这一结果，下面我们采取解析的方法对目标函数进行求解。由于sC和tC是给定的，而收费窗口的数目K为变量，G是K的函数GK，现在要求*K，使得*GK=minGK，K为正整数。由于K只能取正整数，所以函数GK不连续，这样就不能采用经典微分法。这里采用边际分析方法来求解。根据*GK=minGK这一点，则有：*GK*1GK（5）**1GKGK（6）将（4）代入（5），（6），即得到：****(1)1stqstqKCCLKKCCLK（7）****(1)1stqstqKCCLKKCCLK（8）由（7），****11stqqCKKCLKLK由（8），****11stqqCKKCLKLK也就是：**1sqqtCLKLKC**1sqqtCLKLKC即有：****11sqqqqtCLKLKLKLKC（9）根据（9）式，依次求出K1，2，3，…时qL的值。由于stCC已知，根据它落在哪个不等式构成的区间就可定出*K的值。分别代入0.2，0.5计算qL的值