1、精選優質文檔-傾情為你奉上城市應急系統優化選址的模型及其算法隊伍編號：046隊員： 王天成 代川 李黎摘要本文針對城市應急系統選址問題，結合2中位點理論模型、圖論的相關理論和優化方法，在不同的約束條件下，建立了城市應急系統優化選址模型，并且給出了多種條件下最優方案的求解算法。主要工作如下:問題一：我們通過年度、月、以及每個街區等不同的維度來找出事件發生的規律性，挖掘出其發生的規律性如下：每年中每個街區發生應急事件次數主要集中在1、11、12月份；1-8號街區在10年中發生應急事件次數的波動較小；用50個街區00年到09年平均的應急事件次數，通過系統.聚類，發現50個街區可以聚類分成5類。分析過

2、程中，我們發現過去十年的應急事件發生總數原始數據呈現S形，因此我們建立了灰色Verhulst預測模型，對不確定性的應急事件對2010年的預測，為問題二的數據來源做準備。問題二：我們通過建立笛卡爾直角坐標系給各個街區、街道、街角定位，將總響應時間轉化為權距離，并結合圖論，使用了一種獨立的最短路算法，求得每個需求點和應急服務地點在坐標系內的最短距離。通過matlab編程求出的結果為第16號和44號應急服務供給點，最終服務店定位在8、9、13、14號街區的街角處，另一個定位在31、32、36、37號街區的街角處。問題三：對于問題三，我們采取的策略跟問題二基本一致，我們首先假設兩個障礙區中道路可以通過

3、，用問題二的算法，求解得到了一組備選點分別與第8號備選點（即已確定的1、2、6、7號街區之間的街角處）的組合方案，然后考慮L型和長條形的障礙區域的影響，對這些組合的總響應時間進行調整。最后通過matlab計算的方式確定了另外一個點的位置在45號應急設備點，即第32、33、37、38號街區之間的街角處。問題四：問題四跟問題二的問題不同點在于問題二不考慮障礙的影響，而問題四考慮了障礙的影響，但是我們發現，障礙的影響范圍是有限的，只對部分的應急設施點產生障礙，因此，我們在問題二和三結合的基礎上，求得了與問題二相同的答案，即在第16號和44號應急設施點，原因是由于最佳的兩個組合點沒有受到障礙區域的影響

4、。 問題五：對于問題五，我們首先證明了無向圖的頂點是最優應急設施供給點的備擇點，并且優于至少不劣于相應邊的內點。然后順利的把應急設施的備選點轉化到了頂點（也就是街角處）。然后，計算出所有應急設施供應點的組合到所有街區的最短權距離即總響應時間。通過matlab編程實現求解過程，最終的應急設施的選擇點在16、45號應急設施備選點，16號選址點在8、9、13、14號街區的中心街角處，45號選址點在32、33、37、38號街區中心街角處。 關鍵字 灰色verhulst預測 受限制選址優化 優化算法 2-中位問題 應急系統選址問題第一部分 問題重述 對社會各種突發事件進行處理的應急系統中，應急服務設施的

5、選址涉及經濟、技術、社會、安全等多方面因素。因此在應急服務設施的選址上，如何建立一個滿足約束條件的優化模型，成為實際問題的重中之重。 從本文的要求來看，主要是討論在不同的約束條件下，多個服務點選址的問題。題目中給出了50個街區，及其相互之間的道路圖，而且在城市中間設定了兩個障礙區域，并且應急車輛駛過一條垂直向的街區平均要花20秒，而通過一條水平向的街區平均要花30秒。附錄中給出了過去10年間每個街區每月發生應急事件的次數，因此，為了提高該城市突發事件的處理能力而且，在考慮未來10年的應急事件發生的基礎上，欲建立兩個應急服務設施，考察應急服務設施的選址，要分別對如下問題進行探討：1、分析各街區應

6、急事件發生的規律；2、假定應急需求集中在每個街道的中心，而應急設施位于街角處，并假設兩個障礙區域中道路可以通過。為使總的響應時間最少，確定這兩個應急設施的位置。3、假定應急需求集中在每個街道的中心，而應急設施位于街角處，并假設兩個障礙區域中道路不能通過。若一個應急設施的位置已經確定位于1、2、6、7的街角處。為使總的響應時間最少，確定另一個應急設施的位置。4、第3問中若兩個應急設施的位置均未確定，試確定這兩個應急設施的位置。5、若第4問中，將假定改為：假定需求是沿包圍每個街區的街道上均勻分布的，而應急設施可位于街道的任何地方。問題又如何求解？第二部分 基本假設 1. 題目中附錄所給的數據真實可

