4-2+交通流理論-排隊(duì)論

1、第二節(jié)第二節(jié) 排隊(duì)論排隊(duì)論的應(yīng)用的應(yīng)用第四章第四章 交通流理論交通流理論一、引言一、引言排隊(duì)論排隊(duì)論是研究是研究“服務(wù)服務(wù)”系統(tǒng)因系統(tǒng)因“需求需求”擁擠而產(chǎn)生等待行列即擁擠而產(chǎn)生等待行列即排隊(duì)的現(xiàn)象，以及合理協(xié)調(diào)排隊(duì)的現(xiàn)象，以及合理協(xié)調(diào)需求與服務(wù)需求與服務(wù)關(guān)系的一種數(shù)學(xué)理論，關(guān)系的一種數(shù)學(xué)理論，是運(yùn)籌學(xué)中以概率論為基礎(chǔ)的一門重要分支，亦稱是運(yùn)籌學(xué)中以概率論為基礎(chǔ)的一門重要分支，亦稱“隨機(jī)服務(wù)隨機(jī)服務(wù)系統(tǒng)理論系統(tǒng)理論”。典型的例子典型的例子食堂打飯排隊(duì)、高速公路收費(fèi)站進(jìn)出口排隊(duì)；食堂打飯排隊(duì)、高速公路收費(fèi)站進(jìn)出口排隊(duì)；排隊(duì)論排隊(duì)論是是2020世紀(jì)初開始發(fā)展的。世紀(jì)初開始發(fā)展的。19051905年

2、丹麥哥本哈根電話工程年丹麥哥本哈根電話工程師師愛爾朗愛爾朗首先在電話自動交換機(jī)設(shè)計(jì)時應(yīng)用排隊(duì)論。使電話機(jī)首先在電話自動交換機(jī)設(shè)計(jì)時應(yīng)用排隊(duì)論。使電話機(jī)既能滿足通話需求而又不致設(shè)線過多。第二次世界大戰(zhàn)以后，既能滿足通話需求而又不致設(shè)線過多。第二次世界大戰(zhàn)以后，排隊(duì)論在很多領(lǐng)域內(nèi)被采用。在交通工程中，對于研究車輛延排隊(duì)論在很多領(lǐng)域內(nèi)被采用。在交通工程中，對于研究車輛延誤、通行能力、信號燈配時以及停車場、加油站等交通設(shè)施的誤、通行能力、信號燈配時以及停車場、加油站等交通設(shè)施的設(shè)計(jì)與管理方面得到廣泛的應(yīng)用。設(shè)計(jì)與管理方面得到廣泛的應(yīng)用。19361936年年亞當(dāng)斯亞當(dāng)斯（Adams.W.FAdams.W

3、.F）用以考慮未設(shè)置交通信號交叉口的行人延誤問題，用以考慮未設(shè)置交通信號交叉口的行人延誤問題，19511951年年唐納唐納予以推廣應(yīng)用，予以推廣應(yīng)用，19541954年年伊迪伊迪（ EdieEdie ）應(yīng)用排隊(duì)模型估計(jì)收費(fèi)應(yīng)用排隊(duì)模型估計(jì)收費(fèi)亭的延誤。同年在亭的延誤。同年在摩斯柯維茨摩斯柯維茨的報告中，將其應(yīng)用于車輛等候的報告中，將其應(yīng)用于車輛等候交通流空檔的實(shí)驗(yàn)報告。交通流空檔的實(shí)驗(yàn)報告。二、排隊(duì)論的基本原理二、排隊(duì)論的基本原理1基本概念基本概念1) “排隊(duì)排隊(duì)”與與“排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)”的概念的概念“排隊(duì)排隊(duì)”單指等待服務(wù)的，不包括正在被服務(wù)的；單指等待服務(wù)的，不包括正在被服務(wù)的；“排隊(duì)系統(tǒng)

