物流工程與管理學(xué)：物流節(jié)點選址模型與方法

1、2022/7/71物流節(jié)點選址模型與方法2022/7/72 物流設(shè)施：工廠、港口、倉庫、零售店、服務(wù)中心。 選址決策：確定所使用的設(shè)施的數(shù)量、位置和規(guī)模。第一節(jié) 物流設(shè)施選址問題的類型與特點2022/7/73 物流設(shè)施選址問題，是指在一個具有若干供應(yīng)點及若干需求點的區(qū)域內(nèi)，選一個（或者數(shù)個）地址設(shè)置物流設(shè)施的規(guī)劃過程，使得物流系統(tǒng)的整體效益最優(yōu)。 物流設(shè)施選址問題是物流規(guī)劃中的戰(zhàn)略問題，物流設(shè)施一旦建成很難搬遷，如果選址不當(dāng)，將付出長期代價。選址問題是物流系統(tǒng)規(guī)劃中重要的一步。 2022/7/74確定選址目標(biāo) 地區(qū)選擇階段地點選擇階段一、物流設(shè)施選址問題三個階段:2022/7/75二、物流設(shè)施

2、選址問題的類型 1、按離散程度分類：連續(xù)選址模型(Continuous Location Models)離散選址模型(Discrete Location Models)。連續(xù)選址模型認(rèn)為可以在一個連續(xù)空間內(nèi)所有可能的點，選擇其中最優(yōu)的一個或多個，其代表性的方法是重心法(Centroid Method)。離散選址模型則是指在一系列可能方案中做出選擇，這些方案事先已經(jīng)過了合理性分析。2022/7/762、按設(shè)施的數(shù)量分類： 單一設(shè)施選址：運輸成本是考慮的首要因素。 多個設(shè)施的選址：除考慮運輸成本外，需要考慮各設(shè)施間的互相影響關(guān)系（競爭力、設(shè)施間的需求分配、集中庫存的效果、設(shè)施的固定成本和可變運營成

3、本）。2022/7/773、按決策目標(biāo)的數(shù)量分類：三種基本的單目標(biāo)決策分別是：成本最小化類型、服務(wù)最優(yōu)化類型和物流量最大化類型。 除了這三種基本的單目標(biāo)決策外，對于有些物流項目，單獨考慮成本、服務(wù)和物流量尚不能滿足投資決策者的需要，這時可能要綜合考慮多方面的目標(biāo)來進(jìn)行物流設(shè)施選址，這時較多采用多目標(biāo)決策的方法。 2022/7/78（1）選址決策具有廣泛的應(yīng)用背景。（2）選址決策是一個戰(zhàn)略決策，需要考慮長期的、多方面的效益。（3）選址決策涉及多方面因素。包括污染、交通擁擠和經(jīng)濟發(fā)展?jié)摿Φ?。?）多數(shù)選址問題是 NPhard ，很難求得模型的最優(yōu)解。（5）模型的結(jié)構(gòu)（目標(biāo)函數(shù)、變量和約束）由相應(yīng)的

4、應(yīng)用背景決定。沒有一個通用的模型可以解決所有的選址問題。三、設(shè)施選址問題的特點2022/7/79選址問題案例 已知有6個村子A、B、F都生產(chǎn)糧食，擬合建一座糧庫。各村之間道路連接狀況和距離如圖41所示。已知A村每年產(chǎn)糧食50噸，B村40噸，C村60噸，D村20噸，E村70噸，F(xiàn)村90噸。問該糧庫應(yīng)建在哪一個村子，使各村送糧食的費用最低？ AFEDCB2781361364圖41 各村之間道路連接狀況和距離2022/7/710問題分析這個問題尋求最優(yōu)化的原則是保持所有各村運輸總量（噸公里）最小。最直觀的求解方法就是分別計算出在6個備選地點建糧庫所對應(yīng)的總運量，然后選擇總運量最小的備選地點建糧庫?？?/p>

5、先采用Floyd算法計算圖中任意兩點間的最短路，然后再計算對應(yīng)的總運輸量。通過計算，得知在D村建設(shè)糧庫是最佳選擇。2022/7/711 產(chǎn)地糧庫位置ABCDEFA0267811B204569C640125D751014E862103F1195430表4-1 各產(chǎn)地與糧庫間的最短距離表 （公里）2022/7/712 產(chǎn)地糧庫位置ABCDEF總運量A0803601405609902130B10002401004208101670C3001600201404501070D350200600703601040E4002401202002701050F5503603008021001500產(chǎn)量50406

