覆蓋類選址問題分類及研究綜述

喬聯(lián)寶 QIAO Lian-bao

（南京大學(xué) 信息管理學(xué)院，江蘇 南京 210023）

(School of Information Management of Nanjing University,Nanjing 210023,China)

0 引言

選址問題作為一項(xiàng)戰(zhàn)略決策，其影響是深遠(yuǎn)和持久的。根據(jù)決策者的目標(biāo)和所面臨的約束條件的不同，選址問題可以分為不同的種類，較常見的有：?jiǎn)我辉O(shè)施點(diǎn)選址（Single Facility Location），多設(shè)施點(diǎn)選址（Multi-facility Location），層次性選址（Hierarchical Location），p 中值問題（p-Median），p 中心問題（p-Center），覆蓋問題（Coverage）等。在三大經(jīng)典選址模型中，覆蓋類選址是選址問題中的一個(gè)重要分支，它已被廣泛的應(yīng)用到應(yīng)急服務(wù)設(shè)施以及公共設(shè)施點(diǎn)的選址問題中。

目前，國內(nèi)外關(guān)于一般選址研究的文獻(xiàn)相對(duì)較多，其中綜述性的文獻(xiàn)就有：Barbaros 等[1]，Owen 和Daskin[2]，Hale 和Moberg[3]，ReVelle 和Eiselt[4]，楊豐梅等[5]，王非等[6]，以上文獻(xiàn)從總體上對(duì)選址問題的研究進(jìn)展作了介紹與總結(jié)。覆蓋選址相關(guān)的早期重要文獻(xiàn)主要有：Hakimi[7]，Toregas 等[8]，Toregas 和ReVelle[9-10]，Church 和ReVelle[11]，Pirkul 和Schilling[12-13]，Hogan 和ReVelle[14]，這些文獻(xiàn)對(duì)推動(dòng)覆蓋選址問題的研究有重要作用。

Schilling 等[15]對(duì)1991年以前的覆蓋選址問題作了綜述研究。后來，F(xiàn)arahani 等[16]對(duì)1991年以后至2011年之間與覆蓋相關(guān)的選址文獻(xiàn)作了大量的綜述性研究。通過對(duì)比這兩篇綜述所分析的目標(biāo)文獻(xiàn)數(shù)量，可以發(fā)現(xiàn)：20 世紀(jì)90年代以后在理論上出現(xiàn)了大量研究覆蓋選址問題的文獻(xiàn)，其中與應(yīng)急服務(wù)設(shè)施相關(guān)的有：Current 和Kelly[17]，Michael 和Feng[18]，Brotcorne 等[19-20]，Daskin 和Dean[21]，Sorensen 和Church[22]等。縱觀國內(nèi)，覆蓋選址方面的研究文獻(xiàn)主要有：馬云峰[23-24]，翁克瑞、楊超[25]，殷代君[26]，葛春景等[27]，他們主要研究了最大覆蓋選址模型的一些應(yīng)用及其求解算法。應(yīng)用排隊(duì)論來處理覆蓋選址問題的相關(guān)研究主要有胡丹丹[28-29]，鵬翀等[30]。可以發(fā)現(xiàn)，同國外的研究相比，國內(nèi)關(guān)于覆蓋選址問題的研究相對(duì)不足，相關(guān)的綜述研究也較少。

從時(shí)間上來看，Schilling 和Farahani 等人的綜述研究幾乎覆蓋了從覆蓋選址模型最初提出到2011年間的所有相關(guān)文獻(xiàn)。但是，由于分類標(biāo)準(zhǔn)的不同和研究文獻(xiàn)的零散性，要全面了解覆蓋選址問題的發(fā)展以及不同覆蓋模型之間的內(nèi)在關(guān)系就比較困難，尤其是概率選址問題的提出及應(yīng)用。

鑒于此，以下從各個(gè)模型出現(xiàn)的時(shí)間順序以及所使用的方法將覆蓋選址問題其劃分類別，重點(diǎn)分析模型假設(shè)條件的不斷改進(jìn)和不同模型之間的內(nèi)在聯(lián)系，使讀者能夠從整體上把握覆蓋選址模型的發(fā)展邏輯和各種重要的類別細(xì)分。同時(shí)，對(duì)覆蓋選址相關(guān)的重要文獻(xiàn)做相關(guān)的評(píng)述，為今后研究覆蓋選址問題提供便利。

1 覆蓋選址問題的分類

選址問題按照不同的標(biāo)準(zhǔn)可以劃分為不同的類型，較為常見的分類標(biāo)準(zhǔn)有以下幾種：①設(shè)施點(diǎn)的數(shù)目；②潛在設(shè)施點(diǎn)的空間布局；③目標(biāo)函數(shù)的數(shù)量；④設(shè)施點(diǎn)是否有容量限制；⑤設(shè)施點(diǎn)受顧客偏愛的性質(zhì)；⑥設(shè)施點(diǎn)之間是否存在等級(jí)關(guān)系；⑦模型參數(shù)是確定還是隨機(jī)的，等等。眾多的劃分標(biāo)準(zhǔn)，使得如何對(duì)選址問題進(jìn)行闡述本身就是一個(gè)困難的問題，不同的標(biāo)準(zhǔn)體現(xiàn)了研究重點(diǎn)差異。王非等[6]人按照時(shí)間節(jié)點(diǎn)將選址研究劃分為三個(gè)階段：零散研究階段（1909～1960s）；系統(tǒng)研究階段（1960s～1980s）；不確定性研究階段（1980s～至今）。按照時(shí)間維度將選址研究分為不同的階段是很自然的選擇，但是以下將采用另一種更為細(xì)致的標(biāo)準(zhǔn)來介紹覆蓋選址模型的分類和研究進(jìn)展。

