多物流節(jié)點(diǎn)選址方法與模型課件

1、 多物流節(jié)點(diǎn)選址方法與模型多重心法覆蓋模型P-中值模型CFLP模型鮑摩-瓦爾夫（Baumol-Wolfe）模型奎漢-哈姆勃茲（Kuehn-Hamburge）模型1、多重心法 分組如何分？ 選址計(jì)算 調(diào)整分組為什么要調(diào)整？如何調(diào)整？ 分組結(jié)果變化？有，回到第二步；無，結(jié)束。例 某公司計(jì)劃建立2個(gè)藥品配送點(diǎn)向10個(gè)藥品連鎖店送貨，各藥品連鎖店的地址和坐標(biāo)和藥品每日需求如下圖，運(yùn)價(jià)均為1，試確定這兩個(gè)藥品配送點(diǎn)的地址，使送貨運(yùn)輸費(fèi)用最低。連鎖店 j12345678910Xj70958020401040751090Yj7050206010506090304需求量8106578125119藥品連鎖店地址

2、坐標(biāo)與需求量1.分組連鎖店 j12345678910Xj70958020401040751090Yj7050206010506090304需求量81065781251192.選址計(jì)算利用精確重心法，求出2個(gè)配送點(diǎn)的地址坐標(biāo)為（P1,Q1）=(74.342,46.147),（P2,Q2）=（40,60）3.計(jì)算各藥品連鎖店到兩個(gè)配送點(diǎn)的送貨運(yùn)輸費(fèi)用連鎖店號jXjYj需求量到（P1,Q1）運(yùn)輸費(fèi)用到（P2,Q2）運(yùn)輸費(fèi)用170708193.9598252.98222955010210.1425559.017380206160.513339.4113420605280.399710054010734

3、9.0171350610508515.6581252.98227406012444.36930875905219.2897230.48869103011729.7087466.69051090409151.3924484.6648調(diào)整分組為1,2,3,5,8,10和4,6,7,94.將新的分組進(jìn)行重新選址，運(yùn)用精確重心法計(jì)算出新的配送點(diǎn)的地點(diǎn)坐標(biāo)，再次算出各個(gè)藥品連鎖店到兩個(gè)配送點(diǎn)的運(yùn)輸費(fèi)用，繼續(xù)進(jìn)行重新分組，分組迭代，直至迭代后分組不變，不變的分組就是最佳的分配方案。2、覆蓋模型 1)集合覆蓋模型，用最小數(shù)量的設(shè)施去覆蓋所有的需求點(diǎn)。2)最大覆蓋模型，在給定數(shù)量的設(shè)施下，覆蓋盡可能多的需求點(diǎn)

4、。yj xjNminij 1,jMiNdiyij C jx j,iA( j)jB(i)iN, jMjMyij 0,x j 0,1, 1)集合覆蓋模型N ：需求點(diǎn)集合；M：候選點(diǎn)集合；dj：第j個(gè)節(jié)點(diǎn)的需求量；Cj：設(shè)施節(jié)點(diǎn)j的容量；yij：節(jié)點(diǎn)j需求中被分配給節(jié)點(diǎn)的部分；xj：節(jié)點(diǎn)j是否被選中。12 例 在某區(qū)域需規(guī)劃建設(shè)若干個(gè)農(nóng)貿(mào)市場為將來該區(qū)9個(gè)主要居民點(diǎn)提供服務(wù)。除第6居民點(diǎn)外，其他各點(diǎn)均有建設(shè)市場的條件，如圖所示。已知市場的最大服務(wù)半徑為3km，為保護(hù)該區(qū)域的環(huán)境，希望盡可少地建造農(nóng)貿(mào)市場。問應(yīng)如何規(guī)劃？9786543222233333444111居民點(diǎn)A(j)B(i)11，2，3，4

5、1，2，3，421，2，3l，2，33l，2，3，4，5，61，2，3，4，541，3，4，5，6，71，3，4，5，753，4，5，63，4，563，4，5，7，874，6，7，84，7，886，7，8，97，8，998，98，9127865432292333334244111A（j）：節(jié)點(diǎn)j所覆蓋的需求節(jié)點(diǎn)的集合B（i）：可以覆蓋需求節(jié)點(diǎn)i的節(jié)點(diǎn)j的集合最少點(diǎn)覆蓋啟發(fā)式算法選擇指派候選點(diǎn)的集合1,3,4,7,8考慮建一個(gè)農(nóng)貿(mào)市場，不滿足覆蓋全部需求 點(diǎn)的要求考慮建兩個(gè)農(nóng)貿(mào)市場，運(yùn)用窮舉法，農(nóng)貿(mào)市場可取(1,3),(1,4),(1,7),.,(7,8) ，發(fā)現(xiàn)?。?,8）作為農(nóng)貿(mào)市場選址時(shí)，