7、靠 2. 假設每個街區的中心存在一個點，作為臨時需求中轉點，便于求出需求點與應急供給點的最短距離； 3. 假設每個街區的中心點到街區周圍的街道中需求點的距離，垂直向的距離為10，水平向的的距離為15。 4. 應急設施點設定的原則只考慮其未來發生的次數，不考慮應急事件的嚴重程度。 5. 在應急車輛進行救助的過程中，不存在道路擁堵的情況。 6. 對于障礙區，不能通過障礙區內部的的街道，但是可以通過障礙區外圍的街道。第三部分 符號說明符號含義表示原始數據列表示的緊鄰均值數列均方差比值，用于檢驗verhulst預測模型的精確度0-1變量，表示第j個點是否被選為應急設施點0-1變量，表示第j號應急設施點

8、是否服務于第i個街區無向網絡全圖表示第i個街區的編號，應急服務供給點的編號，表示第i個街區中心點的坐標表示第j個應急設施供給點的坐標第i個街區的需求權重，它是未來10年平均每年發生應急事件的次數表示第j個服務點到第i個街區的距離總系統響應時間A是最短路矩陣，B是最小值矩陣，W是權重矩陣受障礙影響的應急服務點的集合表示由于障礙區域而導致的響應時間的增加量受障礙區域影響，街區最短距離路徑變化的集合第四部分 問題分析 本問題涉及到的是關于城市應急系統的選址問題，面對城市中突發事件的的應急處理，對應急服務設施進行選址優化。由于垂直向街道和水平向的街道花費的時間不一樣，因此，為了使得總的響應時間最少，如

9、何選擇應急服務設施的位置。4.1 基本思路題目中給出了過去十年中每個街區每個月發生應急事件的次數，但是由于突發時間的發生是具有不確定性的，因此就加大了從這些數據中挖掘出規律性的難度；找到了每個街區每月或者每年發生應急事件的次數后，由于題目中要求是在考慮未來10年應急事件發生的基礎上來建立服務站，所以要對未來10年的數據進行準確的預測，方法和工具的選擇也是難點；預測出了未來的數據后，就把這個數據的平均值作為每個街區的需求權重，這對確定應急設施的位置有重大的約束作用；后面的問題是如何在考慮L型和長條形狀的障礙區域的基礎上，分別選址。服務點選址的原則有：每個服務店都要覆蓋到一部分需求點；使得總的響應

10、時間最少；服務點只能位于街角處；基于上面的難點與重點原則，我們運用灰色系統理論里面的Verhulst模型對2010年的數據進行預測，并且將結果作為每個街區的需求權；在后面的四個問題中，由于確定了是建設2個應急服務設施。只是限制的條件不同，因此我們利用建立坐標系的方法簡化了問題。4.2 具體分析 對于問題一：先通過excel、spss進行數據統計觀察，然后從三個維度進行考察過去十年每個街區之間發生應急事件的規律性。然后通過兩種不同的角度的聚類找出了50個街區中，具有某些相似特征的街區。在統計的過程中，我們發現2000到2009之間每個街區之間發生應急事件的綜合呈現S型增長，于是就用到了灰色ver

11、hulst理論對2010年的數據進行預測。 對于問題二、三、四，我們發現其基本的模型是一致的，只是在求解算法上的細節差異，對于問題二，我們先求出每個應急設施服務備選點與街區需求之間的一個最短距離矩陣，然后得到最小距離矩陣，通過與權值矩陣的成績，得到了使得總響應時間最短的兩個設施點的組合，即為最優。但是對于問題三來說，由于其中一個點是確定的，在第8號設施點，因此我們只是需要在剩下的65個點中一一與8號設施點作為組合，然后把每種組合按照總響應時間的順序排名。最后做受障礙區影響的組合的調整，我們發現，最優的組合并沒有收到障礙區的影響。對于問題四，也是先假設沒有障礙區，然后對受障礙區影響的某些點進行總

12、距離的調整，最后找出最優解。 對于問題五，我們首先利用定理證明了在頂點是最優應急設施供給點的備擇點，并且優于至少不劣于相應邊的內點。然后就把設施點轉化到了原來問題二、三四中的街角處。最后通過計算機模擬的按照均勻分布的特征在每個街區周圍進行需求點的模擬，最終通過一種搜索式的算法得到最優解。第五部分 模型建立與求解5.1 問題一的模型及其求解5.1.1 模型準備對于問題一，從過去10年的數據中找出規律，我們主要從4個維度進行考察，五個維度分別是：50個街區在不同年份應急事件發生的次數頻率；不同年份的不同月份，應急事件發生的次數統計；應急事件發生的頻率在過去10年之間的變化趨勢；對不同的街區進行聚類