4、排隊(duì)系統(tǒng)”既包括等待服務(wù)的，又包括正在被服務(wù)的車輛。既包括等待服務(wù)的，又包括正在被服務(wù)的車輛。排隊(duì)的排隊(duì)的 8輛車輛車排隊(duì)系統(tǒng)排隊(duì)系統(tǒng) 10輛車輛車排隊(duì)的車輛排隊(duì)的車輛排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)中的車輛中的車輛2)排隊(duì)系統(tǒng)的排隊(duì)系統(tǒng)的3個組成部分：個組成部分：(1)輸入過程輸入過程就是指各種類型的就是指各種類型的“顧客顧客(車輛或行車輛或行人人)”按怎樣的規(guī)律到達(dá)。有各式各樣的輸入過程，按怎樣的規(guī)律到達(dá)。有各式各樣的輸入過程，例如：例如：定長輸入：顧客等時距到達(dá)。定長輸入：顧客等時距到達(dá)。泊松輸入：顧客到達(dá)時距符合負(fù)指數(shù)分布。這種泊松輸入：顧客到達(dá)時距符合負(fù)指數(shù)分布。這種輸入過程最容易處理，因而應(yīng)用最廣

5、泛。輸入過程最容易處理，因而應(yīng)用最廣泛。愛爾朗輸入：顧客到達(dá)時距符合愛爾朗分布。愛爾朗輸入：顧客到達(dá)時距符合愛爾朗分布。排隊(duì)排隊(duì)輸入輸入 輸出輸出 2)排隊(duì)系統(tǒng)的排隊(duì)系統(tǒng)的3個組成部分：個組成部分：(2)排隊(duì)排隊(duì)(規(guī)則規(guī)則)指到達(dá)的顧客按怎樣的次序接受服指到達(dá)的顧客按怎樣的次序接受服務(wù)。例如：務(wù)。例如：損失制：顧客到達(dá)時，若所有服務(wù)臺均被占，該損失制：顧客到達(dá)時，若所有服務(wù)臺均被占，該顧客就自動消失，永不再來。顧客就自動消失，永不再來。等待制：顧客到達(dá)時，若所有服務(wù)臺均被占，他等待制：顧客到達(dá)時，若所有服務(wù)臺均被占，他們就排成隊(duì)伍，等待服務(wù)，服務(wù)次序有先到先服們就排成隊(duì)伍，等待服務(wù)，服務(wù)次序有

6、先到先服務(wù)務(wù)(這是最通常的情形這是最通常的情形)和優(yōu)先權(quán)服務(wù)和優(yōu)先權(quán)服務(wù)(如急救車、如急救車、消防車優(yōu)先消防車優(yōu)先)等多種規(guī)則。等多種規(guī)則?；旌现疲侯櫩偷竭_(dá)時，若隊(duì)伍長小于混合制：顧客到達(dá)時，若隊(duì)伍長小于L，就排入隊(duì)，就排入隊(duì)伍；若隊(duì)伍長等于伍；若隊(duì)伍長等于L，顧客就離去，永不再來。，顧客就離去，永不再來。2)2)排隊(duì)系統(tǒng)的排隊(duì)系統(tǒng)的3 3個組成部分：個組成部分：(3)(3)服務(wù)方式服務(wù)方式( (輸出輸出) )指同一時刻有多少服務(wù)臺可接納顧客，指同一時刻有多少服務(wù)臺可接納顧客，每一顧客服務(wù)了多少時間。每次服務(wù)可以接待單個顧客，每一顧客服務(wù)了多少時間。每次服務(wù)可以接待單個顧客，也可以成批接待，例

7、如公共汽車一次就裝載大批乘客。也可以成批接待，例如公共汽車一次就裝載大批乘客。服務(wù)時間的分布主要有如下幾種：服務(wù)時間的分布主要有如下幾種：定長分布：每一顧客的服務(wù)時間都相等（發(fā)放物品）；定長分布：每一顧客的服務(wù)時間都相等（發(fā)放物品）；負(fù)指數(shù)分布：即各顧客的服務(wù)時間相互獨(dú)立，服從相負(fù)指數(shù)分布：即各顧客的服務(wù)時間相互獨(dú)立，服從相同的負(fù)指數(shù)分布同的負(fù)指數(shù)分布( (看病看病) )；愛爾朗分布：即各顧客的服務(wù)時間相互獨(dú)立，具有相愛爾朗分布：即各顧客的服務(wù)時間相互獨(dú)立，具有相同的愛爾朗分布。同的愛爾朗分布。為敘述方便，引用下列符號，令為敘述方便，引用下列符號，令M代表泊松分布輸入或負(fù)指數(shù)分布服務(wù)；代表泊松