6、能滿足所有需求點(diǎn)的配送需求因此，最少建兩個(gè)農(nóng)貿(mào)市場，能使全部居民點(diǎn)覆蓋，建設(shè)農(nóng)貿(mào)市場的居民點(diǎn)是3和8(2)最大覆蓋模型max d i y ijj N i A ( j ) y ij 1, i Nj B ( i ) d i y ij C j x j , j Mi A ( j )j Mjx p , j Mxj 0,1, j My ij 0, i N , j M12 例 在某區(qū)域需規(guī)劃建設(shè)若干個(gè)農(nóng)貿(mào)市場為將來該區(qū)9個(gè)主要居民點(diǎn)提供服務(wù)。除第6居民點(diǎn)外，其他各點(diǎn)均有建設(shè)市場的條件，如圖所示。已知市場的最大服務(wù)半徑為3km，為保護(hù)該區(qū)域的環(huán)境，最多只能建2個(gè)農(nóng)貿(mào)市場。問應(yīng)如何規(guī)劃？978654322223

7、333344411111，2，3，4231，2，3l，2，3，4，5，64567891，3，4，5，6，73，4，5，64，6，7，86，7，8，98，9129786543222233333444111A（j）：節(jié)點(diǎn)j所覆蓋的需求節(jié)點(diǎn)的集合居民點(diǎn) A ( j)貪婪算法選擇具有最大滿足能力的候選點(diǎn)居民點(diǎn)123456789A ( j)22288，98，9居民點(diǎn)123456789A ( j)1，2，3，41，2，3l，2，3，4，5，61，3，4，5，6，73，4，5，64，6，7，86，7，8，98，9解為（4,8）最優(yōu)解？居民點(diǎn)123456789A ( j)77,87，8，98，9居民點(diǎn)1234

8、56789A ( j)1，2，3，41，2，3l，2，3，4，5，61，3，4，5，6，73，4，5，64，6，7，86，7，8，98，9（3,8）滿足全部需求，為最優(yōu)解 現(xiàn)有一個(gè)企業(yè)有18個(gè)分銷公司，該企業(yè)需要建立3個(gè)配送倉庫，經(jīng)該企業(yè)的考核，有6個(gè)候選地，現(xiàn)在身為企業(yè)決策者的你，要從6個(gè)候選地選出3個(gè)配送倉庫你應(yīng)該如何選？或者說你要考慮的因素有哪一些？總運(yùn)輸費(fèi)用從分銷公司到配送中心的單位運(yùn)輸費(fèi)用分銷公司運(yùn)輸?shù)男枨罅课覀円绾芜x擇倉庫？3.P中值模型指在一個(gè)給定數(shù)量和位置的需求集合和一個(gè)候選設(shè)施位置的集合下，分別為p個(gè)設(shè)施找到合適的位置并指派每個(gè)需求點(diǎn)到一個(gè)特定的設(shè)施，使之達(dá)到在工廠和需求點(diǎn)

9、之間的運(yùn)輸費(fèi)用和最低。需求點(diǎn)設(shè)施候選點(diǎn)P=3 d icij yijiN jMminij yjM1,i Nj pxjMyij=xj，i N，jMP中值模型求解P中值模型方法1、精確法2、啟發(fā)式算法-貪婪取走啟發(fā)式算法貪婪取走總費(fèi)用增加量最小P中值模型貪婪取走算法：第一步：令當(dāng)前選中設(shè)施點(diǎn)數(shù)k m，即將所有m個(gè)候選位置都選中。第二步：將每個(gè)客戶指派給k個(gè)設(shè)施點(diǎn)中距離最近的一個(gè)設(shè)施點(diǎn)。求出總運(yùn)輸費(fèi)用Z。第三步：若k p，輸出設(shè)施點(diǎn)及各客戶的指派結(jié)果，停止；否則，轉(zhuǎn)第四步。第四步：從k個(gè)設(shè)施候選點(diǎn)中確定一個(gè)取走點(diǎn)，滿足：假如將它取走并將它的客戶指派給其他的最近設(shè)施點(diǎn)后，總費(fèi)用增加量最小。第五步：從候選

10、點(diǎn)集合中刪去取走點(diǎn)，令k k 1，轉(zhuǎn)第二步。Greedy Dropping Heuristic algorithm 某醫(yī)藥公司有8個(gè)分銷公司(A1 A8)，公司擬新建2個(gè)配送倉庫，用最低的運(yùn)輸成本來滿足8個(gè)分銷公司的需求。經(jīng)過實(shí)地考察后，公司確定5個(gè)候選(D1D5),從候選地到各分銷公司的單位運(yùn)輸成本、各分銷公司的需求已確定，如表2-7所示，各分銷公司分布及候選倉庫位置如圖2-12所示，試確定倉庫的位置與分銷公司分派情況，并計(jì)算出各倉庫的運(yùn)輸成本。D1D2D3D4D5需求量A1304548103510A225607035506A3281525321011A4453020241225A55812