6、0207090表4-2 各產(chǎn)地到糧庫的運量（噸公里）2022/7/713上例中，如果備選地點增加，或者要選擇的設(shè)施最優(yōu)節(jié)點增加，那么問題的規(guī)模會變得很大，其計算的復(fù)雜性會大大增加。離散選址問題，可以采用枚舉法來求得最優(yōu)解。連續(xù)型選址問題，無法采用枚舉法來求最優(yōu)解。例如，從100個備選點中選擇4個最優(yōu)節(jié)點，將會枚舉 種情況，要計算近400萬種情況下的總運量。因此，大規(guī)模、復(fù)雜性較高、約束條件較多的離散選址問題，用枚舉法是行不通的。啟發(fā)式算法是解決組合優(yōu)化滿意解（最優(yōu)或者次優(yōu)解）的有效方法。2022/7/714求解TSP模型時，如果要得到精確的最優(yōu)解，最簡單的方法也是枚舉法。對于小規(guī)模問題，枚舉法

7、是一種有效的方法。但是對于大規(guī)模問題，由于枚舉法的例舉次數(shù)為（n一1）！次，這在實際操作中是很難實現(xiàn)的。整數(shù)規(guī)劃的方法用于解決部分TSP模型，其原理也是分枝定界法，該算法只能對一部分中小規(guī)模的問題進(jìn)行求解，對于大多數(shù)問題的求解都存在一定的難度。2022/7/715組合爆炸例如，一臺汽車每天要給20-30個不同的自動售貨機補貨。如果要訪問20臺機器的時候，其巡回路線就有20！2432902008176640000條巡回路線可供選擇；如果要訪問30臺，就有30！265252859812191058636308480000000條巡回路線可供選擇，利用現(xiàn)有計算機，若一秒鐘可以計算100億條路線的距離

8、的話，對于20臺自動售貨機的計算需要花費7年的時間，對于30臺自動售貨機則需要花費8411兆年的時間，這種現(xiàn)象稱為“組合爆炸”2022/7/716問題規(guī)模 nn! 的計算時間（1宇宙齡150億年）100.036秒20771年305.61106 宇宙齡401.721022 宇宙齡506.421038 宇宙齡1001.7710132 宇宙齡組合爆炸2022/7/7171、地區(qū)選址應(yīng)考慮的因素(戰(zhàn)略、宏觀因素) （1）市場條件。（2）資源條件。（3）運輸條件。（4）社會環(huán)境。 四、影響場址的主要因素2022/7/7182、 對地點選擇的要求（具體實施的可能性） （1）地形地貌條件。（2）地質(zhì)條件。（

9、3）占地原則。（4）施工條件。（5）供排水條件。2022/7/719經(jīng)濟因素非經(jīng)濟因素1運輸費用1當(dāng)?shù)卣叻ㄒ?guī)2土地成本和建設(shè)費用2經(jīng)濟發(fā)展水平3原材料供應(yīng)價格3環(huán)境保護(hù)標(biāo)準(zhǔn)4燃料價格4人文環(huán)境5水、電等資源成本5氣候條件6勞動力價格3、 影響設(shè)施選址的經(jīng)濟因素和非經(jīng)濟因素2022/7/720進(jìn)行物流設(shè)施選址，可以按照如下七個步驟： 搜集整理資料； 選址約束條件分析； 地址篩選； 定量分析； 結(jié)果評價； 復(fù)查和確定選址結(jié)果。第二節(jié) 物流設(shè)施選址的程序和步驟2022/7/721圖4-2 物流設(shè)施選址的程序 2022/7/722地圖、地價、業(yè)務(wù)量、費用分析、配送路線、設(shè)施現(xiàn)狀的分析及需求預(yù)測收集整

