第15章選址問(wèn)題課件

第15章選址問(wèn)題第15章選址問(wèn)題115.1概述選址理論：是關(guān)于選址問(wèn)題模型和算法的理論。選址在整個(gè)物流系統(tǒng)中占有非常重要的地位，主要屬于物流管理戰(zhàn)略層的研究問(wèn)題。選址決策就是要確定所要分配的設(shè)施的數(shù)量、位置以及分配方案。這些設(shè)施主要指物流系統(tǒng)中的節(jié)點(diǎn)，如制造商、供應(yīng)商、倉(cāng)庫(kù)、配送中心、零售網(wǎng)點(diǎn)等。15.1概述選址理論：是關(guān)于選址問(wèn)題模型21、選址問(wèn)題設(shè)計(jì)算法和模型時(shí)要考慮：（1）被定位的對(duì)象具有什么特性（2）目標(biāo)選址地區(qū)的結(jié)構(gòu)特點(diǎn)是什么（3）目標(biāo)和成本參數(shù)是什么（4）其他限制條件是什么1、選址問(wèn)題設(shè)計(jì)算法和模型時(shí)要考慮：32、選址問(wèn)題的分類(lèi)（1）按被定位的對(duì)象的空間維數(shù)分為：立體選址、平面選址、線選址、點(diǎn)選址。

立體選址：集裝箱裝箱問(wèn)題平面選址：工廠或貨運(yùn)站的設(shè)施布局線選址：巷道內(nèi)劃出揀選帶點(diǎn)選址：制造或配送系統(tǒng)的選址2、選址問(wèn)題的分類(lèi)4（2）按照目標(biāo)區(qū)域的結(jié)構(gòu)來(lái)劃分：連續(xù)選址、網(wǎng)格選址、網(wǎng)絡(luò)選址和離散點(diǎn)選址。連續(xù)選址：候選區(qū)域是一個(gè)平面或球面，任意點(diǎn)都可作為選址點(diǎn)。網(wǎng)格選址：目標(biāo)區(qū)域被劃分成多個(gè)單元，要求為對(duì)象分配其中若干單元。網(wǎng)絡(luò)選址：目標(biāo)選址區(qū)是一個(gè)網(wǎng)絡(luò)，即節(jié)點(diǎn)和邊的集合。離散點(diǎn)選址：候選點(diǎn)數(shù)量有限且較少。（2）按照目標(biāo)區(qū)域的結(jié)構(gòu)來(lái)劃分：連續(xù)選址、網(wǎng)格選址、網(wǎng)絡(luò)選址5（3）從目標(biāo)函數(shù)來(lái)分類(lèi)：中位問(wèn)題、中心問(wèn)題，反中心問(wèn)題中位問(wèn)題：總成本最小為目標(biāo)。中心問(wèn)題：服務(wù)于每個(gè)客戶(hù)的最大成本最小化為目標(biāo)。反中心問(wèn)題：服務(wù)于每個(gè)客戶(hù)的最小成本最大化為目標(biāo)。（3）從目標(biāo)函數(shù)來(lái)分類(lèi)：中位問(wèn)題、中心問(wèn)題，反中心問(wèn)題60567中位點(diǎn)中心點(diǎn)3.5反中心點(diǎn)2.50567中位點(diǎn)中心點(diǎn)3.5反中心點(diǎn)2.57（4）根據(jù)問(wèn)題中的參數(shù)是否與解存在關(guān)聯(lián)：純選址問(wèn)題和選址分配問(wèn)題。純選址問(wèn)題：其中的參數(shù)或結(jié)構(gòu)不依賴(lài)新建設(shè)施而改變，是事先確定的。選址分配問(wèn)題：其中的參數(shù)或結(jié)構(gòu)依賴(lài)新建設(shè)施而改變。（5）根據(jù)問(wèn)題中的參數(shù)是否隨時(shí)間而改變，分為靜態(tài)選址和動(dòng)態(tài)選址。（6）根據(jù)參數(shù)是確定性的還是隨機(jī)性的，分為確定性選址問(wèn)題和隨機(jī)選址問(wèn)題。（7）根據(jù)候選點(diǎn)是否存在服務(wù)能力約束，可以分為無(wú)限能力選址和有限能力選址。（4）根據(jù)問(wèn)題中的參數(shù)是否與解存在關(guān)聯(lián)：純選址問(wèn)題和選址分配815.2連續(xù)點(diǎn)選址問(wèn)題連續(xù)點(diǎn)選址問(wèn)題中，點(diǎn)到點(diǎn)的距離計(jì)算標(biāo)準(zhǔn)有兩種。設(shè)平面上的點(diǎn)坐標(biāo)分別為（xi,yi），（xj,yj）直線距離dijE：折線距離dijR：yxij15.2連續(xù)點(diǎn)選址問(wèn)題連續(xù)點(diǎn)選址問(wèn)題中，點(diǎn)91、直線距離準(zhǔn)則下的選址用直線距離準(zhǔn)則進(jìn)行選址，則目標(biāo)函數(shù)為：1、直線距離準(zhǔn)則下的選址用直線距離準(zhǔn)則進(jìn)行選102、折線距離準(zhǔn)則下的選址重心法，用于以總和最小為目標(biāo)函數(shù)的單一設(shè)施選址問(wèn)題。此時(shí)目標(biāo)函數(shù)為：2、折線距離準(zhǔn)則下的選址重心法，用于以總和最11可見(jiàn)，原問(wèn)題可以被拆成兩個(gè)獨(dú)立的問(wèn)題，即：可見(jiàn)，原問(wèn)題可以被拆成兩個(gè)獨(dú)立的問(wèn)題，即：12例1：報(bào)刊亭選址。有一個(gè)報(bào)刊連鎖公司想在一個(gè)地區(qū)設(shè)一個(gè)新的報(bào)刊零售點(diǎn)，主要的服務(wù)對(duì)象為附近的五個(gè)居民小區(qū)。表中數(shù)字分別為各個(gè)小區(qū)的x坐標(biāo)和y坐標(biāo)，以及需求量。小區(qū)x坐標(biāo)y坐標(biāo)需求量wiA311B527C433D243E156例1：報(bào)刊亭選址。有一個(gè)報(bào)刊連鎖公司想在一個(gè)地區(qū)設(shè)一個(gè)新的報(bào)13用坐標(biāo)圖來(lái)表示五個(gè)小區(qū)的位置小區(qū)x坐標(biāo)y坐標(biāo)需求量wiA311B527C433D243E156xy0123455432112345用坐標(biāo)圖來(lái)表示五個(gè)小區(qū)的位置小區(qū)x坐標(biāo)y坐標(biāo)需求量wiA3114解：先求x坐標(biāo)的解（1）按坐標(biāo)從小到大的順序排列需求點(diǎn)（2）計(jì)算總權(quán)重（需求量）W，計(jì)算累積權(quán)重（需求量）（3）找滿(mǎn)足累積需求量

