物流多設(shè)施選址模型概述

集合覆蓋模型多設(shè)施選址模型P-中值模型問題描述在一個(gè)給定數(shù)量和位置需求集合和一個(gè)候選設(shè)施位置集合下，確定p個(gè)設(shè)施位置，并指派每個(gè)需求點(diǎn)到一個(gè)特定設(shè)施，使之到達(dá)設(shè)施和需求點(diǎn)之間運(yùn)輸費(fèi)用最低。最大覆蓋模型P-中值模型物流多設(shè)施選址模型概述第1頁多設(shè)施選址模型模型建立集合覆蓋模型P-中值模型最大覆蓋模型P-中值模型3-23公式物流多設(shè)施選址模型概述第2頁集合覆蓋模型多設(shè)施選址模型P-中值模型模型求解求解一個(gè)P-中值模型需要處理兩方面問題：選擇適當(dāng)設(shè)施位置（x變量）指派需求點(diǎn)到對(duì)應(yīng)設(shè)施中去（y變量）與覆蓋模型相同，求解P-中值模型主要有兩大類方法，即準(zhǔn)確計(jì)算法和啟發(fā)式算法。慣用求解P-中值模型啟發(fā)式算法被稱為：貪婪取走啟發(fā)式算法。最大覆蓋模型P-中值模型物流多設(shè)施選址模型概述第3頁多設(shè)施選址模型貪婪取走算法第二步第三步將每個(gè)需求點(diǎn)指派給k個(gè)設(shè)施點(diǎn)中離其距離最近一個(gè)設(shè)施點(diǎn)。求出總運(yùn)輸費(fèi)用Z若k=p，得到k個(gè)設(shè)施點(diǎn)及各需求點(diǎn)指派結(jié)果，停頓不然，轉(zhuǎn)第四步第四步從k個(gè)候選點(diǎn)中確定一個(gè)取走點(diǎn)，滿足：若將它取走并將它需求點(diǎn)指派給其它最近設(shè)施后，總費(fèi)用增加量最小從候選集合中刪去取走點(diǎn)，令k=k-1，轉(zhuǎn)第二步第一步令當(dāng)前選中設(shè)施點(diǎn)數(shù)k=m，即全部m個(gè)候選位置都選中集合覆蓋模型最大覆蓋模型P-中值模型P-中值模型物流多設(shè)施選址模型概述第4頁多設(shè)施選址模型