8、分布輸入或負(fù)指數(shù)分布服務(wù)；D代表定長分布輸入或定長分布服務(wù)；代表定長分布輸入或定長分布服務(wù)；Ek代表愛爾朗分布的輸入或服務(wù)。代表愛爾朗分布的輸入或服務(wù)。于是泊松輸入、負(fù)指數(shù)分布服務(wù)，于是泊松輸入、負(fù)指數(shù)分布服務(wù)，N個服務(wù)臺的排個服務(wù)臺的排隊(duì)系統(tǒng)可以寫成隊(duì)系統(tǒng)可以寫成M/M/N；泊松輸入、定長服務(wù)、單個服務(wù)臺的系統(tǒng)可以寫泊松輸入、定長服務(wù)、單個服務(wù)臺的系統(tǒng)可以寫成成M/D/1。同樣可以理解同樣可以理解M/ Ek /N，D/M/N等符號的含義。等符號的含義。如果不附其它說明，則這種符號一般都指如果不附其它說明，則這種符號一般都指先到先先到先服務(wù)，單個服務(wù)通道的等待制系統(tǒng)。服務(wù)，單個服務(wù)通道的等待制

9、系統(tǒng)。3)排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo)最重要的數(shù)量指標(biāo)有最重要的數(shù)量指標(biāo)有3個：個：(1)等待時間等待時間即從顧客到達(dá)時起到他開始接受服務(wù)即從顧客到達(dá)時起到他開始接受服務(wù)時止這段時間。時止這段時間。(2)忙期忙期即服務(wù)臺連續(xù)繁忙的時期，這關(guān)系到服務(wù)即服務(wù)臺連續(xù)繁忙的時期，這關(guān)系到服務(wù)臺的工作強(qiáng)度。臺的工作強(qiáng)度。(3)隊(duì)長（顧客數(shù)）隊(duì)長（顧客數(shù)）有排隊(duì)顧客數(shù)與排隊(duì)系統(tǒng)中顧有排隊(duì)顧客數(shù)與排隊(duì)系統(tǒng)中顧客之分，這是排隊(duì)系統(tǒng)提供的服務(wù)水平的一種衡客之分，這是排隊(duì)系統(tǒng)提供的服務(wù)水平的一種衡量。量。三、三、M/M/1M/M/1系統(tǒng)系統(tǒng)單通道服務(wù)系統(tǒng)單通道服務(wù)系統(tǒng)1dw)8nd)711q)6n

10、q)5)1 ()41n)3)1 ()()21)0() 1/1/1w22排隊(duì)中的平均等待時間系統(tǒng)中的平均消耗時間非零平均排隊(duì)長度平均排隊(duì)長度系統(tǒng)中的平均方差系統(tǒng)中的平均車輛數(shù)個顧客的概率為在系統(tǒng)中有率為在系統(tǒng)中沒有顧客的概客數(shù)。，指的是排隊(duì)系統(tǒng)的顧系統(tǒng)的狀態(tài)。所謂狀態(tài)或交通強(qiáng)度，可以確定叫做服務(wù)強(qiáng)度。比率，則平均服務(wù)時間為率為服務(wù)后通過的平均服務(wù)通過接受。排隊(duì)從單通道服務(wù)后，則到達(dá)的平均時距為設(shè)顧客平均到達(dá)率為nnPnP四、四、M/M/N系統(tǒng)系統(tǒng)系統(tǒng)，計(jì)算公式如下：務(wù)的對于單路排隊(duì)多通道服式亦相同。組成的系統(tǒng)，其計(jì)算公系統(tǒng)個況相當(dāng)于不能隨意換隊(duì)。此種情的一隊(duì)車輛服務(wù)，車輛應(yīng)隊(duì)，每個通道只為其相：

