本文關(guān)鍵詞：選址問題，由筆耕文化傳播整理發(fā)布。

選址問題綜述

〔轉(zhuǎn)自馬云峰〕現(xiàn)代選址研究起于 1909 年，當(dāng)時(shí) Alfred Weber 為解決如何為單個(gè)倉庫選址使得倉庫到多個(gè)顧客間的總距離最小的問題，他在歐氏空間里建立了一個(gè) 1-中位問題模型，就是著名的 Weber 問題。

1）基本選址問題

（1）P-中位問題（p-median problems）
　　P-中位問題是研究如何選擇P個(gè)服務(wù)站使得需求點(diǎn)和服務(wù)站之間的距離與需求量的乘積之和最小。Hakimi[13,16]提出該問題之后給出了 P-中位問題的 Hakimi 特性，他證明了 P-中位問題的服務(wù)站候選點(diǎn)限制在網(wǎng)絡(luò)節(jié)點(diǎn)上時(shí)至少有一個(gè)最優(yōu)解是與不對(duì)選址點(diǎn)限制時(shí)的最優(yōu)解是一致的，所以將網(wǎng)絡(luò)連續(xù)選址的 P-中位問題簡化到離散選址問題不會(huì)影響到目標(biāo)函數(shù)的最優(yōu)值。Goldman[17]給出了在樹和只有一個(gè)環(huán)的網(wǎng)絡(luò)上為單個(gè)服務(wù)站選址中位問題的簡單算法。Miehle 于 1958 年也研究過平面 1-中位問題，也就是 Weber 問題，是他發(fā)現(xiàn)了 Weiszfeld 的研究成果，被選址-分配問題的里程碑文章 Cooper[14] 譽(yù)為 Weiszfeld 研究的發(fā)現(xiàn)者。對(duì)于空間 P-中位問題，也就是更一般的Weber 問題，Rosing[18]提出了最優(yōu)解法。Garey 和 Johnson[19]證明了 P-中位問題是 NP-困難問題。Francis[20]、Francis 和 Cabot[21]、Chen[22]以及 Chen 和 Handler[23]研究了基于歐氏距離的 P-中位問題。
　　近年來，P-中位問題仍然是研究的熱點(diǎn)，許多學(xué)者研究 P-中位問題的各種變形和擴(kuò)展模型：Wesolowsky[24]、Wesolowsky 和ruscott[25]、Drezner[26]研究了動(dòng)態(tài) P-中位問題。ReVelle[27]將目標(biāo)函數(shù)定義為新建的服務(wù)站所占據(jù)的市場(chǎng)份額的最大化，成功地將中位問題運(yùn)用于競(jìng)爭環(huán)境下的零售商店選址問題中。Lorena、Senne[28]和 Luiz 等[29]運(yùn)用列生成方法解決帶容量限制的 P-中位問題。Berman 等[30]研究服務(wù)的可靠度隨著服務(wù)設(shè)施與需求的距離變化的設(shè)施問題問題。Church 提出了通過減少分配的變量來減少約束的傳統(tǒng) P-中位問題的新建模方法[31]。Drezner[32]、Chen[33]、Chen 和 Handler[34]在此基礎(chǔ)上研究條件中位問題，又稱 PQ-中位問題，即網(wǎng)絡(luò)中已存在 Q 個(gè)服務(wù)站的條件下，如何為 P 個(gè)同類服務(wù)站選址的中位問題。

