Baumol-Wolfe模型

Baumol-Wolfe模型是針對動態選址問題的模型。

基本介紹

• 外文名：Baumol-Wolfe模型
• 套用範圍：套用範圍很廣泛
• 常見問題：動態選址問題
• 性質：模型

選址問題

從19世紀60年代中期開始，選址問題的研究多了起來，很多問題的輸入條件為確定的值。有些研究通過建立多目標規劃模型來得出滿意的設施位置。選址問題有兩類基礎問題，很多研究都是在這兩類問題基礎上設定不同的條件進一步擴展的，這兩類基礎問題分別是：中值問題；覆蓋問題，這兩類問題最初研究的都是靜態確定型選址問題

中值問題

Hakimi所提出的第一個與套用領域無關的設施選址問題就是P-中值問題。這種方法可以用來找出P個設施位置，使需求點和設施之間的以需求量為權重的運輸距離之和最小。此模型可以在有限的待選點中選擇設施位置。在上面的模型中，這些待選點位於網路的結點上。有研究人員研究了待選點位於網路邊上的情況，關於這一問題Hakimi已經證明了，在網路中選定P個設施位置，對於P-中值問題，在網路頂點處至少有一個最優解。這樣，可以將待選點位於網路邊上的問題簡化成待選點只位於網路頂點處的問題，這種簡化不會影響求解結果和目標值的最優性。

P-中值問題被歸類為NP-complete問題。將待選點限定在網路頂點能夠很大程度簡化問題。

正如Church和ReVelle所說，評價一個設施選址結果的很重要的標準是到達這些設施的距離最小化。平均運輸距離增大，設施的可達性就減小，從而降低了設施的有效性。當客戶需求對服務水平不敏感時可以採用另外一種評價設施位置有效性的方法，即將需求量作為權重，將需求量與需求點和設施之間的距離一起使用，來計算需求點和設施之間的有權重的運輸距離之和，以此作為評價設施可達性的標準。

覆蓋問題

P-中值問題的套用範圍很廣泛，適用於以平均運輸距離最小為選址目標的情況。但是對於某些設施，如：在城市中選擇諸消火栓或急救中心這類緊急服務設施時，在選址中必須考慮使需求點能夠在最短距離或時間內到達設施獲得服務。如果一個需求點能夠在一定的時間內得到服務，我們稱它被覆蓋了（covered），此類問題也稱為覆蓋問題。覆蓋問題分為兩類，分別是集合覆蓋問題和最大覆蓋問題。集合覆蓋問題的目標是用最少數量的設施去覆蓋所有的需求點。而最大覆蓋問題則研究在給定數量的設施下，覆蓋儘可能多的需求點。最大覆蓋問題並沒有考慮需求量，認為所有需求點的需求量相等，目標函式僅是設施覆蓋的需求點數量最大。

基本的最大覆蓋問題沒有服務距離的限制，如果增加服務距離條件，當需求點不能在要求的服務距離S內得到服務，那么必須在服務距離T（T>S）內得到服務時，問題就變為“有強制範圍條件的最大覆蓋問題”(maximal covering with mandatory closeness problem)。此問題的目標是使被覆蓋的需求點距離它最近的設施不超過T距離，同時保證儘可能多的需求點位於S距離範圍內。Orhan和 Esra專門針對如何確定T和S進行了研究。

在前面討論的覆蓋問題中都假設，如果一個需求點被覆蓋了，那么它就能從設施處得到服務。但是Daskin和Stern]提出了EMS(Emergency Medical Service)車輛定位的覆蓋問題，在這個問題里上面的假設條件就不能成立。若EMS車輛已經回響了一個需求，就不能同時回響另一個需求。針對設施有忙期或不作用期的問題模型也有很多。Batta和Mannur認識到，在EMS車輛配置中有多個回響組的需求問題很難解決，他們分析了具有一般性的確定性的集合覆蓋模型和最大覆蓋模型，在這些模型中考慮了多個回響組和需求相關的覆蓋要求，並對每一問題的求解方法也進行了研究。Tavako和Lightner對Fayetteville市的EMS車輛選址問題進行了研究並得出了滿意的結果。

基本問題延伸

在上面兩種基本問題的基礎上增加不同的條件又產生了多種新的問題。將基本選址模型進行擴展可以將固定成本或建設成本包括在內。再擴展還可包括設施的容量限制。沒有容量限制的固定成本設施選址問題（uncapacitated fixed facility location problem）,與P-中值問題相似，在P-中值模型的目標函式中加入固定成本，並將選定設施數量約束從約束條件中去掉。由於此類問題的求解難度，很多研究人員提出了啟發式算法，如禁忌搜尋方法、領域搜尋方法。Elena和Justo研究了多目標的無容量限制的選址問題。Sankaran和Raghavan 對P-中值問題進行了擴展，將設施的容量限制考慮在了選址問題中。Mukundan和Daskin 則從利潤最大化的角度考慮了同樣的問題。