計(jì)算編號(hào)小區(qū)名稱(chēng)x坐標(biāo)累積需求量1E12D23A34C45B569101320由計(jì)算結(jié)果可知計(jì)算編號(hào)s＝3解：先求x坐標(biāo)的解計(jì)算編號(hào)小區(qū)名稱(chēng)x坐標(biāo)累積需求量1E12D15若，則選址的x坐標(biāo)即為對(duì)應(yīng)的需求點(diǎn)s的x坐標(biāo)。若，則選址的x坐標(biāo)即為對(duì)應(yīng)原需求點(diǎn)s和需求點(diǎn)s+1的x坐標(biāo)范圍內(nèi)任一點(diǎn)。所以，本題選址點(diǎn)的x坐標(biāo)是編號(hào)為3和編號(hào)為4的需求點(diǎn)的x坐標(biāo)之間的任意值，即為[3，4]之間的任意值。再求解y坐標(biāo)的解。若，則選址的16（1）按坐標(biāo)從小到大的順序排列需求點(diǎn)（2）計(jì)算總權(quán)重（需求量）W，計(jì)算累積權(quán)重（需求量）計(jì)算編號(hào)小區(qū)名稱(chēng)y坐標(biāo)累積需求量1A12B23C34D45E518111420（3）y坐標(biāo)為編號(hào)為3的需求點(diǎn)對(duì)應(yīng)的y坐標(biāo)，即y坐標(biāo)為3。（1）按坐標(biāo)從小到大的順序排列需求點(diǎn)計(jì)算編號(hào)小區(qū)名稱(chēng)y坐標(biāo)累17x坐標(biāo)為[3，4]之間的任意值，y坐標(biāo)為3，說(shuō)明新的報(bào)刊零售點(diǎn)的位置可以是PQ線段上的任意一點(diǎn)。xy0123455432112345PQx坐標(biāo)為[3，4]之間的任意值，y坐標(biāo)為3，說(shuō)明新的報(bào)刊零售1815.3離散點(diǎn)選址問(wèn)題離散點(diǎn)選址指的是在有限的候選位置里，選取最為合適的一個(gè)或者一組位置為最優(yōu)方案，相應(yīng)的模型稱(chēng)為離散點(diǎn)選址模型。離散點(diǎn)選址問(wèn)題，目前主要有兩種模型可供選擇，分別是覆蓋模型和k中位模型。其中覆蓋模型常用的是集合覆蓋模型和最大覆蓋模型。覆蓋模型，是對(duì)于需求已知的一些需求點(diǎn)，如何確定一組服務(wù)設(shè)施來(lái)滿(mǎn)足這些需求點(diǎn)的需求。在這個(gè)模型中，需要確定服務(wù)設(shè)施的最小數(shù)量和合適位置。15.3離散點(diǎn)選址問(wèn)題離散點(diǎn)選址指的是在有19覆蓋模型適用于商業(yè)物流系統(tǒng)，如零售點(diǎn)的選址，加油站的選址、配送中心的選址等，公用事業(yè)系統(tǒng)，如急救中心、消防中心等，以及計(jì)算機(jī)與通信系統(tǒng)。集合覆蓋模型：用最小數(shù)量的設(shè)施去覆蓋所有的需求點(diǎn)。覆蓋模型適用于商業(yè)物流系統(tǒng)，如零售點(diǎn)的選址，20最大覆蓋模型：在給定數(shù)量的設(shè)施下，覆蓋盡可能多的需求點(diǎn)。最大覆蓋模型：在給定數(shù)量的設(shè)施下，覆蓋盡可能21集合覆蓋模型：定義：xi——需求點(diǎn)cj——覆蓋成本sj——覆蓋集合子集，取1時(shí)表示該子集啟用，取0時(shí)表示該子集未啟用。A——覆蓋關(guān)系矩陣aij——覆蓋關(guān)系矩陣中的元素，取1時(shí)表示集合sj可以把需求點(diǎn)xi覆蓋進(jìn)去，取0時(shí)表示集合sj不可以把需求點(diǎn)xi覆蓋進(jìn)去。數(shù)學(xué)模型：目標(biāo)函數(shù)：約束條件：aij和sj為0，1變量。集合覆蓋模型：數(shù)學(xué)模型：約束條件：aij和sj為0，1變量。22矩陣簡(jiǎn)化法求解第一步：若A中行i只有一個(gè)非0元素，例如aij，則記J={j}，即sj在最優(yōu)解中。對(duì)A刪除列j以及該列中aij＝1的行。第二步：若A中存在行i和i’，若對(duì)所有列有aij≥ai’j，則刪除行i。第三步：若A中存在列j和j’，若對(duì)所有行有aij≤aij’，則刪除列j。第四步：反復(fù)進(jìn)行前三步，直至矩陣A中不再包含任何元素，或不存在行或列可以刪除。矩陣簡(jiǎn)化法求解23例2：有7個(gè)航線需要安排乘務(wù)員，有五組乘務(wù)組可選，請(qǐng)盡量安排最小的乘務(wù)組，且保證每條航線都至少有一個(gè)乘務(wù)組服務(wù)。乘務(wù)組航線s1s2s3s4s5x110110x210010x311010x401110x510001x600100x701010例2：有7個(gè)航線需要安排乘務(wù)員，有五組乘務(wù)組可選，請(qǐng)盡量安排24解：（1）在矩陣A中找出行中只有一個(gè)非0元素的行。x1x2x3x4x5x6x7s1s2s3s4s5記J={s3}（2）刪除行x3，因?yàn)閤3包含x2。（3）刪除列s5，因?yàn)閟1包含s5。刪除列s2，因?yàn)閟4包含s2。x2x3x5x7s1s2s4s5x2x5x7s1s4

