消防站選址問題附代碼

1、城市消防站點選址問題（附代碼）第二組組員：鄭舟 杜洋洋陳建彬張強沈露陳宇銀摘要隨著國家現(xiàn)代化進程的不斷推進，必須要有一個與之相適應的現(xiàn)代化城市應 急系統(tǒng)和消防布局規(guī)劃.選址問題是應急系統(tǒng)中重要的長期決策之一，選址的好壞直接影響到服務方式、質量以及服務成本等，從而影響到城市應急能力的有效 發(fā)揮和資源的合理配置.本文主要研究城市消防選址的決策問題， 包括單目標選址模型和多目標選址 模型。其中問題一，三，四屆于單目標選址問題，問題二屆于多目標選址問題。 首先我們運用網絡圖的最短路徑算法理論,給出了基于最短路徑的選址問題的算法（Floyd算法），計算出任意兩點的最小路徑。問題一：單一消防站選址問題，我

2、們借用P中心模型，求離消防站的點的最 大距離的最小值。先假定應急服務設施點都選在網絡圖的頂點處，所求的中心點是139點，離消防站的最遠距離為10296.1米。然后考慮了消防站和火災現(xiàn)場在 道路上的的情況，求出了整個網絡的一般絕對中心點 A（7354.915, 4096.364）,離 消防站的最遠距離為10271.18米.問題二：多消防站選址問題，我們采用了多目標決策模型，既考慮了離消防 站最遠距離的最小化，乂考慮了消防站離需求點的總加權最小， 還考慮了超額覆 蓋需求區(qū)域的總權重最大。然后用參數規(guī)劃的目標約束法，把多目標轉化成單目 標，求出消防站的位置。為了簡化問題，僅考慮消防站和火災現(xiàn)場在端點

3、的情況。 本題中，假設離消防站的最大距離為 5000米，超額覆蓋區(qū)域的總權重賦值為 6, 求出消防站的位置分別為點24, 98, 194, 211, 253.該模型可以根據不同城市的 具體情況賦權值，求出適合不同城市的最佳消防點，易于推廣。問題三：共同時間約束下的消防站數量最少問題， 我們首先應用位置集合覆 蓋模型，結合本題的約束條件（10分鐘）算出所需消防站最少個數為 2個，其 次，建立P中值模型，得出所求點為點24和143。問題四：不同時間約束下的消防站最少問題， 通過集合覆蓋模型，結合本題 約束條件（一般位置5分鐘，重要位置3分鐘），算出所需消防站最少個數為 5 個，其次建立P中值模型，

4、得出所求點為點45,點75,點211,點224,點228.問題五：分析消防車的速度對到達時間的影響， 當速度改變時，考慮到經濟 效益以及最優(yōu)化結果，則消防站點的個數相應改變，所以時間隨速度以及站點個 數的影響。根據以上分析可以得到對于實際問題得出最優(yōu)的消防站的選址，解決經濟 效益和滿足實際的救火需求。關鍵詞：最優(yōu)選址問題 P中心模型 P中值模型 多目標決策模型1問題重述在城市中消防站的選址對于及時的消滅火警有著特別重要的意義?？紤]某城市內一區(qū)域，為簡化問題，假定所有火警現(xiàn)場均在下圖的道路上。該區(qū)域內三個重點部位的坐標分別為：(5112, 4806), (9126, 4266) ,( 7434

5、, 1332)(見下圖紅點部位，藍色部分為水域)。要解決如下問題：1. 如果該城市只建一個消防站，最佳的地點應該位于什么位置，該消防站 到達城市道路上的點的最遠距離是多少？2. 如果該城市建五個消防站，最佳的地點應該位于什么位置。3. 如果消防車的行駛速度60km/h,要建幾個消防站才能使得該城市道路上 任何一點發(fā)生火警之后，消防車能在 10分鐘之內到達。4. 如果消防車的行駛速度60km/h,要建幾個消防站才能使得該城市道路上 任何一點發(fā)生火警之后，消防車能在5分鐘之內到達，同時要求到達重點部位的 時間不多于3分鐘。5. 分析消防車的行駛速度對消防車到達火警現(xiàn)場的時間的影響。2問題分析2.1

