物流工程與管理學(xué)：選址問題

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

2、出揀選帶 點(diǎn)選址：制造或配送系統(tǒng)的選址（2）按照目標(biāo)區(qū)域的結(jié)構(gòu)來劃分：連續(xù)選址、網(wǎng)格選址、網(wǎng)絡(luò)選址和離散點(diǎn)選址。連續(xù)選址：候選區(qū)域是一個平面或球面，任意點(diǎn)都可作為選址點(diǎn)。網(wǎng)格選址：目標(biāo)區(qū)域被劃分成多個單元，要求為對象分配其中若干單元。網(wǎng)絡(luò)選址：目標(biāo)選址區(qū)是一個網(wǎng)絡(luò)，即節(jié)點(diǎn)和邊的集合。離散點(diǎn)選址：候選點(diǎn)數(shù)量有限且較少。（3）從目標(biāo)函數(shù)來分類：中位問題、中心問題、反中心問題。 中位問題：總成本最小為目標(biāo)。 中心問題：服務(wù)于每個客戶的最大成本最小化為目標(biāo)。 反中心問題：服務(wù)于每個客戶的最小成本最大化為目標(biāo)。 0567中位點(diǎn)中心點(diǎn)3.5反中心點(diǎn)2.5（4）根據(jù)問題中的參數(shù)是否與解存在關(guān)聯(lián)：純選址問題和

3、選址分配問題。純選址問題：其中的參數(shù)或結(jié)構(gòu)不依賴新建設(shè)施而改變，是事先確定的。選址分配問題：其中的參數(shù)或結(jié)構(gòu)依賴新建設(shè)施而改變。（5）根據(jù)問題中的參數(shù)是否隨時間而改變，分為靜態(tài)選址和動態(tài)選址。（6）根據(jù)參數(shù)是確定性的還是隨機(jī)性的，分為確定性選址問題和隨機(jī)選址問題。（7）根據(jù)候選點(diǎn)是否存在服務(wù)能力約束，可以分為無限能力選址和有限能力選址。15.2 連續(xù)點(diǎn)選址問題 連續(xù)點(diǎn)選址問題中，點(diǎn)到點(diǎn)的距離計(jì)算標(biāo)準(zhǔn)有兩種。設(shè)平面上的點(diǎn)坐標(biāo)分別為（xi,yi），（xj,yj） 直線距離dijE： 折線距離dijR ：yxij1. 直線距離準(zhǔn)則下的選址 用直線距離準(zhǔn)則進(jìn)行選址，則目標(biāo)函數(shù)為：2. 折線距離準(zhǔn)則下的

4、選址 重心法用于以總和最小為目標(biāo)函數(shù)的單一設(shè)施選址問題。此時目標(biāo)函數(shù)為：可見，原問題可以被拆成兩個獨(dú)立的問題，即：例1：報(bào)刊亭選址。有一個報(bào)刊連鎖公司想在一個地區(qū)設(shè)一個新的報(bào)刊零售點(diǎn)，主要的服務(wù)對象為附近的五個居民小區(qū)。表中數(shù)字分別為各個小區(qū)的x坐標(biāo)和y坐標(biāo)，以及需求量。小區(qū)x坐標(biāo)y坐標(biāo)需求量wiA311B527C433D243E156用坐標(biāo)圖來表示五個小區(qū)的位置小區(qū)x坐標(biāo)y坐標(biāo)需求量wiA311B527C433D243E156xy0 1 2 3 4 55432112345解：先求x坐標(biāo)的解（1）按坐標(biāo)從小到大的順序排列需求點(diǎn)。（2）計(jì)算總權(quán)重（需求量）W，計(jì)算累積權(quán)重（需求量）。（3）找滿足

5、累積需求量。 計(jì)算編號小區(qū)名稱x坐標(biāo)累積需求量1E12D23A34C45B569101320由計(jì)算結(jié)果可知計(jì)算編號s3若 ，則選址的x坐標(biāo)即為對應(yīng)的需求點(diǎn)s的x坐標(biāo)。若 ，則選址的x坐標(biāo)即為對應(yīng)原需求點(diǎn)s和需求點(diǎn)s+1的x坐標(biāo)范圍內(nèi)任一點(diǎn)。 所以，本題選址點(diǎn)的x坐標(biāo)是編號為3和編號為4的需求點(diǎn)的x坐標(biāo)之間的任意值，即為3，4之間的任意值。 再求解y坐標(biāo)的解。（1）按坐標(biāo)從小到大的順序排列需求點(diǎn)。（2）計(jì)算總權(quán)重（需求量）W，計(jì)算累積權(quán)重（需求量）。計(jì)算編號小區(qū)名稱y坐標(biāo)累積需求量1A12B23C34D45E518111420（3）y坐標(biāo)為編號為3的需求點(diǎn)對應(yīng)的y坐標(biāo)，即y坐標(biāo)為3。x坐標(biāo)為3，

6、4之間的任意值，y坐標(biāo)為3，說明新的報(bào)刊零售點(diǎn)的位置可以是PQ線段上的任意一點(diǎn)。xy0 1 2 3 4 55432112345PQ15.3 離散點(diǎn)選址問題 離散點(diǎn)選址指的是在有限的候選位置里，選取最為合適的一個或者一組位置為最優(yōu)方案，相應(yīng)的模型稱為離散點(diǎn)選址模型。 離散點(diǎn)選址問題，目前主要有兩種模型可供選擇，分別是覆蓋模型和k中位模型。其中覆蓋模型常用的是集合覆蓋模型和最大覆蓋模型。 覆蓋模型，是對于需求已知的一些需求點(diǎn)，如何確定一組服務(wù)設(shè)施來滿足這些需求點(diǎn)的需求。在這個模型中，需要確定服務(wù)設(shè)施的最小數(shù)量和合適位置。 覆蓋模型適用于商業(yè)物流系統(tǒng)，如零售點(diǎn)的選址，加油站的選址、配送中心的選址等，