10、理資料選址約束條件分析地址篩選定量分析結(jié)果評價物流系統(tǒng)的現(xiàn)狀分析多設(shè)施選址法市場的適應(yīng)性；購置土地條件；服務(wù)質(zhì)量；總費用；商流、物流的職能及其它單設(shè)施選址法地理、地形、地價、環(huán)境、交通條件、勞動條件及有關(guān)法律選址的限制條件確定選址結(jié)果復(fù)查YN選址步驟2022/7/723一、搜集整理資料對業(yè)務(wù)量、運營收入和運營成本進(jìn)行正確的分析和判斷 1運營收入（1）運輸業(yè)務(wù)量、存儲業(yè)務(wù)量、包裝裝卸、流通加工及其他業(yè)務(wù)量；（2）銷售價格及競爭情況；2運營成本（1）運營費用(運輸費用、配送費、物流設(shè)施費用)；（2）管理費用。3與選址決策相關(guān)的其他資料 地圖、土地價格、配送路線、設(shè)施現(xiàn)狀的分析及需求預(yù)測2022/7

11、/724二、 選址約束條件分析1需求條件顧客分布情況預(yù)測、貨物作業(yè)量的增長率及配送區(qū)域的范圍。2運輸條件應(yīng)靠近鐵路貨運站、港口和機場等運輸據(jù)點及辦公地點。3配送服務(wù)的條件發(fā)送時間、頻率、顧客到物流設(shè)施的距離和服務(wù)范圍。4用地條件是否有地？地價如何？5法規(guī)制度指定區(qū)域是否允許建立物流設(shè)施？稅收政策、物流政策、關(guān)稅及匯率等6流通職能條件商流職能是否要與物流職能分開？物流設(shè)施是否也附有流通加工的職能？7其他 貨物質(zhì)量冷凍、保溫設(shè)施、防止公害設(shè)施或危險品保管等設(shè)施。 2022/7/725三、 地址篩選在資料整理和分析的基礎(chǔ)上，考慮各種因素的影響并對需求進(jìn)行預(yù)測后，初步確定選址范圍，即初始候選地點。四、

12、 定量分析針對不同情況選用不同的模型進(jìn)行計算，得出結(jié)果。五、 結(jié)果評價 根據(jù)系統(tǒng)的評價目標(biāo)（市場的適應(yīng)性、客戶服務(wù)水平；總收入、成本與費用；土地條件；商流、物流的職能等）對所選擇方案進(jìn)行評價。對多個影響因素分別賦予權(quán)重，采用加權(quán)法方法進(jìn)行評價。六、確定選址結(jié)果定量計算結(jié)果，不一定為實際最優(yōu)解，還要結(jié)合定性分析。 2022/7/726選址的注意事項1影響選址因素相互矛盾。如業(yè)務(wù)方便，與地價貴、租金高、建設(shè)成本或運營成本較高等。2不同因素的相對重要性很難確定和度量。不同服務(wù)對象對物流設(shè)施的要求不同，反應(yīng)速度、服務(wù)可靠性、成本、便捷程度等。3選址標(biāo)準(zhǔn)會隨時間變化而變化。4不同類型物流設(shè)施在選址要求不

13、同。（1）轉(zhuǎn)運型物流設(shè)施應(yīng)設(shè)置在城市邊緣地區(qū)的交通便利的地段，以方便轉(zhuǎn)運和減少短途運輸。（2）儲備型物流設(shè)施一般應(yīng)設(shè)置在城鎮(zhèn)邊緣或城市郊區(qū)的獨立地段，且具備地價低、方便運輸?shù)葪l件。2022/7/727一、0-1整數(shù)規(guī)劃方法選址問題的提出假設(shè)廠址候選地點有s個，分別用D1，D2，Ds表示；原材料、燃料、零配件的供應(yīng)地有m個，分別用A1，A2，Am表示，其供應(yīng)量分別用P1，P2，Pm表示；產(chǎn)品銷售地有n個，分別用B1，B2，Bn表示，其銷售量分別用Q1，Q2，Qn表示，如圖4-3所示。圖4-3 選址示意圖 第三節(jié) 離散選址問題（整數(shù)規(guī)劃選址方法）2022/7/728從s個候選庫址中選取一個最佳地址