13、分析，考察各個街區發生應急事件的規律；對每個街區未來的應急事件進行預測。5.1.2 數據挖掘與規律探索 （一）50個街區在不同年份應急事件發生的穩定性 我們對該地所有的50個街區在過去10年發生應急事件次數上，進行了統計，統計的結果如下： 從上圖可知，1-8號街區在十年間發生應急時間的頻率比較低，而且波動幅度比較小，說明該地比較穩定，除此之外，8號街區，14號街區，19號，41號47號等在不同的年份波動幅度比較大。 （二）過去10年不同月份應急事件發生的頻率統計 通過數據觀察，我們還發現在不同的年份幾乎應急事件的高發頻度總是出現在1,11,12月三個月份。具體的統計分析圖如下： 由統計分析圖可

14、以看到，每年的1月，11月，12月發生應急事件的頻率高于其他月份，而且在10年間一直保持幾乎相同的態勢。 （三）過去十年應急事件發生總數的變化趨勢 通過對過去10年每年發生應急事件次數的加總統計，我們發現所有地區加總起來，隨著時間增加，應急事件發生的頻率也在逐步升高。 從圖中，可以看到，過去10年發生應急時間的趨勢呈現出一個向上的S型，因此，這滿足了灰色verhulst預測模型的要求。 （四）對50個街區應急事件發生次數的聚類分析 （1）聚類模型建立而對街區進行分類的主要衡量指標是每個街區每年發生應急次數的距離分析，這里的距離，我們選擇的是歐氏距離平方，其介紹如下： 歐氏距離平方是每個老師打分

15、變量值之差的平方和，在上面的公式中，k是樣本的數量，是表示第一個樣本在第i個變量上的取值，是表示第二個樣本在第i個變量上的取值。 最終得到歐氏距離的距離矩陣： （2）聚類分析的結果 我們把所有的50個街區每年發生次數通過聚類發現，一共可以分成五類，聚類的結果如下： 街區編號聚類結果說明第一類1 、2、3、4、5、6、7、9、10、11、13、16、20、24、25、36、37、39、40、44、45、48、49、50這一類街區發生應急事件在不同的年份中發生的次數少，均在（300,700）之間波動第二類8、14、15、19、21、22、23、26、27、28、31、32、33、這一類街區內部發生

16、應急時間的絕對次數很高，并且穩定性較弱第三類29、30、34、35這一類街區年度的變化趨勢不明顯，但是其絕對次數也較低第四類41、42、46、47這一類街區內部發生應急時間的絕對次數很高，并且穩定性較強第五類12、17、18、38、43障礙區域 此外我們還對10年的總次數進行了聚類，聚類的結果如下： 街區編號聚類結果說明第一類1217183843障礙區第二類30343529低第三類1339444452925349611750375204010481361624較低第四類2221262328313233中第五類158191427較高第六類47464142高 由此可見，上述中每一類都有各自的特點。

17、因此這也是該街區發生應急事件的規律性。5.1.3 灰色Verhulst預測模型 （一）模型準備我們要對一個不確定性的應急時間發生的次數進行預測，而且是以時間序列預測，因此，我們先對2000年-2009年的應急事件發生次數進行曲線估計。估計如圖：該圖顯示：2000年-2009年的應急事件發生次數呈S型分布，因此使用于用灰色verhulst預測模型對之后的10年進行預測。（2） 模型建立 設為原始序列，為的一次累加生成序列，即為：， 并且 為的緊鄰均值生成序列，其滿足：， 因此，我們稱為灰色verhulst預測模型，其中，a，b均為參數，又有： 為灰色verhulst預測模型的白化方程，t為時間。

18、 灰色verhulst預測模型具有如下定理： NO.1 設灰色verhulst預測模型如上所述，若為參考數列，且則參數列的最小二乘法估計滿足： NO.2 設灰色verhulst預測模型如上所述，則白化方程的解（時間相應函數）為： 灰色verhulst預測模型的時間響應序列為： 取為，則上式變為： 其中，累減還原式為： 上述就是灰色verhulst預測模型的模型部分，但是在模型部分后，還有一部分是對模型精確度的檢驗部分，在灰色模型部分一共有四種檢驗精確度的方法，我們選取了均方差比合格模型對灰色verhulst預測的精確度檢驗。對于均方差合格模型，設原始序列為：與其對應的灰色預測的序列為： 因此殘