（2）P-中心問題（p-center problems）
　　P-中心問題也叫 minmax 問題，是探討如何在網(wǎng)絡(luò)中選擇 P 個(gè)服務(wù)站，使得任意一需求點(diǎn)到距離該需求點(diǎn)最近的服務(wù)站的最大距離最小問題。Hakimi[13]首先提出網(wǎng)絡(luò)中 P-中心問題，Kariv 和 Hakimi[35]證明了 P-中心問題為 NP-困難問題。Drezner 和Wesolowsky[36]提出了 Drezner-Wesolowsky 法解決多服務(wù)站的 P-中心問題。Francis[37]在平面上的 P-中心問題研究中取得一些進(jìn)展, Wesolowsky[38]研究基于直線距離 P-中心問題；十年后，Chen[22]、Ward 和 Wendell[39]對(duì)基于歐幾里德距離的 P-中心問題作了研究。Masuyayma，Ibaraki 和 Hasegawa[40]、Megiddo 和 Supowit[41]證明了基于直線距離和歐氏距離的 P-中心問題都是 NP-完全問題。C. Caruso 等[42]通過求解一系列集覆蓋的問題的辦法求解 P-中心問題。Hassin, Levin, Morad D[43]提出了運(yùn)用詞典區(qū)域局部搜索法來求解 P-中心問題。Yuri Levin,Adi Ben-Israel[44]對(duì)大規(guī)模 P-中心問題給出了啟發(fā)式算法，對(duì)一些著名的問題進(jìn)行了計(jì)算分析。

（3）覆蓋問題（covering problems）
        覆蓋問題分為最大覆蓋問題和集覆蓋問題兩類。集覆蓋問題研究滿足覆蓋所有需求點(diǎn)顧客的前提下，服務(wù)站總的建站個(gè)數(shù)或建設(shè)費(fèi)用最小的問題。集覆蓋問題最早是由 Roth[45]和 Toregas[46]等提出的，用于解決消防中心和救護(hù)車等的應(yīng)急服務(wù)設(shè)施的選址問題，他們分別建立了服務(wù)站建站成本不同和相同情況下集覆蓋問題的整數(shù)規(guī)劃模型。隨后 Minieka[47]、Moore 和 ReVelle[48]等都繼續(xù)研究集覆蓋問題。Plane 和Hendrick[49]、Daskin 和 Stern[50]建立了服務(wù)站個(gè)數(shù)最小和備用覆蓋的顧客最大的雙目標(biāo)集覆蓋問題。Heung-Suk Huang[51]研究了產(chǎn)品會(huì)隨時(shí)間變壞或變好時(shí)的動(dòng)態(tài)集覆蓋問題。最近十幾年來許多基于啟發(fā)式的算法被用于解決集覆蓋問題，M.L. Fisher 和 P.Kedia[52]提出了基于對(duì)偶的啟發(fā)算法并用來解決最多有 200 個(gè)候選點(diǎn)、2000 個(gè)需求點(diǎn)的集覆蓋問題；Beasley J.E. 和 Jornsten. K[53]將次梯度優(yōu)化法和拉格朗日松弛算法結(jié)合起來求解這類問題；Marcos Alminana 和 Jesus T. Pastor[54]應(yīng)用代理啟發(fā)式算法求解集覆蓋問題。J.E. Beasley 和 P.C. Chu[55]給出了求解服務(wù)站建站成本不同時(shí)集覆蓋問題的遺傳算法。Grossman 和 Wool[56]用大量的實(shí)驗(yàn)對(duì)比了九種用于求解 SCLP 的啟發(fā)式算法，其中隨機(jī)貪婪算法(R-Gr)、簡單貪婪算法(S-Gr)和轉(zhuǎn)換貪婪算法(Alt-Gr)在幾乎
所有問題中都是最好的前四種算法之一，其中隨機(jī)貪婪算法表現(xiàn)最好，在 60 個(gè)隨機(jī)問題中有 56 次獲得最好的解。Karp[57]證明了集覆蓋問題是 NP-完全問題。

