1、基于排隊論的城市隨機應急設備的定位問題摘要在城市規劃建設中,經常需要考慮諸如醫療救護中心、消防中心、110出警 中心等應急服務設施的優化選址問題，一旦某地出現需要服務的緊急事件，有相 應的服務設施點能在規定的時間內到達現場進行服務。對于第一問，要求在5個點6條邊的網絡圖上設計模型和算法，選擇最佳的 應急服務設施位置。在現實情況中，應急服務設施可以建立在圖上的任意一個位 置。我們以時間間隔0.5分鐘（車程500m）為研究對象，將各道路切片離散為 500m的路段，新添28個節點。將平均響應時間F（乂）分解為行程時間，平均等 待時間例3,i），對兩者進行加權求和。利用Floyd算法得到33個節點到5

2、個服 務需求點的最短距離，再除以速度可求得相應的最短行程時間Gt（x，Wt（x，的 求解為M/M/2的等待制排隊模型求平均等待時間。求解得出v2節點的平均響應 時間為2.869最小。所以最佳的應急服務設施位置為v2點。對于第二問，要求在某地區行政地圖內建立24個應急服務設施，配備1520 臺移動服務點，找到最佳的位置。解題思路分為兩步：1）確定分區及應急服務 設施建設點數目；2）確定每個區域相應的移動服務臺配備數目。分區以響應時 間和最大覆蓋度為約束條件。結合實際移動服務臺到達災情現場的合理時間和題目中各點之間的距離情 況，將25分鐘設為節點發生災情后的最大響應時間，并以此為依據將該區域劃 分

3、為4個分區，即需要建立4個應急服務設施。在50個候選點中挑選4個作為 最佳位置，并以它們為中心，25分鐘車程為約束建立覆蓋度為96%的覆蓋模型。 得到5種最優方案。再以第一問為基礎分別計算5種方案四個區域的平均響應時 間，分別為 6.5470、4.9971、4.9645、6.4252、5.7746。選擇方案 3 的 Q 點、3 點、12點和21點作為應急服務設施建設的最佳位置。根據平均響應時間配備相 應的移動服務臺數量為4。對于第三問，該問要求設計一個優先權模型，并利用第二問所給的地圖進 行仿真驗證模型。借鑒銀行客服系統對對VIP顧客開設VIP通道的思想，在本題 針對重大險情發生點開設“重大險

4、情VIP通道”，建立優先權排隊模型。對第二 問中以Q點為中心的區域進行計算機仿真檢驗。Matlab編程實現VIP通道，提 取發生重大險情的點加入VIP通道隊列。服務臺先對優先權較高的VIP通道隊列 進行服務，直到VIP隊列為空，才對普通災害隊列進行服務。最后列舉了兩種仿 真情況，分別對應發生和不發生重大險情的狀況，可以看出仿真效果較好。對于問題四，基于前三問我們從應急服務設施的覆蓋率、運行成本、應具有搶 占性優先權以及市民防災教育的角度，向政府提出了 4條建設性意見。最后，我們對建立的模型進行了客觀的評價，并進行了推廣。關鍵詞Floyd算法 平均響應時間 覆蓋度 枚舉法 重大險情VIP通道1問

5、題的提出1.1研究背景在城市化進程中千萬不能忽視城市基礎設施的建設，以及對未知的自然災害 的防范。防災設施的建設，應該在城市基礎設施建設中占有相當的比重。下水管 道，抽水站，消防站等等防災設施在城市建設過程都不能缺少。由于災害的未知 性和不確定性，往往防災設施不是固定在某一個具體位置，而是可以移動提供服 務的，如抽水車和消防車等。1.2研究的意義應急設施的合理選址及其數量的合理選擇在方便市民生活，提高城市的災害 防御能力的同時，對社會資源的合理配置有重要意義。2問題的分析對于第一問，要求在5個點6條邊的網絡圖上設計模型和算法，選擇最佳的 應急服務設施位置。由于在現實情況中，應急服務設施可以建立

