CFLP法(物流選址模型)

1、.CFLP法(Capacitated Facility Location Problem)目錄?1 什么是 CFLP 法 1?2 CFLP 法的基本原理 2?3 CFLP 法案例分析3.1 案例一： 2?4 相關(guān)條目5 參考文獻(xiàn)什么是 CFLP 法1CFLP 法是反町洋一先生創(chuàng)造并發(fā)表的方法，即用LP(線性規(guī)劃 )運(yùn)輸法，確定各配送中心的 市場(chǎng)占有率 ，求出配送分擔(dān)地區(qū)的重心，再用混合整數(shù)計(jì)劃法的“籌劃型”確定場(chǎng)址的建設(shè)位置。其目標(biāo)函數(shù)和約束條件表示如下。minZ = Cij Xij + FiYiiji式中N 需要地的個(gè)數(shù)；配送中心建設(shè)候補(bǔ)地的個(gè)數(shù)；建設(shè)配送中心的個(gè)數(shù)；Dj 需要地 (j)的需

2、要量；Fi配送中心建設(shè)候補(bǔ)地(i)的不變建設(shè)費(fèi)；Ai配送中心建設(shè)候補(bǔ)地的建設(shè)容量；Cij 從候補(bǔ)地 (i)到需要地 (j)的運(yùn)輸單價(jià)；Xij 從配送中心到需要地(j)的運(yùn)輸量；Yi假定在候補(bǔ)地(i)建設(shè)配送中心時(shí)為1，否則為 0。編輯 CFLP 法的基本原理 2編輯版.當(dāng)配送中心的能力有限制，而且用戶的地址和需求量 及設(shè)置多個(gè)配送中心的數(shù)目均已確定的情況下，可采用CFLP 法 (Capacitated Facility Location Problem)，從 配送中心 的備選地點(diǎn)中選出總費(fèi)用最小的由多個(gè)配送中心(假設(shè)有 m 個(gè))組成的配送系統(tǒng)。 這個(gè)方法的基本步驟如下。首先，假定配送中心的備選

3、地點(diǎn)已定，據(jù)此假定在 保證 總運(yùn)輸費(fèi)用最小的前提下，求出各暫定配送中心的供應(yīng)范圍。然后，再在所求出的供應(yīng)范圍內(nèi)分別移動(dòng)配送中心至其他備選地點(diǎn)，以使各供應(yīng)范圍的總費(fèi)用下降。當(dāng)移動(dòng)每個(gè)配送中心的地點(diǎn)都不能繼續(xù)使本區(qū)域總費(fèi)用下降時(shí)， 則計(jì)算結(jié)束； 否則，按可使費(fèi)用下降的新地點(diǎn)，再求各暫定配送中心的供應(yīng)范圍，重復(fù)以上過(guò)程，直到費(fèi)用不再下降為止。(1)初選配送中心的地點(diǎn)。通過(guò)定性分析 ，根據(jù)配送中心的配送能力和用戶需求分布情況適當(dāng)?shù)卮_定配送中心的數(shù)量及其設(shè)置地點(diǎn)，并以此作為初始方案。這一步驟非常重要，因?yàn)樗鼘⒅苯佑绊懻麄€(gè)計(jì)算的收斂速度。(2)確定各暫定的配送中心的供應(yīng)范圍。設(shè)暫定的配送中心有k 個(gè)，分別

4、為s1， s2，sk；用戶有 n 個(gè)；從配送中心si 到用戶 j 地的單位運(yùn)輸費(fèi)用為；以運(yùn)輸費(fèi)用U 最低為目標(biāo)，則可構(gòu)成的運(yùn)輸問(wèn)題模型如下：式中：配送中心si 到用戶 j 的運(yùn)輸量；配送中心si 的容量；Dj 用戶 j 的需求量。解以上運(yùn)輸問(wèn)題，就可求得各暫定配送中心的供應(yīng)范圍。這可表述為如下的用戶集合：(3)在以上各配送范圍內(nèi)，移動(dòng)配送中心到其他備選地點(diǎn)，尋求可能的改進(jìn)方案。設(shè)在原定配送中心si 的配送范圍為N i，除 si之外，可做配送中心備選地點(diǎn)的還有Li 個(gè)，在這些地點(diǎn)設(shè)置配送中心的固定費(fèi)用分別為 Fil 。其中 tlLi ；則以 tl 為新的配送中心時(shí)， Ni 配送范圍內(nèi)的總費(fèi)用為：