按照模型參數(shù)（或者約束條件的形式）是否確定，覆蓋選址問題可以分為確定性選址模型和概率選址模型兩大類。對(duì)于概率模型，按照所應(yīng)用的方法，進(jìn)一步將劃分為一般概率模型和應(yīng)用排隊(duì)論的概率模型。對(duì)于其他的子類別，則主要通過目標(biāo)函數(shù)或者模型之間的相互關(guān)系進(jìn)一步進(jìn)行細(xì)分，具體結(jié)果如圖1。

圖1 覆蓋選址問題分類

鑒于篇幅限制，本文主要分析確定性覆蓋模型和概率模型中的一般概率覆蓋問題，并且重點(diǎn)回顧國外關(guān)于覆蓋選址問題的相關(guān)研究狀況。對(duì)于選址問題其他的分類方法和相關(guān)介紹，可以進(jìn)一步參考文獻(xiàn)[31-33]。

2 分類評(píng)述

對(duì)于大多數(shù)的覆蓋類選址問題，可以敘述如下：已知需求點(diǎn)集合和潛在的設(shè)施點(diǎn)集合，對(duì)于給定的服務(wù)半徑，①當(dāng)設(shè)施點(diǎn)的數(shù)量無限制時(shí)，要求尋找一種設(shè)施點(diǎn)的配置方式使得使用最少的服務(wù)設(shè)施以覆蓋所有的需求點(diǎn)；②當(dāng)給定設(shè)施點(diǎn)數(shù)量時(shí)，要求找到一種設(shè)施點(diǎn)配置方式使得其覆蓋的需求點(diǎn)盡可能的多。其中情形一為集合覆蓋問題，而情形二為最大覆蓋問題。當(dāng)然，對(duì)于如何確定設(shè)施點(diǎn)能夠覆蓋需求點(diǎn)，不同的方法又會(huì)得到其他的形式，比如，變半徑覆蓋，概率覆蓋以及多重覆蓋等。同時(shí)，目標(biāo)函數(shù)和約束條件的稍微變化又可以得到不同擴(kuò)展類型的覆蓋問題。下文主要按照?qǐng)D1 的劃分對(duì)重要的覆蓋選址問題進(jìn)行分類評(píng)述，對(duì)于每一類問題，同時(shí)給出基本的數(shù)學(xué)規(guī)劃模型。

由于基本覆蓋模型的應(yīng)用較為廣泛，其符號(hào)記法一般也稍有差異，在介紹各個(gè)模型之前，先對(duì)部分符號(hào)做如下規(guī)定：

i:需求點(diǎn)標(biāo)號(hào)；

j:設(shè)施點(diǎn)標(biāo)號(hào)；

V:需求點(diǎn)集合；

W:設(shè)施點(diǎn)集合；

r:服務(wù)半徑；

p:允許建立的設(shè)施點(diǎn)數(shù)量；

hi:需求點(diǎn)i 的需求量；

cj:設(shè)施點(diǎn)j 的固定建造成本；

dij:需求點(diǎn)i 到設(shè)施點(diǎn)j 的距離；

Ni=｛j:dij≤｝r :能夠?qū)π枨簏c(diǎn)i 提供服務(wù)的設(shè)施點(diǎn)集合；

Mj=｛i:dij≤｝r :設(shè)施點(diǎn)j 可以服務(wù)的需求點(diǎn)集合；

Xj:設(shè)施點(diǎn)j 安排的服務(wù)設(shè)施數(shù)量，Xj∈N；

xj=；

yi=。

2.1 確定性覆蓋模型

2.1.1 集合覆蓋（Location Set Covering Problem,LSCP）

LSCP 最早由Toregas[8]等人提出，主要用于解決應(yīng)急服務(wù)設(shè)施點(diǎn)的選址問題，它要求建立最少的服務(wù)設(shè)施點(diǎn)以覆蓋所有的需求點(diǎn)，其模型如下（LSCP）：

其中目標(biāo)函數(shù)（1）式要求建立的服務(wù)設(shè)施點(diǎn)數(shù)量最小；約束（2）式規(guī)定，對(duì)每一個(gè)需求點(diǎn)，至少有一個(gè)設(shè)施點(diǎn)可以對(duì)其提供服務(wù)；（3）式是變量取值類型約束。在上述LSCP 模型中，如果考慮不同設(shè)施點(diǎn)的成本因素，要使建造成本最小，則可以得到加權(quán)集合覆蓋模型（WSCP）：

對(duì)于此模型，Roth[35]最早設(shè)計(jì)了計(jì)算機(jī)求解算法。注意到，LSCP 是WSCP 所有設(shè)施點(diǎn)成本相同時(shí)的特殊情況。就LSCP 的起源，一般認(rèn)為Hakimi 是該問題的最早提出者[7,16]，在1965年的一篇論文中，Hakimi[34]研究了網(wǎng)絡(luò)圖上的頂點(diǎn)覆蓋問題，并考慮了在給定距離約束的條件下，如何安排最少數(shù)量的警察以覆蓋所有高速公路網(wǎng)絡(luò)上的頂點(diǎn)，只是當(dāng)時(shí)所建立的模型并不是標(biāo)準(zhǔn)的覆蓋選址模型。