19、差序列為： 則的均值，方差分別是：的均值、方差分別是： 均方差比值，對于給定的，當時即均方差比合格。5.1.4 預測模型求解 對于上面的模型，我們通過matlab編程進行求解，最后還對預測的結果進行了均方差比值的合格精度檢驗。Matlab源代碼見附錄一 灰色verhulst預測模型采取的算法步驟如下： 第一步：設初始值i=1,從輸入矩陣A中逐步提取出第i行每個街區10年內發生的次數作為初始原始數據列； 第二步：對初始數據列做一次累加生成，變成，轉入第三步； 第三步：對累加生成的數列生成一個緊鄰均值數列，轉入第四步； 第四步：生成B矩陣，為n-1行2列，保持緊鄰均值數列，生成一個Y矩陣，用于保存

20、原始序列； 第五步：對參數列中的參數a和b，通過最小二乘，進行求解，轉入第六步； 第六步：把參數帶入verhulst模型中，并且載入輸入的預測的時間長度，保持預測值，并且i=i+1進入第七步; 第七步：判斷i是否大于66，如果否，那么返回第一步；如果是，則進入第八步； 第八步：記錄每個i產生的預測值，輸出預測值 第九步：對預測的結果做精確性評價，計算均方差比值和模擬的精確度； 第十步：返回預測值，以及均方差值和精確度值，算法結束。5.1.5 模型結果評述對于該模型的返回結果，由于我們考慮到下文中需要的是每個街區的應急事件的發生次數，而為應急服務點的選址提供依據，因此我們返回的結果是預測的10年

21、的發生次數，作為選址的依據，返回的結果是：街區編號10年發生應急次數街區編號10年發生應急次數街區編號10年發生應急次數街區編號10年發生應急次數1690.714950.1342271676.940447.17552495.983115977.5281076.7411260.63516.625916562.200629160.6764421178.14494.270217030137.8134305368.705180311200.444497.52746443.5236191012.632921.845411.11967516.058720536.5343331150.84613208922

22、.753821880.234140.6163471253.19410.857222880.235123.886148552.816610525.3876231030.536546.767949458.212911608.725124571.375237513.685550718.612025404.773838013403.860226954.239390.5654而對上述預測結果的檢驗結果如下：編號精確 度均方差比值編號精確 度均方差比值編號精確 度均方差比值編號精確 度均方差比值10.90.39 140.90.61 2710.18 400.80.57 20.90.46 1510.26 28

23、10.33 410.80.61 30.90.55 160.70.57 290.70.57 420.80.45 40.80.63 1700.00 300.60.63 4300.00 510.36 1800.00 3110.29 440.90.57 60.90.47 190.90.63 320.90.47 450.70.60 70.90.56 200.80.51 3310.30 460.90.52 80.80.54 2110.30 340.90.34 470.90.57 90.80.53 2210.30 350.80.51 480.60.55 1010.45 2310.20 360.80.60 4

24、90.80.73 110.90.38 240.80.64 370.70.57 5010.33 1200.00 250.90.53 3800.00 130.90.64 260.90.42 3910.18 在預測結果里面我們發現所有的預測結果的精確度都在0.6以上，而且大部分都大于0.8（除障礙區點），均方差比值也大都在0.65以下，說明我們的這個預測模型是合格的，所預測的值是比較可靠的5.2 問題二的模型及其求解 5.2.1 模型準備（一）對題設的理解題目中假定應急需求中心在每個街道的中心，我們的理解是應急需求在每個街區的四個方向的街道的中心，也就是說每個街區都有四個需求點，比如說：對于街區1，

25、不論其街區內部什么地點發生應急事件，只要應急車輛趕到任何一個需求點都可以，只要其響應時間最短即可。另外，對于應急設施的位置問題，有兩個決定因素，第一個是應急設施與應急需求點之間的距離，第二個是每個街區的應急需求權重。我們的模型中，將二者的乘積即總應急需求權距離作為模型的目標函數。 （二）定義 對于問題二，我們采用圖論模型描述待確定的應急服務設施的地點及其約束條件，我們給出如下的定義： 給定一個無向連續網絡,其中，為G的點集，為連接G各點間的弧集，為頂點的權重，是弧長，如果弧連接頂點和那么弧氣可以表示成，可以表示成，對于G中的任何兩個點代表連接點x和點y的最短路徑，因此具有以下性質： 設為網絡中