14、建庫，使物流費用達(dá)到最低。設(shè)Cij表示從Ai到Dj的每單位運輸量的運輸成本；djk表示從Dj到Bk的每單位運輸量的運輸成本。引進(jìn)變量：X(Xl，X2，Xs) 。其中那么選址問題表述為：引入0-1變量2022/7/7291在一組（J個）相互排斥的事件中，至多只能選擇一個事件的約束方程為 （表示選中）2如果只是在選擇事件l 的情況下，才考慮是否選擇事件k，建立約束如下 3問題只要滿足兩個約束之一即可。二中選一的約束方程為 和 M是很大的一個數(shù)，=0或1。.二、用0-1變量建立規(guī)劃模型的思路與技巧2022/7/730某集團(tuán)公司的工廠和配送中心選址為例，該集團(tuán)公司生產(chǎn)一種產(chǎn)品，由工廠運至配送中心，再由

15、配送中心將產(chǎn)品運至分銷店。有5家工廠（備選工廠），有3家配送中心可以配送產(chǎn)品，有4家分銷店經(jīng)營產(chǎn)品。這些工廠和配送中心的年度固定成本、工廠的年生產(chǎn)能力和工廠到各備選配送中心的單位運價、配送中心運至各分銷店的運輸成本和各分銷店的需求量如表46。三、混合整數(shù)規(guī)劃選址示例2022/7/7310-1變量S1S2S3運量配送中心1配送中心2配送中心3T1工廠1X11X12X13T2工廠2X21X22X23T3工廠3X31X32X33T4工廠4X41X42X43T5工廠5X51X52X53分銷店1Y11Y21Y31分銷店2Y12Y22Y32分銷店3Y13Y23Y33分銷店4Y14Y24Y34表46 變量定

16、義表 2022/7/732設(shè)工廠i 向配送中心j 運送的貨物量為xij，設(shè)配送中心j 向分銷店k 的配送量為yjk。設(shè)0-1變量Tm，St分別為工廠和配送中心的使用情況，定義如下：顯然，當(dāng)Tm0時必有顯然，當(dāng) St0時，必有其中，i=1，2，3，4，5；j=1，2，3；k=1，2，3，4；m=1，2，3，4，5；t=1、2、3。 2022/7/733固定成本400002000060000運價配送中心1配送中心2配送中心3生產(chǎn)能力35000工廠18001000120030045000工廠270050070020040000工廠380060050030042000工廠450060070020040

17、000工廠5700600500400需求量分銷店1407080200分銷店2804030300分銷店3906050150分銷店4508060250表46 固定成本和單位運費表 2022/7/734生產(chǎn)廠的固定成本35000T1+45000T2+40000T3+42000T4+40000T5生產(chǎn)廠到配送中心的運輸成本800 x11+1000 x12+1200 x13+700 x21+500 x22+700 x23+800 x31+600 x32+500 x33+500 x41+600 x42+700 x43+700 x51+600 x52+500 x53配送中心的固定成本40000S1+2000

18、0S2+60000S3從配送中心到銷售區(qū)的運輸成本40Y11+80Y12+90Y13+50Y14+70Y21+40Y22+60Y23+80Y24+80 Y31+30Y32+50Y33+60Y34目標(biāo)函數(shù)由一下及部分構(gòu)成2022/7/735由以上條件可以列出目標(biāo)函數(shù)如下： Zmin=T1*(800*X11*S1+1000*X12*S2+1200*X13*S3)+T2*(700*X21*S1+500*X22*S2+700*X23*S3)+T3*(800*X31*S1+600*X32*S2+500*X33*S3)+T4*(500*X41*S1+600*X42*S2+700*X43*S3)+T5*(7

19、00*X51*S1+600*X52*S2+500*X53*S3)+S1*(40*Y11+80*Y12+90*Y13+50*Y14)+S2*(70*Y21+40*Y22+60*Y23+80*Y24)+S3*(80*Y31+30*Y32+50*Y33+60*Y34)+35000*T1+45000*T2+40000*T3+42000*T4+40000*T5+40000*S1+20000*S2+60000*S3 生產(chǎn)廠到配送中心的運輸成本配送中心到銷售區(qū)的運輸成本生產(chǎn)廠的固定成本配送中心的固定成本2022/7/736由以上條件可以列出約束條件如下： 最優(yōu)方案為：使用工廠3、4、5，配送中心1、3，最小