1969年，Roth[35]提出了求解覆蓋問題局部最優(yōu)解的計(jì)算機(jī)算法，由于其目標(biāo)函數(shù)是加權(quán)和最小形式，因此并不嚴(yán)格屬于集合覆蓋問題（Set Covering Problem,SCP），而是一般意義上的加權(quán)集合覆蓋問題（Weighted Set Covering Problem,WSCP）。另外，由于該文獻(xiàn)最初并不是基于選址問題而提出，這就造成后來人們?cè)诨仡橪SCP 的研究文獻(xiàn)時(shí)常常將Roth 的研究工作忽略。

1971年，Toregas 等[8]正式建立了應(yīng)急服務(wù)設(shè)施的LSCP 數(shù)學(xué)規(guī)劃模型，當(dāng)服務(wù)設(shè)施點(diǎn)具有相同的成本時(shí)，目標(biāo)函數(shù)轉(zhuǎn)化為建立最少的服務(wù)設(shè)施點(diǎn)以覆蓋所有的需求點(diǎn)。事實(shí)上，這是Roth 模型中目標(biāo)函數(shù)權(quán)系數(shù)相同的特殊情況，但是在選址理論中，一般認(rèn)為Toregas 等人是LSCP 數(shù)學(xué)模型的最早提出者。

LSCP 模型建立以后，人們面臨著如何有效求解的問題。受Roth 提出的求解算法的啟發(fā)，在接下來的兩年時(shí)間里，Toregas和ReVelle[9-10]又分別提出了精確求解LSCP 的行和列簡(jiǎn)化算法（Row and Column Reduction）。Vasko 和Wilson[36]提出了求解LSCP①的啟發(fā)式算法，其結(jié)果表明：在同等條件下，LSCP 比WSCP 更難于求解。

Alminana 和Pastor[37]提出了一種改進(jìn)形式的代理啟發(fā)式算法（Surrogate Heuristic）用以求解LSCP。Brotcorne 等[19]提出了求解需求點(diǎn)離散、潛在設(shè)施點(diǎn)連續(xù)的大規(guī)模覆蓋選址問題的快速啟發(fā)式算法。

以上等人的研究大多屬于標(biāo)準(zhǔn)的SCP，要覆蓋的目標(biāo)對(duì)象為網(wǎng)絡(luò)或者平面上的點(diǎn)集。對(duì)于其他形式的集合覆蓋問題，Boffey 和Narula[38]，Gendreau 等[39]分別提出了路徑覆蓋和回路覆蓋問題，Current 和Storbeck[40]研究了有容量約束的LSCP，Murray等[41]提出了另外兩種隱式和顯式的LSCP 模型。

在現(xiàn)實(shí)生活中，決策者往往面臨著有限的預(yù)算約束，而LSCP 模型為了覆蓋所有的需求點(diǎn)，可能導(dǎo)致建立的設(shè)施點(diǎn)過多從而超出預(yù)算。因此，人們又提出了覆蓋選址問題的另一個(gè)模型：最大覆蓋選址模型。

2.1.2 最大覆蓋（Maximal Covering Location Problem,MCLP）

1974年，Church 和ReVelle[11]提出了MCLP 模型：在給定設(shè)施點(diǎn)數(shù)量的條件下，如何安排設(shè)施點(diǎn)的位置使得覆蓋的需求量盡可能的多，其具體形式如下：

其中目標(biāo)函數(shù)（5）式最大化覆蓋的需求量；約束（6）式是需求點(diǎn)被覆蓋時(shí)應(yīng)滿足的條件；約束（7）式規(guī)定了建立設(shè)施點(diǎn)的最大數(shù)量；約束（8）和（9）式為變量取值類型。

同年，White 和Case[42]以部分覆蓋模型的方式提出了一種特殊的最大覆蓋問題，即所有需求點(diǎn)具有相等的需求量，因此，目標(biāo)函數(shù)轉(zhuǎn)化為覆蓋盡可能多的需求點(diǎn)（而非需求點(diǎn)的需求量），并分析了該模型和SCP 模型的關(guān)系。Klastorin[43]證明了MCLP可以轉(zhuǎn)化為一般指派問題進(jìn)行求解。

在實(shí)踐應(yīng)用方面，MCLP 模型主要用于解決應(yīng)急服務(wù)設(shè)施的選址問題。Bennett 等[44]應(yīng)用MCLP 模型，研究了邊遠(yuǎn)地區(qū)的醫(yī)療資源的選址問題；Eaton 等[45-46]將MCLP 模型應(yīng)用到現(xiàn)實(shí)中的應(yīng)急醫(yī)療車輛的選址問題中。Richard 等[47]應(yīng)用MCLP 模型研究了保護(hù)區(qū)的選擇問題，最大化能夠覆蓋的物種數(shù)量。Li 等[48]綜述了覆蓋模型在應(yīng)急服務(wù)設(shè)施選址和規(guī)劃方面的應(yīng)用，Chung[49]綜述了覆蓋選址模型在其他方面的應(yīng)用，如數(shù)據(jù)提取、統(tǒng)計(jì)分類和認(rèn)知過程建模等。

確定性覆蓋模型在應(yīng)用過程中也存在一定的問題，最為主要的便是覆蓋半徑的確定。早期的文獻(xiàn)一般是規(guī)定一個(gè)事先給定的半徑，在此半徑內(nèi)可以完全覆蓋，否則不覆蓋。因此，這種覆蓋方法也被稱為0～1 覆蓋。針對(duì)這種兩元?jiǎng)澐謽?biāo)準(zhǔn)，后來的研究文獻(xiàn)分別提出了變半徑覆蓋[50]、逐漸覆蓋[51-54]等擴(kuò)展模型。Berman 等[55]對(duì)以上兩種一般的覆蓋模型以及合作覆蓋模型做了分類綜述。