（4）記J={s3,s1}（5）記J={s3,s1,s4}解：（1）在矩陣A中找出行中只有一個(gè)非0元素的行。x1s125例3：某物流企業(yè)要建設(shè)一些配送中心，為九個(gè)城市的客戶(hù)服務(wù)，配送中心最遠(yuǎn)的服務(wù)距離為300km，即任何一個(gè)城市的周邊300km處至少有一個(gè)配送中心。不考慮配送中心的服務(wù)能力，物流企業(yè)要確定需要多少個(gè)配送中心以及這些配送中心的位置。其中第6個(gè)城市由于缺乏建立配送中心的必要條件，不可以建立配送中心。圖表示各個(gè)城市的相對(duì)位置和距離。240013456789200300200100350300250150150300400300200300例3：某物流企業(yè)要建設(shè)一些配送中心，為九個(gè)城市的客戶(hù)服務(wù)，配26解：第一步是要建立覆蓋矩陣。240013456789200300200100350300250150150300400300200300s1s2s3s4s5s7s8s9c11c21c31c41c51c6c71c81c911110100001000000111100001011110000111000000101100000011100000001解：第一步是要建立覆蓋矩陣。240013456789200327第二步進(jìn)行計(jì)算。（1）找出行中只有一個(gè)非0元素的行。（2）簡(jiǎn)化矩陣第二步進(jìn)行計(jì)算。28簡(jiǎn)化矩陣后得記J={s3}記J={s3，s8}簡(jiǎn)化矩陣后得記J={s3}記J={s3，s8}29k中位模型：設(shè)在某一地區(qū)要建立若干的配送中心，給其客戶(hù)配送商品，配送中心有N個(gè)候選地址?，F(xiàn)要求設(shè)立的配送中心到所有客戶(hù)的總運(yùn)輸成本最小。k中位模型：30例4：某公司準(zhǔn)備在8個(gè)客戶(hù)的附近建立2個(gè)倉(cāng)庫(kù)，用最低的運(yùn)輸成本來(lái)滿(mǎn)足客戶(hù)的需求?，F(xiàn)計(jì)劃從4個(gè)候選地址選擇2個(gè)地方建立倉(cāng)庫(kù)。從候選地址到不同的倉(cāng)庫(kù)的運(yùn)輸成本、各個(gè)超市的需求量都已確定，如表所示：p1p2p3p4需求量x1412206100x2210251050x3341614120x4659280x5181273200x61424970x7203021160x82412622100例4：某公司準(zhǔn)備在8個(gè)客戶(hù)的附近建立2個(gè)倉(cāng)庫(kù)，用最低的運(yùn)輸成31用貪婪取走啟發(fā)式算法：第一步：初始化，令循環(huán)參數(shù)k=m，將所有的m個(gè)候選位置全選中，然后將每個(gè)客戶(hù)指派給離其距離最近的一個(gè)候選位置。123456781423400100360160600140120600總成本費(fèi)用為：2480用貪婪取走啟發(fā)式算法：123456781423400100332第二步：選擇并取走一個(gè)位置點(diǎn)，滿(mǎn)足以下條件：取走它并將客戶(hù)重新指派后，總費(fèi)用增加量最小，然后令k=k-1。第三步：重復(fù)第二步，直到k=2。123600500480456781423160600140120600取走1后，總費(fèi)用為3200，增加720。第二步：選擇并取走一個(gè)位置點(diǎn)，滿(mǎn)足以下條件：取走它并將客戶(hù)重33取走2后，總費(fèi)用為2620，增加140。628012345781423400100360160600120600取走2后，總費(fèi)用為2620，增加140。628012345734取走3后，總費(fèi)用為3620，增加1140。1234561423400100360160600140786601200取走3后，總費(fèi)用為3620，增加1140。12345614235取走4后，總費(fèi)用為3520，增加1040。4540014007812361423400100360140120