11、25603015A6653015573313A7653516452820A822303520168各客戶需求量與單位運(yùn)輸成本矩陣圖第一步：貪婪總運(yùn)輸成本=10*10+25*6+10*11+.=1483 k=52 當(dāng)移走D1之后，受到影響的是A2，A2指派給（除D1外，被移除之后）運(yùn)輸費(fèi)用最低的D4，所產(chǎn)生的運(yùn)費(fèi)增加量為=210（35*6）-150（25*6）=60 移除D1后對整體運(yùn)費(fèi)的影響是增加了60 同理當(dāng)移走D2之后，所產(chǎn)生的運(yùn)費(fèi)增加量為=195當(dāng)移走D3之后，所產(chǎn)生的運(yùn)費(fèi)增加量為=435當(dāng)移走D4之后，所產(chǎn)生的運(yùn)費(fèi)增加量為=200當(dāng)移走D5之后，所產(chǎn)生的運(yùn)費(fèi)增加量為=287 K=42

12、總運(yùn)費(fèi)增加量最小的60，也就是移除D1后對整體運(yùn)費(fèi)影響是最小的，故移除D1最為合理。同理移除的三個(gè)候選地分別是D1，D3，D4例 某公司在某新地區(qū)經(jīng)過一段時(shí)間的宣傳廣告后，得到了 8 個(gè)超市的訂單，由于該新地區(qū)離總部較遠(yuǎn)，該公司擬在該地區(qū)新建 2 個(gè)倉庫，用最低的運(yùn)輸成本來滿足該地區(qū)的需求。經(jīng)過一段時(shí)間的實(shí)地考查之后，已有 4 個(gè)候選地址。如圖所示。從候選地址到各個(gè)超市運(yùn)輸成本Cij、各個(gè)超市的需求量di都已經(jīng)確定，試選擇其中的兩個(gè)候選點(diǎn)作為倉庫地址，使總運(yùn)輸成本最小。( p 2)。124567842133圖 超市及倉庫候選點(diǎn)位置124567842133圖 倉庫選址及客戶指派結(jié)果該模型是帶容量

13、限制的多設(shè)施選址問題s.t. Xij（運(yùn)輸量）=Dj(需求量) Xij=WiYi（配送中心容量） Yi=0CFLP模型求解方案一窮舉法方案二分支定界法方案三 lingo軟件求解lingo軟件求解lingo模型基本用法（通常由以下三個(gè)部分組成）(1)目標(biāo)函數(shù):一 般表示成求某個(gè)數(shù)學(xué)表達(dá)式的最大值或最小值。(2)決策變量:目標(biāo)函數(shù)值取決于哪些變(3)約束條件:對變量附加一些條件限制(通常用等式或不等式表示)注:LINGO默認(rèn)所有決策變量都非負(fù)，因而變量非負(fù)條件可以不必輸入。LINGO模型的基本組成:(1)集合定義部分:集合的名稱集合內(nèi)的成員(組成集合的個(gè)體， 元素)，集合的屬性(可以看成是與集合有

14、關(guān)的變量或常量)(2)數(shù)據(jù)初始化(數(shù)據(jù)段)sets函數(shù)給定義的所有集合的已知屬性賦初值“/”是指規(guī)定語法的規(guī)則(3)目標(biāo)函數(shù)和約束條件for(s:e)該函數(shù)常用在約束條件中，表示對集合s中的每個(gè)成員都生成一個(gè)約束條件表達(dá)式，表達(dá)式的具體形式由參數(shù)e描述. sum(s:e)對集合s中的每個(gè)成員，分別得到表達(dá)式e的值然后返回所有這些值的和bin（x）限制x為0或1需求點(diǎn)B1B2B3B4B5B6B7B8需求量101010155151015例 有兩個(gè)資源廠A 1、 A2可供資源量分別為a1 40單位，a2 50單位；有 8 個(gè)需求點(diǎn)Bj(j 1,2.,8)，各點(diǎn)需求量如表 1 所示；已選定 5 個(gè)備選

15、網(wǎng)點(diǎn)DK(K 1,2,.,5)網(wǎng)點(diǎn)，存儲(chǔ)費(fèi)用和網(wǎng)點(diǎn)規(guī)模的關(guān)系為一方根函數(shù)Hj j dK 。其中dK 為 1/2 吞吐量。表 1 各需求點(diǎn)需求量匯源B1B2B3B4B5B6B7B8資源量A112/D118/D110/D113/D510/D313/D311/D211/D240A217/D515/D511/D510/D511/D58/D416/D48/D450需求量101010155151015D1D2D3D4D5中轉(zhuǎn)量201552525邊際成本(四舍五入)8101787步驟一 求初始方案步驟二 求邊際存儲(chǔ)費(fèi)用 總成本2499D1D2D3D4D5B1B2B3B4B5B6B7B8A17781211A2

16、1412968D18511385101111D2101416894744D3171011352595D4815139672102D57973265128匯源B1B2 B3B4B5B6B7B8A120D125 18D5 D120D520D122D421D221D240A224D522 18D5 D517D521D416D424D416D4501010 10155151015步驟三新調(diào)運(yùn)問題新費(fèi)率表新運(yùn)輸規(guī)劃模型匯源B1B2B3B4B5B6B7B8A120D125D51810D1205D5205D121D42410D221D240A224D522D518D517D520D415D4423D415D450101010155151015D1D2D3D4D5中轉(zhuǎn)量251003025邊際成本(四舍五入)81377步驟四 迭代新的費(fèi)率表與前一次