早期覆蓋模型的另一個(gè)缺陷是：只要需求點(diǎn)位于設(shè)施點(diǎn)的覆蓋半徑內(nèi)，任何情況下服務(wù)設(shè)施點(diǎn)都可以對(duì)需求點(diǎn)提供服務(wù)。這種假設(shè)顯然對(duì)于那些服務(wù)設(shè)施點(diǎn)經(jīng)常處于繁忙狀態(tài)的系統(tǒng)過于嚴(yán)格。因此，后來提出了備用覆蓋和合作覆蓋模型來提高服務(wù)水平。如Hogan 和ReVelle[56]較早地提出了用額外一個(gè)設(shè)施點(diǎn)作為備用覆蓋的研究思路并介紹了其應(yīng)用；Pirkul 和Schilling[12]考慮了有工作能力和備用服務(wù)的應(yīng)急服務(wù)設(shè)施選址問題；Curtin[57]建立了警察巡邏區(qū)域的最大覆蓋以及備用覆蓋模型，以上等研究只考慮一級(jí)備用覆蓋。Narisimhan 等[58]建立了有容量約束和不同等級(jí)的備用覆蓋模型，Berman[59]提出了位于平面上、并且服務(wù)設(shè)施點(diǎn)發(fā)出的“信號(hào)”能夠因疊加而增強(qiáng)的合作覆蓋模型。

2.2 概率覆蓋模型

如果考慮到所有的不確定性因素，可提供服務(wù)的設(shè)施點(diǎn)數(shù)量、需求點(diǎn)的位置和需求量以及服務(wù)單位到達(dá)需求點(diǎn)的時(shí)間等都有可能是隨機(jī)變量。備用覆蓋模型的提出，考慮了服務(wù)設(shè)施點(diǎn)可能因處于繁忙狀態(tài)而不可獲得這種情形，因此它提出用額外的服務(wù)設(shè)施來確保所有需求盡可能得到滿足。由于沒有具體考慮服務(wù)設(shè)施點(diǎn)的繁忙狀態(tài)，這種處理方法屬于隱式考慮服務(wù)設(shè)施點(diǎn)繁忙的模型。就應(yīng)急服務(wù)設(shè)施點(diǎn)的選址問題而言，多數(shù)研究文獻(xiàn)重點(diǎn)關(guān)注于服務(wù)設(shè)施因處于繁忙狀態(tài)而造成的不可獲得性，處理方法上主要有概率模型（不同服務(wù)設(shè)施點(diǎn)繁忙狀態(tài)相互獨(dú)立）和排隊(duì)論模型。

2.2.1 最大期望覆蓋（Maximal Expected Coverage Location Problem,MEXCLP）

在研究服務(wù)設(shè)施點(diǎn)經(jīng)常處于繁忙狀態(tài)的概率覆蓋選址問題時(shí)，一個(gè)重要的問題就是服務(wù)設(shè)施點(diǎn)繁忙概率的確定。一般有兩種情況：系統(tǒng)水平的繁忙概率（system-wide busy fraction）和區(qū)域水平的繁忙概率（region-specific busy fraction），前者假定系統(tǒng)內(nèi)所有的服務(wù)設(shè)施點(diǎn)具有相同的繁忙概率，而后者假定不同服務(wù)區(qū)域的設(shè)施點(diǎn)繁忙情況各不相同。如果只考慮概率意義下能夠得到服務(wù)的需求，就得到了期望類型的覆蓋選址模型。

通過假定系統(tǒng)內(nèi)所有的服務(wù)設(shè)施具有相等的繁忙概率，Daskin[60]最早介紹了期望覆蓋模型在應(yīng)急醫(yī)療服務(wù)系統(tǒng)中的應(yīng)用。后來基于同樣的假設(shè)，Daskin[61]又建立了最大期望覆蓋選址問題的整數(shù)規(guī)劃模型，目標(biāo)函數(shù)最大化覆蓋的期望值，并設(shè)計(jì)了求解的啟發(fā)式算法，其形式如下：

其中：

q:服務(wù)設(shè)施繁忙的概率；

yik=

其他符號(hào)如前文所述。目標(biāo)函數(shù)（10）式最大化概率加權(quán)意義下的覆蓋量；約束（11）式代表能夠?qū)γ總€(gè)需求點(diǎn)提供服務(wù)的服務(wù)設(shè)施數(shù)量限制；約束（12）式是總的服務(wù)設(shè)施數(shù)量限制，當(dāng)然也可以取小于等于形式，由于目標(biāo)函數(shù)最大化，兩者等價(jià)；約束（13）和（14）式是變量取值類型條件。

期望覆蓋模型考慮了服務(wù)設(shè)施的繁忙情形，但是并沒有試圖提高系統(tǒng)的可靠性。Fujiwara[62]將MEXCLP 模型應(yīng)用到城市的救護(hù)車輛布局上，設(shè)計(jì)了求解問題的近似算法并通過模擬對(duì)近似解進(jìn)行了分析。Daskin 等[63]將多重備用覆蓋模型和MEXCLP 結(jié)合起來，建立了概率形式的備用覆蓋模型，從備用覆蓋的角度考慮了服務(wù)的可靠性。Sorensen 和Church[64]考慮了服務(wù)的可獲得性，建立了有區(qū)域可靠性的MEXCLP 模型，目標(biāo)函數(shù)最大化在保證服務(wù)質(zhì)量的情況下所能夠覆蓋的需求量。Chuang 和Lin[65]建立了有雙重覆蓋標(biāo)準(zhǔn)的應(yīng)急醫(yī)療救護(hù)車輛MEXCLP 模型。