6、問題一分析在城市中建立一個消防站點，要求出此消防站點的最佳位置以及該點到到達 城市道路上的點的最遠距離。交通條件、自然地理條件、道路狀況等因素都會影響消防站點的選址。為了簡化問題，本題我們只考慮行車距離因素的影響。消防站和火災現(xiàn)場的地址可以是城市道路上的任何位置,而不僅僅是道路端點。要使火災損失達到最小，最重要的是消防隊接到火警后能夠盡快到達火災現(xiàn) 場，這就要求消防站點到城市中任何火災現(xiàn)場的“最遠距離最小”。2.2問題二分析在多個消防站點選址問題中，宜采用多目標方法，并充分體現(xiàn)公共服務設施 的公平性和效率性。首先要求應急求援設施覆蓋所有需求趨于，在考慮具體目標時一是從快速反應或公平性考慮要求消

7、防站服務需求點的最大距離為最?。欢菑某~覆蓋和備用設施考慮,要求消防站覆蓋需求點的總權重最大； 三是從消防 站的易接近性和使用效率出發(fā)，要求消防站服務需求點的總加權距離最小。2.3問題三分析第三問需要求出在相應的時間限制下，為了能使中位選址問題達到最優(yōu)需要 在該城市建立的消防站點個數。根據消防車的行駛速度60km/h以及反應時間限制10分鐘，得出消防站點與相應區(qū)域內的點的最大距離應小于 d=60*10/60km=10km,運用中位點問題模型，采用參數規(guī)劃的約束法，可以很好 的解決該問題。2.4問題四分析第四問在第三問的基礎上，進一步將反應時間限制為5分鐘，同時增加對重 點部位反應時間的限制3

8、分鐘，得出消防站距離相應區(qū)域內的普通部位和重點部 位的最遠距離分另U為5km和3km。在問題三模型的基礎上，增加以及改變某些約束條件，便可讓問題得到解決。3模型假設和符號說明3.1模型假設(1) 相鄰兩個交義路口之間的道路近似認為是直線，把城市地圖抽象成由 點和線組成的無向網絡賦權圖；(2) 假設消防車在到達火災點的途中沒有障礙，即不考慮路況和其他突發(fā) 事件的影響，消防車按照其行駛速度勻速行駛直至到達火災點；(3) 不考慮災情蔓延速度，即火災點不會轉移和增加(4) 不考慮消防隊的反應時間，假設接到火情的瞬間，消防隊即出發(fā)救火3.2符號說明D(i, j)最短距離矩陣dij點Vi到點Vj的最短距離

9、I消防站點的集合J火災現(xiàn)場的集合ii w Ijj w J4模型的建立與求解4.1問題一：單個消防站點選址問題首先，用Floyd算法求出任意兩個結點之間的最短路徑；Floyd算法的基本思想如下：把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達，貝U Gi,j=d, d表示 該路的長度；否則Gi,j=0。定義一個矩陣D用來記錄所插入點的信息，Di,j表 示從Vi到Vj需要經過的點，初始化Di,j=j。把各個頂點插入圖中，比較插點后 的距離與原來的距離，Gi,j = min( Gi,j, Gi,k+Gk,j),如果Gi,j的值變小，M Di,j=k。在G中包含有兩點之間最短道路的信息，而在D中則包

10、含了最短通路徑的信息。如果消防站點和火災現(xiàn)場的地點僅僅可以發(fā)生在網絡圖的節(jié)點上，貝U根據“最遠距離最小”的選址原則，我們很容易就可以得到在途中第139點設置消防站最合適，Lm =10296.1m 。但是實際情況中，更多的消防站點是建設在城市道路上。此模型中運用的符號說明：Lm消防站點到最遠距離最小Si消防站責任區(qū)內bij（0-1）變量，b =1則表示在ej中建設消防站，否則反之zij如果消防站點Vj覆蓋點Vi,則Zj =1 ,否則Zj =0建立如下優(yōu)化模型:min Z = Lm307s.t.Si w (d pi bpq Xpq) 10000 ai(1-1)i 土 307SiZ (dqibpq

11、+d pq Xpq ) 1 0 0 0(1 _ai )(1-2)i z12Lm SiSj dij(1-3)Xij < d ij bij(1-4)以最遠距離最小作為目標函數。約束條件（1-1）, （1-2）表示約束條件（1-3）表示約束條件（1-4）表小用Ling。求解得到：j=139, 147。（即消防站應建在139, 147交義路口）9000800070006000500040003000200010000解 33261。384346627389826766719294 995 102 11110911312830 131157 58 167159193211I255260270275