20、總成本為711500元。工廠生產(chǎn)能力分銷店需求量工廠與分銷店的供需平衡2022/7/737第四節(jié) 重心法連續(xù)選址模型一、關(guān)于距離的三個概念：1.直線距離 歐幾里德距離 2.折線距離3.城市距離 城市中的實際路線距離。2022/7/738二、 重心法模型 圖4-5 物流設(shè)施和需求點的坐標(biāo) 2022/7/739重心法模型 圖4-5 物流設(shè)施和需求點的坐標(biāo) 設(shè)Cj為物流設(shè)施至各需求點的運費，則總運費表示為：而Cj又可以用下式來表示: Cj =hj wj dj （4-2）式中，hj -從物流設(shè)施到需求點j的運費率（即單位噸公里的運費）； wj-需求點j的需求量； dj-從物流設(shè)施到需求點j的距離。 d

21、j也可以寫成如下形式： 2022/7/740設(shè)Cj為物流設(shè)施至各需求點的運費，則總運費表示為：而Cj又可以用下式來表示: Cj =hj wj dj2022/7/741則總運費表示為： 求出使H為最小的x和y。令：其中：（4-4）（4-3）2022/7/7422022/7/743求出使H為最小的x和y。令：2022/7/744可分別求得最適合的 和 ，即 上式（右邊還含有dj，即還含有要求的未知數(shù)x和y，而要從兩式的右邊完全消去x和y，是不可能的。因此采用迭代法來進(jìn)行計算。（4-8）（4-7）2022/7/745（4-8）（4-7）2022/7/746三、重心法的迭代計算步驟（注意）（1）給出物

22、流設(shè)施的初始地點 ；（2）計算與物流設(shè)施初始地點 相應(yīng)的總運費H0；（3）把 ， 分別代入式（4-3）、式（4-7）和式（4-8）中，計算物流設(shè)施的改善地點 ；（4）利用式（4-3）和式（4-4），計算與 ， 相應(yīng)的總運費H1（5）比較 則返回（3）的計算下一個物流設(shè)施的改善地點 2022/7/747則說明 就是滿意解。這樣反復(fù)計算下去，直至，求出滿意解 為止。否則，2022/7/748重心法的局限性 重心法模型適用于連續(xù)型選址問題。重心法能夠給出連續(xù)型選址模型的滿意解由迭代法計算求得的最佳地點實際上往往很難實現(xiàn)，有的地點很可能在河流湖泊上或街道中間等。此外，迭代計算量較大（雖然邏輯上并不復(fù)雜

23、），這也是連續(xù)型模型的缺點之一。重心法選址模型的更大弊病還在于，模型中將運輸距離用坐標(biāo)（兩點間的直線距離）來表示，并認(rèn)為運輸費用是兩點間直線距離的函數(shù)，這與實際情況有較大的差距，在實際運用過程中需要加以修正，這樣才能較好地反映問題本身的特點。 2022/7/749交叉中值模型(Cross Median)是用來解決連續(xù)點選址問題，它是利用城市距離進(jìn)行計算。對單一的選址問題在一個平面上的加權(quán)的城市距離進(jìn)行最小化。例如，在一條大街上確定零售商店或報刊亭位置等。其相應(yīng)的目標(biāo)函數(shù)為：四、重心法特例（交叉中值模型）物流設(shè)施點xs2022/7/750用折線距離的計算公式對在一個平面上的單一設(shè)施選址的加權(quán)距離

24、進(jìn)行最小化問題，其相應(yīng)的目標(biāo)函數(shù)為：其中，wi 與第i個需求點對應(yīng)的權(quán)重（例如需求量等）；xi，yi 第i個需求點的坐標(biāo);xs，ys 服務(wù)設(shè)施點的坐標(biāo);n 需求點的總數(shù)目。或：2022/7/751用折線距離的計算公式根據(jù)求平面中物體系統(tǒng)重心的方法則有： 這種方法將橫向和縱向的距離看成是互相獨立的量，這與實際情況并不相符，這種方法求得的解可以作為一個參考值。2022/7/7522022/7/753討論：下式有什么意義？其中wi是未知變量2022/7/754假設(shè)物流設(shè)施選址范圍內(nèi)有5個需求點，其坐標(biāo)、需求量和運輸費率如表47所示?，F(xiàn)要設(shè)置一個物流設(shè)施，問物流設(shè)施的最佳位置為何處？需求點坐標(biāo)需求量（

25、wj）運輸費率（hj）綜合權(quán)重A（3，8）20000.51000B（8，2）30000.51500C（2，5）25000.751875D（6，4）10000.75750E（8，8）15000.751125五、重心法選址示例表47 需求點的需求狀況 2022/7/755迭代次數(shù)xkyk總運費05.160000500298015.0376915.05659221431.21581024.9902595.03142621427.11040434.9661365.03167121426.14054244.9509285.03676621425.686792594.910110

26、5.05767721425.136231604.9101105.05767721425.136231表8 迭代結(jié)果列表 2022/7/7560 1 2 3 4 5 66 5 4 3 2 1 052314例：重心法解決離散選址問題。如圖5個需求點的坐標(biāo)位置，及需求量（權(quán)重），請確定在區(qū)域范圍內(nèi)的配送中心位置。首先利用計算權(quán)重Wi的中值需求點X 坐標(biāo)Y 坐標(biāo)權(quán)重Wi13112527343342435156首先計算權(quán)重Wi的中值2022/7/7570 1 2 3 4 5 66 5 4 3 2 1 052314需求點需求點位置（沿 X 軸方向）累計Wi從左到右5164263913631103425從右

27、到左257347310134251沿 X 軸方向的權(quán)重中值計算沿 X 軸方向的權(quán)重中值計算表明，Xs的位置在需求點1和需求點3之間，即Xs342022/7/758需求點需求點位置（沿 Y 軸方向）累計Wi從上到下5564463933633122211從下到上1112217833173114455沿 Y 軸方向的權(quán)重中值計算沿 Y 軸方向的權(quán)重中值計算表明，Ys的位置與需求點3重合，即Ys30 1 2 3 4 5 66 5 4 3 2 1 052314AB2022/7/7590 1 2 3 4 5 66 5 4 3 2 1 052314ABA(3,3)B(4,3)需求點距離權(quán)重總和需求點距離權(quán)重

28、總和121213132372122714313330304236433954624556305656位置A、B之間的加權(quán)距離比較結(jié)論：可以在A、B之間選擇任意點2022/7/760用重心法準(zhǔn)確計算選址位置點A(3,3)作為起始點，利用公式：(其中hj=1)需求點（i）12345位置X(i-1) ,Y(i-1)（3，1）（5，2）4，3）（2，4）（1，5）權(quán)重Wi17336距離d(i-1)22.2411.412.82Wi/d(i-1)0.53.1332.132.13(Wi Xi /d(i-1), Wi Yi /d(i-1), )(1.5, 0.5)(15.63,6.25)(12,9)(4.25

29、,8.5)(2.13,10.63)2022/7/761得到迭代結(jié)果如下，然后根據(jù)迭代中止準(zhǔn)則，確定是否繼續(xù)進(jìn)行迭代計算。使用重心法計算得到的選址位置，是一個準(zhǔn)確的最優(yōu)值（近似），一般不會出現(xiàn)一個區(qū)域。2022/7/762 例如：一家公司（例如寶潔）從4家生產(chǎn)廠得到產(chǎn)品，通過105個倉庫（配送中心），向2000個銷售網(wǎng)點銷售，就可能找出80多萬個可能的工廠倉庫客戶物流方案供選擇。如果再增加產(chǎn)品和運輸方式的數(shù)量，要找到一個最優(yōu)的倉庫位置就變得更為困難。第五節(jié) 多設(shè)施選址問題方法分析2022/7/763區(qū)域內(nèi)是否設(shè)倉庫，租用倉庫還是自建倉庫？物流網(wǎng)絡(luò)中應(yīng)該有多少個倉庫？這些倉庫應(yīng)有多大的規(guī)模？倉庫應(yīng)

30、位于什么地點？各工廠、供應(yīng)商或港口、各客戶應(yīng)指定由哪些倉庫負(fù)責(zé)？各倉庫中應(yīng)存放哪些產(chǎn)品？如何對產(chǎn)品數(shù)量進(jìn)行分配（從工廠、供應(yīng)商或港口到客戶手中）？多設(shè)施選址決策涉及的幾個基本問題：2022/7/764多 重 心 法混合-整數(shù)線性規(guī)劃鮑摩-瓦爾夫選址模型基于層次分析法的選址方法AHP2022/7/765一、多 重 心 法找出各個供需點之間使運輸成本最小的物流設(shè)施（倉庫）的位置；要確定的物流設(shè)施點不止一個，就必須將所有的供需點預(yù)先分配給位置待定的倉庫；先將問題劃分為若干個供需點群落，群落數(shù)與待選址倉庫數(shù)相等，找出每個群落的精確重心點。2022/7/766對于多倉庫問題：把相互距離最近的供需點組合起