Repede 和Bernardo[66]考慮了需求隨時(shí)間變化的MEXCLP，并將其同決策支持系統(tǒng)相結(jié)合應(yīng)用到實(shí)例城市的應(yīng)急醫(yī)療服務(wù)系統(tǒng)中，其結(jié)果表明應(yīng)急反應(yīng)時(shí)間可以減少36%。McLay[67]考慮了有兩種不同服務(wù)設(shè)施、不同顧客類型的MEXCLP 模型。Rajagopalan 等[68]設(shè)計(jì)了求解MEXCLP 的三種啟發(fā)式算法：遺傳算法，禁忌搜索和模擬退火，并使用方差分析技術(shù)對(duì)以上三種算法的性能進(jìn)行了分析。根據(jù)模型是否考慮服務(wù)的可獲得性和反應(yīng)時(shí)間這兩種因素的隨機(jī)性，Erkut 等[69]分析了MCLP 和MEXCLP等五類覆蓋模型在救護(hù)車選址問題中的差異。

2.2.2 概率集合覆蓋（Probabilistic Location Set Covering Problem,PLSCP）

通過對(duì)基于區(qū)域的服務(wù)繁忙概率進(jìn)行估計(jì)，ReVelle 和Hogan[70]提出了概率形式的集合覆蓋選址模型。在計(jì)算需求點(diǎn)i 附近的服務(wù)設(shè)施點(diǎn)的繁忙概率時(shí)，他們使用以下計(jì)算公式：

其中：

fk:需求點(diǎn)k 的服務(wù)請(qǐng)求率（個(gè)/天）。

記bi是使得（17）成立的最小整數(shù)，

由此可以得到基于區(qū)域水平估計(jì)的概率集合選址模型：

其中目標(biāo)函數(shù)（18）式最小化服務(wù)設(shè)施的數(shù)量；約束（19）式是為達(dá)到給定的服務(wù)水平所必須的服務(wù)設(shè)施數(shù)量；（20）式是變量類型限制。與LSCP 模型不同的是，PLSCP 模型中，單個(gè)設(shè)施點(diǎn)允許安排的服務(wù)設(shè)施數(shù)量可以多于1 個(gè)，并且由（17）的推導(dǎo)可知，該模型假定各個(gè)服務(wù)器是否繁忙是相互獨(dú)立的。

Ball 和Lin[71]提出了另一種基于系統(tǒng)水平的PLSCP 模型，他們要求需求點(diǎn)不被覆蓋的概率不能小于給定的值。Goldberg 和Paz[72]建立了另一種非線性的概率覆蓋模型，假定服務(wù)單位到達(dá)需求點(diǎn)的時(shí)間是隨機(jī)的，并且服務(wù)時(shí)間依賴于需求點(diǎn)的位置，目標(biāo)函數(shù)最大化在給定時(shí)間限制時(shí)的期望需求量。

上述等人的研究主要考慮了服務(wù)設(shè)施因繁忙而導(dǎo)致的服務(wù)不確定性。對(duì)于一般機(jī)會(huì)約束形式的概率集合覆蓋問題，Beraldi和Ruszczynski[73]提出了約束右端項(xiàng)為0～1 隨機(jī)變量的概率集合覆蓋模型，其中約束成立的聯(lián)合概率不小于給定的值p，在p 有效點(diǎn)的基礎(chǔ)上提出了求解所有p 有效點(diǎn)的枚舉算法和分支定界算法。在Beraldi 和Ruszczynski 提出的模型基礎(chǔ)上，Saxena 等[74]又建立了在約束左端項(xiàng)為0～1 矩陣時(shí)的非線性整數(shù)規(guī)劃模型，進(jìn)一步給出了兩種等價(jià)形式的線性規(guī)劃化模型，并設(shè)計(jì)了基于線性規(guī)劃的分離算法。Hwang[75]將上述概率集合覆蓋模型應(yīng)用到物流系統(tǒng)的設(shè)計(jì)中，在系統(tǒng)設(shè)計(jì)的第一階段用于解決倉庫或分銷中心對(duì)客戶的覆蓋問題。

考慮到服務(wù)設(shè)施的繁忙情形，概率集合覆蓋要求被覆蓋的需求點(diǎn)必須在給定的服務(wù)水平下能夠得到服務(wù)。顯然，這比LSCP 模型假定所有被覆蓋的需求任何時(shí)候都可以得到服務(wù)更符合實(shí)際，尤其是對(duì)于經(jīng)常處于繁忙狀態(tài)的系統(tǒng)而言。

2.2.3 最大可獲的性覆蓋（Maximal Availability Location Problem,MALP）

同集合覆蓋模型一樣，概率集合覆蓋模型為了在給定的服務(wù)水平下覆蓋所有的需求，它同樣會(huì)安排較多的服務(wù)設(shè)施點(diǎn)。如果給定了可以使用的服務(wù)設(shè)施數(shù)量，要在保證服務(wù)水平的條件下覆蓋盡可能多的需求，就得到了對(duì)應(yīng)于MCLP 的概率模型。根據(jù)服務(wù)繁忙概率的不同假設(shè)，ReVelle 和Hogan[76]分別使用系統(tǒng)和區(qū)域水平的服務(wù)繁忙率，建立了有可靠性水平保證的最大可獲得性選址問題模型MALP I 和MALP II。其中前者假定系統(tǒng)內(nèi)所有的服務(wù)設(shè)施具有相等的繁忙概率，而后者假定不同的需求區(qū)域具有不同的繁忙概率。由于前者是后者的特殊情形，因此只考慮MALP II，其形式如下：