12、'I282892979 1210 7 .11 144 518 131516-178346婀2007 |117.1156016iSO24.21i42415650 51 5247 t 44 K 5|61632251 25388 84 焰586，81三779116123124 739138 1 44心污1 M 7316692 97233243443449 ksR44644S48c£43443?442250 258 -2514 2：254276 2812912985000141痛8170370 26 -2282422340241 26550261盥!羸德77叩80歸2 冒壽62T29

13、2 2930942552236235237257：292 293近4 30002 召03 9041295 -296£05 七0630710000150004.2問題二：多個消防站點選址問題 此模型中運用的符號說明：仍i第Vi點的權重，重點部位權值為2,其他點權值為1Ui表示點Vi被超額覆蓋的次數，即總覆蓋次數-1,山為整數V(0-1)變量，yj =1則表示在Vj中建設消防站，否則反之zij(0-1)變量，如果消防站點Vj覆蓋點Vi，則Zj =1 ,否則z“ =0Sij消防站點到圖上的最大距離根據上述選址特點，本文提供了一個針對該問題的多目標決策模型。消防站選址的多目標決策模型表述為：

14、min Z1 =$目(1)307max Z2 = ,心山s.t.L=5j呸307' Zij -Ui _1j AZij - Yj _0(5)307'，idj，fj =1模型說明如下：約束條件（4）和（6）式保證設置的消防站數目為 p；約束條件（5）式保證設置的應急救援設施數目不低丁需求區(qū)域i要求的最少設施數qi，超出的數目（播zj Q'）即為需求區(qū)域i超覆蓋的次數Ui；目標函數（1）式和約束條件（7）式使設置的應急救援設施服務需求區(qū)域的 加權最大距離（平均意義上）L為最?。磒-中心模型），體現(xiàn)公平性；如果約束條件（7）式改為d ij zij - s - 一 i 三 I

15、, j 三 J則目標函數（1）式和約束條件（9）式保證設置的應急救援設施服務需求區(qū) 域的最大距離L為最小，體現(xiàn)對應急救援設施快速反應的要求；目標函數（2）式和約束條件（5）式使超額覆蓋最大化，其主要目的是使權 重越大的需求區(qū)域有更多的應急救援設施為其服務；目標函數（3）式和約束條件（5）式使設置的應急救援設施服務需求點的加 權總距離為最?。磒-中值模型），體現(xiàn)效率性。上述模型為3個目標的多目標決策模型，多目標準則函數為minvi,v2,v3.本文采用參數規(guī)劃的目標約束法把多目標轉化成單目標， 來求解上述選址決 策模型。保留決策問題中的一個目標，其余兩個目標被作為約束，通常保留目標 V3,把目

16、標V1和V2約束化，根據城市的具體情況，使 V1和V2分別約束丁 a和 b.模型求解：對丁本題，給離消防站的最大距離的最小值賦值 5000m,給消防站覆蓋需求 點的總權重賦值為6,寫出目標函數和約束條件如下：min 2：_ :'idj Zjs.t. sj -d zj（2-1）307x Zij -Ui -1（2-2）j =1Sj -5 0 0 0ij < 0（2-3）3 0 7'_6（2-4）i白Zij -Yj _0（2-5）模型說明：約束（2-1） （2-3）表示在要建立五個消防站點約束（2-2）保證每個點至少被一個消防站所覆蓋約束（2-3）給消防站點設置最小距離約束（2

17、-4）保證每個重點部位至少被兩個消防站覆蓋目標函數Zi和約束（2-4）使消防站點到火災現(xiàn)場的加權最大距離最小用Lingo求解得到：j=24, 98, 194, 211, 253。（即消防站應建在 24, 98, 194, 211, 253交又路口）4.3 I可題二：在已知消防車運行速度的前提下，我們將時間約束轉換成最遠距離約束，即 最遠行車距離為10000m。此時我們并不知道要在最遠行車距離為10000m的前提下，需要建設多少個消防站點才能覆蓋全部點。我們以最小消防站點個數為約束條件，建立優(yōu)化模型：min z Yji 1s"、07z,=1j =1Zij - Yj 0djjZjj &l