26、的j個待確定的應急服務設施點集，定義如下： 網絡中的一個頂點到點集的距離為： 5.2.2 模型建立 （一）建立笛卡爾直角坐標系在這個問題上，我們把50個街區和道路放入直角坐標系中，該坐標系帶箭頭方向為正方向，在這個坐標體系中，應急供應點，應急事件的需求點，以及每個街區的中心點都能一一對應一個坐標。具體的坐標如下圖：15009030601201008060402016018020012014023456781109111266第j個服務供給點 j圖例應急服務供給點備選點i第i個街區的中心點應急事件需求點 （二）建立應急服務點與街區中心點之間的對應關系 從上面的直角坐標系可以看到，由于每個街區的長

27、和寬是固定的，每個街區的垂直向的街道的響應時間為20秒，水平向的街道的響應時間為30秒。而且，供給點和需求點都能找到對應的坐標；下面給出二者之間的對應關系： 由于第i個街區的中心點的坐標為，因此： 同理，可以得到第j個應急服務設施的坐標： 建立這樣的一一對應的關系，主要是為了能夠便于計算66個可能設立應急設施的點與任何一個街區之間的最短距離，下面我們舉一個例子，通過應急設施的點的坐標與街區中心的坐標之間的互換。 例如：第28個應急設施供給點的坐標為：；第2個街區中心點的坐標為，又如：第12個應急設施供給點的坐標為，第25個街區中心店的坐標為. （三）最短路矩陣、最小值矩陣、權重矩陣 我們對最短

28、路矩陣定義如下：它是集合了所有可能的應急設施供給點與供給需求點（每個街區）之間的最短距離，用符號表示。 最短路矩陣里面的每一個元素的數值是第j個應急設施供給點到第i個街區需求點的最短距離，其計算公式如下： 如下圖所示：下圖描繪了第28個應急設施供給點到2號街區的最短距離的計算過程，這里，我們解釋為什么要減去15，因為我們前面是以每個街區的中心點與每個應急設施點的距離，我們又發現應急設施供給點到某個街區之間的最短距離與應急設施點到街區中心點的最短距離是等價的,而二者之間正好相差15。15009030601201008060402016018020012014023456781109111266第

29、j個服務供給點 j圖例應急服務供給點i第i個街區的中心點應急事件需求點（45,10）（90,80）最小值矩陣：它記錄的是對于己經求出的最短路矩陣，當以i，j為組合時，我們取第i行和第j行的元素組成一個250的矩陣，比較同列元素，取最小值，并將另一個值賦為0值，若一列的兩個元素相同，同時保留，所得矩陣稱為最小值矩陣。用B表示。起初，最小值矩陣如下：然后，取每一列的最小值進行變換： 權重矩陣：權重矩陣是記錄每一個街區在未來10年的突發事件發生的頻率次數，該矩陣的具體數值，我們通過灰色系統預測方法預測得到，用表示。(4) 約束條件在本問題中，約束條件大致有如下： （1）保證每個需求點有且僅由一個設施

30、點為其服務則需滿足：（2） 限制所選的中位數為2個則需滿足： （3） 兩個0-1變量在上面的分析中，。（4） 模型建立 通過以上的分析，我們可以建立以下的數學模型滿足一定條件的優化問題： 或者 約束條件如下： 5.2.3 模型求解 對于該規劃問題，由于約束條件太離散，并不能采取一般的規劃問題算法求解，這里，我們采取了一種搜索式的算法，并且利用matlab實現求解。具體的matlab程序見附錄二 該問題是算法步驟如下： 第一步：首先用計算出任一應急設施點與任一街區需求點之間的最短距離，其實現步驟如下： Step1:對變量i和j賦值，i為1-66之間的數，j為1-50之間的數，用i和j做二重循環，

31、首先對i和j分別賦初始值1和1； Step2:條件判斷，對于i和j的不同取值進行判斷，若，且，,并且執行計算最短距離的公式如下：，在滿足該條件時，跳轉到step3; Step3:繼續條件判斷，若，且，, 同樣計算最短距離，若以上條件均不滿足，則轉入step4; Step4:若以上條件都不滿足，則直接執行以最短距離公式的計算；并且將以上結果全部保存在A矩陣中；轉入step5; Step5:對循環變量重新賦值，跳轉回step1; Step6:執行循環體直到i=66，j=50,保存最短距離矩陣A;. Step7:跳轉到第二步；第二步：從第一步中得到的的最短距離矩陣A中求出每兩點組合之間的最小值矩陣。