其中bi為滿足（17）式的值，yik同MEXCLP 模型規(guī)定一致。在目標(biāo)函數(shù)（21）式中，只有當(dāng)需求點(diǎn)至少被bi臺(tái)服務(wù)設(shè)施覆蓋時(shí)，該部分需求才認(rèn)為被覆蓋，也即要滿足事先規(guī)定的服務(wù)水平α；由于目標(biāo)函數(shù)不滿足MEXCLP 模型中的凹性，所以約束（23）是必須的；其他約束條件同MEXCLP 模型。

ReVelle 和Marianov[77-78]將MALP 模型擴(kuò)展到兩種不同類型的服務(wù)設(shè)施，考慮了消防系統(tǒng)中引擎和卡車這兩種服務(wù)設(shè)施的共同選址問題，只有當(dāng)每種服務(wù)設(shè)施可獲得的概率或者其聯(lián)合概率大于事先給定的值時(shí)，需求才能夠被覆蓋。

Chiyoshi 和Morabito[79]設(shè)計(jì)了求解擴(kuò)展的MALP 模型的禁忌搜索算法，并同模擬退火算法的結(jié)果進(jìn)行了比較：對(duì)于小規(guī)模的問題，模擬退火算法的效果較好；而大規(guī)模的問題，禁忌搜索算法所得到的解較好。

Erkut 等[80]從批判的角度指出了有概率水平保證的可獲得性覆蓋或者可靠性覆蓋模型在救護(hù)站和應(yīng)急車輛選址中所存在的問題。首先概率模型比確定性模型對(duì)數(shù)據(jù)的要求更高，即使是將機(jī)會(huì)約束線性化處理以后，這種問題依然存在；其次是可靠性水平的確定比較主觀，沒有一個(gè)合理的方式來選擇這一概率值。因此，他們認(rèn)為應(yīng)當(dāng)使用期望類型的覆蓋模型來解決應(yīng)急服務(wù)設(shè)施的選址問題。

3 結(jié)論

覆蓋模型的提出，為解決以應(yīng)急服務(wù)為主的設(shè)施點(diǎn)選址提供了科學(xué)的方法。最先提出的覆蓋選址模型是LSCP 和MCLP，早期的覆蓋問題其模型參數(shù)都是確定性的，并且只要需求點(diǎn)位于事先規(guī)定的服務(wù)半徑內(nèi)，那么所有的需求點(diǎn)都可以得到服務(wù)。但是，對(duì)于一些經(jīng)常處于繁忙狀態(tài)的服務(wù)系統(tǒng)而言，服務(wù)設(shè)施點(diǎn)并不總是能夠?qū)ζ浞?wù)半徑內(nèi)的需求點(diǎn)提供服務(wù)。考慮到這種情況，研究領(lǐng)域又提出了概率覆蓋模型。在概率選址問題中，根據(jù)假設(shè)條件和所使用的方法，可以進(jìn)一步劃分為一般概率覆蓋和排隊(duì)覆蓋模型。一般概率覆蓋模型假定各個(gè)服務(wù)設(shè)施點(diǎn)是否繁忙是相互獨(dú)立的，從而能夠從一般概率意義上來分析所研究的問題。服務(wù)設(shè)施相互獨(dú)立假設(shè)使得模型的構(gòu)建不至于太復(fù)雜、求解不過于困難，這對(duì)早期的理論應(yīng)用有重要的價(jià)值。在研究方法上，也為后來運(yùn)用排隊(duì)論模型提供了框架和自然的過渡。

然而在現(xiàn)實(shí)生活中，服務(wù)設(shè)施在提供服務(wù)時(shí)面臨排隊(duì)是一種十分普遍的現(xiàn)象，如醫(yī)院就診、120 救護(hù)車輛提供救援等。多數(shù)情況下，服務(wù)設(shè)施點(diǎn)在一個(gè)系統(tǒng)內(nèi)工作，其運(yùn)行并不是相互獨(dú)立的，由此來看，一般概率覆蓋模型的假設(shè)需要進(jìn)一步改進(jìn)。基于排隊(duì)論的覆蓋選址模型，可以更精確地反映此類服務(wù)設(shè)施在現(xiàn)實(shí)中的運(yùn)行情況。所以，進(jìn)一步研究工作可以分析排隊(duì)覆蓋選址問題在理論和現(xiàn)實(shí)兩個(gè)方面的發(fā)展及應(yīng)用。

注：①在其文獻(xiàn)中稱之為Minimum Cardinality Set Covering Problem（MCSCP），也有文獻(xiàn)稱為Unicost Set Covering Problem。

[1]Barbaros C T,Richard L F,Timothy J L.Location on networks:a survey.Part I:The p-Center and p-Median Problems[J].Management Science,1983,29(4):482-497.

[2]Owen H S,Daskin M S.Strategic facility location:a review[J].European Journal of Operational Research,1988,111:423-447.

[3]Hale T S,Moberg C R.Location science research:a review[J].Annals of Operations Research,2003,123:21-35.

[4]ReVelle C S,Eiselt H A.Location analysis:a synthesis and survey[J].European Journal of Operational Research,2005,165:1-19.

[5]楊豐梅，華國偉，鄧猛,等.選址問題研究的若干進(jìn)展[J].運(yùn)籌與管理，2005,14(6):1-7.

[6]王非，徐渝，李毅學(xué).離散設(shè)施選址問題研究綜述[J].運(yùn)籌與管理，2006,15(5):64-69.

[7]Hakimi S L.Optimum distribution of switching centers in a communication network and some related graph theoretic problems[J].Operations Research,1965,13:462-475.