某企業(yè)在一新地域經(jīng)過一段時(shí)間宣傳廣告后，得到了8個(gè)超市訂單，因?yàn)樵摰赜螂x總部較遠(yuǎn)，企業(yè)擬在該地域新建2個(gè)倉庫，用最低配送成原來滿足該地域需求。經(jīng)過一段時(shí)間實(shí)地考查之后，已經(jīng)有4個(gè)候選地址，以下列圖所表示。從候選地址到各個(gè)超市運(yùn)輸成本cij、各超市需求量di都已經(jīng)確定，以下表所表示。試選擇其中兩個(gè)候選點(diǎn)作為倉庫地址，使總運(yùn)輸成本最小。集合覆蓋模型最大覆蓋模型P-中值模型P-中值模型3-6例物流多設(shè)施選址模型概述第5頁第一步初始化，令k=m=4；將每個(gè)客戶指派給運(yùn)輸成本最低一個(gè)候選位置，指派結(jié)果為：A=(a1,a2,…a8)=(1,1,1,4,4,2,3,3)；總費(fèi)用多設(shè)施選址模型集合覆蓋模型最大覆蓋模型P-中值模型3-6例物流多設(shè)施選址模型概述第6頁多設(shè)施選址模型第二步分別對(duì)取走候選點(diǎn)1,2,3,4進(jìn)行分析，并計(jì)算各自費(fèi)用增量：集合覆蓋模型最大覆蓋模型P-中值模型3-6例取走候選點(diǎn)1，結(jié)果(4,2,2,4,4,2,3,3)，Z=3200，費(fèi)用增量ΔZ=720物流多設(shè)施選址模型概述第7頁多設(shè)施選址模型第二步分別對(duì)取走候選點(diǎn)1,2,3,4進(jìn)行分析，并計(jì)算各自費(fèi)用增量：集合覆蓋模型最大覆蓋模型P-中值模型3-6例取走候選點(diǎn)2，結(jié)果(1,1,1,4,4,3,3,3)，Z=2620，費(fèi)用增量ΔZ=140物流多設(shè)施選址模型概述第8頁多設(shè)施選址模型第二步分別對(duì)取走候選點(diǎn)1,2,3,4進(jìn)行分析，并計(jì)算各自費(fèi)用增量：集合覆蓋模型最大覆蓋模型P-中值模型3-6例取走候選點(diǎn)3，結(jié)果(1,1,1,4,4,2,4,2)，Z=3620，費(fèi)用增量ΔZ=1140物流多設(shè)施選址模型概述第9頁多設(shè)施選址模型第二步分別對(duì)取走候選點(diǎn)1,2,3,4進(jìn)行分析，并計(jì)算各自費(fèi)用增量：集合覆蓋模型最大覆蓋模型P-中值模型3-6例取走候選點(diǎn)4，結(jié)果(1,1,1,2,3,2,3,3)，Z=3520，費(fèi)用增量ΔZ=1040物流多設(shè)施選址模型概述第10頁多設(shè)施選址模型第二步取走候選點(diǎn)2，使得ΔZ=140為最小所以，第一個(gè)被取走是候選點(diǎn)2候選位置：k=4-1=3指派結(jié)果：(1,1,1,4,4,3,3,3)總費(fèi)用：Z=2620集合覆蓋模型最大覆蓋模型P-中值模型3-6例物流多設(shè)施選址模型概述第11頁多設(shè)施選址模型第三步分別對(duì)取走候選點(diǎn)1,3,4進(jìn)行分析，并計(jì)算各自費(fèi)用增量：集合覆蓋模型最大覆蓋模型P-中值模型3-6例取走候選點(diǎn)1，結(jié)果(4,4,4,4,4,3,3,3)，Z=4540，費(fèi)用增量ΔZ=1920物流多設(shè)施選址模型概述第12頁多設(shè)施選址模型第三步分別對(duì)取走候選點(diǎn)1,3,4進(jìn)行分析，并計(jì)算各自費(fèi)用增量：集合覆蓋模型最大覆蓋模型P-中值模型3-6例取走候選點(diǎn)3，結(jié)果(1,1,1,4,4,4,4,4)，Z=5110，費(fèi)用增量ΔZ=2490物流多設(shè)施選址模型概述第13頁多設(shè)施選址模型第三步分別對(duì)取走候選點(diǎn)1,3,4進(jìn)行分析，并計(jì)算各自費(fèi)用增量：集合覆蓋模型最大覆蓋模型P-中值模型3-6例取走候選點(diǎn)4，結(jié)果(1,1,1,1,3,3,3,3)，Z=3740，費(fèi)用增量ΔZ=1120物流多設(shè)施選址模型概述第14頁多設(shè)施選址模型第三步取走候選點(diǎn)4，使ΔZ=1120為最小所以，第二個(gè)被取走是候選點(diǎn)4候選位置：k=3-1=2指派結(jié)果：(1,1,1,1,3,3,3,3)總費(fèi)用：Z=3740集合覆蓋模型最大覆蓋模型P-中值模型3-6例物流多設(shè)施選址模型概述第15頁多設(shè)施選址模型第四步∵k=2=p∴計(jì)算結(jié)束，得到2個(gè)設(shè)施點(diǎn)及各客戶指派結(jié)果：在候選位置1,3建設(shè)新倉庫指派結(jié)果：(1,1,1,1,3,3,3,3)總運(yùn)輸費(fèi)用：Z=3740集合覆蓋模型最大覆蓋模型P-中值模型3-6例物流多設(shè)施選址模型概述第16頁多設(shè)施選址模型

