連續設施選址：模型、方法與應用

張 蘇， 吳晨晨， 蔣建林， 呂一兵

(1.南開大學 商學院，天津 300071； 2.天津理工大學 理學院，天津 300384; 3.南京航空航天大學 理學院,江蘇 南京 210016; 4.長江大學 信息與數學學院,湖北 荊州 434023)

0 引言

早在17世紀早期Pierrede Fermat提出如下問題：平面上有坐標已知的三點，如何在平面上尋找到第四個點使得該點到給定三點的距離和達到最小？該問題即為選址領域中具有重要地位的Fermat問題(Fermat problem)。1909年Alfred Weber將Fermat問題推廣到有多個給定點且每個給定點都賦予權重(代表其需求)的情形，因而該問題常被稱為Fermat-Weber問題或Weber 問題。一般來說，設施選址領域中將上述給定點稱為顧客(customer)，而將需要選址的點稱為設施(facility)。盡管Weber問題似乎是有正式記載的最早的選址問題，但實際上設施選址一直伴隨著人類歷史的發展，它對人類的生活和生產活動有著重要而深刻的影響。

許多學科都存在著各式各樣的選址問題，不同學科對問題的描述不盡相同。綜合不同學科的描述可得到設施選址最本質的定義為：給定某個度量空間及其中的顧客位置，在該空間中為新設施選址使得由設施和顧客確定的某種目標達到最優。設施選址在現實生活中占據極其重要的地位，甚至具有戰略意義。半個多世紀以來隨著數學工具特別是優化技術被引入到設施選址中，該領域進入到了蓬勃發展的時期。人們對不同應用領域的設施選址問題進行了深入的研究和分析，建立了優化模型并研究其理論性質，提出了有效的數值算法求解模型并將研究結果應用于解決實際問題。

設施選址問題可以按不同方式進行分類。按照度量空間的拓撲結構設施問題可分為連續選址、離散選址、網絡選址。連續選址中新設施可以在度量空間的某連續區域上進行選址。連續選址在選址領域中的研究歷史最為悠久，前面提到的Weber問題即為其中的典型問題。離散選址是在度量空間中給定的一系列離散點上進行選址，而網絡選址則是在給定圖或網絡的頂點或邊上選址。就求解技術而言連續選址主要采用連續優化的方法如線性與非線性規劃進行求解，而離散選址和網絡選址由于包含了0-1變量多采用組合優化的方法和(混合)整數規劃進行求解。連續選址、離散選址和網絡選址在現實生活中均有著重要的應用，它們可用于解決不同情形下的實際問題。本文將對連續選址的模型、算法和應用等方面的研究工作進行回顧、總結并給出一些展望。需要指出的是，離散選址和網絡選址的理論和應用研究方面也都取得了大量的重要成果，相關工作請讀者們參考[1～5]及其中的文獻。

本文將按照如下結構展開連續設施選址工作的論述。第一章介紹連續設施選址中的幾個要素；第二章和第三章分別給出連續設施選址中的一些經典模型和拓展模型；第四章概述連續選址中某些重要方法和技術；第五章將簡述連續選址在實際生活中的應用；最后一章則對全文進行總結并給出研究展望。

1 連續設施選址中的幾個要素

本章將詳細介紹連續設施選址中的幾個關鍵元素，包括：新設施個數、距離度量函數、目標函數。其它影響選址決策的重要元素，如設施容量、土地費用、稅收政策等，我們在此將不一一贅述。

1.1 新設施個數

設施選址中新設施的個數m(m∈N)可能為1也可能大于1。當m=1時，此時問題一般稱為單設施選址(single-source location)問題；而當m≥2時，問題則被稱為多設施選址(multi-source location或者multi-facility location)問題。相比于單設施選址問題，多設施選址問題的求解會更加困難，這主要體現在如下幾方面：

設施的服務對象。多設施選址中需要考慮顧客到哪個設施獲取服務。為方便求解，我們常假設顧客到最近的設施獲得服務。然而這一假設并非在所有情形下都成立，如當顧客具有偏好、不同設施提供不同類型的服務等情形。

設施的容量約束。某些情況下顧客所需的服務量是有要求的但設施的容量(即設施能提供的服務量)卻是有限的，此時則需考慮設施的容量約束。帶設施容量約束的選址問題求解是非常困難的。

設施間的互動。在多設施情形下不同設施間可能存在著相互作用或互動(facility interaction)，此時需在優化問題的目標中引入反映設施間距離的項。

設施數m的確定。某些選址問題中設施數是給定的，但在另一些問題中設施數卻是內生變量，需要由選址問題本身在考慮各方面因素(如設施的固定費用、資金預算、選址目的等)后確定。

