【文章內(nèi)容簡(jiǎn)介】 2/1221ssssdddd1965)()0( ??????????ZFPD 選址模型 精確重心法 第四步，以點(diǎn)（ ， ）作為配送中心，計(jì)算距離與總費(fèi)用， 第五步，計(jì)算改善的配送中心選址， ???????????????????????????????????????????????6/)1()1()2(6/)1()1()2(41414141i isii isiisi isii isiisdwdywydwdxwx???????????????????????????6])()[()1(])()[()1(])()[()1(])()[()1(2/12242/12232/12222/1221ssssdddd1915)()1( ??????????ZFPD 選址模型 精確重心法 第六步，以點(diǎn)（ ， ）作為配送中心，計(jì)算距離與總費(fèi)用， 此時(shí)， Z(2)(1)=191，雖然結(jié)果是取小數(shù)而得，但二者已經(jīng)非常接近，所以可認(rèn)為最佳點(diǎn)為（ ， ）或（ ， ）。 ???????????????????????????])()[()1(])()[()1(])()[()1(])()[()1(2/12242/12232/12222/1221ssssdddd1915)()2( ??????????ZFPD 選址模型 交叉中值模型與精確重心法 ? 城市距離（折線距離）； ? 適合于小范圍的城市內(nèi)選址問題； ? 目標(biāo)使對(duì)加權(quán)的城市距離最小化； ? 屬于單一設(shè)施連續(xù)點(diǎn)選址問題。 ? 歐幾米德距離（直線距離）； ? 適合于大范圍城市間選址問題； ? 目標(biāo)是使加權(quán)的直線距離最小化； ? 屬于單一設(shè)施的連續(xù)點(diǎn)選址問題。 FPD 選址模型 離散點(diǎn)選址問題指的是在有限的候選位置里面，選取最為合適的一個(gè)或一組位置為最優(yōu)方案，相應(yīng)的模型稱為離散點(diǎn)選址模型。 離散點(diǎn)選址模型與連續(xù)點(diǎn)選址模型的區(qū)別在于：它所擁有的候選方案只有有限個(gè)元素。 對(duì)于離散點(diǎn)選址問題，目前主要有兩種模型，分別是覆蓋模型和中值模型。覆蓋模型常用的又有集合覆蓋模型和最大覆蓋模型兩種。 覆蓋模型（） 覆蓋模型，是對(duì)于需求已知的一些需求點(diǎn)，確定一組服務(wù)設(shè)施來滿足這些需求點(diǎn)的需求。在這個(gè)模型中，需要確定服務(wù)設(shè)施的最小數(shù)量和合適的位置。該模型適用于商業(yè)物流系統(tǒng)，如零售點(diǎn)的選擇問題、加油站的選址、配送中心的選址問題等。 離散點(diǎn)選址問題 FPD 選址模型 根據(jù)解決問題的方法的不同，覆蓋模型可以分為兩種不同的主要模型： ①集合覆蓋模型，用最小數(shù)量的設(shè)施去覆蓋所有的需求點(diǎn)； ②最大覆蓋模型，在給定數(shù)量的設(shè)施下，覆蓋盡可能多的需求或需求點(diǎn)。 覆蓋模型 FPD 選址模型 IV. 集合覆蓋模型 V. 集合覆蓋模型的目標(biāo)是用盡可能少的設(shè)施去覆蓋所有的需求點(diǎn)。 VI. 數(shù)學(xué)模型為： 集合覆蓋模型 N－區(qū)域中的需求點(diǎn)（客戶）集合， {1,2,…} ； M－區(qū)域中可建設(shè)設(shè)施的候選點(diǎn)集合， {1,2,…} ； －第 i個(gè)需求點(diǎn)的需求量； －設(shè)施點(diǎn) j的服務(wù)能力； A(i)－設(shè)施節(jié)點(diǎn) i可以覆蓋的需求點(diǎn) j的集合； B(j)－可以覆蓋需求節(jié)點(diǎn) j的設(shè)施節(jié)點(diǎn) i的集合； 為 01變量， 1,在 i點(diǎn)建立設(shè)施； 0,不在 i點(diǎn)建立設(shè)施， i∈M — 節(jié)點(diǎn) j需求中被分配給設(shè)施點(diǎn) i的部分。 ??????????????????????????MiyNjMixNjDxMiyCxtsyiijjmiijiinjijmii},1,0{,0,..min111FPD 選址模型 集合覆蓋模型啟發(fā)式算法： 第一步：初始化。令所有的＝ 0，＝ 0， （已分配的需求），并確定集合 A(i)和集合 B(j)； 第二步：選擇下一個(gè)設(shè)施點(diǎn)。在 M中選擇＝ 0，且 A(i)的規(guī)模為最大的點(diǎn)i’為設(shè)施點(diǎn)，即 ，令 ，并在 M集合中剔除節(jié)點(diǎn) i’，即 第三步：確定節(jié)點(diǎn) i’的覆蓋范圍。將 A(i’ )中的元素按 B(j)的規(guī)模從小到大的順序指派給 i’，直至 i’的容量為’＝ 0或 A(i’ )為空。其中對(duì)于j∈A(i ’ )且， ，將 j支配給 i’的方法為：若 ，則令’－，’’ ()，＝ 1，在 A(i’ )和 N中剔除需求點(diǎn) j。若 ，則令 第四步：若 N或 M為空，停止；否則，更新集合 A(i)和集合 B(j)，轉(zhuǎn)第二步。 集合覆蓋模型啟發(fā)式算法 0?? ?? Mi ijixx })(max{)( iAiA ??1??ix }{\ iMM ? ijj CxD ???ijj CxD ??? 0, 39。39。 ???? ?? iijjjiij CxxxCxFPD 選址模型 例：在某區(qū)域需規(guī)劃建設(shè)若干個(gè)農(nóng)貿(mào)市場(chǎng)為將來該區(qū) 9個(gè)主要居民點(diǎn)提供服務(wù)，除第 6居民點(diǎn)外，其他各點(diǎn)均有建設(shè)市場(chǎng)的條件，如下圖所示。已知市場(chǎng)的最大服務(wù)直徑為 3，為保護(hù)該區(qū)域的環(huán)境，希望盡可能少地建造農(nóng)貿(mào)市場(chǎng)。問應(yīng)如何規(guī)劃？ 解： N＝ {1,2,3,4,5,6,7,8,9}， M＝ {1,2,3,4,5, 7,8,9}，由圖兩點(diǎn)間的最短距離，根據(jù)最大服務(wù)半徑為 3的約束及第 6居民點(diǎn)不適合建市場(chǎng)的要求，可確定集合 A(j)和 B(i)。如下表所示，值得指出的是本問題沒有需求量和容量，故無需考慮服務(wù)能力約束式。 集合覆蓋模型啟發(fā)式算法 1○ 7○ 8○ 4○ 9○ 2○ 5○ 6○ 3○ 2 2 4 3 4 1 4 3 2 3 3 2 1 1 圖 小區(qū)居民點(diǎn)位置圖 3 FPD 選址模型 集合覆蓋模型啟發(fā)式算法 第一步，初始化 居民點(diǎn)號(hào) A(i) B(j) 1 1,2,3,4 1,2,3,4 2 1,2,3 1,2,3 3 1,2,3,4,5,6 1,2,3,4,5 4 1,3,4,5,6,7 1,3,4,5,7 5 3,4,5,6 3,4,5 6 3,4,5,7,8 7 4,6,7,8 4,7,8 8 6,7,8,9 7,8,9 9 8,9 8,9 第二步，確定一個(gè)設(shè)施點(diǎn)。因?yàn)?A(4)={1,3,4,5,6,7}， (4)6為最大，故首先選取 i’＝ 4。由于無容量約束故依次指派 5,7,1,6,3,4點(diǎn)歸節(jié)點(diǎn) 4服務(wù)。 第三步，更新。此時(shí)， N＝ {2,8,9}＝ {1,2,3,5,7,8,9},更新集合 A(i)和集合B(j)后如下表所示。 FPD 選址模型 集合覆蓋模型啟發(fā)式算法 居民點(diǎn)號(hào) A(i) B(j) 1 2 1,2,3 2 2 1,2,3 3 2 1,2,3,5 4 1,3,5,7 5 3,5 6 3,5,7,8 7 8 7,8 8 8,9 7,8,9 9 8,9 8,9 第四步，確定一個(gè)設(shè)施點(diǎn)。因?yàn)?A(8)＝ {8,9}， (8)|＝ 2為最大，故首先選取 i’＝ 8，并且 8， 9兩點(diǎn)歸節(jié)點(diǎn) 8服務(wù)。 第五步，更新。此時(shí)， N＝ {2}＝ {1,2,3,5,7,9},更新集合 A(i)和集合 B(j)后如下表所示。 FPD 選址模型 集合覆蓋模型啟發(fā)式算法 第六步，確定一個(gè)設(shè)施點(diǎn)。因?yàn)?A(2)＝ {2}， (2)|＝ 1為最大，故首先選取 i’＝ 2，并且 2點(diǎn)歸節(jié)點(diǎn) 2服務(wù)。 第七步，更新。此時(shí)， N＝ {}＝ {1,3,5,7,9},結(jié)束。 因此，計(jì)算結(jié)果為（ 4,8,2）。 居民點(diǎn)號(hào) A(i) B(j) 1 2 1,2,3 2 2 1,2,3 3 2 1,2,3,5 4 1,3,5,7 5 3,5 6 3,5,7 7 7 8 7 9 FPD 選址模型 集合覆蓋模型整數(shù)規(guī)劃 為 01變量， 1,在 i點(diǎn)建立設(shè)施； 0,不在 i點(diǎn)建立設(shè)施， i∈M — 節(jié)點(diǎn) i供給量中被分配給需求點(diǎn) j的部分。 ??????????????????????????MiyNjMixNjDxMiyCxtsyiijjmiijiinjijmii},1,0{,