某企業(yè)在某地域有6個(gè)主要客戶A1,A2,A3,A4,A5和A6，該企業(yè)擬在該地域新建兩個(gè)倉庫，用最低運(yùn)輸成原來滿足該地域主要客戶需求。經(jīng)過一段時(shí)間實(shí)地考查之后，企業(yè)確定三個(gè)候選地址D1、D2和D3，以下列圖所表示。從候選地址到各客戶運(yùn)輸成本、各客戶需求量都已經(jīng)確定，以下表所表示。試確定倉庫位置。集合覆蓋模型最大覆蓋模型P-中值模型P-中值模型3-3練習(xí)物流多設(shè)施選址模型概述第17頁多設(shè)施選址模型鮑摩-瓦爾夫(Baumol-Wolfe)模型（1）鮑摩-瓦爾夫(Baumol-Wolfe)模型，又稱為單品種選址模型。模型從一組候選地點(diǎn)中選擇若干個(gè)位置作為物流設(shè)施節(jié)點(diǎn)，使得從已知若干個(gè)資源點(diǎn)(工廠)，經(jīng)過某幾個(gè)設(shè)施節(jié)點(diǎn)，向若干個(gè)需求點(diǎn)(客戶)運(yùn)輸同一產(chǎn)品時(shí)，總物流布局成本為最小。奎漢-哈姆勃茲模型鮑摩-瓦爾夫模型物流多設(shè)施選址模型概述第18頁多設(shè)施選址模型3-24公式奎漢-哈姆勃茲模型鮑摩-瓦爾夫模型物流多設(shè)施選址模型概述第19頁多設(shè)施選址模型奎漢-哈姆勃茲(Kuehn-Hamburger)模型奎漢-哈姆勃茲(Kuehn-Hamburger)模型，又稱為多品種選址模型。模型從一組候選地點(diǎn)中選擇若干個(gè)位置作為物流設(shè)施節(jié)點(diǎn)，使得從已知若干個(gè)資源點(diǎn)(工廠)，經(jīng)過某幾個(gè)設(shè)施節(jié)點(diǎn)，向若干個(gè)需求點(diǎn)(客戶)運(yùn)輸各種產(chǎn)品時(shí)，總物流布局成本為最小。鮑摩-瓦爾夫模型奎漢-哈姆勃茲模型物流多設(shè)施選址模型概述第20頁多設(shè)施選址模型3-25公式鮑摩-瓦爾夫模型奎漢-哈姆勃茲模型物流多設(shè)施選址模型概述第21頁多設(shè)施選址模型鮑摩-瓦爾夫(Baumol-Wolfe)模型（2）鮑摩-瓦爾夫(Baumol-Wolfe)模型（2）屬于非線性規(guī)劃，是以逐次求解運(yùn)輸問題為思緒啟發(fā)式算法。其只考慮租用倉庫或配送中心，所以模型中不包含倉庫或配送中心固定投資成本?？鼭h-哈姆勃茲模型鮑摩-瓦爾夫模型物流多設(shè)施選址模型概述第22頁多設(shè)施選址模型鮑摩-瓦爾夫(Baumol-Wolfe)模型（2）

鮑摩-沃爾夫法（2）問題抽象定義為：①運(yùn)輸成本與運(yùn)輸量呈簡(jiǎn)單線性關(guān)系。②用戶位置及需求量為已知。③配送中心容量無限制。④配送中心候選位置及其變動(dòng)成本已知。

在上述四項(xiàng)假設(shè)條件下，求解配送中心個(gè)數(shù)及位置，以使運(yùn)輸成本及存放成本之和最小。奎漢-哈姆勃茲模型鮑摩-瓦爾夫模型物流多設(shè)施選址模型概述第23頁多設(shè)施選址模型鮑摩-瓦爾夫(Baumol-Wolfe)模型（2）

與其它選址問題不一樣，鮑摩—沃爾夫（2）不再假設(shè)配送中心存放成本隨流通量呈線性改變，因?yàn)閷?shí)際中更常見情況是存放成本隨流通量增大而變得平坦，即表現(xiàn)出一定規(guī)模經(jīng)濟(jì)性。所以鮑摩—沃爾夫假設(shè)存放成本與配送中心流通量之間函數(shù)關(guān)系為：奎漢-哈姆勃茲模型鮑摩-瓦爾夫模型3-26公式物流多設(shè)施選址模型概述第24頁多設(shè)施選址模型鮑摩-瓦爾夫(Baumol-Wolfe)模型（2）

——存放成本；

——

配送中心單位流通量可變費(fèi)用；

——配送中心流通量。

則邊際存放成本（存放費(fèi)率）

奎漢-哈姆勃茲模型鮑摩-瓦爾夫模型3-27公式物流多設(shè)施選址模型概述第25頁多設(shè)施選址模型鮑摩-瓦爾夫(Baumol-Wolfe)模型（2）