5、令：編輯版.若,說(shuō)明步驟 (3)求出的目標(biāo)函數(shù)值是步驟(2)求出的第i 個(gè)配送中心目標(biāo)函數(shù)值的一部分，則令si= ti；否則令 si= si。對(duì)所有 k 個(gè)區(qū)域重復(fù)上述過(guò)程，得到新的配送中心的集合。(4)比較新、舊配送中心集合的總費(fèi)用。若前者大于或等于后者，說(shuō)明已經(jīng)得到了所要求的解，計(jì)算可停止；若前者小于后者， 說(shuō)明新得到的配送心地點(diǎn)可使總費(fèi)用下降，通過(guò) 改善配送中心的供應(yīng)范圍， 還有可能進(jìn)一步降低總費(fèi)用。 為了進(jìn)一步降低總費(fèi)用， 以新的配送系統(tǒng)代替原有的配送系統(tǒng)，重復(fù)步驟(2)至步驟 (4)，直到總費(fèi)用不能再下降為止。按以上步驟得到的收斂解，雖然沒(méi)有得到理論上的證明，但是由于費(fèi)用總是在下降的

6、，因此在實(shí)際應(yīng)用中，可以充分相信所得到的解。編輯 CFLP 法案例分析編輯 案例一： 2現(xiàn)有選址問(wèn)題如圖 1 所示，要求在該地域范圍內(nèi) 12 個(gè)需求點(diǎn)中選出 3 個(gè)作為配送中心的地址。同時(shí)，假設(shè)各配送中心的 固定費(fèi)用 均為 10 個(gè)單位，容量為 13 個(gè)單位， 運(yùn)輸費(fèi)率 為一個(gè)常數(shù)，即運(yùn)輸費(fèi)用與運(yùn)輸距離成正比。編輯版.解：根據(jù)圖1 可得各需求點(diǎn)之間的最短運(yùn)輸距離如表1 所示。表 1 各需求點(diǎn)之間的最短運(yùn)輸距離需求點(diǎn) j需123456789101112求點(diǎn) i1O1674346698921056545771091036503691012121514154763O31011131316151254

7、56307810101312963491070649106674510 1l 86O 29549編輯版.867121310420106279671213109910O48131091015161310564O49118914151264284O5129101512969713950(1)根據(jù)需求量的分布情況，可將配送中心的初始位置暫定在4、 6、 9 三個(gè)節(jié)點(diǎn)上。(2)以點(diǎn) 4、6、9 為配送點(diǎn)，其他各節(jié)點(diǎn)為需求點(diǎn)，求運(yùn)輸問(wèn)題的最優(yōu)解，如表3 一 12所示。于是得到初始方案，總費(fèi)用為179 個(gè)單位。 (具體求解過(guò)程略)(3)根據(jù)以上求得的初始解，可以看出配送中心4 的配送范圍為用戶1、2、3、

8、4、 5 的集合，配送中心 6 的配送范圍為用戶 1、6、8、12 的集合， 配送中心 9 的配送范圍為用戶 1、7、9、 10、11 的集合。表 2 配送中心布局的初始方案配送中心123456789101112供應(yīng)量需求點(diǎn)42423213624521391343213需求量54232435432239對(duì)于集合 1 ， 2， 3， 4， 5 ，配送中心的位置設(shè)在4 時(shí)配送費(fèi)用為：如果配送中心的位置從4 移到其他需求點(diǎn)，則配送費(fèi)用分別為：編輯版.如果移到 1，則；如果移到 2，則；如果移到 3，則；如果移到 5，則。所以，移到配送中心2 時(shí)，配送費(fèi)用最少。同理，通過(guò)計(jì)算，可知對(duì)于用戶集合 l ， 6， 8，12 ，配送中心移到 6，配送費(fèi)用最??；對(duì)于用戶集合 1 ， 7， 9， 10， 11 ，配送中心移到 10，配送費(fèi)用最小。于是，新的配送系統(tǒng)應(yīng)由用戶集合 2 、 6、 10 組成。(4)對(duì)新的配送系統(tǒng) 2 ，6，10重復(fù)步驟 (2)至步驟 (4)，重新計(jì)算。經(jīng)計(jì)算，再次計(jì)算所得配送中心方案與前一次結(jié)果相同， 說(shuō)明方案已達(dá)到最優(yōu)， 所以最終解決方案就是配送中心選擇在 2 ， 6， 10，供應(yīng)方案如表 3 所示，總費(fèi)用為 152 個(gè)單位。表 3 配送中心布局的最終方案配送中心