7、公用事業(yè)系統(tǒng)，如急救中心、消防中心等，以及計(jì)算機(jī)與通信系統(tǒng)。 集合覆蓋模型：用最小數(shù)量的設(shè)施去覆蓋所有的需求點(diǎn)。 最大覆蓋模型：在給定數(shù)量的設(shè)施下，覆蓋盡可能多的需求點(diǎn)。集合覆蓋模型：定義：xi需求點(diǎn) cj覆蓋成本 sj覆蓋集合子集，取1時表示該子集啟用，取0時表示該子集未啟用。 A覆蓋關(guān)系矩陣 aij覆蓋關(guān)系矩陣中的元素，取1時表示集合sj可以把需求點(diǎn)xi覆蓋進(jìn)去，取0時表示集合sj不可以把需求點(diǎn)xi覆蓋進(jìn)去。數(shù)學(xué)模型：目標(biāo)函數(shù)：約束條件：aij和sj為0，1變量。矩陣簡化法求解第一步：若A中行i只有一個非0元素，例如aij，則記J=j，即sj在最優(yōu)解中。對A刪除列j以及該列中aij1的行。

8、第二步：若A中存在行i和i，若對所有列有aijaij，則刪除行i。第三步：若A中存在列j和j，若對所有行有aijaij，則刪除列j。第四步：反復(fù)進(jìn)行前三步，直至矩陣A中不再包含任何元素，或不存在行或列可以刪除。例2：有7個航線需要安排乘務(wù)員，有五組乘務(wù)組可選，請盡量安排最小的乘務(wù)組，且保證每條航線都至少有一個乘務(wù)組服務(wù)。 乘務(wù)組航線s1s2s3s4s5x110110 x210010 x311010 x401110 x510001x600100 x701010解：（1）在矩陣A中找出行中只有一個非0元素的行。x1x2x3x4x5x6x7s1 s2 s3 s4 s5記J=s3x1x2x3x4x5x

9、6x7s1 s2 s3 s4 s5（2）刪除行x3，因?yàn)閤3包含x2。（3）刪除列s5，因?yàn)閟1包含s5。刪除列s2，因?yàn)閟4包含s2x2x3x5x7 s1 s2 s4 s5x2x5x7s1 s4 （4）記J=s3,s1（5）記J=s3,s1,s4例3：某物流企業(yè)要建設(shè)一些配送中心，為九個城市的客戶服務(wù)，配送中心最遠(yuǎn)的服務(wù)距離為300km，即任何一個城市的周邊300km處至少有一個配送中心。不考慮配送中心的服務(wù)能力，物流企業(yè)要確定需要多少個配送中心以及這些配送中心的位置。其中第6個城市由于缺乏建立配送中心的必要條件，不可以建立配送中心。圖表示各個城市的相對位置和距離。2400134567892

10、00300200100350300250150150300400300200300解：第一步是要建立覆蓋矩陣。240013456789200300200100350300250150150300400300200300s1s2s3s4s5s7s8s9c11c21c31c41c51c6c71c81c911110100001000000111100001011110000111000000101100000011100000001第二步進(jìn)行計(jì)算。（1）找出行中只有一個非0元素的行。（2）簡化矩陣簡化矩陣后得記J=s3記J=s3 ，s8k中位模型： 設(shè)在某一地區(qū)要建立若干的配送中心，給其客戶配送商品

11、，配送中心有N個候選地址。現(xiàn)要求設(shè)立的配送中心到所有客戶的總運(yùn)輸成本最小。例4：某公司準(zhǔn)備在8個客戶的附近建立2個倉庫，用最低的運(yùn)輸成本來滿足客戶的需求。現(xiàn)計(jì)劃從4個候選地址選擇2個地方建立倉庫。從候選地址到不同的倉庫的運(yùn)輸成本、各個超市的需求量都已確定，如表所示：p1p2p3p4需求量x1412206100 x2210251050 x3341614120 x4659280 x5181273200 x61424970 x7203021160 x82412622100用貪婪取走啟發(fā)式算法：第一步：初始化，令循環(huán)參數(shù)k=m，將所有的m個候選位置全選中，然后將每個客戶指派給離其距離最近的一個候選位置

12、。123456781423400100360160600140120600總成本費(fèi)用為：2480第二步：選擇并取走一個位置點(diǎn)，滿足以下條件：取走它并將客戶重新指派后，總費(fèi)用增加量最小，然后令k=k-1。第三步：重復(fù)第二步，直到k=2。123600500480456781423160600140120600取走1后，總費(fèi)用為3200，增加720。取走2后，總費(fèi)用為2620，增加140。628012345781423400100360160600120600取走3后，總費(fèi)用為3620，增加1140。1234561423400100360160600140786601200取走4后，總費(fèi)用為3520，增加1040。4540014007812361423400100360140120600此時應(yīng)取走2，總費(fèi)用為2620，如圖所示：628012345781423400100360160600120600628045781423160600120600取走1后，總費(fèi)用為4540，