6、在圖上的任意一 個位置，而不僅限于節點處。我們以時間間隔0.5分鐘（車程500m）為研究對象， 將各道路切片離散為500m的路段，新添28個節點。響應時間=（行程時間+等待 時間）X權重，平均準備時間忽略不計。用Floyd求出行程時間，用排隊論求出 等待時間，分別求出33個點的平均響應時間，比較得出最佳應急服務設施位置。對于第二問，要求在某地區行政地圖內建立24個應急服務設施，配備1520 臺移動服務點，找到最佳的位置。結合實際移動服務臺到達災情現場的合理時間 和題目中各點之間的距離情況，將25分鐘設為節點發生災情后的最長等待時間， 并以此為依據將該區域劃分為4個分區，即需要建立4個應急服務設

7、施。在50 個候選點中挑選4個作為最佳位置，并以該4個點為中心，25分鐘車程為約束 建立覆蓋度為96%的覆蓋模型。再以第一問為基礎分別計算四個區域的平均響應 時間。根據平均響應時間配備相應的移動服務臺數量。對于第三問，借鑒銀行客服系統對對VIP顧客開設VIP通道的思想，針對重 大險情發生點開設“重大險情VIP通道”，建立優先權排隊模型。對第二問中以 Q點為中心的區域進行計算機仿真檢驗。計算機產生隨機數a，對應11個點發生 災害并請求救援的概率，模擬出原始險情隊列；再次產生隨機數b,模擬發生災 害為重大險情的概率。Matlab編程實現VIP通道，提取發生重大險情的點加入 VIP通道隊列。服務臺先

8、對優先權較高的VIP通道隊列進行服務，直到VIP隊列 為空，才對普通災害隊列進行服務。對于第四問，要求給政府寫一個通俗易懂、觀點明確的建議。基于前三問的 求解結果，基于應急設施的覆蓋率、運營成本等角度提出建議。3模型的假設3.1假設移動服務臺的出車平均準備時間在情況緊急下極小，忽略不計。3.2假設災情都發生在路口節點上，其他地方的災情也近似到附近的節點;3.3假設所有道路的路況都一樣，不存在堵車和紅綠燈等狀況；3.4假設應急服務站不為自己管轄范圍以外的對象提供服務；3.5假設被多個服務覆蓋范圍包含的對象點，可以優先選擇距離自己最近的空閑 的服務站服務；3.6假設當移動服務點在為某對象服務時，在

9、服務未完成之前不會中途終止此處 的服務而去響應別的對象；3.7假設移動服務點在服務完一處對象后，先返回自己的服務站再才去響應其他 對象。4符號說明符號說明F (X)平均響應時間Gt (x, i)行程時間Wt (x, i)平均等待時間d (x, i)節點i到五個服務點的最短距離矩陣T移動服務臺到達災情現場的約束時間L移動服務臺到達災情現場的約束距離Qi每個區域配備移動服務臺的數量m點覆蓋度T L仿真隊長Ls平均隊長WS平均逗留時間L平均等待隊長注：其他符號見文中說明5模型的建立與求解5.1問題一模型的建立與求解5.1.1.問題分析首先由于在現實情況中，最佳的應急服務設施位置可以建立在圖上的任意一