31、來形成群落，找出各群落的重心位置，然后將各點重新分配到這些位置已知的倉庫，找出修正后的各群落新的重心位置，繼續(xù)上述過程直到不再有任何變化。方法：初始需求點群落 初始設(shè)施點 初始運費 根據(jù)設(shè)施點的位置第一次調(diào)整群落之間的需求點數(shù)目 根據(jù)需求點的數(shù)目調(diào)整設(shè)施點位置 第二次調(diào)整2022/7/767如何把供需點組合起來形成群落？（1）集合覆蓋模型（2）最大覆蓋模型（3）P中值模型2022/7/7681、集合覆蓋模型用盡可能少的設(shè)施去覆蓋所有的需求點。要求物流設(shè)施必須滿足所有需求點的需求。2022/7/769目標(biāo)函數(shù)約束條件N集合中有n個需求點di 第i個需求點的需求量Cj第j個設(shè)施的容量xj =0 ，

32、節(jié)點j沒有物流設(shè)施xj =1，節(jié)點j設(shè)有物流設(shè)施yij 第i個需求點的需求量 被分配給節(jié)點j的部分。70 模型求解 集合覆蓋模型是NP困難問題，雖當(dāng)規(guī)模較小時，可設(shè)計枚舉法或隱枚舉法（如分枝定界法等）求模型的最優(yōu)解，但在實際問題中，往往需求點數(shù)n和可供選擇的候選點數(shù)m較大（也可能nm），一般仍需要設(shè)計近似算法來對模型進(jìn)行求解。下面給出一個最少點覆蓋的啟發(fā)式算法，該算法是最常用也是最簡單的一個近似算法，主要步驟如下： 第一步：初始化。令所有的yi0，xj0，（已分配的需求），并確定集合A(j)和集合B(i)； _A(j)設(shè)施節(jié)點j所覆蓋的需求點i的集合_服務(wù)集合 _B(i)可以覆蓋需求節(jié)點i的設(shè)

33、施節(jié)點j的集合_被服務(wù)集合71 第二步：選擇下一個設(shè)施點。在M中選擇xj0，且A(j)的模為最大的點j為設(shè)施點，即 ，令 ，并在M集合中剔除節(jié)點j，即 。 第三步：確定節(jié)點j的覆蓋范圍。將A(j)中的元素按B(i)的規(guī)模從小到大的順序指派給j，直至j的容量為Dj0或A(j)為空。其中對于iA(j)且，yi1，將i支配給j的方法為：若 ，則令yij1yi，DjDjdi(1yi)，yi1，在A(j)和N中剔除需求點i。若 ，則令 第四步：若N或M為空，停止；否則，更新集合A(j)和集合B(i)，轉(zhuǎn)第二步。 例：在某區(qū)域需規(guī)劃建設(shè)若干個農(nóng)貿(mào)市場為將來該區(qū)9個主要居民點提供服務(wù)，除第6居民點外，其他各

34、點均有建設(shè)市場的條件，如圖所示。已知市場的最大服務(wù)直徑為3km，為保護(hù)該區(qū)域的環(huán)境，希望盡可能少地建造農(nóng)貿(mào)市場。問應(yīng)如何規(guī)劃？ 解：N1,2,3,4,5,6,7,8,9，M1,2,3,4,5,6,7,8,9，由圖兩點間的最短距離，根據(jù)最大服務(wù)半徑為3km的約束及第6居民點不適合建市場的要求，可確定集合A(j)和B(i)。如表所示，值得指出的是本問題沒有需求量和容量，故無需考慮約束式。7217849256322434143233211圖 小區(qū)居民點位置圖73居民點號A(j)B(i)11,2,3,41,2,3,421,2,31,2,331,2,3,4,51,2,3,4,541,3,4,5,6,71

