配送中心設(shè)施平面布局模型.ppt

配送中心 設(shè)施平面布局模型,參考文獻(xiàn)：孫焰，現(xiàn)代物流管理技術(shù)建模理論及算法設(shè)計(jì)，同濟(jì)大學(xué)出版社,內(nèi)容,前言 系統(tǒng)布局設(shè)計(jì)基本概念與流程 關(guān)系表布局法 CORELAP布局法 ALDEP布局算法 CRAFT布局算法 MultiPLE布局算法,前言,設(shè)施的平面布局模型也稱為二維選址模型，主要研究在一個(gè)給定區(qū)域內(nèi)確定具有一定面積要求的各個(gè)設(shè)施的最佳位置問題。一個(gè)配送中心一般由若干個(gè)設(shè)施組成，如停車場(chǎng)、驗(yàn)貨場(chǎng)、倉(cāng)庫等，當(dāng)不同類別的貨物運(yùn)到配送中心后，根據(jù)作業(yè)流程的要求，需要在其中不同的設(shè)施進(jìn)行處理，所需要的時(shí)間、數(shù)量和次序是不相同的，因此，各種設(shè)施在配送中心內(nèi)的相對(duì)位置是否合理，將直接影響配送中心的工作效率，進(jìn)而影響物流成本。 基本問題：已知各個(gè)設(shè)施的作業(yè)面積、作業(yè)量以及作業(yè)流程，試在一個(gè)給定的區(qū)域內(nèi)合理布置這些設(shè)施的位置和形狀，使配送中心內(nèi)的作業(yè)流程最為順暢。,系統(tǒng)布局設(shè)計(jì)（Systematic Layout Planning）基本概念與流程,相互關(guān)系圖,相互關(guān)系圖是用于描述各個(gè)設(shè)施之間關(guān)系的密切程度的圖，通常，所謂的關(guān)系密切程度指的是貨品流量。,通常，用A-F等6個(gè)等級(jí)來描述設(shè)施間的關(guān)系，A最重要、B其次，一直到E。而F表示兩設(shè)施間不能有聯(lián)系。,關(guān)系等級(jí)的標(biāo)定,通常，等級(jí)關(guān)系可以利用設(shè)施間的貨品流量、信息流量來確定。,流量大的給予高的關(guān)系等級(jí)，反之給予低的等級(jí)； 從管理的信息流量角度對(duì)關(guān)系等級(jí)進(jìn)行補(bǔ)充； 等級(jí)標(biāo)定的規(guī)則要保障A、B級(jí)占15以內(nèi)，以方便后期的布局設(shè)計(jì)。,空間關(guān)系圖,空間關(guān)系圖指的是考慮了面積需求后的各個(gè)設(shè)施的位置關(guān)系的圖。例如某配送中心的5個(gè)主要設(shè)施，其空間關(guān)系圖：,基本流程,（1）對(duì)各設(shè)施之間的相互關(guān)系作出分析，包括物流和非物流的相互關(guān)系，建立關(guān)系圖 （2）根據(jù)相互關(guān)系圖中各設(shè)施的關(guān)系的密切程度，決定各設(shè)施之間距離的遠(yuǎn)近，安排各設(shè)施的位置，繪制設(shè)施位置相關(guān)圖，將各設(shè)施實(shí)際占地面積與設(shè)施位置相關(guān)圖結(jié)合起來，形成設(shè)施空間關(guān)系圖； （3）通過設(shè)施空間關(guān)系圖的修正與調(diào)整，得到若干可行的布局方案； （4）量化各因素，建立方案質(zhì)量評(píng)估的數(shù)量指標(biāo)，對(duì)各個(gè)方案進(jìn)行評(píng)估，以得到最佳布局方案。,關(guān)系表布局法,主要步驟,（1）將設(shè)施相互關(guān)系圖轉(zhuǎn)化為關(guān)系表； （2）選擇A級(jí)關(guān)系最多的設(shè)施作為第1設(shè)施優(yōu)先進(jìn)入布置； （3）選擇與第1設(shè)施具有A級(jí)關(guān)系的設(shè)施作為第2設(shè)施進(jìn)入布置； （4）按照與第1設(shè)施、第2設(shè)施為AA、AB、AC、AD的排列順序選擇第3設(shè)施； （5）依次選擇直至全部設(shè)施選擇完畢； （6）按照設(shè)施排序，根據(jù)面積進(jìn)行實(shí)際布置的操作過程，形成空間關(guān)系圖。,例子,設(shè)某配送中心由5個(gè)主要設(shè)施D1、D2、D3、D4、D5組成，各個(gè)面積需求如表1所示。該配送中心的主要業(yè)務(wù)流程有3個(gè)，記為P1、P2和P3 ，各業(yè)務(wù)流程及流量如表2所示。,解第1步：計(jì)算流量矩陣,設(shè)Qij為由Di到Dj的流量，可以求出各設(shè)施間的流量矩陣Q（也可稱為O-D矩陣）。,解第2步：繪制相互關(guān)系圖,解第3步：生成關(guān)系表,解第4步：確定設(shè)施排序,設(shè)施2具有1個(gè)A關(guān)系，2個(gè)C關(guān)系，所以選擇設(shè)施2作為首選設(shè)施進(jìn)行安排； 其次，選擇與設(shè)施2具有A關(guān)系的設(shè)施，即設(shè)施1； 接下來，分析其它設(shè)施與設(shè)施2、設(shè)施1的關(guān)系組合，設(shè)施4、設(shè)施5均為C，任選設(shè)施4； 分析其它設(shè)施與設(shè)施2、設(shè)施1、設(shè)施4的關(guān)系，選中設(shè)施5； 最后是設(shè)施3； 所確定的布置順序?yàn)?-1-4-5-3。,解第5步：形成空間關(guān)系圖,根據(jù)已經(jīng)確定的順序，考慮具體的面積，將關(guān)系密切的設(shè)施相鄰放置，關(guān)系較不密切的設(shè)施，位置可較靈活放置。,D2,D2,D5,D4,D1,D2,D1,D4,D2,D1,D5,D4,D2,D1,D3,CORELAP布局算法,簡(jiǎn)介,CORELAP(Computerized Relationship Layout Planning)是Lee R.C.和Moore J.M.于1967年提出的一種布局優(yōu)化算法。 提出一個(gè)衡量設(shè)施布局方案的評(píng)價(jià)方法（布局質(zhì)量指標(biāo)），以及最優(yōu)布局方案的選取步驟。 基本思路： 按一定規(guī)則生成一個(gè)設(shè)施順序矢量，依照這個(gè)矢量的順序逐個(gè)將設(shè)施加入到區(qū)域中去，并盡量使新加入的設(shè)施與已有的設(shè)施在相對(duì)位置上保證關(guān)系最密切。布置方案完畢后，對(duì)其質(zhì)量指標(biāo)進(jìn)行評(píng)估。 該算法無論是設(shè)施順序矢量的確定、相對(duì)位置的選擇以及質(zhì)量指標(biāo)的計(jì)算，都依賴于設(shè)施間的關(guān)系程度的衡量，即CORELAP算法的出發(fā)點(diǎn)是設(shè)施之間的相互關(guān)系圖（Relation-Chart）。,布局質(zhì)量指標(biāo),要計(jì)算布局質(zhì)量指標(biāo)，首先需要對(duì)關(guān)系等級(jí)標(biāo)定轉(zhuǎn)換成數(shù)值。 優(yōu)化的目標(biāo)函數(shù)值可通過計(jì)算任意兩設(shè)施間的關(guān)系值乘以該兩設(shè)施間的最短距離的總和來求得，即：,最小化,布置設(shè)施順序的確定,CORELAP的選擇方法，即布置順序矢量的產(chǎn)生方法，是根據(jù)各設(shè)施所有關(guān)系的綜合TCR（Total Closeness Rating）的值來確定的。令 稱TCR(i)為設(shè)施i的關(guān)系總和，選擇TCP最大的設(shè)施作為最先進(jìn)入布置的設(shè)施。若最大的TCR值有多個(gè)設(shè)施，即出現(xiàn)“結(jié)”（相持），則選擇面積最大的設(shè)施解“結(jié)”（相持的突破）；若依然解不開，則隨機(jī)選取。 第2個(gè)設(shè)施選擇與第1個(gè)設(shè)施具有最高級(jí)別關(guān)系（A級(jí)）的設(shè)施，依次選擇B級(jí)、C級(jí)、，如果同一關(guān)系級(jí)別出現(xiàn)多個(gè)設(shè)施（“結(jié)”），選擇這些設(shè)施中TCR最大的設(shè)施先布置（解“結(jié)”）。 在布置中，設(shè)施的形狀盡可能設(shè)計(jì)成若干個(gè)正方形組成。,相對(duì)位置的確定,生成了布置矢量后，依照這個(gè)矢量的順序逐個(gè)將設(shè)施向布置圖中放置。放置原則是在所有可布置的位置中選擇使進(jìn)入布置圖的設(shè)施與前面進(jìn)入的相鄰設(shè)施的關(guān)系值的和NCR（Neighbour Closeness Rating）最大的那個(gè)位置。,3,3,4,1a,1b,1c,案例：,已知配送中心的5個(gè)設(shè)施場(chǎng)所作業(yè)面積和相互關(guān)系如圖，試用CORELAP法求該配送中心的設(shè)施布局方案。,求各個(gè)設(shè)施的TCR值,順序： 2 1 4 5 3,根據(jù)各設(shè)施面積確定布置,評(píng)估布置方案,對(duì)多個(gè)方案進(jìn)行比較，可獲得最佳方案（或較佳方案）。,ALDEP布局算法,簡(jiǎn)介,ALDEP（Automated Layout Design Procedure）法與CORELAP法類似，其布置基礎(chǔ)也是關(guān)系圖，算法思路也是每次選擇一個(gè)設(shè)施加入布置圖，按一定規(guī)則尋找其適當(dāng)?shù)奈恢?，并?duì)方案進(jìn)行評(píng)估。 三個(gè)方面與CORELAP不同： 方案評(píng)估的指標(biāo)（目標(biāo)） 設(shè)施的選擇次序 位置的確定方法,布局質(zhì)量指標(biāo),優(yōu)化目標(biāo)函數(shù)是求所有兩兩相鄰設(shè)施間的關(guān)系值的總和達(dá)到最大，即 在做關(guān)系等級(jí)轉(zhuǎn)換（映射）時(shí)，特地拉大了不同等級(jí)之間的數(shù)值差距。,設(shè)施的順序,第1個(gè)布置設(shè)施的選擇方法是隨機(jī)選取的； 隨后，給定一個(gè)最低關(guān)系門檻值TCR（Threshold Closeness Rating），對(duì)其它設(shè)施，根據(jù)與第1個(gè)設(shè)施的關(guān)系進(jìn)行降序排隊(duì)，直到排到設(shè)定的最低關(guān)系門檻值TCR； 選擇大于TCR的所有設(shè)施，如果數(shù)量大于1，順序?yàn)殡S機(jī)。 例如：設(shè)TCR=B，則只選擇與先布置設(shè)施具有A、B關(guān)系的設(shè)施進(jìn)入排列，對(duì)于與先布置設(shè)施均為A或B的布置設(shè)施，則隨機(jī)選擇進(jìn)入布置。,設(shè)施位置的確定,ALDEP的設(shè)施位置放置方法是將選定布置順序的各設(shè)施，按照其單位面積數(shù)，以設(shè)定的寬度，從布置圖的左上角向下，蛇形蜿蜒，直至布置完所有的設(shè)施，如圖，其中設(shè)定的寬度（稱為掃描寬度，Sweep Width）為2。,案例：,已知配送中心的5個(gè)設(shè)施場(chǎng)所作業(yè)面積和相互關(guān)系如圖，試用ALDEP法求該配送中心的設(shè)施布局方案，其中TCR=C，掃描寬度為1。,設(shè)施順序,隨機(jī)選擇第1個(gè)設(shè)施，如D3； 與D3不存在有A/B/C關(guān)系的設(shè)施，因此進(jìn)一步隨機(jī)選擇第2個(gè)設(shè)施，如D4； 與D4不存在有A/B關(guān)系的設(shè)施，但存在有C關(guān)系（是設(shè)定的TCR的最小值）的設(shè)施，分別是D2和D5，隨機(jī)確定，如D2； 與D2存在有A關(guān)系的設(shè)施，即D1，因此第4個(gè)設(shè)施是D1； 最后一個(gè)是D5。 即進(jìn)入順序?yàn)?4215。,依照順序布置設(shè)施,計(jì)算質(zhì)量指標(biāo),可進(jìn)行多次布局，生成多個(gè)方案 選擇Z值最大的作為最終方案。,CRAFT布局算法,簡(jiǎn)介,CRAFT（Computerized Relative Allocation of Facilities Technique）是Buffa等人于1964年提出的。 其優(yōu)化目標(biāo)是使物流節(jié)點(diǎn)內(nèi)的總搬運(yùn)費(fèi)最少。 CRAFT是一種改進(jìn)型的算法，對(duì)一個(gè)初始可行布置方案，它給出了一種使總搬運(yùn)費(fèi)用減少的調(diào)整方法，并保證調(diào)整后的方案仍是可行布置方案。,目標(biāo)函數(shù),關(guān)于設(shè)施交換,設(shè)施交換是CRAFT一個(gè)重要操作，通過兩個(gè)設(shè)施的位置的交換，企圖降低總體的搬運(yùn)成本。設(shè)施交換操作需要注意：相互交換的設(shè)施必須滿足具有公共邊或者面積相等，以便使得位置交換后不引起其它設(shè)施位置的變化。,CRAFT算法,輸入：設(shè)施數(shù)n，流量矩陣Q=(qij)，單位距離成本矩陣C=(cij)，初始布局方案P0。 輸出：布局方案P，總搬運(yùn)成本Z。 步驟： 第1步：將規(guī)劃區(qū)按要求劃分成若干面積相等的方形小單元（方便交換），滿足每個(gè)設(shè)施至少包含1個(gè)單元，且每個(gè)單元只在1個(gè)設(shè)施中。 第2步：計(jì)算P0中各個(gè)設(shè)施的折線距離dij和目標(biāo)函數(shù)Z0。 第3步：列出所有滿足交換條件的設(shè)施交換方案，進(jìn)行逐個(gè)交換，選擇目標(biāo)函數(shù)最小的布局作為交換結(jié)果，記為P，所對(duì)應(yīng)的目標(biāo)函數(shù)值為Z。 第4步：若Z Z0 ，則令Z0 = Z ， P0 =P，重復(fù)第2、3步；否則令Z = Z0 ， P = P0 ，計(jì)算停止。,案例,某配送中心5個(gè)設(shè)施之間的貨物流量矩陣Q和一個(gè)初始布局方案P0如圖，試用CRAFT算法對(duì)該方案進(jìn)行調(diào)整。,第1步：,區(qū)域劃分,計(jì)算距離矩陣,其中，單位距離成本cij設(shè)為1,第2步,列出P0所有的滿足交換條件的設(shè)施交換方案，分別是1-2，1-3，1-5，2-3，2-4，2-5，3-5，4-5（1-4不能交換是因?yàn)閮烧呙娣e不等，也沒有公共邊）。 先交換1-2，并計(jì)算距離矩陣與Z。 繼續(xù)對(duì)1-3、1-5、2-3、2-4、2-5、3-5、4-5等交換，分別計(jì)算出Z，直到找到搬運(yùn)費(fèi)下降最大的一種交換，結(jié)束本輪交換。,P0,P,ZZ0,第3步,第1輪交換結(jié)束后，繪制出首輪布置圖。針對(duì)這一布置圖，再次進(jìn)行具有公共邊（或面積相等）的設(shè)施的新一輪交換。 直到搬運(yùn)費(fèi)用不再降低為止。,CRAFT算法的注意事項(xiàng),計(jì)算結(jié)果與所劃分的單元大小有關(guān) 當(dāng)單元?jiǎng)澐痔?，則可行的交換方案少，很難優(yōu)化目標(biāo)函數(shù)。 當(dāng)單元面積太小，則計(jì)算結(jié)果可能使得各設(shè)施的形狀很不規(guī)則，在實(shí)際布局中無法接受，同時(shí)也增加計(jì)算次數(shù)。,MultiPLE布局算法,簡(jiǎn)介,MultiPLE（Multi-floor Plant Layout Evaluation）時(shí)類似于CRAFT的一種改進(jìn)的算