奎漢-哈姆勃茲模型鮑摩-瓦爾夫模型3-28公式物流多設(shè)施選址模型概述第26頁多設(shè)施選址模型迭代算法第二步第三步求解工廠i和需求點(diǎn)j間最優(yōu)運(yùn)輸問題,得到,并統(tǒng)計(jì)每個(gè)備選配送中心流通量,進(jìn)而依據(jù)式(3-27)計(jì)算各備選配送中心邊際成本。令L=L+1，求改進(jìn)方案。用

代替，求解運(yùn)輸問題模型求解一組新。第四步新舊方案比較，假如兩個(gè)方案完全相同，迭代結(jié)束，取得最優(yōu)解。不然返回第二步，繼續(xù)迭代，直到與完全相同。第一步初始迭代數(shù)L=0令全部q個(gè)備選配送中心上流通量，則對(duì)全部工廠i和需求點(diǎn)j,求各工廠和各需求點(diǎn)之間最低費(fèi)率鮑摩-瓦爾夫(Baumol-Wolfe)模型（2）物流多設(shè)施選址模型概述第27頁多設(shè)施選址模型某區(qū)域（企業(yè)）配送中心在選址規(guī)劃時(shí),經(jīng)調(diào)查大致有3個(gè)進(jìn)貨渠道,分8個(gè)客戶方向,現(xiàn)有5個(gè)配送中心候選地址,詳細(xì)數(shù)據(jù)見以下2表,求總費(fèi)用最小時(shí)配送中心選址和配送方案。鮑摩-瓦爾夫(Baumol-Wolfe)模型（2）3-7例工廠到備選配送中心單位運(yùn)費(fèi)及其生產(chǎn)能力備選配送中心到需求點(diǎn)單位運(yùn)費(fèi)及客戶需求量各配送中心單位可變費(fèi)用物流多設(shè)施選址模型概述第28頁第一步令，依據(jù)原始數(shù)據(jù)由公式求出從各生產(chǎn)地i經(jīng)備選配送中心k到需求點(diǎn)j最小運(yùn)費(fèi)，進(jìn)而經(jīng)過運(yùn)輸問題最小元素法知經(jīng)過各配送中心經(jīng)過量。多設(shè)施選址模型3-7例鮑摩-瓦爾夫(Baumol-Wolfe)模型（2）最小運(yùn)輸成本及所經(jīng)過配送中心物流多設(shè)施選址模型概述第29頁第二步求解該運(yùn)輸問題，得到初始運(yùn)輸方案、各配送中心流通量和單位可變費(fèi)用。注：因?yàn)閭溥x配送中心D1可變費(fèi)用低于D2，所以A2-B3選擇經(jīng)過D1。計(jì)算總費(fèi)用Z0=12×50+16×20+9×30+17×30+8×40+12×60+11×30+15×20+15×20+300×(80^0.5)+600×(50^0.5)+500×(100^0.5)+200×(70^0.5)=17269.2多設(shè)施選址模型3-7例鮑摩-瓦爾夫(Baumol-Wolfe)模型（2）初始運(yùn)輸方案各配送中心流通量

及邊際可變費(fèi)用物流多設(shè)施選址模型概述第30頁第三步令L=L+1，由公式，求出從各生產(chǎn)地i經(jīng)備選配送中心k到需求點(diǎn)j最小運(yùn)輸成本，進(jìn)而經(jīng)過運(yùn)輸問題最小元素法知經(jīng)過各配送中心經(jīng)過量。多設(shè)施選址模型3-7例鮑摩-瓦爾夫(Baumol-Wolfe)模型（2）最小運(yùn)輸成本及所經(jīng)過配送中心物流多設(shè)施選址模型概述第31頁求解該運(yùn)輸問題，得到改進(jìn)運(yùn)輸方案、各配送中心流通量和邊際可變費(fèi)用。為計(jì)算方便，按以上最小運(yùn)輸成本表格計(jì)算總費(fèi)用。

Z1=34.8×50+32.8×20+25.8×30+33.8×30+33×40+37×60+23×30+27×2+27×20=9494注意：盡管在上面最小運(yùn)輸成本表格中隱含了可變費(fèi)用，但其是按邊際可變費(fèi)用計(jì)算，即最終一個(gè)單位產(chǎn)品存放成本。依據(jù)邊際效用遞減理論，其余產(chǎn)品