計算機技術在應急設施選址問題上的應用

劉建友，蔣春霞

(廣東理工學院，廣東 肇慶 526020)

人們對各種應急服務的需求變得越來越強烈，如果能迅速地把有效的應急資源分配到事故現場，可以大大減少損失，這就需要有合適的應急救援倉庫和救援設施派遣站點。研究了計算機技術在應急設施選址問題中的應用，展望了未來需要關注的方向，以提供一些參考。

1 應急設施分類

應急設施按照不同方法可以分為不同種類。按照時效性可分為永久應急設施和臨時應急設施。永久應急設施長期存在于固定站點，在緊急情況下迅速開設或啟用并提供應急服務，屬于大規模緊急事件發生前的規劃范疇。臨時應急設施一般是暫時占用，只有當發生非常緊急情況時，有關部門根據緊急形勢分析出在某一地點臨時建立救援點。按照應用領域可以分為應急醫療設施、應急物流設施和防災減災設施三種類型。應急醫療設施主要包括救護車站點、供血站等。應急物流設施主要包括應急倉庫、配送中心等。防災減災設施是指發生災害時，把大批受災群眾轉移到避難所的一些必要設施。

2 應急設施選址模型

選址問題主要有連續型和離散型。連續型是指在事前指定區域內進行任意位置的選擇(即指定的任選)。離散型則是在候選站點選取部分進行選擇(即選再選)。研究針對離散型，利用計算機技術和混合整數線性規劃構建模型，將其分為5個控制因素，即基本選址問題、動態選址問題、隨機選址問題、魯棒選址問題和其他選址問題。

2.1 基本選址問題

基本選址問題有基于覆蓋和基于中值兩種類型。

基于覆蓋的問題有：第一，最大覆蓋問題。它通常是配備設施于一個最大的覆蓋區域，在給定區域內進行選址，方法是根據需求水平的高低對需求點進行重要程度區分。很多文獻中關于救護車選址、救災物資分發中心選址中都選用了這種方法。第二，集合覆蓋問題。它的核心是想盡辦法把覆蓋區域內所有需求點的設施數量最小化，即在滿足需求覆蓋水平的情況下，盡可能讓設施數量或總的選址成本最小。第三，P-中點問題。它是在第二類問題基礎上發展起來的，目的是在滿足覆蓋區域內需求點數量的情況下，讓需求點和與其對應的設施間的最大距離或到達時間最小，把人口分布、經濟狀況、交通及部分關鍵部位等都作為關鍵要素考慮進去。

基于中值的問題是在被選的位置中進行選址，把所需點和設備間用距離或時間進行加權，使其成本最小化，以達到設施選址位置為整個設施系統網絡的中值目標。它包括P-中值問題，即使設施覆蓋的每一個需求點的加權平均距離最小化。固定費用設施選址問題，即使設施建立和服務的總成本最小化。

2.2 動態選址問題

在生活中，任何東西都是隨時間而變化的，如環境、需求、服務成本和效率，因此在選址時要考慮動態問題，必須劃分不同的時間段，每個時間段根據當前的情況來選址，不斷進行調整。可以利用計算機技術建立一個動態確定性模型，總時間為T，每一個時間段為t，候選點的集合M里包含nt個候選站點或候選目標點，進行遷移所花費的成本用ct表示，則時段t內設施遷移到候選點m所花費的運輸成本用ftm(xt，yt)表示，在時段t的設施遷移距離用dt-1，t。建立函數：

制約條件是：

2.3 隨機選址問題

制約條件：

在一些地方應急物流配送中心選址-配送模型充分利用了這種方法，他們把運輸車的超載問題和應急倉庫容積問題也一并納入了不確定因素中。

2.4 魯棒選址問題

它與隨機選址問題相似，它的不確定因素是事前并不知道，同時把不確定性因素通過一定的方法加入不同的離散區域或連續區域來體現其具有松弛性。表達方法如下：I={不確定性因素}，不確定性因素i∈I，Ui={可能的不確定性因素}，在決策變量的向量x下進行的選址成本是fo(x)；建立函數：

minfo(x)

制約條件是：

fi(x,ui)≤0,?ui∈Ui,1≤i≤m

這個函數對于包含不確定參數具有優化作用，在一些國家常用于災后血液供應設施選址上。

2.5 其他選址問題

除了以上幾種常見的選址之外，還有其他幾種常見的類型，如構建最小化 P-嫉妒模型，它的原理是根據用戶對設施服務的滿意水平不同，把區域j內的客戶不滿意度的范圍建立一個從j到p服務設施點的函數。在此基礎上，又出現了最低存活率要求的最小P-嫉妒選址模型，跟原來的最大區別是把“嫉妒”定義由原來的不滿意變為了滿意，所以計算函數也由原來的距離函數變為生還率函數。

3 應急設施選址優化求解

應急設施選址一般有精確算法和非精確算法兩種，精確算法適用于相對簡單的優化問題，一般能找到準確的最優解，但是隨著現場各種復雜情況的出現，精確算法已不能滿足需求，因而產生了非精確算法。

3.1 精確算法

對于一些簡單的選址，應用精確算法快速準確，如分支界限法經常運用于供血設施的魯棒選址模型。擬合動態規劃算法常常用于救護車選址問題。對無容量限制的設施選址問題求解時，運用分支界限法和分支割平面法。隱枚舉-下降算法常用在預防緊急事件上，如應急物流設施選址問題等。

3.2 非精確算法

非精確算法中，最普遍的是經典啟發式算法和新型啟發式算法，而經典啟發式算法又分為緊急搜索法、遺傳算法、模擬退火法、蟻群算法和拉格朗日松弛算法 5 種類型。使用緊急搜索算法可以用樣本的平均近似值去推測各個待選址的目標函數值，實現了快速搜索大規模場景樣本。遺傳算法是利用自然進化過程搜索最優解，在發展中又引入了懲罰種群用來表達已經存在的設施點，在算法運行過程中還加入了變異強度。在大城市藥物分發設施選址中，一般使用模擬退火算法。

運行時如果加入了變鄰域搜索算法等就變成了新型啟發式算法。為了增加算法的尋優性能，在應急倉庫的選址或救護車位置選址中，在給定期限條件的選址問題求解中利用了量子競爭決策算法，同時把進化博弈論中學習和調整的動態演化思想引入到算法中。結果表明，運用這種方法求解公共衛生應急服務設施點選址問題，算法性能有了顯著提高。

兩種求解方法都運用了通用優化軟件，使用了編程語言編制、算法等。將以上算法總結如表1：

表1 優化算法歸類

4 未來研究方向

應急選址方面，因為問題出現的隨機和不確定性，所以選址時要關注動態需求，資源連續性消耗問題。如可以把變量由二元變為多元和連續，方向由水平變為多維度等。

求解過程方面，由于現實中的問題規模越來越大，這就要求優化求解的性能要越來越好，可以利用計算機對現有算法進行并行計算的改進，以達到高速度、高效率的目的。

體系研究方面，可以利用多階段多分辨率迭代計算的方法代替目前的離散選址。選址只是應急體系中的一個問題，選址時要配合其他它問題一起考慮。

應急設施選址問題在滿足應急需要的同時，除了要考慮其本身的動態性和不確定性因素外，還要考慮其與其他配套問題的協調，以開展整體應用場景及標準測試用例的研究。