18、t; 10000用Lingo軟件編程求出在反應時間限制下，在該城市建立的最少消防站為 2。目標為使距離總和最小，所以得到的模型為：min ZTgjZjji ± j T3 0 7 s.t. ' Yj =2(3-1)j 土dijZij -10000(3-2)Zij -Yj H(3-3)307 ' Zij =1(3-4 )j =i 模型說明：約束（3-1）表小在圖上建立兩個消防站點約束（3-2）表示Vj消防站到服務點Vi的最遠距離為10000m約束（3-3）在Vj點建立消防站后它才能覆蓋該區(qū)域內的點約束（3-4）使p中心問題得到最優(yōu)，城市內每個點僅且僅被一個消防站覆用Lin

19、g。求解得到：j=84,143。（即消防站應建在84和143交義路口）9000800070006000500040003000200010000942<1432 #32607302731 :112eJ822 29-4口23J66一二6271157158 167 淄193211I255275297260270I28289117J9185516016838204244.48伊424151 .524792 94 995102 11110911312830 131犯§2 ,13或筍涵照2276291298|一5000£69 J268如氐281288平

20、92 i2930If300 物2，3037728024170272,295296-305 306307237257236235251 25351617225 -2282421161"29930410000150004.4問題四：首先，把各個部位對時間的約束轉化為最遠距離約束，即消防站點到其責任 區(qū)內普通火災現(xiàn)場的最遠距離為 5000m,到三個重點部位火災的時間約束，仍然 轉化為最遠距離約束。根據第四問中對普通部位反應時間 5分鐘及重點部位3分鐘的限制，編制算 法得到的最少消防站個數為5yii W I , yi為（0 -1）變量，Vi =1表示在Vi點建立消防站，Yi= 0，否d0點V

21、i到點Vj的最短距離z ziJZj為（0-1）變量，Zj =1表示消防站點Vj服務于點Vimin z =£ yi3 0 7S.t. 、' zij =1 j AZij -yj £0瞄§ £ 5 0 0 0d 103 j Z103 j 3000d123 j Z123 j 一 3000d 277 j Z277 j - 3000求解的模型：min zL、Zij i ± j 3 0 7s.t. w yj =5 j w dijZij < 5 0 0 0 dijZij - 3 0 0 0 Zj -yj -0 3 0 7 .二 Zij -1 j

22、=1同樣用ling。求解得出：j=45, 75, 211, 224, 228 （即消防站應建在第45, 75, 211, 224, 228交又路口）。90008000700060009_.12107_.111432 332630虻F?7?1'4 #650 妄1.634 518 131516174241 .52-47 44 ,48.5000400030002000100067 663749294 攢 8982 9009111 109芾112830 13191-83 18884物107,167 攻193211255275297260270282897典6116 心M14T 一靜37魁2 .

23、13324291梁215嬲硼蹦83一 臀催>24矗447263瓠 2682!132 23423,294825.2456人29W2276 281291 <2984L4J51 169668.184!5_192238l0.241 ,2422魅6,261SS72l77 案2 M：H300 郃02 3032722802137170228296307236235237251 253257I I;49456163785 86 81f'1299304._30500500010000150004.5問題五：根據查閱的資料得到，消防車的速度最小值達到30km/h,最大速度值可達到110km/h

24、，如森林消防車的速度一般為30km/h,機場消防車的速度為 80110km/h，針對本題第五問，我們設置城市消防車的速度v占如而仆，以此為最低值考慮消防車到達火警現(xiàn)場的時間t的影響。由物理學公式有：消防車行駛的距離s=vt，根據國家標準城市消防規(guī)劃 規(guī)劃，消防車從出發(fā)到火警現(xiàn)場的時間不超過5分鐘，對丁某一城市，消防站的轄區(qū)面積一定，即可知消防車達到某一現(xiàn)場距離s是確定的，即得到v與t成反比例關系，進而考慮影響速度的因素：1:道路狀況其中城市道路的彎折度為主要影響因素，記其為h,查閱資料，h計算公式：、若改0寸上匚廣轄區(qū)內任一點到消防站該兩點的最小實際距離道路的彎折度=該兩點的直線距離對丁確定的

