摘 要：根據模型參數的類型及建模所使用的方法，將覆蓋選址問題劃分為確定性覆蓋和概率覆蓋兩個大類。在確定性覆蓋問題中，重點分析了集合覆蓋和最大覆蓋兩個子類型;在概率覆蓋模型中，則回顧了概率集合覆蓋、最大可獲得性覆蓋和最大期望覆蓋三種重要的概率覆蓋問題。在以上劃分的基礎上，給出了各種覆蓋選址問題典型的數學規劃模型，重點分析了上述模型的假設條件及其發展的內在邏輯，并對相關的問題作了評述。

　　關鍵詞：研究生論文發表,綜述,覆蓋,選址,分類

　　Abstract： The covering facility location problem is divided into deterministic and probabilistic type covering model according to the parameter and methods used. The set covering and maximal covering location problem in the deterministic model and the probabilistic set covering， the maximal available covering and maximal expected coverage location problem in the probabilistic model are reviewed in the time order， respectively. Based on the above classification， detailed information about classic location mathematical programming models， assumptions and their development logic of each type are given and analyzed as well as review on some important issues.

　　Key words： review; covering; location; classification

　　0 引 言

　　選址問題作為一項戰略決策，其影響是深遠和持久的。根據決策者的目標和所面臨的約束條件的不同，選址問題可以分為不同的種類，較常見的有：單一設施點選址(Single Facility Location)，多設施點選址(Multi-facility Location)，層次性選址(Hierarchical Location)，p中值問題(p-Median)，p中心問題(p-Center)，覆蓋問題(Coverage)等。在三大經典選址模型中，覆蓋類選址是選址問題中的一個重要分支，它已被廣泛的應用到應急服務設施以及公共設施點的選址問題中。

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

　　Schilling等[15]對1991年以前的覆蓋選址問題作了綜述研究。后來，Farahani等[16]對1991年以后至2011年之間與覆蓋相關的選址文獻作了大量的綜述性研究。通過對比這兩篇綜述所分析的目標文獻數量，可以發現：20世紀90年代以后在理論上出現了大量研究覆蓋選址問題的文獻，其中與應急服務設施相關的有：Current和Kelly[17]，Michael和Feng[18]，Brotcorne等[19-20]，Daskin和Dean[21]，Sorensen和Church[22]等。縱觀國內，覆蓋選址方面的研究文獻主要有：馬云峰[23-24]，翁克瑞、楊超[25]，殷代

　　君[26]，葛春景等[27]，他們主要研究了最大覆蓋選址模型的一些應用及其求解算法。應用排隊論來處理覆蓋選址問題的相關研究主要有胡丹丹[28-29]，鵬�等[30]。可以發現，同國外的研究相比，國內關于覆蓋選址問題的研究相對不足，相關的綜述研究也較少。

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

　　鑒于此，以下從各個模型出現的時間順序以及所使用的方法將覆蓋選址問題其劃分類別，重點分析模型假設條件的不斷改進和不同模型之間的內在聯系，使讀者能夠從整體上把握覆蓋選址模型的發展邏輯和各種重要的類別細分。同時，對覆蓋選址相關的重要文獻做相關的評述，為今后研究覆蓋選址問題提供便利。

　　1 覆蓋選址問題的分類

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

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

　　覆蓋選址問題

　　圖1 覆蓋選址問題分類

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

　　2 分類評述

　　對于大多數的覆蓋類選址問題，可以敘述如下：已知需求點集合和潛在的設施點集合，對于給定的服務半徑，①當設施點的數量無限制時，要求尋找一種設施點的配置方式使得使用最少的服務設施以覆蓋所有的需求點;②當給定設施點數量時，要求找到一種設施點配置方式使得其覆蓋的需求點盡可能的多。其中情形一為集合覆蓋問題，而情形二為最大覆蓋問題。當然，對于如何確定設施點能夠覆蓋需求點，不同的方法又會得到其他的形式，比如，變半徑覆蓋，概率覆蓋以及多重覆蓋等。同時，目標函數和約束條件的稍微變化又可以得到不同擴展類型的覆蓋問題。下文主要按照圖1的劃分對重要的覆蓋選址問題進行分類評述，對于每一類問題，同時給出基本的數學規劃模型。

　　由于基本覆蓋模型的應用較為廣泛，其符號記法一般也稍有差異，在介紹各個模型之前，先對部分符號做如下規定：

　　i： 需求點標號;

　　j： 設施點標號;

　　V： 需求點集合;

　　W： 設施點集合;

　　r： 服務半徑;

　　2.1 確定性覆蓋模型

　　2.1.1 集合覆蓋(Location Set Covering Problem， LSCP)

　　其中目標函數(1)式要求建立的服務設施點數量最小;約束(2)式規定，對每一個需求點，至少有一個設施點可以對其提供服務;(3)式是變量取值類型約束。在上述LSCP模型中，如果考慮不同設施點的成本因素，要使建造成本最小，則可以得到加權集合覆蓋模型(WSCP)：

　　s.t.(2)～(3)

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