32、執行下面的步驟： Step9:取初始值i和j,分別滿足,并且,從最短距離矩陣A中提取第i行和第j行組合成初始最小值矩陣B:，轉入Step10; Step10:對初始最小值矩陣進行變換，取兩行中最小的數值記錄到最小值矩陣中去：，得到最小值矩陣后，轉入第三步；第三步：通過最小值矩陣B與權重矩陣W的乘積計算出總的響應時間，轉入第四步；第四步：選出使得總響應時間最小的組合作為2-中位，即求得最優解，算法結束。 5.2.4 模型結果評述通過執行附錄二中的matlab程序，可以得到為了使得總的系統響應時間最少，這兩個應急設施的位置分別位于第16號和44號應急服務供給點，第16號應急服務供給點位于第8、9、

33、13、14號街區之間的街角處；第44號應急服務供給點位于31、32、36、37號街區的街角處。11120第j個服務供給點 903060120j80604020圖例23456781109150i第i個街區的中心點可供選擇應急服務供給點140120180160應急事件需求點10020066兩個服務設施站的服務分界線確定的應急設施的位置交叉服務區域 如上圖所示：圖中帶星型的點即為我們確定的應急服務的點的地址，另外黑色線是兩個應急服務站的輻射范圍的分界線，圖中陰影部分是兩個應急服務點的交叉服務店，兩個服務店到其的響應時間相等。5.3 問題三的模型及其求解5.3.1 模型準備在問題三里面，由于考慮了障礙

34、的存在，就使得某些可以直達的區域必須繞道通行，這樣就增加了從應急服務點到需求點街區之間的響應時間，為了充分的考慮障礙的存在，下面我們給出幾個定義及其說明：受障礙影響的應急設施備選點的點集:由于障礙的影響范圍有限，只影響到了其中的一部分應急設施備選點，下面給出具體的應急設施點的約束范圍： 即是下圖中標注的部分為受障礙影響的供給服務集合點集： 由于障礙的存在而導致第j個設施點到某些街區的響應時間增加，那么我們把這些街區放入一個集合中。5.3.2 模型建立 真個模型的步驟跟問題二的步驟基本一致，因此得出的模型也跟問題二有相似之處，整個問題我們把他當成一個規劃問題，有如下的約束條件是對應急設施備選點的

35、約束和備選點與需求點之間的關系，以及他們之間的運算規則約束 （一）約束條件（1）保證每個需求點有且僅由一個設施點為其服務 則需滿足： 其中， （2）限制所選的中位數為1個，因為已經確立了一個應急設施點的位置，因此只需要確定另一個的位置即可： 則需滿足： ，其中：（3） 限制每個需求點只能由已選的設施點服務 則需滿足： 由于第八個應急服務點已經確立，因此8必須在j中體現。（二）目標函數 我們的目標函數是需要使得總的響應時間最少，則建立如下的目標函數： 其中 （三）最終模型 綜上分析，得到如下的規劃模型： 5.3.3 模型求解 對于以上的建立的模型，我們依然采取以下的算法流程，算法實現方式是用ma

36、tlab計算再加上后期的調整實現。 算法流程圖如下： 第一步算法：求最短距離矩陣A開始初值 i=1,j=1mod(i,5)0且mod(i,5)0YNmod(i,5)=0且mod(i,5)=0YN計算,計算,計算,計算，i=i+1,j=j+1i<=50,且j<=66Y最短距離矩陣AN 第二步算法：計算最小值矩陣B以及最少響應時間輸入A賦初值i=1,j=8j=8?N提取第j行元素與A中的第八行組成一個矩陣Z(2行50列)Y提取Z中每一列中最小元素，保存到新的B中i<=66?Y更新B,得到最小距離矩陣輸入權重矩陣W響應時間TN 第三步算法：對響應時間進行排名，并且提取出對應的應急設

37、施點j。 第四步算法：計算考慮障礙物對距離的影響調整設施點的位置。 對于第四步的調整計算部分，我們給出如下的計算規則： 首先從提取的排名的序列中選擇在沒有障礙的條件假設下，使得總的響應時間最短的應急設施點，進行如下步驟： Step1:首先檢查該點是否在受障礙影響的點集S內，如果在點集S內，則執行step2,如果沒有在S內，就不做處理；Step2:從街道圖中找出存在障礙的情況下，障礙會導致該設施點到某些街區的需求點的路徑發生變化，我們把這些街區導入到一個集合中，然后分別手動計算出該設施點到每一個街區的實際最短距離（響應時間），然后又手動計算出第8點到這些受影響的設施點的距離，對比二者的距離。St