1.2 距離度量函數

選址領域有各種各樣的距離度量函數。范數是一種重要的距離度量函數，因其滿足正定性、齊次性和次可加性其度量的距離比較真實地反映了實際距離。lp-范數是連續選址中常用的距離度量函數：當p=1時該范數可以度量l1-距離(也稱為Manhattan距離)，該距離常用于表示城市內兩點間的距離；當p=2時該范數可以度量歐幾里得距離，它表示了兩點間的直線距離；當p=∞時該范數度量的距離常被稱為Chebyshev距離。某些推廣的lp-范數也常用于度量設施和顧客間的距離，比如加權lp-范數(weightedlp-norm，即klp-范數)、加權和lp-范數(weighted sumlp-norm，lbp-范數)等。

當連續設施選址中的顧客在度量空間中占有較大范圍時，則不應被簡單地視為點而應為區域，于是設施和顧客之間的距離就變為了點和區域的距離。點和區域的距離有多種度量方式，比如點到區域的最近距離、平均距離、最遠距離等。文獻[6,7]研究了顧客到設施最近距離意義下的選址模型[8,9]，研究了平均距離意義下的選址問題，而[10,11]則討論了最遠距離下的問題。進一步地，當顧客和距離均為所處空間內的區域時，此時距離則應為區域和區域間的距離，上述的最近距離、平均距離和最遠距離也需推廣到區域間的相應距離，甚至是一些更復雜的距離，如Hausdorff距離[12]。

設施并非總是在Rn空間內選擇合適的位置(特別地n=2時即為平面選址)，有時需要考慮在地球表面的某一區域內進行選址。當該區域范圍較大時，其不能簡單地視為平面的一部分，于是相應的問題就變為了球面選址問題。度量球面上兩點間的距離常采用測地線距離，即兩點所在的大圓上兩點的距離。測地線距離在度量球面上大尺度距離時會更接近于真實值，但測地線距離顯然比平面上范數度量的距離更加復雜。球面選址的理論分析和算法設計方面也取得了大量的研究成果，如[13～15]。

由范數度量的距離具有對稱性，即由點A到點B的距離等于由B到A的距離。但是距離具有對稱性并非在所有情形下都是成立的，比如：交通中同一道路不同向的擁堵情況、海洋中順洋流和逆洋流航行、高空順氣流和逆氣流飛行中都體現出距離的非對稱性。當范數定義中的齊次性減弱為正齊次性時，范數將退化為gauge。連續選址中常用gauge度量非對稱距離。盡管非對稱距離的連續選址研究也取得了一系列成果，但相比于對稱距離的選址研究卻要少得多。關于非對稱距離的研究成果讀者們請參考[16,17]。

不同的距離度量函數有著各自的優缺點和適用范圍，因此描述實際選址問題時需要我們充分發掘問題的特性以選擇合適的距離度量函數，這樣才能使得建立的數學模型更符合實際問題，基于該模型的理論、算法與應用研究也才更有意義和價值。

1.3 目標函數

設施選址的目標函數大致可分為拉式目標(pull objective)、推式目標(push objective)和推拉式目標(push-pull objective)三類[18,19]。當設施為顧客所期望(desirable)的類型(如超市、銀行、消防站等)時顧客總是希望設施離自己越近越好，因而往往采用拉式目標，如最小化顧客與設施間的距離和、最大化市場占有率等；當設施屬于被顧客排斥(undesirable)的類型(如有污染的工廠、垃圾處理站等)時顧客則希望設施離自己越遠越好，此時常采用推式目標，如最大化顧客與設施間的距離和、最小化被覆蓋的顧客數等；還有些情形下設施的類型介于desirable和undesirable之間，此時問題中將存在吸引和排斥兩個相互矛盾或對立的因素，這類選址問題常采用推拉式目標。

Minisum函數是一種常用的拉式目標：最小化顧客與設施間的(加權)距離和，相應的選址問題稱為minisum問題。Weber問題即為minisum問題，其設施數m=1。設施數m>1的問題被稱為多設施minisum問題，其中包含兩類重要問題：multi-facility Weber問題和multi-source Weber問題。Minimax 函數是另一種常用的拉式目標：最小化顧客與設施間的最大距離，相應的模型稱為minimax問題。因為該模型關注最遠的顧客所以在某種程度上體現了公平性。當m=1時相應的minimax問題為單設施選址問題；而對于m>1的多設施minimax問題其顧客與設施間距離常為顧客與最近設施間的距離。覆蓋問題也是使用拉式目標的重要問題。覆蓋問題包含最大覆蓋和最小(費用)覆蓋兩類問題：前者是在設施數給定的情形下讓設施覆蓋盡可能多的顧客，而后者則是在設施個數為變量時用最少的設施覆蓋所有的顧客。