　　最大覆蓋問題或 P-覆蓋問題是研究在服務(wù)站的數(shù)目和服務(wù)半徑已知的條件下，如何設(shè)立 P 個(gè)服務(wù)站使得可接受服務(wù)的需求量最大的問題。同其它基本問題一樣，最大網(wǎng)絡(luò)覆蓋問題也是 NP-困難問題(Mark s.Daskin)[58]。最初的最大覆蓋問題是由 Church RL 和 ReVelle C[59]提出的，他們將服務(wù)站最優(yōu)選址點(diǎn)限制在網(wǎng)絡(luò)節(jié)點(diǎn)上；Church RL和 Meadows ME[60]在確定的關(guān)鍵候選節(jié)點(diǎn)集合中給出了一般情況下的最優(yōu)算法，他們通過線性規(guī)劃的方法求解，如果最優(yōu)解不是整數(shù)就用分枝定界法求解；Church 和
Meadows[60]提出了最大覆蓋問題的偽 Hakimi 特性，即在任何一個(gè)網(wǎng)絡(luò)中，存在一個(gè)有限節(jié)點(diǎn)的擴(kuò)展集，在這個(gè)集合中至少包含一個(gè)最大覆蓋問題的最優(yōu)解。Benedict[61]，Hogan 和 ReVelle[62]，Daskin[63]考慮服務(wù)系統(tǒng)擁擠情況下的最大覆蓋問題，他們把任意一個(gè)服務(wù)站繁忙的概率當(dāng)作外生變量，目標(biāo)函數(shù)是服務(wù)站可以覆蓋的期望需求量最大。Haldun Aytug 和 Cem Saydam[64]用遺傳算法來求解大規(guī)模最大期望覆蓋問題，并進(jìn)行了比較。Fernando Y[65]等對(duì)最大期望覆蓋問題中排隊(duì)與非排隊(duì)的情況進(jìn)行了對(duì)比。Berman[66]研究了最大覆蓋問題和部分覆蓋問題之間的關(guān)系。Oded Berman 和 DmitryKrass[67] 、Oded Berman, Dmitry Krass 和 Zvi Drezner[68]討論比傳統(tǒng)最大覆蓋問題更一般的最大覆蓋問題，并給出了拉格朗日松弛算法。Orhan Karasakal 和 Esra K.Karasakal[69]討論了部分覆蓋問題，對(duì)覆蓋程度進(jìn)行了定義。Jorge H. Jaramillo、Joy Bhadury 和 Rajan Batta[70] 在選址問題的遺傳算法應(yīng)用研究時(shí)介紹了最大覆蓋問題遺傳算法的操作策略。

2）擴(kuò)展選址問題
       在前面三個(gè)基本選址問題的基礎(chǔ)上考慮其它因素就形成了擴(kuò)展選址問題。由于擴(kuò)展選址問題是由不同的分類方法根據(jù)實(shí)際應(yīng)用需要組合而成，所以各類型之間存在較大的交叉，本文僅以最具代表特征的部分對(duì)不同的類型命名并進(jìn)行綜述。

（1）帶固定費(fèi)用和/或容量限制的選址問題
        最容易也最常想到也最有實(shí)際意義的就是考慮服務(wù)站建站的固定費(fèi)用和服務(wù)站的容量(服務(wù)能力)限制這兩個(gè)因素，所以早期對(duì)基本選址問題的擴(kuò)展研究較多地集中在將這兩個(gè)因素加進(jìn)基本選址問題上。無容量限制固定費(fèi)用下的選址問題(UFLP)就是將固定建站費(fèi)用加到 P-中位問題的目標(biāo)函數(shù)上，并且去掉對(duì)服務(wù)站建站個(gè)數(shù)的約束。Cornuejols、Fisher 和 Nemhauser[71]對(duì)該問題進(jìn)行了細(xì)致的分類和具體的分析，Swain[72]運(yùn)用 Bender 分解法求解 UFLP，Barros 和 Labbe[73]、Holmberg[74]對(duì) UFLP 進(jìn)行了更深入的研究。Geoffrion 和 McBride[75]研究用拉格朗日算法解決帶容量限制的服務(wù)站選址問題。Mukundan 和 Daskin[76]將固定費(fèi)用有容量限制的選址問題模型(CFLP)用于解決利潤最大化的類似問題，Bender 分解法也被 Mark s. Daskin[58]用來求解 CFLP。最近Hinojosa，Puerto 和 Fernandez[77]研究了多產(chǎn)品帶容量限制的服務(wù)站選址問題，Melkote和 Daskin[78]總結(jié)了網(wǎng)絡(luò)上帶容量限制的服務(wù)站選址問題的各種模型。Roberto Baldacci等[79]提出了一種基于集剖分的方法來求解容量限制的選址問題。