38、ep3:找出考慮了障礙影響后導致的響應時間的增加后仍然使得響應時間最少的設施點。則找到了設施點。5.3.4 模型結果的評述 根據上述的算法，得到的最終的結果是第45個應急設施點，即在32、33、37、38號街區中間的街角處。090301208060402060150140120180160100200確定的應急設施的位置 如下圖所示： 5.4 問題四的模型及其求解 5.4.1 模型準備 與問題三一樣，我們依然引入受障礙影響的應急設施備選點的點擊S: 由于障礙的影響范圍有限，只影響到了其中的一部分應急設施備選點，下面給出具體的應急設施點的約束范圍： 5.4.2 模型建立 與前面的問題二模型一樣，

39、問題四的模型沒有發生變化，只是需要加入一個檢驗的過程。 建立的模型如下： 或者 5.4.3 模型求解 對于這個問題，我們的求解算法跟問題三的也類似，題目的求解采用matlab進行編程求解，其具體的算法步驟如下： Step1: 計算出第j個應急設施的備選點到第i個街區之間的距離，并且把結果保存在最短距離矩陣A中，并執行step2。 Step2: 從A中提取任意的兩行，然后對每一列的數據進行比較，選擇最小值保存到最小值矩陣B中，執行step3。 Step3: 用最小值矩陣B乘以權值矩陣，得到最終的響應時間，逐步尋找出兩個組合使得總響應時間最短。并且同時按照總響應時間的大小對選址組合進行排名，并且把

40、這些組合計入一個二維矩陣C中，轉入step4; Step4: 對矩陣C中的組合的每個點與受障礙影響的應急服務設施點集S中進行檢驗，并且檢驗的順序從排名高低依次進行。如果矩陣C中的組合點均沒有在S中，那么該組合即為最優。如果C中有元素在集合S中，那么進入step5。 Step5:如果C中和S中有相同的元素，比如，第j個應急點，那么考慮到障礙的影響，就提取出第j個應急設施備選點。然后計算出由于障礙的產生而增加的響應時間，加入到總響應時間T中，更新后的時間如果低于排名次之的點，那么該組合就達到了最優，如果不是，則轉入step6; Step6:如果更新后的排名高于排名次之的點，那么繼續重復執行step

41、5,逐步依次執行，直到找出最優解。5.4.4 模型結果評述通過問題四的matlab程序，得到的結果如下（我們截取部分組合）：組合一組合二組合三組合四組合五16，4450， 2245，16 44 ，2250, 16而受障礙影響的應急選址點集S:集合受障礙影響選址的點S19,20,21,22,23,24,26,27,32,33,38,39,44,45,50,51,55,56,57,58,59,60,62,63可以發現，使得總響應時間最少的組合為（16,44），而這兩個點均沒有被障礙影響，所以，問題四的最終解跟問題二是一樣的，兩個應急服務店分別為第16個和第44個，第16個點為8、9、13、14號街

42、區中間的街角處。確定的應急設施的位置 如下圖所示：5.5 問題五的模型及其求解5.5.1 模型準備 定義設表示圖個G中邊上的f一點到所有頂點的最短距離之和，即 在所有邊的f 一點中，使得取最小值的那個點，稱為圖G的絕對中位點，記為，有 對于尋找圖G 的絕對中位點，有一個重要定理，這里稱之為絕對中位點定理： 定理1 在無向網絡選址問題中，至少有一個頂點是絕對中位點。 為了證明定理1，我們先引入凹函數的概念及一個定理： 對于一個函數，如果定義域U 中的任意兩點，如果均成立，則稱函數為凹函數。 引理1 如果凹函數的定義域為有一維有限連續閉區域，那么在其端點處取得最小值。 不妨設的定義域為，設，定義域

43、內任意一點x 總可以表示為，由凹函數的定義可知：顯然引理1 成立。下面簡單地對定理1 做一證明。證明: 對于無向圖，由上述內容可知,若將f 看作自變量, 則 可以看作是f 的函數,其圖像只可能是圖1 所示的3 種情況之一： 圖一 的圖像 可見，在以上3 種情況中函數均是凹函數，由于凹函數的非負線性組合仍是凹函數，故也是凹函數，由引理1 可知在頂點處取得最小值。 得證。 由此可以得出結論：無向圖的頂點是絕對中位點的備擇點，并且優于至少不劣于相應邊的內點。5.5.2 模型建立 由于前面已經證明了當應急設施點位于街道任何一個點的時候，要確定的兩個應急設施點的最優點應該位于頂點上，因此，這個問題就大大