與拉式目標類似，maxisum函數和maximin 函數是兩種重要的推式目標。Maxisum問題尋求顧客與設施間的距離和達到最大，而maximin則是使得顧客與設施間的最近距離最大化。當設施數m>1時，推式目標的多設施模型可分為max-min-min、max-sum-min、max-min-sum、max-sum-sum等幾類，其中第三層的min/sum表示給定顧客到所有設施間的最小距離或距離和。彌散模型(dispersion model)也是一種具有推式目標的重要模型。該模型僅考慮新設施間的最大距離(這也是將其命名為彌散模型的原因)。彌散模型的目標函數也有前述四類，此時第三層的min/sum表示給定設施到其他設施間的最小距離或距離和。即使是單設施推式目標的選址問題一般也是非凸的，求解這類問題時常用到全局優化和計算幾何方法。

由于推拉式目標中存在著吸引和排斥兩種對立的因素，推拉式目標的選址問題常可建模為雙目標優化。于是雙目標優化的方法和技術則可有效地用來求解推拉式目標的選址問題，比如：(1) 應用多目標優化的Pareto理論求出Pareto前沿面和Pareto有效點；(2) 給定推式目標的界并將之作為約束條件優化拉式目標；(3)給定拉式目標的界并將之作為約束條件優化推式目標；(4)利用線性加權技術將雙目標問題轉化為單目標問題求解。

2 連續設施選址經典模型

本章將介紹連續選址中的幾種經典模型，這些模型在連續選址領域占據著重要地位。首先，這些模型來源于實際問題，因此其本身就具有重要的應用性；同時基于這些模型可建立大量的更具實用性的選址模型，故這些模型也被稱為連續設施選址的基礎模型(fundamental models)。

2.1 Weber問題

盡管Weber問題為凸優化問題，其目標函數卻是不可微的，如當‖·‖為l2-范數時所有的顧客點處均不可微。選址領域將這一現象稱為奇異情形(singular case)。由于Weber問題在連續選址中的重要地位，該模型得到了深入和廣泛的研究。學者們提出了數值方法或計算幾何方法對其進行求解，同時也將其進行了各種各樣的推廣。在諸多求解方法中以Weiszfeld方法[20]最為著名。文獻[21]證明了該方法本質上為Weber問題的最速下降法，并且分析了該方法的收斂性和收斂速度。進一步地，文獻[22]將該方法推廣到了求閉凸集約束的Weber問題。為使得Weiszfeld方法能夠有效處理奇異情形，一些改進的Weiszfeld方法也不斷地被提出[23,24]。 關于Weber問題更豐富的理論與算法結果以及其推廣模型的研究請參考[25]。

2.2 Minimax問題

2.3 Multi-facility Weber問題

Multi-facility Weber問題(簡寫為MFWP)是一種重要的多設施minisum模型，其中每個設施提供的服務類型不同因而顧客需到各個設施處獲取服務，同時不同設施間存在著互動(facility interaction)。MFWP的數學模型為：

其中xi為第i個設施的位置，wij為第j個顧客到第i個設施距離的權重，vil為設施xi與xl距離的權重。

與Weber問題一樣，MFWP也是凸優化問題且不具備可微性(奇異情形)。Miehle算法是求解l2-范數下MFWP最早的算法，它可以看作是Weiszfeld算法在多設施選址問題上的推廣。Miehle算法也存在著與Weiszfeld 算法相同的問題，即不能有效地處理奇異情形，因此其產生的迭代序列可能發散或收斂到非最優解。Hyperboloid approximation procedure(HAP)則是將小正數ε引入到MFWP 的目標函數使其光滑化后再運用類似Miehle的方法求解光滑化問題。HAP可能是目前求解l2-范數下MFWP最標準的算法，其優點在于算法簡單易實現，但其缺點也是顯而易見的：需選擇合適的正數ε。最近文獻[28]考慮了一種推廣的MFWP，其中的設施帶有約束且gauge被用作為距離度量函數。文獻基于變分不等式的框架對該問題進行了研究并提出了數值算法：首先將該模型等價地轉化為變分不等式，然后基于該變分不等式的特殊結構設計投影算法求解該變分不等式從而得到推廣MFWP的最優解。基于變分不等式的方法可有效地處理奇異情形且不需引入小正數ε。

2.4 Multi-source Weber問題