（2）截流問題
        截流問題研究顧客需求產(chǎn)生在路線上的問題，根據(jù)服務(wù)站工作性質(zhì)可以分為服務(wù)型和對(duì)抗型兩大類。服務(wù)型截流問題廣泛應(yīng)用于交通規(guī)劃、交通服務(wù)、交通監(jiān)測(cè)等方面，比如如何在交通路網(wǎng)中設(shè)立交通量觀測(cè)點(diǎn)使監(jiān)測(cè)到的交通流量最大的問題就是服務(wù)型截流問題。對(duì)抗型截流問題用于解決收費(fèi)、檢查、緝私等站點(diǎn)的選址問題。Hodgson[80]，Berman、Fouska 和 Larson[81]最早提出截流問題，研究了需求路線確定的條件下，給定設(shè)施的數(shù)目，如何在網(wǎng)絡(luò)中選址使通過服務(wù)站的需求量總和達(dá)到最大的截流問題，并建立了此類問題的基本模型，提出了啟發(fā)式的貪婪算法來求解截流問題模型。Mirchandani 、Rebello 和 Agnetis[82]通過基本截流問題向集覆蓋問題的轉(zhuǎn)換證明了基本的截流問題是 NP-困難問題。Hodgson 等[83]研究了服務(wù)站的顧客流量是由兩部分組成的截流問題，一部分是產(chǎn)生于日常路線上的過路需求，另一部分是產(chǎn)生于節(jié)點(diǎn)的固定需求。Averbakh、Berman[84]研究了顧客流量細(xì)分和接受多次服務(wù)的一般模型和擴(kuò)展模型。Berman 和 Krass[85]首先給出了競(jìng)爭環(huán)境下的服務(wù)站截流選址問題，并給出了啟發(fā)式算法和最壞情況分析。Mirchandani、Rebello 和 Agnetis[86]最早提出了對(duì)抗型服務(wù)站的截流問題。Yang.H和 Yang.C[87]研究了用戶路線不確定條件下，檢查站設(shè)在網(wǎng)絡(luò)的邊上的截流問題，建立了線性規(guī)劃模型，并用列生成法求得精確解。

（3）Hub 選址問題
        Hub 選址問題是和截流問題有些類似的選址問題，需求也是產(chǎn)生在 OD 對(duì)上，在顧客從 O 點(diǎn)出發(fā)到 D 的過程中要接受 Hub 的服務(wù)。同截流問題不同的是，OD 流并不是走最短路從 O 點(diǎn)到 D 點(diǎn)，經(jīng)過 Hub 中轉(zhuǎn)服務(wù)后要比直接從 O 點(diǎn)到 D 點(diǎn)要快，比如交通系統(tǒng)中的中轉(zhuǎn)站、通信系統(tǒng)的交換機(jī)或服務(wù)器等。O’Kelly[88,89]開創(chuàng)了 Hub 選址問題的研究工作，Marianov[90]研究了競(jìng)爭環(huán)境下的 Hub 選址問題，Kara 和 Tansel[91]研究了單分配 P-Hub 選址問題，Ebery 和 Krishnamoorthy[92]研究了帶容量限制多分配的 Hub 選址問題。

（4）選址－分配問題
        選址－分配問題的一般形式類似于 P-中位問題，最初由 Curry 和 Skeith[93]提出這一問題。Geoffrion 和 Graves[94]開始研究多級(jí)服務(wù)站選址－分配問題。Wesolowsky 和Truscott[95]研究了多階段的選址分配問題，并用 Bender 分解法求解配送中心選址問題。oodchild[96,97]、Hodgson[98]也參與了這個(gè)問題的研究并對(duì)選址－分配問題進(jìn)行了理論回顧。Marianov 和 Serra D[99]研究了受等待時(shí)間或排隊(duì)約束的多服務(wù)中心選址－分配問題。Luce Brotcorne、Gilbert Laporte 和 Frederic Semet[100]以救護(hù)車為背景的選址－分配問題研究現(xiàn)狀進(jìn)行了總結(jié)。