10、個 位置，而不僅限于節點處。我們以時間間隔0.5分鐘（車程500m）為研究對象， 將各道路切片離散為500m的路段，新添28個節點，分別標記為A1A28。如圖 所示：V1圖1道路離散圖以平均響應時間最小為最終目標，計算出分別以33個節點為設置點的平均 響應時間，比較得出最佳應急服務設施位置。將平均響應時間F (X)分解為行程 時間Gt(x,i)(從服務設施到達服務對象位置的時間)、平均等待時間Wt(x,i)(災 情現場處理時間)，對兩者進行加權求和。Gt(x,i)的求解為33個節點到v1v5 的最短行程時間，利用Floyd求得33個節點到5個服務需求點的最短距離再除 以速度可求得，Wt(x，i

11、)的求解為M/M/2的等待制排隊模型求平均等待時間。圖2應急響應流程圖5.1.2.建立模型與求解將33個節點以v1v5, A1A28的順序統一為節點1至33。，取1到5表 示五個服務需求點。以第x個節點為設置點的平均響應時間為F(X)，平均行程時間為Gt3,i)， 第i個服務需求點的平均等待時間為Wt3,i)，第i個服務需求點的權重分別為七。假設事件的到達服從參數為人=z。的泊松分布，需求服務時間服從腥入 負指數分布。機r 、人ne-九PI = n=n!F(X) = (Gt(x, i)+Wt (x, i)hil =x Wq q總響應時間返回時間服務時間休整時間可能的排隊等待時間* 行程時間服務

12、準備時間圖3時間軸5.1.2.1.行程時間Gt(x,i)的求解首先用Floyd求得節點i到五個服務需求點v1v5的最短距離矩陣d(x,i)， 速度v為60km/hGt (x, i) = d (x, i) / v表1 33個節點到五個服務點的行程時間v1v2v3v4v5A1A2A3A4A5A6A7v1012660.50.511.51.522.5v2103570.51.522.50.511.5v3230642.51.510.52.521.5v4656025.56.576.55.566.5v5674206.55.554.56.565.5續表1A8A9A10A11A12A13A14A15A16A17A

13、18A19A2032.52.533.544.555.51.522.5322.53.544.555.566.50.511.5210.50.511.522.533.53.544.5576.55.554.543.532.54.543.5354.53.532.521.510.56.565.55續表1A21A22A23A24A25A26A27A283.544.555.56.576.52.533.544.55.566.55.566.576.55.554.52.521.510.50.511.54.543.532.51.510.55.1.2.2.平均等待時間Wt3,i）的求解Wt（尤,i）為M/M/2等待制排

14、隊模型的求解，各項參數分別為：系統中并聯服 務臺的數目s=2，單位時間內平均進入系統的顧客數R=0.012,0.042, 0.012, 0.042, 0.012,平均服務時間T=1。利用LINGO求解（附錄1）得到結果如下所 示：表2五個服務點的平均等待時間（單位：h）Wt (x,1)Wt (x,2)Wt (x,3)Wt (x,4)Wt (x,5)0.36 X 10 -40.44 X 10 -30.36X 10 -40.44 X 10 -30.36X 10 -45.1.2.3平均響應時間F（X）的求解將行程時間Gt3,i）與平均等待時間Wt（x，i）進行加權求和得到平均響應時間 F（X）。用M

15、ATLAB求解（附錄二）得到結果。表3 33個節點的平均響應時間v1v2v3v4v5A1A2A3A4A5A63.2692.8693.7693.1694.1693.0693.5693.8693.8193.1693.469A7A8A9A10A11A12A13A14A15A16A173.7694.0693.9193.8193.8693.9193.9694.0194.0694.1192.919A18A19A20A21A22A23A24A25A26A27A282.9693.0193.0693.1193.1693.2193.2693.2193.4693.7693.969比較33個節點的平均響應時間，v2的

16、平均響應時間為2.869最小。也就是 說將應急服務設施設置在v2點時，節點v1、v2、v3、v4、v5等待移動服務臺前 來救災的平均響應時間最短。所以最佳的應急服務設施位置為v2點。5.2問題二模型的建立與求解5.2.1.問題分析對于第二問，要求在某地區行政地圖內建立24個應急服務設施，配備1520 臺移動服務點，找到最佳的位置。結合實際移動服務臺到達災情現場的合理時間和題目中各點之間的距離情況，將25分鐘設為節點發生災情后的最長等待時間， 并以此為依據將該區域劃分為4個分區，即需要建立4個應急服務設施。在50 個候選點中挑選4個作為最佳位置，并以該4個點為中心，25分鐘車程為約束 建立覆蓋度

17、為96%的覆蓋模型。再以第一問為基礎分別計算四個區域的平均等待 時間。思路圖如下：Stepl：建立時間約束為T25min，轉化為L25km;Step2：根據時間約束計算分區與設施合理數目為S=4;Step3:建立分區覆蓋模型，并求解得到5個方案；Step4:求解5個方案第i個區域的平均等待時間W七，得到總的平均等待時 間Step5 :根據每個區域的平均等待時間確定配備移動服務臺的數量Qi5.2.2建立模型與求解5.2.2.1應急服務設施分區確定時間約束。由于現實生活中移動服務臺到達災情發生點的時間T有一 定要求，并且T越短越好。超過一定時間災情造成的損失將不可挽回，移動服務 臺到達已沒有意義。

18、經過調查并結合題目中區域圖的實際距離，將該約束時間定 為T 25min，轉化為路程為L 25km。確定分區數目。建立點覆蓋模型。在50個候選點中選擇S=2、3、4時分別有C2 , C3 , C4種情況。為尋求有限最優解，加入覆蓋率m為約束條件。經過 505050反復調試程序S=2、3時，必須將約束T調試到極大，遠遠大于25min，才能將 覆蓋度提升到90%，因此將這兩個方案舍棄。S=4時，覆蓋度m能夠達到96%， 基于覆蓋度最大原則，選擇S=4的方案，即劃分為4個區域建設4個應急服務設 施點。表4點到達模型的服務臺管轄分布情況表中心點EO1827KQ312Q312214 R服務覆蓋點D，F,G

19、,J,L,6，7，8，9，10，11，12A，B,C,D,虬 O,P,R,1，2，3，5，26，28，29，30，31，32G，I,J,K,L,11，13，14，15，16，17，18，19，20，21，22,23， 24， 25N，P,Q,23，24,26，27，28，29，30I,J,K,L,M,N,13，16，17,18,19，20，21，22，23，24，25A,P,Q,R,26，27，28，29，30，31，32B,C,D,O,P,1，2，3，4，5，6，7E,F,G,H,9，10,11，12，13，14A,P,Q,R,26，27，28，29，30，31，32B,C,D,O,P,1，

20、2，3，4，5，6，7E,F,G,H,9，10,11，12，13，14I,J,K,L,M,N,6，16，17,18,19，20，21，22，23，24，25A,B,C,O,P,Q,R,1，2，28，29，30，31，32713炎71423D,E,F,G,L,M,3, 5, 6, 7, 8, 9, 10, 11, 19, 20G,H,I,J,K,L,11, 12, 13, 14, 15, 18, 19K,L,虬 N,16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27A,B,C,O,P,Q,R,1, 2, 28, 29, 30, 31, 32D,E,F,G,L,M

21、,3, 5, 6, 7, 8, 9, 10, 11, 19, 20G,H,I,J,12, 13, 14, 15, 18K,L,虬 N,16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27表5五種方案平均響應時間情況表方案響應時間總平均響應區域1區域2區域3區域4時間16.43419.59866.65173.50366.547026.46683.94395.71763.86034.997133.94395.71763.86036.33604.964546.68328.05406.03844.92516.425256.68328.05403.43614.92515.

22、7746位置。此方案中重點、次服務點A至R全部覆蓋，其他服務點1至32除了 8點、15點沒有覆蓋之外全部覆蓋。覆蓋率達到96%，覆蓋度較好。其它1區域邊界重點服務地點 0伯次服務地點A.B.R*鄰區路口圖4分區圖五種方案平均響應時間對比可以得到方案3的總平均響應時間為4.9645最 小。所以選擇方案3的Q點、3點、12點和21點作為應急服務設施建設的最佳5.2.2.2移動服務點配備因為區域中權重最大的點為0點，計算S =2,3,4,5時0點的平均等待時間，如果該點符合要求，則其他點的等待時間都符合要求。計算M/M/S等待制排隊模型，各項參數分別為S=2/3/4/5，R=0.085,0.035,

23、0.01，T=10。Lingo 求解結果如下：表6不同服務臺數目平均等待時間情況表服務臺數目S=2S=3S=4S=5平均等待時間2.20440.282180.0374500.0045878從表中可以看出S=4和5時，平均等待時間分別為2.2min、0.27min，都已 達到極小值且滿足要求。由于移動服務臺屬于貴重基礎設施，每增加一臺服務點， 消防部門或者政府就必須投入大量資金，基于節約成本，在滿足等待時間約束下， 選擇服務臺數目盡可能少。因此，我們選擇S=4的情況，即每個區域配備4個移 動服務點。5.3問題三模型的建立與求解5.3.1問題分析該問要求設計一個優先權模型，并利用第二問所給的地圖進

24、行仿真驗證模型。 借鑒銀行客服系統對對VIP顧客開設VIP通道的思想，在本題針對重大險情發生 點開設重大險情VIP通道。5.3.2模型建立在第一問M/M/1等待制排隊模型基礎上建立服務臺為4的優先權排隊模型M /M/4/8/8/PRT = K X LLs =X 吒，I =X WW = W +1， L = L +-s q H S q 日符號解釋：K :放大因子（常數），因為真實模型求解的LS十分小，為了仿真方便， 將隊長擴大K倍。5.3.3仿真檢驗對以Q點為中心的區域進行計算機仿真對模型進行檢驗，模擬T為5。把Q 點覆蓋區域的11個點 A,P,Q,R,26，27，28，29，30，31，32）進

25、行標號 1,2,3,4,5,6,7,8,9，10,11）。位置點APQR26272829303132編號1234567891011計算機產生隨機數a，對應11個點發生災害并請求救援的概率，模擬出原 始險情隊列；再次產生隨機數b,模擬發生災害為重大險情的概率。Matlab編程 實現VIP通道，提取發生重大險情的點加入VIP通道隊列。服務臺先對優先權較 高的VIP通道隊列進行服務，直到VIP隊列為空，才對普通災害隊列進行服務。 相同等級的服務隊列中，不同成員遵循先到先服務的原則。表7仿真模擬結果中的兩種情況模擬結果情況一情況二發生重大險情沒有重大險情原始應急災害隊列58745109461重大險情位

26、置0100000000普通災害隊列5745109461重大險情VIP通道隊列8圖5發生重大險情圖6未發生重大險情同理可以模擬其他三個區域遇到突發重大險情時優先服務的情況。5.4給政府的建議城市建設不只是使城市昌盛，經濟繁榮，更重要的一個方面是使城市安定祥 和。其中，城市防災應急規劃就是城市建設的一個重要內容。基于前三問的模型 與求解結果，我們向政府部門提出4條建議：建議一，增加應急服務設施，提高服務的點覆蓋率。經過第二問的討論，我 們得出了在本地區建立四個應急服務設施，每個服務站配備四個移動服務點可使 服務覆蓋度達到96%，已經相當可觀了。但是，8號點和15號點還是未能包括在 服務范圍內，這是

27、因為這兩個點離最優服務站位置太偏遠，如果從最近的服務站 派移動服務點對其服務，其行程時間已超過了服務限制期，這樣就不具有實際意 義了。為避免個別偏遠地區發生險情卻無法享受應急服務，對人民社會造成不必 要的損失，政府可以在這些地區單獨配備一個移動服務臺以應對險情。建議二，在服務時間允許的前提下減少區域內移動服務臺數，以節約成本， 減少財政支出。建議三，某些應急服務還具有非強占性優先權，比如消防系統、急救系統， 服務站應該優先為災情嚴重的對象提供服務。建議四，加強對市民的防災教育。即便政府的防災應急規劃怎么合理，應急 服務臺到達服務點仍需要一定時間，在應急服務臺到達之前，市民必須做好自救 與自我保

28、護工作。因此政府除了要做好城市防災應急規劃之外，也要加強對市民 的防災自我保護教育與演練。希望市政府在進行服務點選址時可以綜合充分地考慮這些問題，把我們的城 市建設得更加和諧繁榮。6模型的優缺點與推廣6.1模型的缺點第二問求解每個區域的最佳配備移動服務臺數量時，并沒有仔細量化，只 是簡單主觀判斷。第二問中設置的時間約束25min太大，事實上移動服務臺到達災情現場的 最佳時間為5-10分鐘。6.2模型的優點第一問求最佳設置點時，采用了離散化的思想，認為時間間隔在0.5分鐘 內（距離為500米）的道路為一個離散點。第二問以時間約束和覆蓋率約束求得的點覆蓋模型較為科學合理，而且覆 蓋率高，能夠很好地

29、對整個區域進行應急服務。Floyd算法只求解了服務臺與各節點之間的最短距離，減小了計算復雜度， 同時也沒有必要計算任意兩節點之間的最短距離。為優先權較高的服務點開設“重大險情VIP通道”，形成兩條隊列，能夠 很好的實現優先權原則下的應急服務點派出。利用計算機仿真時，首先對一個應急服務設施的覆蓋區域進行仿真，然后 推廣到其他區域，進而覆蓋整個區域。6.3模型的推廣該模型不僅可以應用到城市災害應急體系構建與應急設施的布局，也可以推廣應用到各種最優位置選取或資源最優化配置的問題。比如物流網絡的布設、巡 查服務系統的建立。參考文獻：Oded Berman Richard C. Larson OPTIM

30、AL SERVER LOCATION ON A NET OPERATING AS AN M/G/1 QUEUE July 1980常玉林，王煒，城市緊急服務系統優化選址模型，系統工程理論與實踐，2000年2月第2期方磊，何建敏，城市應急系統優化選址決策模型和算法，管理科學學報，2005年2月，第8卷第1期傅昱賢，陳 適，黃松錢，交巡警服務平臺的設置與調度，2011.9曹永榮，韓瑞霞，胡偉，基于馬爾科夫狀態轉移過程的M/M/m排隊模型仿真，2012年1月，第29卷第1期景良竹，吳 窮，單個應急服務設施點選址模型分析，2011年3月第23卷第 1期附錄:Longo程序代碼：T=1；!M/M/S/8

31、/8/FCFS 模型；load=R*T；!Pwait=peb(load,S)；!符號說明W_q=Pwait*T/(S-load)； L_q=R*W_q；!S表示系統中的服務臺數；W_s=W_q+T； L_s=W_s*R；!R表示單位時間內平均進入系統的顧客數；!M/M/4/8/8 模型；叮表示平均服務時間；!load表示系統的載荷數；S=4；!Pwait表示顧客的等待概率；R=0.085；!W_q表示平均等待時間；T=10；!L_q表示平均等待隊長，load=R*T；!W_s表示平均逗留時間；Pwait=peb(load,S)；!L_s表示平均隊長；W_q=Pwait*T/(S-load)；

32、L_q=R*W_q；!W_s=W_q+T； L_s=W_s*R；S=2；Matlab程序代碼：R=0.012；%求解平均響應時間的floyd算法主T=1；程序load二R*T；%Pwait=peb(load,S)；%符號說明W_q=Pwait*T/(S-load)； L_q=R*W_q；%A離散后所有點之間的權重矩陣W_s=W_q+T； L_s=W_s*R；%D任意兩點之間的最短距離矩陣S=2；%n矩陣長度R=0.035；%h權重矩陣%DD不同點對應災害發生五點的距離%-%mint最短響應時間%jizhan基站建立位置function%D,R=floydwarshall(A)-D=A;clea

33、rn=length(D);clcfor i=1:n%權重矩陣for j=1:nquanjuzhen;R(i,j)=j;t3=1/inf;endD,R=floydwarshall(A);endD;for k=1:nn=length(D);for i=1:nfor j=1:nh=0.1 0.35 0.1 0.35 0.1;ifh=h;for i=1:n(D(i,k)+D(k,j)D(i,j)for j=1:5D(i,j)=D(i,k)+D(k,j);DD(i,j)=D(i,j);R(i,j)=k;endendendendDDendDD(:,1)=DD(:,1)+60*4/111107pd=0;+t3;for i=1: