第15章選址問題_第1頁
第15章選址問題_第2頁
第15章選址問題_第3頁
第15章選址問題_第4頁
第15章選址問題_第5頁
已閱讀5頁,還剩38頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論