25、轄區(qū)內，設可能發(fā)生火災部位的個數為n,轄區(qū)內任一點到消防站的最小實際距離為Si(i =1,2,，n)，直線距離為li(i =1,2,., n)；Si hi = (i =1,2,., n)lin'、' hih = (i =1,2,., n) 則該轄區(qū)平均道路的彎折度n, h為道路的彎折度最終比較量。h越大，道路越彎折，平均速度v越小，s 一定時，消防車到達火警現(xiàn)場的時間越大。2:交通擁堵情況，天氣情況，駕駛員駕車技術等等都會對會通過速度來影 響消防車到達火警現(xiàn)場的時間。5模型的分析本論文針對五個問題，建立了四個模型。第一問的模型考慮了圖上的所有點，而不僅僅是圖上的頂點，對應現(xiàn)實問

26、題， 相當于考慮了城市街道上的所有住戶，而不僅僅是以往問題中的路口上的住戶， 這樣得到的中心點更具有現(xiàn)實意義。第二問所建立的多目標規(guī)劃模型，考慮突發(fā)事件應急救援設施的選址決策目 標時，宜采用多目標方法，并充分體現(xiàn)公共服務設施的公平性和效率性。比一般的單目標規(guī)劃模型更加具有靈活性和綜合性。第三問、第四問建立的都是根據消防站點責任區(qū)內最大行車距離建立的中位 點選址模型，但是此模型要求知道圖中最少需要建立的消防站點數目，故先建立了一個以最少站點數位約束目標函數的優(yōu)化模型，求出需要的最少消防站點數。這兩個模型算法簡潔，結果穩(wěn)定，具有一定可推廣性。6模型的評價優(yōu)點：1.模型本身不存在近似誤差，計算誤差由

27、 Ling。軟件和計算機精度決 定。2. 適用范圍廣，該模型適用于諸如醫(yī)院急救站、巡邏警點等類似公共設施的 規(guī)劃建設，只需將參數或約束條件做相應修改即可。3. 該模型易于推廣普及，僅需一幅城市地圖和相應的坐標信息，便可解決 一類中位選址問題。4. 算法簡單易懂，得到的結果穩(wěn)定性好缺點：1. 假設理想化，沒有考慮到諸多因素如水源的影響，實際問題可能更加復雜 化。2. 只考慮了將消防站建立在交義路口的情況，忽略了消防站可建立在路邊 的情形，所以得到的模型可能不是最優(yōu)的模型。7參考文獻11王正東，數學軟件與數學實驗，北京：科學出版社，2004年【2】 鄧佩，蘇翔，時間約束下的運輸網絡最短路徑研究，

28、機電產品開發(fā)與創(chuàng)新， 第19卷第一期：18-20, 2006年【3】 韓偉一，王錚，Dijkstra算法的一個改進，運籌與管理，第十三卷第6期: 6-10, 2004 年【4】 李德宜，李明，數學建模，北京：科學出版社， 2009年【5】 謝金星，薛毅，優(yōu)化建模與LINDO/LINGO軟件，北京：活華大學出版社,2005 年附錄：第一問代碼(lingo)model:sets:point/1.307/:s,a;links(point,point):d;connect(point,point)/1,2 1,35 2,5 2,21 3,6 3,4 3,13 4,5 4,15 5,16 6,8 6,1

29、8 7,10 7,117,278,11 8,22 9,12 9,14 10,1210,30 11,20 12,2613,18 13,23 14,32 14,33 15,16 15,2516,1717,24 18,29 19,20 19,2820,34 21,24 21,3721,45 22,28 22,29 22,50 23,25 23,2923,4224,25 24,49 25,44 26,3026,33 27,30 27,3127,57 28,34 29,51 30,60 31,34 31,5332,3332,36 33,38 34,54 35,4036,38 36,43 37,3938,

