第15章選址問題

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

2、選址：巷道內(nèi)劃出揀選帶 點選址：制造或配送系統(tǒng)的選址.（2）按照目標區(qū)域的結(jié)構(gòu)來劃分：連續(xù)選址、網(wǎng)格選址、網(wǎng)絡(luò)選址和離散點選址。連續(xù)選址：候選區(qū)域是一個平面或球面，任意點都可作為選址點。網(wǎng)格選址：目標區(qū)域被劃分成多個單元，要求為對象分配其中若干單元。網(wǎng)絡(luò)選址：目標選址區(qū)是一個網(wǎng)絡(luò)，即節(jié)點和邊的集合。離散點選址：候選點數(shù)量有限且較少。.（3）從目標函數(shù)來分類：中位問題、中心問題，反中心問題 中位問題：總成本最小為目標。 中心問題：服務(wù)于每個客戶的最大成本最小化為目標。 反中心問題：服務(wù)于每個客戶的最小成本最大化為目標。 jjXXC)(min)(maxminXCjjX)(minmaxXCjjX.0

3、567中位點中心點3.5反中心點2.5.（4）根據(jù)問題中的參數(shù)是否與解存在關(guān)聯(lián)：純選址問題和選址分配問題。 純選址問題：其中的參數(shù)或結(jié)構(gòu)不依賴新建設(shè)施而改變，是事先確定的。 選址分配問題：其中的參數(shù)或結(jié)構(gòu)依賴新建設(shè)施而改變。（5）根據(jù)問題中的參數(shù)是否隨時間而改變，分為靜態(tài)選址和動態(tài)選址。（6）根據(jù)參數(shù)是確定性的還是隨機性的，分為確定性選址問題和隨機選址問題。（7）根據(jù)候選點是否存在服務(wù)能力約束，可以分為無限能力選址和有限能力選址。.15.2 連續(xù)點選址問題 連續(xù)點選址問題中，點到點的距離計算標準有兩種。設(shè)平面上的點坐標分別為（xi,yi），（xj,yj） 直線距離dijE： 折線距離dijR

4、：22)()(jijiEijyyxxd|jijiRijyyxxdyxij.1、直線距離準則下的選址 用直線距離準則進行選址，則目標函數(shù)為：nisisiiEisniiyyxxwdwZ1221)()(min.2、折線距離準則下的選址 重心法，用于以總和最小為目標函數(shù)的單一設(shè)施選址問題。此時目標函數(shù)為：nisiinisiinisisiiRisniiyywxxwyyxxwdwZ1111|min.可見，原問題可以被拆成兩個獨立的問題，即：nisiixxxwZ1|minnisiiyyywZ1|min.例1：報刊亭選址。有一個報刊連鎖公司想在一個地區(qū)設(shè)一個新的報刊零售點，主要的服務(wù)對象為附近的五個居民小區(qū)。

5、表中數(shù)字分別為各個小區(qū)的x坐標和y坐標，以及需求量。小區(qū)x坐標y坐標需求量wiA311B527C433D243E156.用坐標圖來表示五個小區(qū)的位置小區(qū)x坐標y坐標需求量wiA311B527C433D243E156xy0 1 2 3 4 55432112345.解：先求x坐標的解（1）按坐標從小到大的順序排列需求點（2）計算總權(quán)重（需求量）W，計算累積權(quán)重（需求量）（3）找滿足累積需求量 計算編號小區(qū)名稱x坐標累積需求量1E12D23A34C45B56910132022111WwWwsiisii由計算結(jié)果可知計算編號s3.若 ，則選址的x坐標即為對應(yīng)的需求點s的x坐標。若 ，則選址的x坐標即為

6、對應(yīng)原需求點s和需求點s+1的x坐標范圍內(nèi)任一點。 所以，本題選址點的x坐標是編號為3和編號為4的需求點的x坐標之間的任意值，即為3，4之間的任意值。 再求解y坐標的解。21Wwsii21Wwsii.（1）按坐標從小到大的順序排列需求點（2）計算總權(quán)重（需求量）W，計算累積權(quán)重（需求量）計算編號小區(qū)名稱y坐標累積需求量1A12B23C34D45E518111420（3）y坐標為編號為3的需求點對應(yīng)的y坐標，即y坐標為3。.x坐標為3，4之間的任意值，y坐標為3，說明新的報刊零售點的位置可以是PQ線段上的任意一點。xy0 1 2 3 4 55432112345PQ.15.3 離散點選址問題 離散

7、點選址指的是在有限的候選位置里，選取最為合適的一個或者一組位置為最優(yōu)方案，相應(yīng)的模型稱為離散點選址模型。 離散點選址問題，目前主要有兩種模型可供選擇，分別是覆蓋模型和k中位模型。其中覆蓋模型常用的是集合覆蓋模型和最大覆蓋模型。 覆蓋模型，是對于需求已知的一些需求點，如何確定一組服務(wù)設(shè)施來滿足這些需求點的需求。在這個模型中，需要確定服務(wù)設(shè)施的最小數(shù)量和合適位置。. 覆蓋模型適用于商業(yè)物流系統(tǒng)，如零售點的選址，加油站的選址、配送中心的選址等，公用事業(yè)系統(tǒng)，如急救中心、消防中心等，以及計算機與通信系統(tǒng)。 集合覆蓋模型：用最小數(shù)量的設(shè)施去覆蓋所有的需求點。. 最大覆蓋模型：在給定數(shù)量的設(shè)施下，覆蓋盡可

8、能多的需求點。.集合覆蓋模型：定義：xi需求點 cj覆蓋成本 sj覆蓋集合子集，取1時表示該子集啟用，取0時表示該子集未啟用。 A覆蓋關(guān)系矩陣 aij覆蓋關(guān)系矩陣中的元素，取1時表示集合sj可以把需求點xi覆蓋進去，取0時表示集合sj不可以把需求點xi覆蓋進去。數(shù)學(xué)模型：目標函數(shù)：njjs1minnjjjsc1min約束條件：11njijaaij和sj為0，1變量。.矩陣簡化法求解第一步：若A中行i只有一個非0元素，例如aij，則記J=j，即sj在最優(yōu)解中。對A刪除列j以及該列中aij1的行。第二步：若A中存在行i和i，若對所有列有aijaij，則刪除行i。第三步：若A中存在列j和j，若對所有

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

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

11、50150150300400300200300.解：第一步是要建立覆蓋矩陣。240013456789200300200100350300250150150300400300200300s1s2s3s4s5s7s8s9c11c21c31c41c51c6c71c81c911110100001000000111100001011110000111000000101100000011100000001.第二步進行計算。（1）找出行中只有一個非0元素的行。（2）簡化矩陣11000000111000000110100001111000000111000011110100011111000001110000

12、111198765432198754321cccccccccssssssss.簡化矩陣后得100011100011000197528743ccccssss記J=s3記J=s3 ，s8.k中位模型： 設(shè)在某一地區(qū)要建立若干的配送中心，給其客戶配送商品，配送中心有N個候選地址。現(xiàn)要求設(shè)立的配送中心到所有客戶的總運輸成本最小。.例4：某公司準備在8個客戶的附近建立2個倉庫，用最低的運輸成本來滿足客戶的需求?，F(xiàn)計劃從4個候選地址選擇2個地方建立倉庫。從候選地址到不同的倉庫的運輸成本、各個超市的需求量都已確定，如表所示：p1p2p3p4需求量x1412206100 x2210251050 x334161

13、4120 x4659280 x5181273200 x61424970 x7203021160 x82412622100.用貪婪取走啟發(fā)式算法：第一步：初始化，令循環(huán)參數(shù)k=m，將所有的m個候選位置全選中，然后將每個客戶指派給離其距離最近的一個候選位置。123456781423400100360160600140120600總成本費用為：2480.第二步：選擇并取走一個位置點，滿足以下條件：取走它并將客戶重新指派后，總費用增加量最小，然后令k=k-1。第三步：重復(fù)第二步，直到k=2。123600500480456781423160600140120600取走1后，總費用為3200，增加720。.取走2后，總費用為2620，增加140。628012345781423400100360160600120600.取走3后，總費用為3620，增加1140。1234561423400100360160600140786601200.取走4后，總費用為3520，增加1040。4540014007812361423400100360140120600.此時應(yīng)取走2，總費用為2620，如圖所示：628012345781423400100360160600120600.628045781423160600120600取走1后，總費用為4540，增加1920。1236005001680.取走3