盡管MSWP看似簡單，但它卻是非凸非光滑的NP-hard問題[29,30]。眾多學者對該問題的理論進行了廣泛的探討和研究并提出了有效的數值算法[31]。 在這些算法中最為重要的當屬起源于1964年的交替選址-分配類方法。注意到解決MSWP需完成兩個任務：確定m個設施的位置以及將n個顧客分配給m個設施。如果顧客已經分配給了m個設施(此時每個設施服務的顧客將形成一個cluster，于是所有顧客就分為了m個clusters)，若針對該顧客分配方式中的每個cluster求解一個單設施的Weber問題則可得到此分配方式下的最優設施位置(選址步)；同樣當確定了m個設施的位置后，最優的顧客分配方式應為所有的顧客均到離它最近的設施處獲得dj的服務量(分配步)。正是基于如上結論，交替選址-分配類方法設計了每步迭代均包含一次選址步和一次分配步并將選址步和分配步交替進行的迭代格式。在應用某些簡單的技術后，文獻[16]證明了交替選址-分配類方法能夠收斂到MSWP的局部最優解。關于交替選址-分配類方法讀者們可參考[32,33]及其中的文獻。

2.5 Multi-facility minimax問題

3 連續設施選址拓展模型

本章將簡單介紹連續設施選址領域中幾類拓展模型。這幾類拓展模型中的每一類都是連續選址的重要研究方向。當然除了這幾類模型外，連續選址中還有其它重要的拓展模型，如層級選址、動態選址、選址-庫存等。關于本章介紹的拓展模型和其他重要拓展模型更詳細的研究成果請參考[36,37]。

3.1 不確定設施選址(Facility Location under Uncertainty)

大量設施選址問題考慮的是長期的戰略決策。在此期間，情況會發生改變，比如顧客的需求水平、運輸的時間或成本、顧客的位置、商品的價格等。因此設施選址時有必要在模型中提前考慮不確定性，以便作出更好的決策。不確定設施選址模型的關鍵點在于不確定性如何表示。不確定性可用不確定參數來表示，不確定參數既可能是離散型隨機變量也可能是連續型隨機變量。當概率分布信息可得時，我們一般運用隨機規劃的模型和算法來考慮隨機設施選址問題；當概率分布信息不可得時，魯棒優化技術可被用來求解魯棒設施選址問題。

建模時需要考慮決策者對待風險的態度，常用的態度包括風險中性和風險厭惡兩種態度。風險中性的決策者考慮的是極小化期望成本或極大化期望收益；而風險厭惡的決策者常使用凹效用函數作為目標，比如尋求極小化最大成本的解。另一個需要考慮的因素為決策為事前決策還是事后決策。前者為當前所做的決策，必須在不確定性揭示之前實施；后者為不確定性揭示之后做出的決策，通常作為對不確定性參數觀測值的反應。在設施選址問題中，確定設施位置屬于事前決策，這是戰略決策的一種自然屬性；而分配或分布的決策則取決于問題的特點，它既可能是事前決策也可能是事后決策。

不確定設施選址一般會根據實際問題的特點綜合使用多種不確定優化工具。比如文獻[38]運用了魯棒優化求解多階段帶不確定需求的網絡設施選址問題，其中使用了箱形和橢球形的不確定集。文獻[39]考慮了帶容量限制的不確定多設施選址問題，其中將缺貨的概率上限作為機會約束。文獻中采用了不同的魯棒優化模型解決該問題。文獻[40]考慮了中斷風險下的可靠性設施選址問題，其目標為最小化開設成本和包含正常情形和中斷情形的期望運輸成本。

3.2 樞紐選址(Hub Location)

樞紐是起點和終點之間信息傳遞的戰略性設施。如何在起點和終點之間建立合適的樞紐以便降低服務成本同時提高服務質量，引起了專家學者們的關注。這類選址問題被稱為樞紐選址問題。當樞紐建成之后，運輸網絡就不需要在所有起點/終點之間直接連接，只需要通過樞紐進行運輸。為滿足起點和終點之間的運輸需求，樞紐選址問題涉及起點/終點對之間的人員、商品和信息流動等因素。

在樞紐選址問題中，O’Kelly做出了很多奠基性的重要工作，讀者們請參見[41～43]。

3.3 競爭選址(Competitive Location)

當建立新設施時決策者需要考慮很多因素，其中重要的一點為已經在市場中存在的競爭者，此時的選址問題被稱為競爭選址問題。

文獻[44]首先將競爭機制引入到選址問題中，其中的顧客均勻分布在長度為l的線段上。兩個具有競爭性的公司在線段上均開設一個設施為顧客提供相同的產品服務。公司除了需要決策各自設施的位置，還需要決策產品的價格。文獻[44]從博弈論的角度給出了該競爭選址問題的納什均衡點。然而，納什均衡點在實際中并不穩定：當選址決策或者選址的參數發生細微的擾動，均衡就會被破壞。于是另一種序列競爭選址模型應運而生，即在競爭中競爭的參與者們分別以領導者和跟隨者的身份進行斯塔克伯格博弈。文獻[45]討論了平面上跟隨者增加一個設施的斯塔克伯格博弈。文獻[46]考慮了3個設施的序列選址問題：領導者擁有一個已經存在的設施，跟隨者需要建立一個新的設施，之后領導者接著再建立一個設施。文獻[47]考慮了一個領導者和多個跟隨者的情形。

