收費站的設(shè)計.doc

收費站最佳窗口數(shù)問題摘要：本文討論了收費站收費窗口設(shè)置的數(shù)目問題。首先，建立了一個評判最佳的標(biāo)準(zhǔn)：單位時間的全部費用。然后分析了這個問題的特點，采用了排隊論中的模型。根據(jù)評判標(biāo)準(zhǔn)求出了目標(biāo)函數(shù)，建立了無約束規(guī)劃模型。求解時先對找到的數(shù)據(jù)進行了分布的檢驗，檢驗通過后算出模型需要的相關(guān)參數(shù)值，再取定車流量，采用了遺傳算法進行求解，得出結(jié)果為：當(dāng)平均車流量輛/秒時，最佳收費窗口數(shù)目為5；當(dāng)高峰時期車流量為輛/秒時，最佳收費窗口數(shù)目為10.所以建議收費站設(shè)置10個窗口。本文采用邊際分析的方法對上述結(jié)果進行了驗證，兩種方法得到的結(jié)果完全相同。而為了驗證模型的合理性，對取了20個值進行求解，得到結(jié)果非常符合實際。另外也對參數(shù)的選取和求解過程中出現(xiàn)的反常結(jié)果進行了合理的解釋。本文還對模型結(jié)果與現(xiàn)實情況進行了比較，當(dāng)現(xiàn)實情況收費站窗口數(shù)為6時，結(jié)果如下：當(dāng)車流量時，本文模型的結(jié)果（即10個窗口）更為有效；當(dāng)車流量時，現(xiàn)行情況（即6個窗口）更為有效。 最后，我們對模型進行了評價以及對現(xiàn)行收費系統(tǒng)提出了幾條改進建議。關(guān)鍵詞：收費窗口數(shù)目 評判標(biāo)準(zhǔn) 遺傳算法 邊際分析1. 問題重述：交通流量大的收費道路一般都是多車道的高速公路，那里總會有很多收費站，司機需要在收費處停車收費。通常情況下，收費站收費窗口的數(shù)量會遠大于高速公路上的車道數(shù)。進入收費站時，車輛分散開，進入各個收費窗口；出站時，這些車輛就要擠回車道上。于是，當(dāng)交通流量大時，出收費站時往往就會出現(xiàn)交通擁擠。而在交通非常繁忙時，由于每輛車交費都需要一定的時間，這樣在收費站入口處也會出現(xiàn)交通擁擠。當(dāng)車道數(shù)目給定時，若收費窗口較少，就會造成入口處的擁擠，車輛排隊等待的時間就會增多；當(dāng)收費窗口較多時，雖然車輛等待時間會減少，但這樣就會在出口處造成擁擠，而且收費窗口的增加會在交通低峰期間造成窗口空閑損失。在這兩者之間，必然會存在一個平衡，會存在一個最優(yōu)解。這樣就需要建立一個模型，來決定對于一個交通繁忙的收費處多少個收費窗口才是最佳數(shù)目。另外還考慮每條路只有一個收費站的情況。在什么情況下會比現(xiàn)行的有效，在什么情況下會比現(xiàn)行的效率低。自己找到數(shù)據(jù)，對模型進行求解并分析。2. 基本假設(shè)及說明：1） 在單位時間內(nèi)車輛到來的數(shù)目服從泊松分布。由于車輛的到來過程服從平穩(wěn)性、無后效性、普通性這三條性質(zhì)，所以這一假設(shè)必定成立。2） 車輛的數(shù)目是無限的。也就是說，當(dāng)時間足夠長時，到來車輛的總數(shù)目可以無限的大。由于我們的研究目標(biāo)是交通流量很大的高速公路，所以這一點自然服從。3） 收費系統(tǒng)的容量無限大。也就是說，即使到來車輛所排的隊列相當(dāng)長，新來的車輛也將排隊等待而不會離開，這一點在高速公路收費站也是服從的。4） 通過收費站的車輛將遵守先到先服務(wù)，先到先出的原則。5） 多車道，多收費窗口時，駕駛員會自己根據(jù)隊列的長度來選擇最短隊列排隊，也就是說每個隊列的隊列長度基本一樣。6） 所有車輛都可以在任一車道上行駛，在任一收費窗口交費。7） 假定所有收費窗口收費效率一樣，也就是每個窗口服務(wù)時間服從同種分布，且參數(shù)相同。8） 車輛的進站等候時間，收費服務(wù)時間及出站等候時間相互獨立。3. 符號約定： ： 車輛在收費站的平均停留時間 ： 車輛的平均進站等候時間 ： 車輛的平均服務(wù)時間 ： 車輛的平均出站等候時間 ： 單位時間車輛到達數(shù)目所服從的泊松分布的參數(shù) ： 每個收費窗口的服務(wù)強度 ： 收費站中等待收費的平均排隊長度 ： 收費站收費窗口的數(shù)目： 收費站最佳收費窗口數(shù) ： 收費站每個收費窗口單位時間的成本 ： 每輛車在收費站中停留單位時間造成的平均損失 ： 收費站中單位時間的全部費用4. 問題分析：我們需要建立模型來決定收費窗口的最佳數(shù)目。那么什么才是最佳呢？很顯然，這就需要確定一個評判的標(biāo)準(zhǔn)，并以此來確立問題的目標(biāo)函數(shù)。我們把單位時間的全部費用作為目標(biāo)函數(shù)。這主要從兩方面來考慮：一是收費站的服務(wù)成本；二是收費站中等待的車輛的損失。一般來說，窗口越多，等待車輛的對長越短，單位時間的損失越大，而收費站單位時間的成本就增多；反之則反。我們把這兩個目標(biāo)相加，即得到目標(biāo)函數(shù)。收費窗口的成本，取決于收費站本身，我們可以直接找到某收費站的窗口成本，將其代入我們的目標(biāo)函數(shù)。至于等待車輛的損失，我們需要對找到的數(shù)據(jù)加以分析和判斷，求出其符合的分布，然后根據(jù)排隊論理論，求出收費站中等待收費的平均排隊車輛數(shù)，乘以每一車輛在收費站中停留單位時間的損失。至于約束條件，從理論上講，只需要保證窗口數(shù)目是正整數(shù)也就足夠了。當(dāng)然，實際上對于每一車道，設(shè)置的窗口數(shù)目顯然是不會太多。這樣我們就建立了一個無約束規(guī)劃模型。5. 模型的建立 很顯然，當(dāng)一輛車到達收費站時，如果所有的收費窗口都正在收費，那么這輛車就必須等待，這樣就形成了一個隊列，車輛較多時就會形成幾個隊列。我們可以用排隊論的理論來分析這個問題。一個排隊系統(tǒng)能夠用下面的形式表示出來： 輸入過程一定時間顧客的到達數(shù)目服從的分布 服務(wù)時間服從的分布 服務(wù)臺的數(shù)目 系統(tǒng)容量 顧客的總數(shù)目 服務(wù)規(guī)則對于本問題，輸入過程是泊松過程，服務(wù)時間服從的分布未知，服務(wù)臺（在本題中即收費窗口）的數(shù)目有限（一般大于1），而根據(jù)我們的假設(shè)和說明，系統(tǒng)容量和顧客（即到來車輛總數(shù)目）均為無窮大，而服務(wù)的規(guī)則為先進先出。所以本問題的模型即：這樣的收費站的示意圖如圖1所示：表示通行車輛圖1：收費站示意圖 表示收費窗口再由排隊模型的理論，有： （1） （2） （3）注：分別表示對后面的隨機變量取方差和均值。我們的目標(biāo)函數(shù)即為。另外，由于目前對于排隊模型的研究并沒有建立公認的確切理論，在這個模型中，每個收費窗口的服務(wù)強度并沒有確切的表達式，我們就取目標(biāo)函數(shù)為： （4）同時把的值適當(dāng)?shù)脑龃缶涂梢韵@一改變造成的誤差。這樣，（3）和 （4）就構(gòu)成了我們的模型：min ，其中6. 模型的求解 我們先對找到的數(shù)據(jù)進行分析，算出（3）式中各參數(shù)的值。在假設(shè)中，我們已經(jīng)知道，在單位時間內(nèi)車輛到來的數(shù)目服從泊松分布。而由排隊論理論，該泊松分布的參數(shù)即為單位時間的車流量。另外，由于高速公路往往會有多條車道，我們設(shè)第i條車道的車流量為（i=1，2，），由泊松分布的可加性可以知道，所有車道的總的車流量，也就是到達收費站的車流量為，根據(jù)我們在多篇文獻及網(wǎng)上查到的資料顯示，高速公路上的平均車流量在0.2輛/秒左右，而高峰期的車流量在0.5輛/秒，我們就使用這兩個數(shù)值對模型進行求解。下圖2是我們找到的某路段收費站窗口服務(wù)時間概率的分布圖。 圖2：收費窗口服務(wù)時間概率分布圖根據(jù)我們查得的文獻結(jié)論以及上圖圖象，服務(wù)時間近似服從對數(shù)正態(tài)分布或正態(tài)分布。下面我們分別對它們進行檢驗：我們采用MATLAB工具箱對兩個分布進行檢驗。對于對數(shù)正態(tài)分布，先將上圖橫坐標(biāo)取對數(shù)得到新的圖象；對于正態(tài)分布，圖象不變。然后用正態(tài)分布檢驗命令normplot對兩者進行檢驗，分別得到圖3和圖4。該命令檢驗結(jié)果有如下意義：如果數(shù)據(jù)來自正態(tài)分布，則圖形顯示出直線性形態(tài)。圖3：服務(wù)時間對數(shù)正態(tài)分布檢驗圖 圖4：服務(wù)時間正態(tài)分布檢驗圖容易看出，圖4的圖形直線性更明顯一些，而且擬合得相當(dāng)不錯，因此我們認為收費站服務(wù)時間近似服從正態(tài)分布。再對的分布參數(shù)進行極大似然估計得到（單位分別為秒，秒），然后我們對的分布進行皮爾遜檢驗，在95%的置信水平上檢驗通過。圖5：離去時間概率分布圖 圖5是車輛出站時間的概率分布圖，近似服從正態(tài)分布。同上面一樣我們對其進行檢驗，得到如下檢驗圖： 圖6：出站時間正態(tài)分布檢驗圖我們可以看到，直線性形態(tài)還是比較明顯的。然后我們對的分布參數(shù)進行極大似然估計，得到（單位分別為秒，秒），然后我們對的分布進行皮爾遜檢驗，在95%的置信水平上檢驗通過。由于服務(wù)時間和出站時間是相互獨立的，所以有：另外，假定= 0.02，= 0.05（單位為元/秒，關(guān)于這兩個參數(shù)的選取我們會在后面進行分析），則= 0.4這樣模型所需要的參數(shù)都確定了，我們采用了遺傳算法對模型進行了求解，算法的流程圖如下： 圖7：遺傳算法流程圖具體步驟如下：1 編碼初始化：鑒于實際中窗口的數(shù)目不可能太大，對于一個收費站來說，能建設(shè)到40個窗口的可能性太小了。因為窗口的數(shù)目不僅取限于車站的面積，而且還要受經(jīng)濟效益的約束。所以我們選擇編碼的二進制精度：串長為20，范圍為1到40 。2評價函數(shù)：即為模型的目標(biāo)函數(shù)3. 選擇過程：我們采用的通用的旋轉(zhuǎn)賭輪法。4雜交操作：并且根據(jù)我們多次試驗的經(jīng)驗：取雜交概率為0.95，有更好的全局最優(yōu)解搜索能力和收斂速度快的優(yōu)點。然后隨機確定雜交位置然兩個父本進行交換基因。5變異操作：根據(jù)我們多次的實驗數(shù)據(jù)，對于我們這個問題取變異率為0.01有更好的全局最優(yōu)解的搜索能力和收斂速度快的優(yōu)點。然后隨機進行選擇父本和變異基因位。6確定遺傳算法終止條件：大多數(shù)研究者認為對于遺傳算法的終止條件目前尚無定論，一般都取為遺傳代數(shù)。在這里為了增加收斂速度，并且取迭代數(shù)為25也有更好的全局最優(yōu)解的搜索能力。我們得到的結(jié)果為：當(dāng)平均車流量輛/秒時，最佳收費窗口數(shù)目為5；當(dāng)高峰時期車流量為輛/秒時，最佳收費窗口數(shù)目為10.顯然，由于收費站交通繁忙，應(yīng)該著重考慮高峰時期，倘若只按平均車流量來設(shè)置5個收費窗口，在車流高峰時期就會發(fā)生嚴(yán)重的堵車現(xiàn)象，所以我們最后的結(jié)果為：收費站應(yīng)設(shè)置10個收費窗口。7. 模型結(jié)果的檢驗與分析7.1 模型結(jié)果的檢驗為了驗證這一結(jié)果，下面我們采取解析的方法對目標(biāo)函數(shù)進行求解。由于和是給定的，而收費窗口的數(shù)目為變量，是的函數(shù)，現(xiàn)在要求，使得 = min，為正整數(shù)。由于只能取正整數(shù)，所以函數(shù)不連續(xù)，這樣就不能采用經(jīng)典微分法。這里采用邊際分析方法來求解。根據(jù) = min這一點，則有： （5） （6） 將（4）代入（5），（6），即得到： （7） （8）由（7）， 由（8）， 也就是： 即有： （9）根據(jù)（9）式，依次求出1，2，3，時的值。由于已知，根據(jù)它落在哪個不等式構(gòu)成的區(qū)間就可定出的值。分別代入 ，0.5 計算的值，得到：時， 表1 4 5 6 7 0.9672 0.2176 0.0613 0.0178的相應(yīng)差值為0.7496，0.1563，0.0435， 而 ，根據(jù)（9）式 我們?nèi)? 5；時， 表2 9 10 11 12 1.8102 0.6205 0.2520 0.1075的相應(yīng)差值為1.1897，0.3685，0.1445，而 ，根據(jù)（9）式我們?nèi)? 10.上面的結(jié)果與我們用遺傳算法得到的結(jié)果完全一樣！7.2 模型參數(shù)和的解釋由于我們查不到相關(guān)的資料，模型中兩個參數(shù)的值= 0.02，= 0.05是我們自己給定的，其意義如符號約定中所述。自然這樣的取值會與現(xiàn)實有較大的出入。但從上面分析中可以看到，最佳窗口數(shù)目只與這兩個參數(shù)的比值有關(guān)，只要我們?nèi)〉膬蓚€參數(shù)的值的比值是合理的，則得到的結(jié)果就是合理的。7.3 模型求解過程中反常結(jié)果的解釋在應(yīng)用（3）式我們發(fā)現(xiàn)在有的和取值的時候，隊長會出現(xiàn)負值。經(jīng)過觀察后，我們發(fā)現(xiàn)問題在于（3）式中有的出現(xiàn)了負值，經(jīng)分析后我們對這一現(xiàn)象作出如下解釋：當(dāng)隊長為負值時，即，這表示收費窗口的平均服務(wù)強度大于1，這樣當(dāng)收費站運營一段時間后，在站里排隊等待收費的長度將越來越大，最終這一系統(tǒng)將崩潰！所以在實際求解時我們將隊長取負值的情況舍去了。為了進一步驗證我們模型的合理性，我們對從0.05到1.00，步長為0.05進行取值，分別得到的最佳服務(wù)窗口數(shù)目如下表3所示：表3：對應(yīng)每一車流量的最佳服務(wù)窗口數(shù)目 0.050.100.150.200.250.300.350.400.450.50 2 3 4 5 6 7 8 9 10 10 0.550.600.650.700.750.800.850.900.951.00 11 12 13 14 15 16 17 17 18 19為了更清楚地顯示我們的結(jié)果，將表3轉(zhuǎn)化為圖8（見下頁）：從圖7中可以清楚地看到：當(dāng)車流量逐漸增大時，最佳服務(wù)窗口的數(shù)目也逐漸增大或不變，這個結(jié)果顯然與實際相符。7.4 模型的結(jié)果與現(xiàn)實情況的比較 考慮每條路只有一個收費站的情況。從表3和圖8中可以看到，當(dāng)取最佳收費窗口數(shù)為10時，倘若車流量時，最佳收費窗口數(shù)并不為10，由于我們并不能確定現(xiàn)行收費站的窗口數(shù)，所以在這里不好對我們模型的結(jié)果與現(xiàn)行情況進行比較。這里不妨取，從表3和圖8中可以得到： 當(dāng)車流量時，并不是最佳收費窗口數(shù)，設(shè)6個窗口會使得車輛排隊長度過長，顯然不是有效的。在這種情況下，雖然隨著的變化，最佳收費窗口數(shù)也在變化，但設(shè)10個收費窗口顯然要比設(shè)6個收費窗口要有效。 當(dāng)車流量時，設(shè)置6個收費窗口已經(jīng)足夠，而設(shè)置10個收費窗口會加大收費站的成本，這表明模型的結(jié)果在這種情況下比現(xiàn)行的效率低。 圖7：對應(yīng)每一車流量的最佳收費窗口數(shù)目折線圖8. 模型的評價 （1） 在模型的處理中只對單種車型進行了考慮，對于不同的車型我們可以給它們加個權(quán)重系數(shù)來考慮不同的車型，這樣得到一個加權(quán)的進站等待時間，服務(wù)時間以及出站等待時間，模型的結(jié)果就會更精確一些。（2）. 本模型忽略了對車道的考慮，鑒于我們對模型的假設(shè)（5）以及泊松分布的可加性，這樣的處理應(yīng)該是合理的。同樣根據(jù)這兩點，我們也可以進行對多車道的推廣。（3）. 本模型中有些參數(shù)是根據(jù)人工選定的，可能跟實際情況會存在一些差別，但是并不影響該模型的適用性。模型的結(jié)果非常符合實際，說明我們選取的參數(shù)與實際情況還是比較符合的。（4） 當(dāng)考慮到各種車型以及各種收費方式時，所改變的也只是幾個時間變量，我們只需要相應(yīng)地改變模型的參數(shù)，即可對模型進行求解。這說明該模型具有橫強的適