[8]Toregas C,Swain R,ReVelle C,Bergman L.The location of emergency services facilities[J].Operations Research,1971,19:1363-1373.

[9]Torgas C,ReVelle C.Optimal Location under Time or Distance Constraints[J].Papers of the Regional Science Association,1972,28:133-143.

[10]Torgas C,ReVelle C.Binary logic solutions to a class of location problems[J].Geographical Analysis,1973,5:145-155.

[11]Church R,ReVelle C.The maximal covering location problem[J].Papers of the Regional Science Association,1974,32:101-111.

[12]Pirkul H,Schilling D.The capacitated maximal covering location problem with backup service[J].Annals of Operations Research,1989,18:141-154.

[13]Pirkul H,Schilling D.The maximal covering location problem with capacities on total workload[J].Management Science,1991,32(2):233-248.

[14]Hogan K,ReVelle C.Concepts and applications of backup coverage[J].Management Science,1986,32:1434-1444.

[15]Schilling D A,Jayaraman V,Barkhi R.A review of covering problem in facility location[J].Location Science,1993,1(1):25-55.

[16]Farahani R Z,Asgarin N,Herdari N,et al.Covering problems in facility location:a review[J].Computers &Industrial Engineering,2012,62:368-407.

[17]Current J,Kelly M O.Locating emergency warning sirens[J].Decision Sciences,1992,23(1):221-234.

[18]Michael O B,Feng L L.A Reliability Model Applied to Emergency Service Vehicle Location[J].Operations Research,1993,41(1):18-36.

[19]Brotcorne L,Laporte G,Semet F.Fast heuristics for large scale covering location problems[J].Computers &Operations Research,2002,29:651-665.

[20]Brotcorne L,Laporte G,Semet F.Ambulance location and relocation models[J].European Journal of Operational Research,2003,147:451-463.

[21]Daskin M S,Dean L K.Location of health care facilities[C]// Brandeau M L,Sainfort F,Pierskalla W P.Operations Research and Health Care:A Handbook ofMethodsand Applications.Boston:Kluwer Academic Publishers,2005:43-76.

[22]Sorensen P,Church R.Integrating expected coverage and local reliability for emergency medical services location problems[J].Socio-Economic Planning Sciences,2010,44:8-18.

[23]馬云峰，楊超，張敏,等.基于時(shí)間滿意的最大覆蓋選址問題[J].中國管理科學(xué)，2006,14(2):45-51.

[24]馬云峰.網(wǎng)絡(luò)選址中基于時(shí)間滿意的覆蓋問題研究[D].武漢：華中科技大學(xué)（博士學(xué)位論文），2005.

[25]翁克瑞，楊超.多分配樞紐站最大覆蓋選址問題[J].工業(yè)工程與管理，2007(1):40-44.

[26]殷帶君.廣義最大覆蓋模型在應(yīng)急服務(wù)設(shè)施選址中的應(yīng)用研究[D].濟(jì)南：山東大學(xué)（碩士學(xué)位論文），2007.

[27]葛春景.重大突發(fā)事件應(yīng)急設(shè)施多重覆蓋選址模型及算法[J].運(yùn)籌與管理，2011,20(5):50-56.

[28]胡丹丹.考慮服務(wù)數(shù)量和服務(wù)時(shí)間的緊急救援站選址[J].公路交通科技，2012,29(10):132-136.

[29]胡丹丹.擁塞型設(shè)施的選址問題研究[D].武漢：華中科技大學(xué)（博士學(xué)位論文），2011.

[30]鵬翀.應(yīng)急救援物流中物資分發(fā)點(diǎn)多目標(biāo)排隊(duì)選址優(yōu)化[J].交通科學(xué)與工程，2011,27(2):96-100.

[31]楊豐梅，盧曉姍.競(jìng)爭(zhēng)設(shè)施選址理論與方法[M].北京：科學(xué)出版社，2010.

[32]Daskin M S.Network and discrete location:models,algorithms and applications[M].New York:Wiley Interscience,1995.

[33]Farahani R Z,Hekmatfar M.Facility location:concepts,models,algorithms and case studies[M].Berlin:Springer-Verlag,2009.

[34]Hakimi S L.Optimum distribution of switching centers in a communication network and some related graph theoretic problems[J].Operations Research,1965,13(3):462-475.

[35]Roth R.Computer solutions to minimum cover problems[J].Operations Research,1969,3:455-464.

[36]Vasko F J,Wilson G R.Hybrid heuristics for minimum cardinality set covering problems[J].Naval Research Logistics,1986,33(2):241-249.

[37]Alminana M,Pastor J T.An adaptation of SH heuristic to the location set covering[J].European Journal of Operational Research,1997,100:586-593.

[38]Boffey B,Narula S C.Models for multi-path covering-routing problems[J].Annals of Operations Research,1998,82:331-342.

[39]Gendreau M,Laporte G,Semet F.The covering tour problem[J].Operations Research,1997,45(4):568-576.

[40]Current J R,Storbeck J E.Capacitated covering models[J].Environment and Planning B:Planning and Design,1988,15(2):153-163.

[41]Murray A T,Tong D,Kim K.Enhancing classic coverage location Models[J].International Regional Science Review,2010,33(2):115-133.

[42]White J A,Case K E.On covering problems and the central facilities location problem[J].Geographical Analysis,1974,6:281-293.

[43]Klastorin T D.On the maximal covering location problem and the generalized assignment problems[J].Management Science,1979,25(1):107-112.

[44]Bennett V,Eaton D,Church R.Selecting sites for rural health workers[J].Social Science and Medicine,1982,16:63-72.