3.4 厭惡型選址(Obnoxious Facility Location)

很多選址模型的目標函數為最小化。當設施是服務型設施，這樣的設置自然是合理的。然而對于另一些設施如垃圾處理站、污水處理廠、核反應堆等顧客則希望這些設施離自己越遠越好，即這些設施為厭惡型設施，此時目標函數則變為最大化。

Maxisum厭惡型選址問題與minisum問題相反，需要設置m個設施使得顧客和距離其最近的設施距離和最大。文獻[48]考慮了平面上單設施的maxisum厭惡型選址問題。文獻[49]考慮了權重有正有負情況下平面上單設施minisum問題，其中的方法可以用于求解maxisum厭惡型選址問題。 Maximin厭惡型選址問題是指最大化顧客到設施的最小距離。文獻[50]考慮了平面和球面上單設施maximin厭惡型選址問題。文獻[51]研究了l1-范數下單設施maximin厭惡型選址問題，并提出基于線性規劃的搜索算法對其進行求解。

此外，顧客對醫院、消防站這類設施抱有的是半厭惡的心理，這樣就產生了半厭惡型選址問題(參見[52,53])。

3.5 選址-路徑(Location-Routing)

選址-路徑問題是設施選址問題與路徑選擇問題的組合。對于制造商和供應商而言，一個關鍵的問題是如何將產品從倉庫分發給位置分散的客戶。倉庫的位置以及產品的配送路徑是影響管理者成本的兩個關鍵因素。因此，確定倉庫位置并規劃產品配送路徑的同時優化構成了選址-路徑問題。

早期的連續選址-路徑問題通過將兩個決策獨立處理的啟發式方法進行求解：首先求解minisum問題確定倉庫的位置，再固定倉庫的位置解決多倉庫的車輛路徑問題[54]。文獻[55]將連續選址-路徑問題分解為確定倉庫位置和規劃車輛路徑兩種操作，并將兩種操作交替地迭代進行。文獻[56]使用神經網絡模型求解連續空間中的單倉庫選址-路徑問題。文獻[57]提出迭代啟發式方法求解飛機場的選址-路徑問題。文獻[58]首次提出了帶有取貨和送達時間限制的連續選址-路徑問題，并利用可變鄰域搜索算法求解。

4 連續設施選址常用方法與技術

大量的方法和技術被應用于連續設施選址中求解各種各樣的選址問題，而本章僅列出其中幾類有代表性的方法，包括：共軛對偶、全局優化、不確定優化、變分不等式、維諾圖。

4.1 共軛對偶(Conjugate Duality)

考慮設施選址(原始)問題的如下優化模型形式:

(原始問題)ming0(x0)

s.t.gi(xi)≤0,i∈I,(顯式約束)

x0∈C0,xi∈Ci,i∈I,(隱式約束)

x=(x0,xI)∈χ,(錐約束))

(1)

其中gi(xi),i∈{0}∪I是定義在凸集Ci上的閉凸函數，χ為閉凸錐。根據共軛對偶理論，其對偶問題如下:

i∈I,x*∈γ

(2)

可見共軛對偶理論得到的是最小-最小對偶，而非一般的最小-最大對偶。在滿足某些可行性和相對內點的條件下[60]，優化問題的最優性條件表達如下:

x0*∈?g0(x0)

(3)

其中?gi(xi)表示在xi點gi的次梯度集合。

文獻[61]對拓展的多設施選址問題分析了其共軛對偶結果，并以此作為最優性條件。文獻[62]在共軛對偶的框架下討論了帶幾何約束的線性和非線性單設施minimax問題，并給出了無約束線性minimax問題的對偶問題最優解的幾何表示。文獻[63]進一步考慮了帶擾動最小時間的非線性minimax問題，并在特定的情形下給出了其最優解的理論性質。

4.2 全局優化(Global Optimization)

連續設施選址中存在相當多的非凸模型。導致模型非凸的因素有很多：設施位置的約束具有非凸性；距離度量函數關于設施位置非凸；目標函數為設施位置的非凸函數；模型整體具有非凸性(如MSWP)。正因為非凸選址模型的普遍性，全局優化方法與技術[64～66]在其中具有極為重要的作用。本節僅討論幾種典型的連續選址全局優化方法。

