選址問題是運籌學中經典的問題之一。選址問題在生產生活、物流、甚至軍事中都有著非常廣泛的套用，如工廠、倉庫、急救中心、消防站、垃圾處理中心、物流中心、飛彈倉庫的選址等。選址是最重要的長期決策之一，選址的好壞直接影響到服務方式、服務質量、服務效率、服務成本等，從而影響到利潤和市場競爭力，甚至決定了企業的命運。好的選址會給人民的生活帶來便利，降低成本，擴大利潤和市場份額，提高服務效率和競爭力，差的選址往往會帶來很大的不便和損失，甚至是災難，所以，選址問題的研究有著重大的經濟、社會和軍事意義。
基本介紹
- 中文名：選址問題
- 外文名：Location problem
簡介,研究內容 ,來源,分類,綜述,基本問題,擴展空間,
簡介
研究內容
選址問題研究內容十分廣泛，從城市、產業帶、經濟技術開發區、跨國經濟集團分公司到機場、水利設施、人類居住區、銷售網點以及倉庫、配送中心等的區位決策都是選址問題研究的範疇，涉及經濟、政治、社會、管理、心理及工程地質等多門學科。設施選址是眾多選址問題的一個重要研究領域。所研究的設施是指與生產、商業流通及人類生活有關的用地規模相對較小的具體網點、場所，如工廠、倉庫、消防站、變電站、污水處理中心，加油(氣)站等。研究方法主要依靠運籌學、拓撲學、管理學等計量方法，這是設施選址與其他選址問題的重要區別。
來源
1909 年，Weber 研究了在平面上確定一個倉庫的位置使得倉庫與多個顧客之間的總距離最小的問題(稱為韋伯問題) ，正式開始了選址理論的研究。1964 年，Hakimi 提出了網路上的p-中值問題與p-中心問題，這篇具有里程碑意義的論文大大激發了選址問題的理論研究，從此，選址理論的研究開始活躍起來，文獻數目也急劇增多。
分類
選址研究中的典型問題，如Weber（韋伯） 問題、中值問題、覆蓋問題、中心問題、多目標選址、競爭選址、不受歡迎的設施選址、選址-分配、選址-路線等，都是引起廣泛關注和深入研究的熱點課題，研究的也較為成熟。
綜述
基本問題
（1）P-中位問題（p-median problems）
P-中位問題（也叫P-中值問題）是研究如何選擇P個服務站使得需求點和服務站之間的距離與需求量的乘積之和最小。Hakimi提出該問題之後給出了 P-中位問題的 Hakimi 特性，他證明了 P-中位問題的服務站候選點限制在網路節點上時至少有一個最優解是與不對選址點限制時的最優解是一致的，所以將網路連續選址的 P-中位問題簡化到離散選址問題不會影響到目標函式的最優值。Goldman給出了在樹和只有一個環的網路上為單個服務站選址中位問題的簡單算法。Miehle 於 1958 年也研究過平面1-中位問題，也就是Weber 問題，是他發現了 Weiszfeld 的研究成果，被選址-分配問題的里程碑文章 Cooper譽為 Weiszfeld 研究的發現者。對於空間 P-中位問題，也就是更一般的Weber 問題，Rosing提出了最優解法。Garey 和 Johnson證明了 P-中位問題是 NP-困難問題。Francis、Francis 和 Cabot、Chen以及 Chen 和 Handler研究了基於歐氏距離的 P-中位問題。
（2）P-中心問題（p-center problems）
P-中心問題也叫 minmax 問題，是探討如何在網路中選擇 P 個服務站，使得任意一需求點到距離該需求點最近的服務站的最大距離最小問題。Hakimi首先提出網路中 P-中心問題，Kariv 和 Hakimi證明了 P-中心問題為 NP-困難問題。Drezner 和Wesolowsky提出了 Drezner-Wesolowsky 法解決多服務站的 P-中心問題。Francis在平面上的 P-中心問題研究中取得一些進展, Wesolowsky研究基於直線距離 P-中心問題；十年後，Chen、Ward 和 Wendell對基於歐幾里德距離的 P-中心問題作了研究。Masuyayma，Ibaraki 和 Hasegawa、Megiddo 和 Supowit證明了基於直線距離和歐氏距離的 P-中心問題都是 NP-完全問題。C. Caruso 等通過求解一系列集覆蓋的問題的辦法求解 P-中心問題。Hassin, Levin, Morad D提出了運用詞典區域局部搜尋法來求解 P-中心問題。Yuri Levin,Adi Ben-Israel對大規模 P-中心問題給出了啟發式算法，對一些著名的問題進行了計算分析。
（3）覆蓋問題（covering problems）
覆蓋問題分為最大覆蓋問題和集覆蓋問題兩類。集覆蓋問題研究滿足覆蓋所有需求點顧客的前提下，服務站總的建站個數或建設費用最小的問題。集覆蓋問題最早是由 Roth和 Toregas等提出的，用於解決消防中心和救護車等的應急服務設施的選址問題，他們分別建立了服務站建站成本不同和相同情況下集覆蓋問題的整數規劃模型。隨後 Minieka、Moore 和 ReVelle等都繼續研究集覆蓋問題。Plane 和Hendrick、Daskin 和 Stern建立了服務站個數最小和備用覆蓋的顧客最大的雙目標集覆蓋問題。Heung-Suk Huang研究了產品會隨時間變壞或變好時的動態集覆蓋問題。自2000年以來許多基於啟發式的算法被用於解決集覆蓋問題，M.L. Fisher 和 P.Kedia提出了基於對偶的啟發算法並用來解決最多有 200 個候選點、2000 個需求點的集覆蓋問題；Beasley J.E. 和 Jornsten. K將次梯度最佳化法和拉格朗日鬆弛算法結合起來求解這類問題；Marcos Alminana 和 Jesus T. Pastor套用代理啟發式算法求解集覆蓋問題。J.E. Beasley 和 P.C. Chu給出了求解服務站建站成本不同時集覆蓋問題的遺傳算法。Grossman 和 Wool[56]用大量的實驗對比了九種用於求解 SCLP 的啟發式算法，其中隨機貪婪算法(R-Gr)、簡單貪婪算法(S-Gr)和轉換貪婪算法(Alt-Gr)在幾乎所有問題中都是最好的前四種算法之一，其中隨機貪婪算法表現最好，在 60 個隨機問題中有 56 次獲得最好的解。Karp證明了集覆蓋問題是 NP-完全問題。
最大覆蓋問題或 P-覆蓋問題是研究在服務站的數目和服務半徑已知的條件下，如何設立 P 個服務站使得可接受服務的需求量最大的問題。同其它基本問題一樣，最大網路覆蓋問題也是 NP-困難問題(Marks.Daskin)。最初的最大覆蓋問題是由 Church RL 和 ReVelle C提出的，他們將服務站最優選址點限制在網路節點上；Church RL和 Meadows ME在確定的關鍵候選節點集合中給出了一般情況下的最優算法，他們通過線性規劃的方法求解，如果最優解不是整數就用分枝定界法求解；Church 和Meadows提出了最大覆蓋問題的偽 Hakimi 特性，即在任何一個網路中，存在一個有限節點的擴展集，在這個集合中至少包含一個最大覆蓋問題的最優解。Benedict，Hogan 和 ReVelle，Daskin考慮服務系統擁擠情況下的最大覆蓋問題，他們把任意一個服務站繁忙的機率當作外生變數，目標函式是服務站可以覆蓋的期望需求量最大。Haldun Aytug 和 Cem Saydam用遺傳算法來求解大規模最大期望覆蓋問題，並進行了比較。Fernando Y等對最大期望覆蓋問題中排隊與非排隊的情況進行了對比。Berman研究了最大覆蓋問題和部分覆蓋問題之間的關係。Oded Berman 和 DmitryKrass 、Oded Berman, Dmitry Krass 和 Zvi Drezner討論比傳統最大覆蓋問題更一般的最大覆蓋問題，並給出了拉格朗日鬆弛算法。Orhan Karasakal 和 Esra K.Karasakal討論了部分覆蓋問題，對覆蓋程度進行了定義。Jorge H. Jaramillo、Joy Bhadury 和 Rajan Batta在選址問題的遺傳算法套用研究時介紹了最大覆蓋問題遺傳算法的操作策略。
擴展空間
在前面三個基本選址問題的基礎上考慮其它因素就形成了擴展選址問題。由於擴展選址問題是由不同的分類方法根據實際套用需要組合而成，所以各類型之間存在較大的交叉，這裡僅以最具代表特徵的部分對不同的類型命名並進行綜述。
（1）帶固定費用和容量限制的選址問題
最容易也最常想到也最有實際意義的就是考慮服務站建站的固定費用和服務站的容量(服務能力)限制這兩個因素，所以早期對基本選址問題的擴展研究較多地集中在將這兩個因素加進基本選址問題上。無容量限制固定費用下的選址問題(UFLP)就是將固定建站費用加到 P-中位問題的目標函式上，並且去掉對服務站建站個數的約束。Cornuejols、Fisher 和 Nemhauser對該問題進行了細緻的分類和具體的分析，Swain運用 Bender 分解法求解 UFLP，Barros 和 Labbe、Holmberg對 UFLP 進行了更深入的研究。Geoffrion 和 McBride研究用拉格朗日算法解決帶容量限制的服務站選址問題。Mukundan 和 Daskin將固定費用有容量限制的選址問題模型(CFLP)用於解決利潤最大化的類似問題，Bender 分解法也被 Mark s. Daskin用來求解 CFLP。2011年5月Hinojosa，Puerto 和 Fernandez研究了多產品帶容量限制的服務站選址問題，Melkote和 Daskin總結了網路上帶容量限制的服務站選址問題的各種模型。Roberto Baldacci等提出了一種基於集剖分的方法來求解容量限制的選址問題。
（2）截流問題
截流問題研究顧客需求產生在路線上的問題，根據服務站工作性質可以分為服務型和對抗型兩大類。服務型截流問題廣泛套用於交通規劃、交通服務、交通監測等方面，比如如何在交通路網中設立交通量觀測點使監測到的交通流量最大的問題就是服務型截流問題。對抗型截流問題用於解決收費、檢查、緝私等站點的選址問題。Hodgson，Berman、Fouska 和 Larson最早提出截流問題，研究了需求路線確定的條件下，給定設施的數目，如何在網路中選址使通過服務站的需求量總和達到最大的截流問題，並建立了此類問題的基本模型，提出了啟發式的貪婪算法來求解截流問題模型。Mirchandani 、Rebello 和 Agnetis通過基本截流問題向集覆蓋問題的轉換證明了基本的截流問題是 NP-困難問題。Hodgson 等研究了服務站的顧客流量是由兩部分組成的截流問題，一部分是產生於日常路線上的過路需求，另一部分是產生於節點的固定需求Averbakh、Berman研究了顧客流量細分和接受多次服務的一般模型和擴展模型。Berman 和 Krass首先給出了競爭環境下的服務站截流選址問題，並給出了啟發式算法和最壞情況分析。Mirchandani、Rebello 和 Agnetis最早提出了對抗型服務站的截流問題。Yang.H和 Yang.C研究了用戶路線不確定條件下，檢查站設在網路的邊上的截流問題，建立了線性規劃模型，並用列生成法求得精確解。
（3）Hub 選址問題
（4）選址－分配問題
選址－分配問題的一般形式類似於 P-中位問題，最初由 Curry 和 Skeith提出這一問題。Geoffrion 和 Graves開始研究多級服務站選址－分配問題。Wesolowsky 和Truscott研究了多階段的選址分配問題，並用 Bender 分解法求解配送中心選址問題。oodchild、Hodgson也參與了這個問題的研究並對選址－分配問題進行了理論回顧。Marianov 和 Serra D研究了受等待時間或排隊約束的多服務中心選址－分配問題。Luce Brotcorne、Gilbert Laporte 和 Frederic Semet以救護車為背景的選址－分配問題研究現狀進行了總結。
（5）隨機選址問題
隨機選址問題中考慮到現實世界的複雜性，把服務站的運行時間、建設成本、需求點位置、需求數量等部分或全部輸入參數看作是不確定的。隨機選址問題分為隨機機率問題和隨機情景問題。隨機機率問題是指輸入參數是服從某種分布時的隨機選址問題。Carbone在解決需求不確定下公共設施的網路選址問題時開始研究了需求量服從多變數常態分配、帶機會約束的 P-中位問題，建立了非線性模型。Weaver 和Church研究在任意弧長服從離散隨機分布的隨機網路上的中位問題，建立了整數規劃模型並用拉格朗日鬆弛算法和替代啟發式算法求解。Berman 和 Odoni、Berman和 LeBlanc研究了行程時間狀態隨馬爾可夫狀態轉移矩陣變化的多設施選址問題。Mirchandani研究了行程時間、供應與需求模式都是隨機變化的條件下的 P-中位問題和無容量限制固定費用的倉庫選址問題。Daskin在研究EMS車輛選址問題時，研究考慮運輸車輛繁忙機率的最大覆蓋期望問題。ReVelle 和 Hogan在集覆蓋的背景下考慮車輛可用性的問題，並在最大覆蓋的基礎上研究可靠度的 P-中心問題。Ghosh 和 Craig研究了只有兩個賣主的壟斷市場、固定的市場需求量、多零售點的隨機選址問題。隨機情景問題是將不確定的性分解成多個可能在將來發生的狀態，同隨機機率選址問題相區別的是它是離散的隨機問題，模型的目標是在所有可能的情況下達到最佳。Vanston 等研究了情景建模的方法，給出了12 種生成合適情景的步驟，Amara和 Lipinski、Georgantzas 和 Acar和 Van der Heijden作了更進一步的研究。隨機情景模型的目標最少有三種方式：所有情景下的期望值最好、最壞情景下的目標值最優、所有情景下的期望遺憾度或最壞情景下遺憾度最小。Averbakh 和 Berman研究了間隔需求不確定條件下最小遺憾度的網路 P-中心問題。D.Serra、S.Ratick 和 C.ReVelle和 D. Serra、V. Marianov通過建立多種需求情景，建立了目標函式為服務的最小需求最大和最大遺憾度最小的兩個隨機情景問題模型，在他們用此辦法解決巴塞隆納的消防站選址決策的問題中，網路節點需求和行程時間都是不確定的。A.Ghosh 和 S.L. McLafferty套用這種方法解決了環境不確定時零售連鎖店選址問題，目標是使市場份額最大化。
（6）動態選址問題
現實世界中不僅存在著不確定性，也存在著動態性，因此動態模型能更準確地反映實際問題，當然，考慮動態因素不可避免地會增加模型的複雜性和求解的難度。動態選址問題研究的是在未來若干時間段內服務站的最優選址問題，在不同的時間段內動態選址模型的參數值是不同的，但在某一具體的時間段內模型參數是確定的。R.HBallou在有限個計畫的時間段內為單個倉庫選址的問題中，建立了以利潤最大化為目標的動態模型，並運用一系列的靜態確定型最優選址策略來解決這個多階段的動態選址問題。D.J. Sweeney 和 R.L. Tatham通過增加備選服務站集改善了 Ballou 的算法。A.J. Scott研究多個設施多階段的選址－分配的問題，並套用近視算法（myopic algorithm）來求解。C.S. Tapiero研究了有運輸成本和服務站有容量限制的動態選址－分配模型。T.J. VanRoy 和 D. Erlenkotter研究了不帶容量限制的動態選址問題，允許早期建立的服務站在一定時間後關閉。Z. Drezner提出了漸進式 P-中位問題，研究需求隨時間分階段變化，不考慮分配問題，目標是在整個時間範圍內總的運輸費用最低。G. Gunawardane在研究公用設施的選址問題中建立了動態的集覆蓋問題和最大覆蓋問題模型，考慮了未來若干時間段的覆蓋情況。
（7）競爭選址問題
競爭選址問題考慮市場上存在兩個以上的同類產品或服務的提供者，或服務站提供多個產品或服務。目前的競爭選址研究集中在靜態問題上，考慮確定和隨機兩種情況，研究背景多以連鎖零售業為主。靜態確定型的競爭選址問題是在現存的競爭者已知而且確定，顧客只到最有吸引力的服務站的“全有全無”假設的條件下研究的，靜態隨機競爭選址問題是在 Huff的引力模型的基礎上研究的。Hotelling H.在 1929 年首先提出了兩家賣主寡頭壟斷的市場競爭模型。Nakanishi 和 Cooper在競爭選址研究中提出了一個影響市場份額分配的效用函式。Hakimi研究了競爭環境下的 P-中位問題。T. Drezner在向現有服務站集增建一個服務站的問題中引入了考慮服務站品質引力和平衡距離的效用函式，建立了確定競爭選址模型。T. Drezner 和 Z. Drezner研究了效用函式決定顧客選擇服務站的機率，新建服務站的市場份額期望最大的選址問題。Marianov、Serra 和 ReVelle研究了競爭條件下無容量限制的 Hub 選址模型。Drezner 和 Z. Drezner 和 Salhi提出了套用模擬退火和 Ascent 相結合的算法求解新建服務站市場份額期望最大的競爭選址問題。