[45]Eaton D,Daskin M,Simmons D,et al.Determining emergency medical service vehicle deployment in austin,texas[J].Interfaces,1985,15:96-108.

[46]Eaton D,Sanchez H,Lantigua R,et al.Determining ambulance deployment in santo domingo,dominican republic[J].The Journal of the Operational Research Society,1986,37:113-126.

[47]Church R L,Stoms D M,Davis F W.Reserve selection as a maximal covering location problem[J].Biological Conservation,1996,76:105-112.

[48]Li X P,Zhao Z X,Zhu X Y,et al.Covering models and optimization techniques for emergency response facility location and planning:a review[J].MathematicalMethodsof Operations Research,2011,74:281-310.

[49]Chung C H.Recent applications of the maximal covering location planning（M.C.L.P.）model[J].The Journal of the Operational Research Society,1986,37(8):735-746.

[50]Berman O,Drezner Z,Krass D,et al.The variable radius covering problem[J].European Journal of Operational Research,2009,196:516-525.

[51]Berman O,Krass D,Drezner Z.The gradual covering decay location problem on a network[J].European Journal of Operational Research,2003,151:474-480.

[52]Drezner Z,Wesolowsky G O,Drezner T.The Gradual Covering Problem[J].Naval Research Logistics,2004,51:841-855.

[53]Berman O,Kalcsics J,Krass D,et al.The Ordered Gradual Covering Location Problem on a Network[J].Discrete Applied Mathematics,2009,157:3689-3707.

[54]Eiselt H A,Marianov V.Gradual location set covering with service quality[J].Socio-Economic Planning Sciences,2009,43:121-130.

[55]Berman O,Drezner Z,Krass D.Generalized coverage:New developments in covering location models[J].Computers &Operations Research,2010,37:1675-1687.

[56]Hogan K,Revelle C.Concepts and Applications of Backup Coverage[J].Management Science,1986,32(11):1434-1444.

[57]Curtin K M,Hayslett-McCall K,Qiu F.Determining optimal police patrol areas with maximal covering and backup covering location models[J].Networks and Spatial Economics,2010,10(1):125-145.

[58]Narisimhan S,Pirkul H,Schilling D.Capacitated emergency facility siting with multiple levels of backup[J].Annals of Operations Research,1992,40:323-337.

[59]Berman O,Drezner Z,Krass D.Cooperative cover location problems:The planar case[J].IIE Transactions,2010,42:232-246.

[60]Daskin M S.Application of an expected covering model to emergency medical service system design[J].Decision Sciences,1982,13:416-439.

[61]Daskin M S.A maximum expected covering location model:Formulation,properties and heuristic solution[J].Transportation Science,1983,17:47-70.

[62]Fujiwara O,Makjamroen T,Gupta K.Ambulance deployment analysis:a case study of Bangkok[J].European Journal of Operational Research,1987,31(1):9-18.

[63]Daskin M S,Hogan K,ReVelle C.Integration of multiple excess backup and expected covering models[J].Environment and Planning B:Planning and Design,1988,15:15-35.

[64]Sorensen P,Church R.Integrating expected coverage and local reliability for emergency medical services location problems[J].Socio-Economic Planning Sciences,2010,44:8-18.

[65]Chuang C,Lin R.A maximum expected covering model for an ambulance location problem[J].Journal of the Chinese Institute of Industrial Engineers,2007,24(6):468-474.

[66]Repede J F,Bernardo J J.Developing and validating a decision support system for locating emergenct medical vehicles in louisville Kentucky[J].European Journal of Operational Research,1994,75(5):567-581.

[67]McLay L A.A maximum expected covering location model with two types of servers[J].IIE Transactions,2009,41:730-741.

[68]Rajagopalan H K,Vergara F E,Saydam C,et al.Developing effective meta-heuristics for a probabilistic location model via experimental design[J].European Journal of Operational Research,2007,177:83-101.

[69]Erkut E,Ingolfsson A,Sim T.Computational comparison of five maximal covering models for locating ambulances[J].Geographical Analysis,2009,41:43-65.

[70]ReVelle C,Hogan K.A reliability-constrainted siting model with local estimates of busy factions[J].Environment and Planning B:Planning and Design,1988,15:143-152.

[71]Ball M O,Lin F L.A reliability model applied to emergency service vehicle location[J].Operations Research,1993,41(1):18-36.

[72]Goldberg J,Paz L.Locating emergency vehicle bases when service time depends on call location[J].Transportation Science,1991,25:264-280.

[73]Beraldi P,Ruszczynski A.The probabilistic set-covering problem[J].Operations Research,2002,50(6):956-967.

[74]Saxena A,Goyal V,Lejeune M.A.MIP reformulations of the probabilistic set covering problem[J].Mathematical Programming,Series A,2010,121:1-31.

[75]Hwang H.Design of supply-chain logistics system considering service level[J].Computers and Industrial Engineering,2002,43:283-297.

[76]ReVelle C,Hogan K.The maximum availability location problem[J].Transportation Science,1989,23(3):192-200.

[77]ReVelle C,Marianov V.A probabilistic FLEET model with individual vehicle reliability requirements[J].European Journal of Operational Research,1991,53:93-105.

[78]Marianov V,ReVelle C.A probabilistic fire-protection siting model with joint vehicle reliability requirements[J].Papers in Regional Science,1992,71:217-241.

[79]Chiyoshi F Y,Morabito R.A Tabu search algorithm for solving the extended maximal availability location problem[J].International Transactions in Operational Research,2011,18:663-678.

[80]Erkut E,Ingolfsson A,Budge S.Maximum availability/reliability models for selecting ambulance station and vehicle locations:a critique[Z].2008.