分支定界法。分支定界法是求解(混合)整數規劃的重要方法，在離散和網絡選址中有著廣泛的應用。相對來說，分支定界法在連續選址中的應用要比在離散和網絡選址中少。連續選址的分支定界法也包含了分支和定界兩個操作：前者將可行域或包含可行域的區域劃分為小區域；后者對小區域判斷是否刪除該小區域或者將其繼續劃分為更小的區域。分支定界法在連續設施選址中主要表現為Big Square Small Square(BSSS)方法[67]，該方法將選址區域劃分為長方形小區域。為了使得BSSS方法計算效率更高或適用范圍更廣，各種推廣的BSSS方法不斷地被提出[68～70]。

Lipschitz優化。當連續選址模型的函數滿足Lipschitz條件且Lipschitz常數已知時可采用Lipschitz優化求解該模型。Lipschitz優化的思想是生成包含最優目標函數值的區間并不斷縮短該區間直至其長度小于給定的精度。由此可見，該方法的迭代過程中需不斷更新最優目標函數值的上界和下界。Lipschitz優化的難點在于：(1)Lipschitz常數不容易確定；(2)更新最優目標函數值下界時一般需求解非凸優化問題。

Polyhedralannexation(PA)方法。PA也是求解凹優化問題的重要方法之一，它可被視為OA方法求解凹優化問題的對偶，因此其也具有與OA方法相同的理論收斂性。與OA方法相比，PA方法不需要計算函數的梯度或次梯度(OA中引入直線l時往往需要求函數g(x)的梯度或次梯度)，但是需計算一系列凸優化子問題。

分解方法。大量的優化問題常包含兩類變量x和y，即變量為(x,y)。當固定變量y時，優化問題變為僅關于x的易解的優化問題(比如線性規劃、凸優化或規模較小的NP-hard問題)。分解方法利用優化問題的這一性質將原問題降為一系列低維的簡單問題進行求解。列生成算法被用于求解某些連續設施選址問題，該方法可以被看作為一類特殊的分解方法。

4.3 不確定優化(Optimization under Uncertainty)

在某些設施選址問題中，如果需求不確定但決策者仍希望滿足各種可能的需求，此時得到的解將會使得設施的容量大大高于正常的需求水平而造成浪費。一種解決方案為只需要保證一定的服務水平，也就是在某個給定的概率下設施的容量滿足總需求即可，于是我們將會考慮帶機會約束的設施選址問題。機會約束可被視為選址系統的某種可靠性的度量。

如何定義情景也是不確定優化中的重要問題。有時候情景來源于某些驅動因素(如經濟趨勢或技術變革)，顯然這些驅動因素將影響著模型的輸入。一般來說，驅動因素和不確定參數之間是高度相關的。決策者只有在完全理解這些驅動因素后才能夠生成情景的完備定義[72]。

4.4 變分不等式方法(Variational Inequality Approach)

變分不等式(variational inequality，VI)是近幾十年優化領域研究的熱點之一。它一方面可以描述經濟、交通、管理領域中大量的均衡問題，另一方面又可刻畫約束優化的一階必要性條件，因此吸引了運籌與優化學者們極大的關注。經過幾十年的快速發展，VI無論在理論還是算法上都已經相當成熟同時它在其它領域也已得到了廣泛的應用[73～80]。盡管相比于其它選址方法，變分不等式是一類較新的方法，但經過十余年的發展它已成為研究連續設施選址不可或缺的工具之一。

變分不等式方法求解連續設施選址問題的思路為：將凸選址問題或子問題通過原始-對偶等技術轉化為等價的變分不等式并基于其特殊結構設計有效的變分不等式求解算法。變分不等式方法求解設施選址問題的優點包括如下方面：(1)基于變分不等式成熟的理論和算法，變分不等式方法為連續設施選址的研究提供了一個不同于以往但非常有效的研究框架；(2)在變分不等式算法設計框架下，變分不等式方法可基于VI問題的特殊結構提出有效的新算法；(3)在變分不等式算法分析框架下，變分不等式方法易于證明新算法的收斂性質；(4)變分不等式方法能同時為設施選址問題提供原始最優解和對偶最優解；(5)變分不等式方法能夠有效地解決連續設施選址中的奇異情形。