設施選址問題往往不僅要選擇設施位置，還要考慮分配的問題，即需求點應怎樣由設施提供服務。這就是選址-分配問題（location-allocation）此問題也是建立在基本選址模型基礎上的。不但能夠確定設施位置，同時還能得出設施和需求點之間的流量。這類問題Scott進行了綜述，它是將標準運輸問題與選址問題結合起來，來選擇設施位置。Sherali等研究了選址-分配問題的全局最佳化方法。

前面所提到的模型都是以方便需求點到達設計為目的的，而有些設施，如垃圾處理廠、核電站等，大家期望這種設施越遠越好。對於此類設施就產生了一類稱為“易受譴責（obnoxious）設施”選址的問題[35]。處理這類情況的問題包括：反中值問題(antimedian problem)，目標是使設施與需求點之間的平均距離最大化；反中心問題（anticenter problem），目標是使設施與需求點之間的最小距離最大化；p-分散問題，目標是使任意兩個設施之間的最小距離最大化。

在靜態確定型的選址問題中還有一種是中心問題(center problem)，其目標是Minimax，使需求點與設施之間的最大距離最小化，即最佳化最壞的情況。這種問題通常在軍隊和公共部門中使用。它與中值問題和覆蓋問題有所不同，但可歸類為靜態確定型選址問題。

動態選址問題

設施選址問題是屬於戰略層的決策問題，設立一個新設施將會是一項時間跨度較大的項目，因此期望所建立的設施在建成後的一段時間內都能夠很好地實現既定目標。在設施生命期內，周圍環境的變化可能會使原來適合建立設施的地點變得不合時宜，因此選址模型需要考慮到將來的變化。使選定的設施位置在將來一段時間內仍保持最優性。也就是說，決策者不僅要選一個在當前時間需求情況下最優的設施位置，而且在將來情況發生變化後仍然最優的設施位置。

Ballou第一個提出了動態選址問題，他提出靜態、確定型選址模型在套用上沒有考慮到時間的變化，並研究了如何選擇一個倉庫使其在規劃期內實現利潤最大化。他的方法是在決策期內的每個階段，求解出最優倉庫位置，建立一個“好位置”集合，然後使用動態規劃方法來求出決策期內一系列最優位置集合。Sweeney和Tatham在Ballou的基礎上提出了改進方法。由於這些方法都沒有考慮到設施建設所需要的時間，所以Wesolowsky研究了一個無約束的有限規劃時期的單設施選址問題，他在其中加入了再選址成本。Drezner和Wesolowsky研究了一個成長型城市的設施選址問題，這個城市的人口數量隨時間在發生變化（可預測的），這就意味著隨著時間變化，需求量也在發生變化，只是這些變化是確定型的。他們的目標是找出一個設施位置，使其在規劃時期內的成本最低。