11、指每個通道各排一個）多路排隊(duì)多通道服務(wù)服務(wù)；道有空就到哪里去接受中頭一車輛可視哪條通隊(duì)條通道服務(wù)的情況，排：指排成一個隊(duì)等待數(shù)）單路排隊(duì)多通道服務(wù)的不同，可分為：系統(tǒng)根據(jù)車輛排隊(duì)方式。隊(duì)長度將趨向于無窮大不穩(wěn)定，排時系統(tǒng)是穩(wěn)定的，否則相仿，當(dāng)為飽和度。和強(qiáng)度，亦可稱系統(tǒng)的服務(wù)強(qiáng)度或交通稱為，則仍記。服務(wù)時間是，則每個服務(wù)臺的平均率為接受服務(wù)后的平均輸出隊(duì)行列從每個服務(wù)臺車輛的平均到達(dá)率，排為進(jìn)入多通道服務(wù)系統(tǒng)設(shè)服務(wù)”系統(tǒng)。條，所以也叫“多通道有排隊(duì)系統(tǒng)中，服務(wù)通道在計(jì)算公式NMMMMNNMMNMMNMMNNNMM/1/21/1/1/1/. 1 多通道服務(wù)方式多通道服務(wù)方式例例3. 一加油站，今

12、有一加油站，今有2400輛輛/h的車流量通過的車流量通過4個通道引個通道引向向4個加油泵，平均每輛車加油時間為個加油泵，平均每輛車加油時間為5s，服從負(fù)指數(shù)服從負(fù)指數(shù)分布，試按多路多通道系統(tǒng)（分布，試按多路多通道系統(tǒng)（4個個M/M/1系統(tǒng)系統(tǒng) ）單路）單路多通道系統(tǒng)（多通道系統(tǒng)（M/M/4系統(tǒng)）計(jì)算各相應(yīng)指標(biāo)。系統(tǒng)）計(jì)算各相應(yīng)指標(biāo)。解：解： 按按4個個M/M/1系統(tǒng)由題意可知：系統(tǒng)由題意可知：s/6136004/2400輛s/51輛，系統(tǒng)穩(wěn)定165輛17.46/55nq輛/255301sd輛/306/15snd輛56/516/5)1 (n按單路多通道系統(tǒng)按單路多通道系統(tǒng)M/M/4計(jì)算：計(jì)算：s

13、/3236002400輛s/51輛310，系統(tǒng)穩(wěn)定1654310N0213. 08642.300617.161651! 4310!31010304kkkP）（兩種系統(tǒng)比較兩種系統(tǒng)比較四、簡化的排隊(duì)延誤分析方法四、簡化的排隊(duì)延誤分析方法交通工程師在應(yīng)用數(shù)學(xué)上成熟的排隊(duì)論之外，還對交通擁擠交通工程師在應(yīng)用數(shù)學(xué)上成熟的排隊(duì)論之外，還對交通擁擠現(xiàn)象以現(xiàn)象以簡化的方式簡化的方式作過分析，作過分析，前提：前提：假定在某一持續(xù)時間內(nèi)假定在某一持續(xù)時間內(nèi)車輛的出入是均一的。車輛的出入是均一的。例：例：有一公路與鐵路的交叉口，火車通過時，柵欄關(guān)閉的時有一公路與鐵路的交叉口，火車通過時，柵欄關(guān)閉的時間間 tr= 0.1h。已知公路上車輛以均一的到達(dá)率。已知公路上車輛以均一的到達(dá)率 900(輛輛h)到達(dá)交叉口，而柵欄開啟后排隊(duì)的車輛以均一的離去率到達(dá)交叉口，而柵欄開啟后排隊(duì)的車輛以均一的離去率u1200(輛輛h)離開交叉口。試計(jì)算由于關(guān)閉柵欄而引起的：離開交叉口。試計(jì)算由于關(guān)閉柵欄而引起的： 單個車輛的最長延誤時間單個車輛的最長延誤時間tm， 最大排隊(duì)車輛數(shù)最大排隊(duì)車輛數(shù)Q， 排隊(duì)疏散時間排隊(duì)疏散時間t 0， 排隊(duì)持續(xù)時間排隊(duì)持續(xù)時間t j 受限車輛總數(shù)受限車輛總數(shù)n， 平均排隊(duì)車輛數(shù)平均排隊(duì)車輛數(shù) ， 單個車輛的平均延誤時間單個車輛的平均延