文獻[81]可能是將變分不等式方法應用于連續設施選址研究的首項工作。該文獻針對lp-范數下帶凸約束的Weber問題提出了變分不等式的投影方法求解該問題。文獻[32]針對帶凸約束的MSWP 提出了一種新的交替選址-分配方法：選址步利用變分不等式方法設計新算法進行求解；分配步利用最近分配原則將顧客分配給最近設施。該交替選址-分配方法被證明可求得MSWP的局部最優解。文獻[82]考慮了不同區域采用不同距離度量函數的Weber問題。由于該問題為非凸優化問題，文獻[82]將其劃分為3個子問題并對其中2個較復雜的子問題設計了變分不等式方法進行求解。通過從3個子問題的最優解中選擇最好的解可求得該非凸Weber問題的全局最優解。文獻[28]研究了gauge距離下帶凸約束的推廣MFWP問題，并在變分不等式框架下提出了新的投影算法(該算法可被看作為非對稱PPA方法)求解該問題。

4.5 維諾圖(Voronoi Diagrams)

給定平面上的m個點X={x1,…,xm}，根據距離最近的原則將平面劃分成m個多邊形V1,…,Vm，這樣的劃分叫做維諾圖。構成維諾圖的多邊形被稱為維諾多邊形，而點的集合X被稱為生成集，其中的點被稱為生成點。維諾多邊形的數學表達為：Vi=∩j:j≠i{x∈R2|‖x-xi‖<‖x-xj‖}。根據定義，如果點x在Vi內，則xi為最靠近它的生成點。計算幾何中設計了很多高效算法計算維諾圖，其中兩種主要的方法為分治法(divide-and-conquer method)和遞增法(incremental method)[83]。分治法在最壞情形和平均情形下計算時間均為O(mlogm)，而遞增法在最壞情形下計算時間為O(m2)，平均計算時間為O(m)。

維諾圖是一種非常簡單的幾何構造，它在各個領域具有大量的應用。維諾圖的生成取決于距離度量函數，不同的度量函數生成不同的維諾圖。計算幾何中構造維諾圖的高效數值方法可被用來求解連續設施選址問題。特別地，多設施minisum問題和minimax問題均可以運用維諾圖求解。算法的一般框架為:

由算法的一般框架可見求解設施選址問題的每步迭代中均使用到維諾圖。文獻[84]提出了一個帶動態需求的混合型設施選址模型，并證明對于n個顧客和m個設施的c輪次問題，基于維諾圖的算法的計算復雜度為O(c(n2+m)logn)。文獻[85]考慮了兩類多設施厭惡選址問題，提出基于維諾圖和二元線性規劃的啟發式算法，其計算時間要比一些常用的非線性求解器要少得多。文獻[86]將維諾圖的概念進行了推廣，引入帶部分重疊區域的維諾圖。關于維諾圖在設施選址問題上的更多應用可參見文獻[87]。

5 連續設施選址的應用

在經濟生活和公共服務的選址中廣泛存在著成本和利潤的平衡。公司需要衡量能否通過增加設施而減少服務成本，政府需要衡量在何地建立設施可更好地服務民眾。在不同的實際應用場景中公司或政府均需要綜合考慮不同因素對選址的影響。以下從商業應用和公共服務兩方面介紹設施選址的應用。

5.1 商業應用

銀行是現代經濟中不可或缺的金融機構。隨著銀行業務的發展，銀行的分銷渠道，如信貸信用卡、電話-互聯網銀行、自動柜員機(ATM)等日益成熟。此外，銀行需要通過建立分行維持和發展客戶并開展業務。據統計，摩根大通、BB&T等國際銀行都在快速增加自己的分行數目以提升競爭力。在銀行選址中，需要考慮地址的商業屬性、客戶群體分布、具有競爭性的其他金融機構等因素。處理銀行選址的常見方法有數學規劃、元啟發式算法等。具體的研究可參見[88]。

由于電商行業的全球配送，“物流園”在現代物流業中發揮著越來越重要的作用。物流園通常包括倉庫、配送中心和物流相關公司/辦公室。物流園遍布世界各地，包括 美國伯靈頓北部物流園區、中國深圳平湖物流園區、荷蘭阿姆斯特丹物流園區等。物流園大多坐落在大城市的郊區，同時還需要考慮交通的便利性以及倉儲成本等因素，因此在物流園中存在著各種設施選址問題。具體研究可參見[89]。

森林是一種廣泛的自然資源，通常分布在數百萬公頃的土地上，因而林業是最受空間因素支配的自然資源產業。林產品供應鏈不僅僅是一條供應鏈，更是一條價值鏈。林產品供應鏈的長期、中期和短期各類規劃中均存在著重要的選址問題。林業選址中考慮的因素很多，如生態系統管理的戰略、林產品的產地、運輸點等。具體的研究可參見[90]。

5.2 公共服務

選址研究中的模型和算法長期以來一直應用于公共設施的規劃。以下僅以交通傳感器和消防站為例說明設施選址在公共服務中的應用。