44、簡化了，原來的問題是供給點與需求點都不固定，現在明確了應急設施點在頂點上。因此，我們采用了模擬取點的方法，取點的規則來處理應急需求沿每個街區的街道上均勻分布的問題，對于每個街區，我們模擬取點的個數為每個街區的需求權數，最終，我們建立了如下的數學模型： 其中，是第i個街區的需求權重，是第1-66應急設施備選點中的任意兩個店，表示 的是第i個街區周圍均勻分布的p個需求點，5.5.3 模型求解算法對于這個問題的求解，我們采用如下的算法步驟：Step1：輸入50個街區在預測年度中的應急需求權數據的數組cishu，給j1、j2賦初值為1；跳入step2；Step2：變量j1=j1+1，如果j1不大于66

45、，跳到step3；否則進入step8；Step3：變量j2=j2+1，如果j2不大于66且j2不等于j1，跳到step4；否則，情況一：如果j2=j1且j1不大于66，重新進入step3.情況二：如果j2大于66且j2不等于j1，跳到step2；Step4：變量i=i+1，如果i不大于50，跳到step4，否則跳到step2；Step5：變量p=p+1，如果p不大于fix(cishu(j)/10)，跳到step5，否則跳到step3；Step6：用均勻分布隨機函數unifrnd函數模擬出第i個街區的位置，利用位置坐標計算出j1、j2到第i個街區的距離，分別為j1i和j2i；跳到step6；St

46、ep7：將j1i和j2i中較小的數加到sum（j1，j2）中。跳到step4；Step8：找到sum矩陣中非零的最小值所在的位置（j1，j2），跳入step9；Step9：重復進行以上step1到step8總共100次然后進入step10；Step10：按出現的頻數從大到小將100次結果中的組合（j1，j2）排序，這些組合是要尋找的最優應急供應點的備選點。進入step11；Step11：對排序后的（j1，j2）逐個進行檢驗。檢驗過程是，計算j1、j2到50個街區的最短距離。跳到step12；Step12：如果j1、j2到50個街區的最短距離等于在無障礙情況下j1、j2到50個街區的最短距離，跳

47、到step13，否則，將這個距離去替換無障礙情況的距離，跳到step11；Step13：找出并輸出已經檢驗過的所有組合（j1，j2）中j1、j2到50個街區的總距離最小的組合；Step14；根據每個組合采取問題三種最后的檢驗步驟好原則，進行，知道求得最優解，算法結束。5.5.4 模型結果及其評述 通過上面的算法步驟，最后我們得出了最終的應急設施的選擇點在16、45號應急設施備選點，16號選址點在8、9、13、14號街區的中心街角處，45號選址點在32、33、37、38號街區中心街角處。 如下圖所示：090301208060402060150140120180160100200確定的應急設施的位

48、置 第六部分 模型的評價與改進 可以看到，在問題2、3、4、5中，其實模型的本質是一樣的，只是有個別的細微的約束條件不一樣，而且在考慮障礙的時候，我們對應急設施備選點的檢測缺乏程式化的準則，而且這個步驟也沒有在前面的模型中體現出，考慮到受障礙區域影響后結果的調整，因此，我們把前面的模型加入這個過程，主要針對的是第3、4、5個問題，調整過程我們考慮一下幾個方面。 （1）考慮了受障礙影響的時候，我們首先引入受障礙影響的應急設施備選點的點集:其中，是第j個應急備選點的橫坐標，是第j個應急設施備選點的縱坐標。由于障礙的影響范圍有限，只影響到了其中的一部分應急設施備選點，下面給出具體的應急設施點的約束范圍： （2）我們給出一個排序集合，這個集合是記錄最短路矩陣中的某兩個應急設施備選點的組合，該集合的元素為這些所有備選點的組合按照總響應時間排序而得到的，排序集合：其中，指的是最短距離矩陣中的任意兩行，并不是指第一行和第二行。R記錄了任意的兩個應急設施備選組合按照總響應時間進行排序的結果。（3） 當受障礙影響的某個應急設施備選點恰好位于排序集合中，那么這個時候，就需要對排序集合進行調整。調整之