（5）隨機(jī)選址問題
        隨機(jī)選址問題中考慮到現(xiàn)實(shí)世界的復(fù)雜性，把服務(wù)站的運(yùn)行時(shí)間、建設(shè)成本、需求點(diǎn)位置、需求數(shù)量等部分或全部輸入?yún)?shù)看作是不確定的。隨機(jī)選址問題分為隨機(jī)概率問題和隨機(jī)情景問題。隨機(jī)概率問題是指輸入?yún)?shù)是服從某種分布時(shí)的隨機(jī)選址問題。Carbone[101]在解決需求不確定下公共設(shè)施的網(wǎng)絡(luò)選址問題時(shí)開始研究了需求量服從多變量正態(tài)分布、帶機(jī)會(huì)約束的 P-中位問題，建立了非線性模型。Weaver 和Church[102]研究在任意弧長服從離散隨機(jī)分布的隨機(jī)網(wǎng)絡(luò)上的中位問題，建立了整數(shù)規(guī)劃模型并用拉格朗日松弛算法和替代啟發(fā)式算法求解。Berman 和 Odoni[103]、Berman和 LeBlanc[104]研究了行程時(shí)間狀態(tài)隨馬爾可夫狀態(tài)轉(zhuǎn)移矩陣變化的多設(shè)施選址問題。Mirchandani[105]研究了行程時(shí)間、供應(yīng)與需求模式都是隨機(jī)變化的條件下的 P-中位問題和無容量限制固定費(fèi)用的倉庫選址問題。Daskin[106-108]在研究EMS車輛選址問題時(shí)，研究考慮運(yùn)輸車輛繁忙概率的最大覆蓋期望問題。ReVelle 和 Hogan[109]在集覆蓋的背景下考慮車輛可用性的問題，并在最大覆蓋的基礎(chǔ)上研究 可靠度的 P-中心問題。Ghosh 和 Craig[110]研究了只有兩個(gè)賣主的壟斷市場(chǎng)、固定的市場(chǎng)需求量、多零售點(diǎn)的隨機(jī)選址問題。隨機(jī)情景問題是將不確定的性分解成多個(gè)可能在將來發(fā)生的狀態(tài)，同隨機(jī)概率選址問題相區(qū)別的是它是離散的隨機(jī)問題，，模型的目標(biāo)是在所有可能的情況下達(dá)到最佳。Vanston 等[111]研究了情景建模的方法，給出了 12 種生成合適情景的步驟，Amara和 Lipinski[112]、Georgantzas 和 Acar[113]和 Van der Heijden[114]作了更進(jìn)一步的研究。隨
機(jī)情景模型的目標(biāo)最少有三種方式：所有情景下的期望值最好、最壞情景下的目標(biāo)值最優(yōu)、所有情景下的期望遺憾度或最壞情景下遺憾度最小。Averbakh 和 Berman[115]研究了間隔需求不確定條件下最小遺憾度的網(wǎng)絡(luò) P-中心問題。D.Serra、S.Ratick 和 C.ReVelle[116]和 D. Serra、V. Marianov[117]通過建立多種需求情景，建立了目標(biāo)函數(shù)為服務(wù)的最小需求最大和最大遺憾度最小的兩個(gè)隨機(jī)情景問題模型，在他們用此辦法解決巴塞羅那的消防站選址決策的問題中，網(wǎng)絡(luò)節(jié)點(diǎn)需求和行程時(shí)間都是不確定的。A.Ghosh 和 S.L. McLafferty[118]應(yīng)用這種方法解決了環(huán)境不確定時(shí)零售連鎖店選址問題，目標(biāo)是使市場(chǎng)份額最大化。

