計算機(jī)技術(shù)在應(yīng)急設(shè)施選址問題上的應(yīng)用

劉建友，蔣春霞

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

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

1 應(yīng)急設(shè)施分類

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

2 應(yīng)急設(shè)施選址模型

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

2.1 基本選址問題

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

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

基于中值的問題是在被選的位置中進(jìn)行選址，把所需點和設(shè)備間用距離或時間進(jìn)行加權(quán)，使其成本最小化，以達(dá)到設(shè)施選址位置為整個設(shè)施系統(tǒng)網(wǎng)絡(luò)的中值目標(biāo)。它包括P-中值問題，即使設(shè)施覆蓋的每一個需求點的加權(quán)平均距離最小化。固定費用設(shè)施選址問題，即使設(shè)施建立和服務(wù)的總成本最小化。

2.2 動態(tài)選址問題

在生活中，任何東西都是隨時間而變化的，如環(huán)境、需求、服務(wù)成本和效率，因此在選址時要考慮動態(tài)問題，必須劃分不同的時間段，每個時間段根據(jù)當(dāng)前的情況來選址，不斷進(jìn)行調(diào)整?？梢岳糜嬎銠C(jī)技術(shù)建立一個動態(tài)確定性模型，總時間為T，每一個時間段為t，候選點的集合M里包含nt個候選站點或候選目標(biāo)點，進(jìn)行遷移所花費的成本用ct表示，則時段t內(nèi)設(shè)施遷移到候選點m所花費的運輸成本用ftm(xt，yt)表示，在時段t的設(shè)施遷移距離用dt-1，t。建立函數(shù)：

制約條件是：

2.3 隨機(jī)選址問題

制約條件：

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

2.4 魯棒選址問題

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

minfo(x)

制約條件是：

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

這個函數(shù)對于包含不確定參數(shù)具有優(yōu)化作用，在一些國家常用于災(zāi)后血液供應(yīng)設(shè)施選址上。

2.5 其他選址問題

除了以上幾種常見的選址之外，還有其他幾種常見的類型，如構(gòu)建最小化 P-嫉妒模型，它的原理是根據(jù)用戶對設(shè)施服務(wù)的滿意水平不同，把區(qū)域j內(nèi)的客戶不滿意度的范圍建立一個從j到p服務(wù)設(shè)施點的函數(shù)。在此基礎(chǔ)上，又出現(xiàn)了最低存活率要求的最小P-嫉妒選址模型，跟原來的最大區(qū)別是把“嫉妒”定義由原來的不滿意變?yōu)榱藵M意，所以計算函數(shù)也由原來的距離函數(shù)變?yōu)樯€率函數(shù)。

3 應(yīng)急設(shè)施選址優(yōu)化求解

應(yīng)急設(shè)施選址一般有精確算法和非精確算法兩種，精確算法適用于相對簡單的優(yōu)化問題，一般能找到準(zhǔn)確的最優(yōu)解，但是隨著現(xiàn)場各種復(fù)雜情況的出現(xiàn)，精確算法已不能滿足需求，因而產(chǎn)生了非精確算法。

3.1 精確算法

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

3.2 非精確算法

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

運行時如果加入了變鄰域搜索算法等就變成了新型啟發(fā)式算法。為了增加算法的尋優(yōu)性能，在應(yīng)急倉庫的選址或救護(hù)車位置選址中，在給定期限條件的選址問題求解中利用了量子競爭決策算法，同時把進(jìn)化博弈論中學(xué)習(xí)和調(diào)整的動態(tài)演化思想引入到算法中。結(jié)果表明，運用這種方法求解公共衛(wèi)生應(yīng)急服務(wù)設(shè)施點選址問題，算法性能有了顯著提高。

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

表1 優(yōu)化算法歸類

4 未來研究方向

應(yīng)急選址方面，因為問題出現(xiàn)的隨機(jī)和不確定性，所以選址時要關(guān)注動態(tài)需求，資源連續(xù)性消耗問題。如可以把變量由二元變?yōu)槎嘣瓦B續(xù)，方向由水平變?yōu)槎嗑S度等。

求解過程方面，由于現(xiàn)實中的問題規(guī)模越來越大，這就要求優(yōu)化求解的性能要越來越好，可以利用計算機(jī)對現(xiàn)有算法進(jìn)行并行計算的改進(jìn)，以達(dá)到高速度、高效率的目的。

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

應(yīng)急設(shè)施選址問題在滿足應(yīng)急需要的同時，除了要考慮其本身的動態(tài)性和不確定性因素外，還要考慮其與其他配套問題的協(xié)調(diào)，以開展整體應(yīng)用場景及標(biāo)準(zhǔn)測試用例的研究。