劉建友，蔣春霞

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

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

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

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

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

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

2.1 基本選址問(wèn)題

基本選址問(wèn)題有基于覆蓋和基于中值兩種類型。

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

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

2.2 動(dòng)態(tài)選址問(wèn)題

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

制約條件是：

2.3 隨機(jī)選址問(wèn)題

制約條件：

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

2.4 魯棒選址問(wèn)題

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

minfo(x)

制約條件是：

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

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

2.5 其他選址問(wèn)題

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

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

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

3.1 精確算法

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

3.2 非精確算法

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

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

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

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

4 未來(lái)研究方向

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

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

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

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