30、46 39,40 39,77 40,79 41,42 41,4742,5243,46 43,67 44,47 44,4844,84 45,49 45,8146,62 47,52 48,49 48,61 49,63 50,5150,5651,52 51,83 52,88 53,5553,57 54,55 54,5654,87 55,64 56,91 57,58 57,68 58,5958,6559,60 59,65 60,62 60,6960,82 61,63 61,7862,66 64,72 65,69 65,70 66,67 66,7167,9268,70 69,74 69,93 70,75

31、71,73 72,75 73,8974,76 75,90 76,98 77,79 77,81 78,8478.85 79,237 80,93 80,96 80,100 81,86 82,89 82,93 83,88 83,91 83,108 84,88 84,11685.86 85,122 86,137 87,90 87,91 87,106 88,115 89,95 90,98 90,99 91,107 92,94 92,11193,100 94,97 94,109 95,97 95,102 96,98 96,104 97,102 98,101 99,101 99,105 100,132101

32、,103 101,110102,113103,104 103,112 104,124105,106106,107106,118 106,120107,108 107,114108,117109,111 109,113 110,112110,118111,128112,121 113,131114,117 114,140115,116115,117 115,138 116,123117,139118,119118,125 118,134119,121 119,127120,126121,129 122,123 123,141124,129124,135125,127 125,143126.146

33、 127,133128,130128,157 129,133 130,131130,158131,132131,167 132,135132,160 133,142134,144136,137 136,148 138,139138,141139,147139,149 140,145140.146 140,152141,148141,215 142,143 143,144143,156144,146144,153 145,147145,150 146,152147,154149,151 149,154 149,169150,152150,154151,166 152,155153,163 153

34、,201154,171155,171 156,162 156,183157,158157,193158,167 159,160159,174 160,161160,178161,162 162,179 163,164164,172165,169165,173 166,173167,211 168,170168,192169,192 169,194 171,185171,172172,184174,180 174,186175,179 175,182175,188176,177 176,180 176,187177,178177,199178,181 178,191179.189 181,182

35、181,190182,200 183,196 184,214185,194186,187186,198 187,195188.189 189,205190,191190,204 191,208 193,211193,255194,210194,213 194,214194,238 195,198195,199196,206 196,209 197,203197,215198,211198,218 199,208200,204 200,209200,219201,206 201,207 202,207202,214202,216203,210 203,220204,208 205,209205,

36、254206,243 207,222 208,212209,221210,225211,260 212,234213,223 214,216215,226215,228 216,222 216,224217,218217,232218,231 219,221219,233 220,226 220,227 221,229 222,230 223,224 224,239 224,244 225,227 226,242228,251 229,233 230,250 231,232 231,259 232,234 232,246 233,234 233,248 234,247235,236 235,2

37、37 236,251 237,257 238,240 238,244 238,265 239,252 240,241 240,266241,242 241,261 242,272 243,249 243,263 244,268 245,246 245,256 246,247 247,248247,258 249,250 250,252 250,264 251,253 251,305 252,269 253,257 253,295 254,258255,260 255,275 256,258 256,259 257,296 258,276 260,270 261,266 261,280 262,

38、263262,267 264,271 265,266 265,277 267,281 268,269 268,279 269,273 270,287 271,284272.304 273,274 274,278 275,297 276,281 276,291 277,279 277,280 277,285 278,279278,290 279,286 280,299 282,283 282,284 282,288 283,293 285,286 285,294 286,290287,289 288,292 289,291 290,294 290,302 291,292 291,298 292,

39、300 293,301 294,303295,296 295,306 296,307 297,298 298,300 299,303 299,304 300,301 301,302 302,303304.305 305,306 306,307/:b,x;endsetsdata:桌面 D1.xlsx','distance');enddatamin=dis;for(point(i):s(i)>sum(connect(p,q):d(p,i)*b(p,q)+x(p,q)-100000*a(i);for(point(i):s(i)>sum(connect(p,q):d(q,i)*b(p,q)+d(p,q)*b(p,q)-x(p,q)-100000*(1-a(i);for(connect(i,j):x(i,j)<d(i,j)*b(i,j);for(connect(i,j):2*dis>s(i)+s(j)+d(i,j);for(point:bin(a);for(connect:bin(b);sum(connect(i,j):b(i,j)=1;end第二問代碼：model:sets:point/1.307/:w,u,y;lin