　　1969年，Roth[35]提出了求解覆蓋問題局部最優解的計算機算法，由于其目標函數是加權和最小形式，因此并不嚴格屬于集合覆蓋問題(Set Covering Problem， SCP)，而是一般意義上的加權集合覆蓋問題(Weighted Set Covering Problem， WSCP)。另外，由于該文獻最初并不是基于選址問題而提出，這就造成后來人們在回顧LSCP的研究文獻時常常將Roth的研究工作忽略。 　　 1971年，Toregas等[8]正式建立了應急服務設施的LSCP數學規劃模型，當服務設施點具有相同的成本時，目標函數轉化為建立最少的服務設施點以覆蓋所有的需求點。事實上，這是Roth模型中目標函數權系數相同的特殊情況，但是在選址理論中，一般認為Toregas等人是LSCP數學模型的最早提出者。

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

　　Alminana和Pastor[37]提出了一種改進形式的代理啟發式算法(Surrogate Heuristic)用以求解LSCP。Brotcorne等[19]提出了求解需求點離散、潛在設施點連續的大規模覆蓋選址問題的快速啟發式算法。

　　以上等人的研究大多屬于標準的SCP，要覆蓋的目標對象為網絡或者平面上的點集。對于其他形式的集合覆蓋問題，Boffey和Narula[38]，Gendreau等[39]分別提出了路徑覆蓋和回路覆蓋問題，Current和Storbeck[40]研究了有容量約束的LSCP，Murray

　　等[41]提出了另外兩種隱式和顯式的LSCP模型。

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

　　2.1.2 最大覆蓋(Maximal Covering Location Problem， MCLP)

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

　　其中目標函數(5)式最大化覆蓋的需求量;約束(6)式是需求點被覆蓋時應滿足的條件;約束(7)式規定了建立設施點的最大數量;約束(8)和(9)式為變量取值類型。

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

　　在實踐應用方面，MCLP模型主要用于解決應急服務設施的選址問題。Bennett等[44]應用MCLP模型，研究了邊遠地區的醫療資源的選址問題;Eaton等[45-46]將MCLP模型應用到現實中的應急醫療車輛的選址問題中。Richard等[47]應用MCLP模型研究了保護區的選擇問題，最大化能夠覆蓋的物種數量。Li等[48]綜述了覆蓋模型在應急服務設施選址和規劃方面的應用，Chung[49]綜述了覆蓋選址模型在其他方面的應用，如數據提取、統計分類和認知過程建模等。

　　確定性覆蓋模型在應用過程中也存在一定的問題，最為主要的便是覆蓋半徑的確定。早期的文獻一般是規定一個事先給定的半徑，在此半徑內可以完全覆蓋，否則不覆蓋。因此，這種覆蓋方法也被稱為0～1覆蓋。針對這種兩元劃分標準，后來的研究文獻分別提出了變半徑覆蓋[50]、逐漸覆蓋[51-54]等擴展模型。Berman等[55]對以上兩種一般的覆蓋模型以及合作覆蓋模型做了分類綜述。 　　 早期覆蓋模型的另一個缺陷是：只要需求點位于設施點的覆蓋半徑內，任何情況下服務設施點都可以對需求點提供服務。這種假設顯然對于那些服務設施點經常處于繁忙狀態的系統過于嚴格。因此，后來提出了備用覆蓋和合作覆蓋模型來提高服務水平。如Hogan和ReVelle[56]較早地提出了用額外一個設施點作為備用覆蓋的研究思路并介紹了其應用;Pirkul和Schilling[12]考慮了有工作能力和備用服務的應急服務設施選址問題;Curtin[57]建立了警察巡邏區域的最大覆蓋以及備用覆蓋模型，以上等研究只考慮一級備用覆蓋。Narisimhan等[58]建立了有容量約束和不同等級的備用覆蓋模型，Berman[59]提出了位于平面上、并且服務設施點發出的“信號”能夠因疊加而增強的合作覆蓋模型。

　　2.2 概率覆蓋模型

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

　　2.2.1 最大期望覆蓋(Maximal Expected Coverage Location Problem， MEXCLP)

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

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

　　其他符號如前文所述。目標函數(10)式最大化概率加權意義下的覆蓋量;約束(11)式代表能夠對每個需求點提供服務的服務設施數量限制;約束(12)式是總的服務設施數量限制，當然也可以取小于等于形式，由于目標函數最大化，兩者等價;約束(13)和(14)式是變量取值類型條件。

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

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

　　通過對基于區域的服務繁忙概率進行估計，ReVelle和Hogan[70]提出了概率形式的集合覆蓋選址模型。在計算需求點i附近的服務設施點的繁忙概率時，他們使用以下計算公式：

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

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

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

　　考慮到服務設施的繁忙情形，概率集合覆蓋要求被覆蓋的需求點必須在給定的服務水平下能夠得到服務。顯然，這比LSCP模型假定所有被覆蓋的需求任何時候都可以得到服務更符合實際，尤其是對于經常處于繁忙狀態的系統而言。

　　2.2.3 最大可獲的性覆蓋(Maximal Availability Location Problem， MALP)

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

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

　　Chiyoshi和Morabito[79]設計了求解擴展的MALP模型的禁忌搜索算法，并同模擬退火算法的結果進行了比較：對于小規模的問題，模擬退火算法的效果較好;而大規模的問題，禁忌搜索算法所得到的解較好。

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

　　3 結 論

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

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

　　注：①在其文獻中稱之為Minimum Cardinality Set Covering Problem(MCSCP)，也有文獻稱為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]. 運籌與管理，2005，14(6)：1-7.

　　[6] 王非，徐渝，李毅學. 離散設施選址問題研究綜述[J]. 運籌與管理，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.