35、,3,4,5,753,4,5,63,4,564,5,7,874,6,7,84,7,886,7,8,97,8,998,98,9表 候選點服務(wù)范圍 因為A(4)=1,3,4,5,6,7，|A(4)|=6為最大，故首先選取j4。由于無容量約束故依次指派5,7,1,6,3,4點歸節(jié)點4服務(wù)。 此時，N2,8,9,M1,2,3,5,7,8,9,更新集合A(j)和集合B(i)后如表所示。74居民點號A(j)B(i)12222324567888,98,998,98,9表 候選點服務(wù)范圍 因為A(8)8,9，|A(8)|2為最大，故首先選取j8，并且8，9兩點歸節(jié)點8服務(wù)。 同理，再迭代一次，得j2，居民點2

36、歸節(jié)點2服務(wù)。 因此，計算結(jié)果為（4,8,2）。 注意：近似算法一般不能求得問題的最優(yōu)解，請大家驗證?2022/7/7752、最大覆蓋模型用有限的設(shè)施點為盡可能多的需求點提供服務(wù)。物流設(shè)施僅僅覆蓋有限個需求點的需求。2022/7/776目標(biāo)函數(shù)約束條件N集合中有n個需求點di 第i個需求點的需求量Cj第j個設(shè)施的容量xj =0 ，節(jié)點j沒有物流設(shè)施xj =1，節(jié)點j設(shè)有物流設(shè)施yij 第i個需求點的需求量 被分配給節(jié)點j的部分。P 允許投資的設(shè)施數(shù)目2022/7/777模型求解 同樣可以設(shè)計近似算法進(jìn)行求解，最常用的方法是Richard Church和Charles Re Velle設(shè)計的貪婪

37、算法，該算法是一個空集合作為原始的解集合，然后在剩下的所有的其他候選點中選擇一個具有最大滿足能力的候選點加入到原來的候選集合中，如上往復(fù)，直到到了設(shè)施數(shù)目的限制或者全部的需求都得到滿足為止。集合覆蓋模型要滿足所有的需求點，而最大覆蓋模型則只覆蓋有限的需求點，兩種模型的應(yīng)用情況取決于設(shè)施的資源充足與否。2022/7/7783、P中值模型對于給定位置和數(shù)量的需求點和物流設(shè)施點集合，選擇P個物流設(shè)施點，找到合適位置和需求數(shù)量的需求點，達(dá)到總運費最低。1、選擇合適的設(shè)施位置（變量x)2、指派需求點到相應(yīng)的設(shè)施（變量y）2022/7/779目標(biāo)函數(shù)約束條件N集合中有n個需求點di 第i個需求點的需求量C

38、ij從點i到j(luò)的單位運輸費用xj =0 ，節(jié)點j沒有物流設(shè)施xj =1，節(jié)點j設(shè)有物流設(shè)施yij 第i個需求點的需求量 被分配給節(jié)點j的部分。P 允許投資的設(shè)施數(shù)目保證每個需求點只有一個設(shè)施提供服務(wù)?？傇O(shè)施數(shù)為P個。2022/7/780二、混合-整數(shù)線性規(guī)劃模型：整數(shù)規(guī)劃考慮因素：工廠到倉庫、倉庫到需求地的固定成本（實際用地等所承擔(dān)的費用）、線性可變成本（運輸成本、庫存持有成本），工廠、需求商的輸出、輸入數(shù)量以及產(chǎn)品價格。物流設(shè)施包括：工廠、車站、倉庫、零售、服務(wù)點。2022/7/781約束條件：不能超過每個工廠的供貨能力；所有產(chǎn)品的需求必須得到滿足；各倉庫的吞吐量不能超過其吞吐能力；必須達(dá)到最低吞吐量倉庫才可以開始運營；同一消費者需要的所有產(chǎn)品必須由同一倉庫供給。目標(biāo)函數(shù)： 找出物流網(wǎng)絡(luò)中倉庫的數(shù)量、規(guī)模和位置，使得通過該網(wǎng)絡(luò)運送所有產(chǎn)品的采購成本（價格）、設(shè)施固定成本和線性可變成本的總和，在滿足約束的情況下最低。2022/7/782說明：對于多設(shè)施規(guī)劃問題（重心法和整數(shù)規(guī)劃法）