根據中國公安部交管局發布的數據顯示，2017年全國汽車保有量達2.17億輛，而且車輛數量還在逐年增長。這樣的增長雖然提高了道路運輸網絡的利用率，但同時也帶來了擁堵和不安全因素。美國聯邦公路管理局的數據顯示全球每年交通事故導致的人員傷亡以百萬計。事實證明，采用智能交通系統(ITS)可顯著提高交通安全、減少交通擁堵。ITS使用先進的通信技術、傳感器技術和計算機技術解決交通問題并提高人貨流動的效率。ITS系統中需要安裝大量傳感器以便進行事故檢測和交通管理。傳感器的安裝即為典型的選址問題，其中需要考慮傳感器的覆蓋范圍、傳感器數量以及交通狀況等因素。具體研究可參見[91,92]。

由于特殊的社會屬性，消防站的選址變得非常重要。首先，消防站非常注重響應速度。快速的響應意味著救援人員能在盡可能短的時間內到達現場從而更有效地挽救生命和財產安全。其次，消防站建設的固定成本非常龐大，同時其使用過程中的人力成本也很巨大，這些都涉及到切實的財政問題。在消防站選址時需綜合考慮各種成本投入、位置的輻射范圍、周邊設施等因素。具體研究可參見[93,94]。

6 總結與展望

本文對連續設施選址進行了綜述，主要介紹了連續設施選址的要素、經典模型、拓展模型、方法與技術以及連續設施選址在現實生活中的一些應用。期望通過本文的介紹，感興趣的讀者們能夠對連續設施選址具備一定的了解并建立連續選址研究的基本框架，同時為其開展該領域的研究打好初步的基礎。

連續選址研究的展望主要包括如下三方面：

(1)模型。設施選址的研究本質上為實際問題驅動的研究，因此選址模型的建立應盡可能地反映實際選址問題的特點和需求。

模型的整合與拓展。連續設施選址的經典模型或基礎模型具有極其重要的地位。然而基于便于求解的考慮，這些模型可能忽略實際問題中的某些重要因素。對基礎模型進行整合或拓展并形成更豐富且更適用于實際應用場景的整合模型或拓展模型將是連續選址模型方面的重要工作之一。

模型的目標函數和參數。實際的連續選址問題中常存在多個決策目標，這些目標相互間可能存在一定的沖突，也有可能無法進行數學量化。因此建立部分目標具有模糊性或定性刻畫的多目標選址模型并對其進行研究是連續選址重要研究方向之一。同時，選址模型中一般都帶有參數。這些參數對數學模型模擬實際選址問題的準確度有著相當大的影響，因此研究參數對模型及決策結果的影響也是連續選址的重要研究內容。

(2)方法與技術。連續設施選址模型為連續優化問題，所以在求解這類模型時線性與非線性規劃發揮著重要作用。

精確算法與(元)啟發式方法。當連續選址模型的規模較小時，可以考慮設計小規模問題的精確算法。但對于整合模型或者拓展模型而言其規模非常大，求解就會復雜。考慮到數學模型總是實際問題某種程度上的近似，故很難界定該模型的最優解是否即為實際問題的最優設施位置。因此對于大規模選址問題設計快速的(元)啟發式方法求得其近似最優解有時比求得精確解更重要。將精確算法和(元)啟發式方法相結合設計混合算法也是一個比較有效的思路：利用(元)啟發式方法求得選址模型的近似解，再利用其作為精確算法的初始點求得選址模型的最優解。

優化技術的應用與發展。連續設施選址的研究涉及到大量優化技術，比如不確定優化、多目標優化、變分不等式等。另一方面，隨著大數據時代的來臨設施選址中會產生了大量的數據，故數據分析與處理技術也必不可少。這些技術在連續選址中的應用將極大地推動該領域的蓬勃發展。將已有的優化技術以及不斷發展的新技術應用于連續選址的研究也將是這一領域的重要發展方向。

(3)應用。設施選址研究的最終目的是要落地，即能夠真正解決實際選址問題，因此連續設施選址的應用研究也是非常重要的。

工業與管理角度。實際的選址問題都有其自身的特點，這就要求我們在進行設施選址應用研究時能夠真正地從工業與管理的角度出發建立適合于實際問題的整合模型、拓展模型或新模型。這是連續設施選址應用研究的第一步，顯然也是應用研究中的難點。

拓展應用范圍。將連續選址的模型、理論和算法與相關領域(如供應鏈、城市規劃等)的實際問題相結合開展多學科交叉的應用研究將是一項有意義的工作。此外，某些領域表面上與設施選址并無聯系，但實際上設施選址的理論和方法也可用于這些領域解決其中的實際問題。將設施選址的研究成果應用到這些領域從而拓展其應用范圍也是設施選址應用研究的工作之一。