（6）動(dòng)態(tài)選址問題
        現(xiàn)實(shí)世界中不僅存在著不確定性，也存在著動(dòng)態(tài)性，因此動(dòng)態(tài)模型能更準(zhǔn)確地反映實(shí)際問題，當(dāng)然，考慮動(dòng)態(tài)因素不可避免地會(huì)增加模型的復(fù)雜性和求解的難度。動(dòng)態(tài)選址問題研究的是在未來若干時(shí)間段內(nèi)服務(wù)站的最優(yōu)選址問題，在不同的時(shí)間段內(nèi)動(dòng)態(tài)選址模型的參數(shù)值是不同的，但在某一具體的時(shí)間段內(nèi)模型參數(shù)是確定的。R.HBallou[119]在有限個(gè)計(jì)劃的時(shí)間段內(nèi)為單個(gè)倉庫選址的問題中，建立了以利潤最大化為目標(biāo)的動(dòng)態(tài)模型，并運(yùn)用一系列的靜態(tài)確定型最優(yōu)選址策略來解決這個(gè)多階段的動(dòng)態(tài)選址問題。D.J. Sweeney 和 R.L. Tatham[120]通過增加備選服務(wù)站集改善了 Ballou 的算法。A.J. Scott[121]研究多個(gè)設(shè)施多階段的選址－分配的問題，并應(yīng)用近視算法（myopic algorithm）來求解。C.S. Tapiero[122]研究了有運(yùn)輸成本和服務(wù)站有容量限制的動(dòng)態(tài)選址－分配模型。T.J. VanRoy 和 D. Erlenkotter[123]研究了不帶容量限制的動(dòng)態(tài)選址問題，允許早期建立的服務(wù)站在一定時(shí)間后關(guān)閉。Z. Drezner[26]提出了漸進(jìn)式 P-中位問題，研究需求隨時(shí)間分階段變化，不考慮分配問題，目標(biāo)是在整個(gè)時(shí)間范圍內(nèi)總的運(yùn)輸費(fèi)用最低。G. Gunawardane[124]在研究公用設(shè)施的選址問題中建立了動(dòng)態(tài)的集覆蓋問題和最大覆蓋問題模型，考慮了未來若干時(shí)間段的覆蓋情況。

（7）競(jìng)爭選址問題
       競(jìng)爭選址問題考慮市場(chǎng)上存在兩個(gè)以上的同類產(chǎn)品或服務(wù)的提供者，或服務(wù)站提供多個(gè)產(chǎn)品或服務(wù)。目前的競(jìng)爭選址研究集中在靜態(tài)問題上，考慮確定和隨機(jī)兩種情況，研究背景多以連鎖零售業(yè)為主。靜態(tài)確定型的競(jìng)爭選址問題是在現(xiàn)存的競(jìng)爭者已知而且確定，顧客只到最有吸引力的服務(wù)站的“全有全無”假設(shè)的條件下研究的，靜態(tài)隨機(jī)競(jìng)爭選址問題是在 Huff[125]的引力模型的基礎(chǔ)上研究的。Hotelling H.在 1929 年首先提出了兩家賣主寡頭壟斷的市場(chǎng)競(jìng)爭模型。Nakanishi 和 Cooper[126]在競(jìng)爭選址研究中提出了一個(gè)影響市場(chǎng)份額分配的效用函數(shù)。Hakimi[16]研究了競(jìng)爭環(huán)境下的 P-中位問題。T. Drezner[127]在向現(xiàn)有服務(wù)站集增建一個(gè)服務(wù)站的問題中引入了考慮服務(wù)站品質(zhì)引力和平衡距離的效用函數(shù)，建立了確定競(jìng)爭選址模型。T. Drezner 和 Z. Drezner[128]研究了效用函數(shù)決定顧客選擇服務(wù)站的概率，新建服務(wù)站的市場(chǎng)份額期望最大的選址問題。Marianov、Serra 和 ReVelle[129]研究了競(jìng)爭條件下無容量限制的 Hub 選址模型。Drezner 和 Z. Drezner 和 Salhi[130]提出了應(yīng)用模擬退火和 Ascent 相結(jié)合的算法求解新建服務(wù)站市場(chǎng)份額期望最大的競(jìng)爭選址問題。

0

更多

下一篇：博/碩士學(xué)位論文的研究過程

上一篇：穩(wěn)健性與可靠性

  本文關(guān)鍵詞：選址問題，由筆耕文化傳播整理發(fā)布。