Scott[研究了動態選址-分配問題，此問題研究多設施在多個規劃期間的選址。Wesolowsky和Truscott 進一步研究了多階段選址-分配問題，在他們的研究中設施可以根據預測的需求變化改變位置。他們提出了一個整數規劃模型，約束條件為每一階段允許變化位置的設施數量，還提出了一個動態規劃模型。Sheppard的研究擴展了此類問題的套用範圍，他提出了各種模型，適用於工業或公共領域裡的多種情況，不但能夠確定多個設施的位置，而且能夠確定設施的規模和建設/擴建時間。Drezner研究了改進的p-中值問題（progressive P-median problem），在T個規劃期內選擇P個設施，他的研究沒有考慮設施再選址。Balakrishnan在前人研究的基礎上提出了一種改進算法，來求解多規劃期的設施選址問題。

另外一種能考慮時間跨度的設施選址方法是Daskin等提出的。作者認為由於未來環境的不確定性，求解動態設施選址問題很困難。他們認為應對不確定性的最好方法就是儘可能延遲決策，收集儘量多的信息，隨著時間的推進提高預測的準確性。在各決策階段中，第一個決策階段是唯一一個需要即時實施的決策，所以作者認為動態選址決策的目標不應該是決定所有階段的設施位置或再選定位置，而是找出所有選址規劃階段中第一個階段的最優位置或近似最優位置。

隨機選址問題

靜態、確定型模型假設輸入的參數值是確定的，或在一定時間內是確定的；動態選址研究的是在將來一定規劃期內針對可預測變化的設施選址問題，因此輸入參數也可認為是確定的。但現實世界內卻有諸多不確定性，下面回顧隨機型選址問題的研究。

研究隨機選址問題的方法可以分為兩大類，一類是機率方法（probabilistic approach）,一類是場景規劃方法（scenario planning approach）。在兩種方法中都會假定某些參數是不確定的，這些參數包括：運輸時間、建設成本、需求位置、需求數量。選址目標是選定健壯（robust）的設施位置，使其在不確定的環境下能夠較好地實現系統目標。機率方法主要是使用機率分布函式來表達模型的參數。場景規劃方法並不是直接使用函式表達式來表示模型參數，而是將機率分布函式使用生成的一系列變數數值用在模型中，與模擬方法有相似之處。Mulvey等討論了機率方法和場景規劃法和優、缺點比較。下面分別對機率方法和場景規劃方法進行討論。

機率方法

在1961年，Manne首先提出了輸入條件為隨機變數的選址問題。他的研究前提為，需求量是不確定的，未滿足的需求可再次訂貨；設施容量可以擴大。問題的目標為總擴張成本最低。這項研究結果表明，需求的不確定性對模型的其它方面沒有影響，但所求出的設施容量變大了。Bean等研究了需求隨機增長情況下，在無限時間範圍內的設施容量擴大問題。在此研究中允許非固定的、連續或離散的需求，但是未滿足的需求不允許再訂貨，只有當現有商品消費完時才能再訂貨。Berman和Odoni還有Berman和LeBlanc研究了運輸時間變化時重新選擇P個設施中的一個或多個設施位置的問題。這項研究的網路狀態定義如下，當有至少一條邊的運輸時間發生變化時，稱網路狀態發生變化。在兩篇文章中都使用了馬爾柯夫變化矩陣來求解網路的變化狀況。Mirchandani研究了運輸特徵、供應/需求模式為隨機情況的P-中值問題和無能力限制的倉庫選址問題，他所關注的套用領域是消防設施選址問題。在他的研究中還考慮了服務需求擁擠的情況，當並發服務需求過多時，有些需求點的需求可能會得不到滿足。

使用機率方法研究設施可得性的問題也有很多。Daskin將確定型的最大覆蓋模型擴展套用到EMS車輛問題中，他考慮了車輛處於忙時的需求情況。假設各車輛處於忙狀態的機率是不相關的，並且各車輛處於忙狀態的機率是相同的。作者提出了單點替代啟發式算法（single node substitution-based heuristic）來求解此問題。ReVelle和Hogan提出了兩種新模型來研究集合覆蓋問題中的車輛可得性問題。Beraldi等提出了一種解決隨機EMS車輛的選址問題，他提出的模型不但能確定EMS服務設施的位置，而且能夠得出在各選定位置處應配置車輛的數量。

EMS問題激發了大量的相關研究，研究人員已經將其研究成果廣泛套用於各種隨機選址問題。Belardo等研究了處理海上漏油事故的設施位置問題，此類設施的功能是當海上有漏油事故發生時，從設施處派出設備來控制事故和收集、移走泄漏到水域中的油料。Hanink研究使用投資組合理論來解決多設施選址問題。Gregg等提出了一種選擇公共圖書館位置的方法，通過隨機規劃方法建立需求不確定條件下的選址模型。

前面討論的模型中都包含了一系列隨機參數，很多研究使用排隊論的方法將這些參數包含在選址問題中。下面將討論對這些參數進行處理的方法。

Larson的超立方體模型(hypercube model) 第一個將排隊論方法套用到設施選址研究中。Larson研究了與車輛選址和緊急服務設施回響區域設計相關的問題，將跨區回響、隨機到達、隨機服務時間考慮在內。他把緊急服務系統看作是多服務台的排隊系統來建立模型。Berman等進一步研究了在擁堵網路中的車輛選址問題。作者提出當設施處於忙狀態時，需求要排隊等候。需求到達設施時，若設施處於忙狀態，對需求會有不同的處理方法，一種是設施忙狀態時需求被放棄，一種是設施忙狀態時需求排隊等候。針對這兩種不同的情況，作者建立了兩種模型，若排隊等候則遵從先進先出原則（FIFO）。兩種模型都看作是M/G/1排隊系統。Marianov等用M/D/<f>c</f>排隊系統研究了航空網路中心的選址問題。Brandeau和Chiu著將隨機排隊中心問題、隨機排隊中值問題，以及其它一些單設施選址問題進行統一化。作者考慮了排隊和運送兩種原因造成的延遲，將系統看作是M/G/1排隊系統。

場景規劃方法

場景規劃方法在套用時，先由決策者提出幾種未來可能發生的情況，稱這些情況為場景（scenario），在這此場景基礎上做出決策，決策目標是找出在所有場景下均能運作良好的方案。場景規劃法有定性和定量兩種套用方法。Mobasheri在他的研究中用場景規劃方法取代了預測方法來評價未來的發展趨勢和變化，這項研究以現狀和將要發生的變化為基礎，定性描述未來狀況，使企業能夠制定應對環境變化的戰略。在Mulvey的研究中，通過給問題輸入各種參數，使用場景規劃方法定量描述一系列未來狀況。設施選址中的場景規劃方法採用的是定量的方法。Vanston等討論了場景規劃方法並提出了包含12個步驟的場景生成方法。Ghosh和McLafferty使用場景規劃方法研究不確定環境下的零售店選址決策，目標是使零售店的市場份額最大化。Carson和Batta使用場景規劃方法研究了紐約布法羅市的州立大學校園中選擇救護車位置的問題。

設施選址場景規劃方法的核心是找出隨機情況下問題的一系列可能狀況，並在這些狀況基礎上確定設施選址方案。設施選址場景規劃的目標可以分為三類，分別是：針對所有場景進行最佳化；針對最壞情況的場景進行最佳化；使所有場景的最壞損失最小化。