物流建模及選址后五章

1、5.3*企業(yè)物流的基本形式*U型：接收與發(fā)送處于工場(chǎng)的同一位置，利于物料搬運(yùn)和JIT布置的物流形式。*O型：常見(jiàn)于物料搬運(yùn)機(jī)器人服務(wù)的制造單元中。*S型：用于長(zhǎng)的裝配線(xiàn)布置中，如汽車(chē)裝配線(xiàn)。5.4*物流分析的圖表方法5.4.2*物流分析的圖表方法*常用的：線(xiàn)圖、多種產(chǎn)品工藝圖、從至表、* 工藝流程表、物流布置筒圖等。1.線(xiàn)圖*：用節(jié)點(diǎn)代表各部門(mén)，其間發(fā)生的物流波動(dòng)用直線(xiàn)或弧線(xiàn)連接。直線(xiàn)*：相鄰部門(mén)間發(fā)生的物流?；【€(xiàn)*：不相鄰部門(mén)間發(fā)生的物流。 上方弧線(xiàn)*：跳躍。 下方弧線(xiàn)*：回退。即采用不同的線(xiàn)形來(lái)區(qū)分不同的物流內(nèi)容。5.4*物流分析的圖表方法2.*多種產(chǎn)品工藝圖：是將不同的產(chǎn)品分別裂成圖表，

2、節(jié)點(diǎn)表示部門(mén)，直線(xiàn)表示正向物流，斜線(xiàn)表示回退。+產(chǎn)量如：p86 圖4-9*優(yōu)點(diǎn)：可表面產(chǎn)量；品種多時(shí)可直觀(guān)顯示個(gè)產(chǎn)品的物流情況（不雜）；物流路徑效率的計(jì)算與線(xiàn)路相同。*缺點(diǎn)：產(chǎn)品多、工藝復(fù)雜時(shí)難以用該法尋找最佳的布置方案。但仍可幫助找產(chǎn)量大、物流復(fù)雜的產(chǎn)品作為主要分析對(duì)象。*適用：簡(jiǎn)單、定性的分析。 定量化的物流分析需從至表。5.4*物流分析的圖表方法5.4.1*物流優(yōu)化的目標(biāo)*目標(biāo)：物流成本要求移動(dòng)次數(shù)，移動(dòng)距離從物流路徑上要避免回退及交叉現(xiàn)象。1*回退現(xiàn)象：兩部門(mén)之間的波動(dòng)與產(chǎn)品的主流方向相反。如：P84 圖4-5注*：回退可通過(guò)布置的改變而避免，但不可能完全避免，如：次品的返修。2.*交

3、叉現(xiàn)象：物流的波動(dòng)出現(xiàn)交叉。物流的交叉點(diǎn)易造成交通阻塞，使效率，成本，需通過(guò)布置的改變減少交叉點(diǎn)。需要進(jìn)行設(shè)施布置優(yōu)化，先需應(yīng)用圖表分析方法或物仿真技術(shù)進(jìn)行物流分析。缺點(diǎn)*：該圖只看到回退、頻繁等信息，無(wú)定量信息。只能得到一定布置下 *物流路徑的效率*（量）：100% 起始部門(mén)至終了部門(mén)間最短單位間隔和起始部門(mén)至終了部門(mén)間實(shí)際的總單位間隔和 （唯一的定量信息） 如圖4-7：A，B產(chǎn)品物流路徑的效率=（3+3）/（5+3）*100%=75% 3.從至表*：（1）從至表*：表示不同部門(mén)之間物流流動(dòng)的大小。該表為正方矩陣，其行（列）數(shù)為部門(mén)數(shù)量，行（列）中的部門(mén)按統(tǒng)一的順序排列。aij為i到j(luò)部門(mén)間

4、物流流動(dòng)的總量。（2）aij分析：由產(chǎn)品的工藝及產(chǎn)量信息分析得，如：從BOM表，工藝路線(xiàn)圖、裝配/操作工藝圖表、操作順序圖等工藝文件中獲得零部件流動(dòng)信息；從產(chǎn)品預(yù)測(cè)中獲得產(chǎn)品產(chǎn)量數(shù)據(jù)。 （求：部門(mén)間物料流動(dòng)的量）（3）制從至表注意事項(xiàng)*：aij=0,即不考慮部門(mén)內(nèi)的流動(dòng)。（aij為部門(mén)間）*當(dāng)量物流量 （*使進(jìn)入從至表的物流量具有可比性）在一個(gè)給定的系統(tǒng)中，物料的幾何形狀、物化形態(tài)、表面形態(tài)、易損程度等都有很大的差別，簡(jiǎn)單用物料的重量作為物流量的計(jì)算單位并不合理，因而提出當(dāng)量物流量的概念。*當(dāng)量物流量：物料運(yùn)動(dòng)過(guò)程中一定時(shí)間內(nèi)按規(guī)定標(biāo)準(zhǔn)修正、折算的搬運(yùn)和運(yùn)輸量。（計(jì)算尚無(wú)統(tǒng)一模式）一般采用重量

5、或物料搬運(yùn)單元來(lái)計(jì)算，單位可以是貨筐、托盤(pán)或箱子。如x：1000件；y：100件；y的重量是x的100則x、y的重量當(dāng)量物流分別為1和10.若靈劍昂貴或易損，則可由風(fēng)險(xiǎn)及零件的價(jià)值表示。*主流方向與回退現(xiàn)象：*原則：盡可能選擇物流量大的幾個(gè)部門(mén)建立布置的主流方向。即決定從至表行（列）各部門(mén)的順序。如：依圖4-5順序，回退物流處于下三角矩陣； 依圖4-6順序，無(wú)回退，為上Hessenberg矩陣。*注意：交換部門(mén)的順序，會(huì)引起從至表矩陣的變化，但部門(mén)的物流量不變，即“aij”的值不變，但位置變了，相應(yīng)地該值所對(duì)應(yīng)部門(mén)間的距離也變了。 *物流費(fèi)用=部門(mén)間的物流量*部門(mén)間距離最優(yōu)設(shè)施布置方案，即為最

6、小物流費(fèi)用對(duì)應(yīng)的布置方案。即*目標(biāo)： （最早的計(jì)算機(jī)化布置程序CRAFT的布置思想）用新的距離乘不 的物流量用新的距離乘不 的物流量*方法：交換部門(mén)的位置最小的物流費(fèi)用優(yōu)化的設(shè)施布置方案。*矩陣的秩：用矩陣的秩代替物流費(fèi)用來(lái)比較方案的優(yōu)劣。即選擇矩陣的秩較小的布置為優(yōu)選方案。*矩陣的秩：其中： dijaij距主對(duì)角線(xiàn)的距離（或aji）； fij部門(mén)i，j之間的物流量。 *目標(biāo)：選擇矩陣的秩較小的布置為優(yōu)選方案。*物流從至表的具體制定過(guò)程：i.由零件的工藝卡確定其加工中所經(jīng)過(guò)的部門(mén)；ii.由產(chǎn)品的產(chǎn)量預(yù)測(cè)及BOM表確定零件數(shù)；iii.據(jù)具體情況轉(zhuǎn)換成當(dāng)量物流量；iv.將任兩部門(mén)間的所有當(dāng)量物流量

7、相加形成物流從至表。例：P89 線(xiàn)圖；多種產(chǎn)品工藝圖；從至表。*5.5非物流因素分析技術(shù)作業(yè)單位相互關(guān)系分析*即關(guān)系圖分析法：關(guān)系圖分析法在受物流因素或非物流因素影響的設(shè)施布置中都非常有用，如：車(chē)間、服務(wù)設(shè)施或辦公室的布置設(shè)計(jì)。1.*相關(guān)程度評(píng)分等級(jí)：一般在一個(gè)設(shè)施內(nèi)除了生產(chǎn)單位外，還有其他單位，它們需要有良好的流程安排，如：物料流程，信息流程，人員流程等。活動(dòng)關(guān)系圖可為這些部門(mén)找出最有效率的布局方式，以符合各單位間所要求的重要關(guān)系。在關(guān)系圖方法中，將部門(mén)間所有的關(guān)系分為6個(gè)等級(jí)，即A、E、I、O、U、X，其含義*分別為：A：絕對(duì)重要；E：特別重要；I：重要；O：一般重要；U：不重要；X：禁止

8、，不要接近。2.*制作活動(dòng)關(guān)系的步驟：（注：若整個(gè)作業(yè)區(qū)只有生產(chǎn)作業(yè)，而無(wú)輔助勞務(wù)活動(dòng)時(shí)，幾乎不需非物流因素關(guān)系圖，只單純作物流因素關(guān)系圖。）確定包含哪些作業(yè)或部門(mén)單位；列示包含哪些主要作業(yè)（先將作業(yè)群組化）；（注：將類(lèi)似相關(guān)的作業(yè)群組化，避免作業(yè)數(shù)太大。）設(shè)立活動(dòng)相關(guān)性等級(jí)（依知識(shí)、計(jì)算、討論等）；評(píng)估每對(duì)活動(dòng)的相關(guān)性，確定等級(jí)；填入確定相關(guān)性的理由。4.*工藝流程表：該表是采用物流標(biāo)準(zhǔn)符號(hào)來(lái)表示每一個(gè)工藝過(guò)程。將某種產(chǎn)品整個(gè)加工工藝中的各種物料搬運(yùn)全部列在一起，分析統(tǒng)計(jì)各項(xiàng)活動(dòng)的次數(shù)比例、時(shí)間比例，以尋求提高物流效率的關(guān)鍵。*物流標(biāo)準(zhǔn)符號(hào)：（這些符號(hào)是由F.M.Gilbreth于1920年

9、所設(shè)定的，至今仍采用之）例：P91加工工藝流程程序圖（次數(shù)統(tǒng)計(jì)有誤）從分析結(jié)果看，停滯過(guò)程的次數(shù)和時(shí)間比例較高，重點(diǎn)考慮*第5章 企業(yè)物流分析*本章小結(jié)*作業(yè)單位相互關(guān)系分析：重點(diǎn)掌握 根據(jù)物流因素和非物流因素繪制*作業(yè)（部門(mén)）關(guān)系圖。重點(diǎn)掌握*設(shè)施布置的基本形式：工藝布置、產(chǎn)品布置、成組布置及固定位置布置。*設(shè)施布置的目標(biāo)：設(shè)施間物料搬運(yùn)費(fèi)用最小。*企業(yè)物流的基本形式：直線(xiàn)型、L型、U型、O型、S型*物流分析的圖表方法：線(xiàn)圖、多種產(chǎn)品工藝圖、*從至表、工藝流程表、物流布置筒圖等。6.1 *系統(tǒng)化設(shè)施布置方法SLP6.1.1 * 經(jīng)典的SLP方法*在SLP方法中，可將研究設(shè)施布置問(wèn)題的依據(jù)和切

10、入點(diǎn)歸納為五個(gè)基本要素，即：P產(chǎn)品（材料或貨物類(lèi)別）；Q數(shù)量（產(chǎn)品）；R生產(chǎn)路線(xiàn)（工藝過(guò)程順序或貨物處理次序）；S輔助部門(mén)（輔助設(shè)施，如服務(wù)部門(mén)或設(shè)施）；T時(shí)間（時(shí)間安排）。 （解決布置問(wèn)題的“鑰匙”）其中：P和Q是一切其他特征或條件的基礎(chǔ)。1.*問(wèn)題：對(duì)一個(gè)待布置區(qū)域（某一物流節(jié)點(diǎn)）內(nèi)各作業(yè)單位（或設(shè)施），根據(jù)其作業(yè)流程等定量地確定它們之間相互關(guān)系的等級(jí)，并系統(tǒng)地布置各設(shè)施的相對(duì)位置，以及對(duì)設(shè)施布置方案的質(zhì)量驚醒定量評(píng)估。2.*SLP法的設(shè)計(jì)原理（步驟）：建立作業(yè)單位相互關(guān)系圖：對(duì)各作業(yè)單位之間的相互關(guān)系作出分析，包括物流和非物流的相互關(guān)系；繪制作業(yè)單位位置相關(guān)圖和面積相關(guān)圖（空間關(guān)系圖）：

11、據(jù)關(guān)系圖中的相互關(guān)系等級(jí)決定設(shè)施間距離的遠(yuǎn)近并安排相應(yīng)的位置位置相關(guān)圖；結(jié)合各設(shè)施的實(shí)際占地面積空間關(guān)系圖；通過(guò)空間關(guān)系圖的修正和調(diào)整，得若干個(gè)可行的布置方案；量化各因素，用加權(quán)系數(shù)法建立方案質(zhì)量評(píng)估的數(shù)量指標(biāo)，并用該指標(biāo)對(duì)各方案進(jìn)行評(píng)價(jià)，得分最多的布置方案就是最佳布置方案。3.*空間關(guān)系圖： （2）試錯(cuò)法 *用試錯(cuò)法由關(guān)系圖生成空間關(guān)系圖的步驟：（多次“試錯(cuò)”）將A、E級(jí)關(guān)系的部門(mén)放進(jìn)布置圖中，同級(jí)別的關(guān)系用相同長(zhǎng)度的線(xiàn)段表示。調(diào)整使E級(jí)關(guān)系的線(xiàn)段長(zhǎng)度為A級(jí)關(guān)系的2倍。按同樣的規(guī)劃布置1級(jí)關(guān)系。若部門(mén)較多，線(xiàn)段混亂，可以不必畫(huà)出0級(jí)關(guān)系。但X關(guān)系必須畫(huà)出。調(diào)整各部門(mén)的位置，以滿(mǎn)足關(guān)系的稀疏程

12、度。將各部門(mén)的面積表示進(jìn)布置圖中，生成空間關(guān)系圖。經(jīng)過(guò)評(píng)價(jià)、修改，獲得最終布置。6.2 *計(jì)算機(jī)化布置方法（4種布置算法）*計(jì)算機(jī)化布置方法的分類(lèi)： 構(gòu)建型：CORELAP，ALDEP; 改進(jìn)型：CRAFT,MULTIPLE; 基于物流從至表：CRAFT,MULTIPLE; （依信息基礎(chǔ)分） 基于關(guān)系圖：ALDEP,CORELAP; 單層布置方法：CRAFT,CORELAP; (單層或多層) 多層布置方法：CRAFT,CORELAP: 整個(gè)方法基本都可分成3步*：選擇（確定布置順序矢量）、放置（如何放）、評(píng)估（布置結(jié)果評(píng)估）。6.2.1 *CRAFT布局算法*改進(jìn)型、基于物流從至表、單層布置算

13、法。 （Buffa等人1964年提出）1.*問(wèn)題： 設(shè)一個(gè)物流節(jié)點(diǎn)由n個(gè)設(shè)施組成，一直各設(shè)施間的貨物流量矩陣Q（從至表），試對(duì)一個(gè)初始布置方案P0進(jìn)行適當(dāng)?shù)恼{(diào)整，使物流節(jié)點(diǎn)內(nèi)的總搬運(yùn)費(fèi)用最少。注：*該法對(duì)P0給出了一種使總搬運(yùn)費(fèi)用減少的調(diào)整方法，并保證調(diào)整后的方案仍是可行的。調(diào)整的方法是將若干個(gè)滿(mǎn)足一定條件的設(shè)施進(jìn)行交換。2.*設(shè)施交換條件： 具有公共邊或面積相等。 這種交換條件不是可行交換的必要條件，它是為了使相交換的設(shè)施的位置互換后不致引起其他設(shè)施位置的變化。交換方式：兩兩交換，或3設(shè)施交換。最大交換次數(shù)n(n-1)/23.*目標(biāo)函數(shù)：其中： qij設(shè)施間的物流量； dij設(shè)施間的距離，一

14、般采用設(shè)施中心間的折線(xiàn)距離； cij設(shè)施間單位距離運(yùn)輸成本。4.*CRAFT算法：輸入：設(shè)施數(shù)n，物流量矩陣Q=（qij）， 單位距離成本矩陣C=（cij），初始布置方案P0輸出：布置方案p，總搬運(yùn)成本Z*步驟：將規(guī)劃區(qū)域按要求劃分成若干面積相等的方形小單元，滿(mǎn)足每個(gè)設(shè)施至少包含一個(gè)單元，且每個(gè)單元只在一個(gè)設(shè)施之中；計(jì)算P0中各設(shè)施中心間的折線(xiàn)距離dij和目標(biāo)函數(shù)值Z0；列出P0所有的滿(mǎn)足交換條件的設(shè)施交換方案，進(jìn)行逐個(gè)交換，選擇目標(biāo)函數(shù)最小的布置作為交換結(jié)果，記為P，對(duì)應(yīng)的目標(biāo)函數(shù)值為Z；若ZZ0，則令Z0=Z,P0=P,轉(zhuǎn)。否則，令Z=Z0，P=P0，停止。6.2.2CORELAP布置算法

15、*構(gòu)造型、基于關(guān)系圖的單層布置方法 （計(jì)算機(jī)化關(guān)系布置方法）1.問(wèn)題*：設(shè)一個(gè)物流節(jié)點(diǎn)由n個(gè)設(shè)施組成，已知各設(shè)施的作業(yè)面積需求及相互間關(guān)系等級(jí)。需確定一個(gè)設(shè)施布置方案，使各設(shè)施的總關(guān)系程度達(dá)到最優(yōu)。2.算法思路*： 算法的出發(fā)點(diǎn)是設(shè)施之間的關(guān)系圖，布置的目標(biāo)是實(shí)現(xiàn)設(shè)施之間最大的密切度。 算法*：首先按一定規(guī)劃生成一個(gè)（確定）設(shè)施順序矢量，依該矢量的順序逐個(gè)將設(shè)施加入到區(qū)域中去，并盡量（選擇）使新加入的設(shè)施與原有的設(shè)施在相對(duì)位置上保證關(guān)系最密切。布置方案完成后，對(duì)其質(zhì)量指標(biāo)（計(jì)算）進(jìn)行評(píng)估。3.*布置質(zhì)量指標(biāo)：為對(duì)布置方案進(jìn)行優(yōu)化，需定義一個(gè)反映關(guān)于設(shè)施間密切度的數(shù)量指標(biāo)。先量化兩個(gè)設(shè)施間的關(guān)系

16、程度：其中：rij設(shè)施間的關(guān)系值，dij同上。注：*不同方案的比較，總得分越小的方案越優(yōu)。4.*布置設(shè)施順序的確定 *布置順序原則;(選擇方法)選擇TCR最大的設(shè)施作為最優(yōu)進(jìn)入布置的設(shè)施。若最大的TCR值有多個(gè)設(shè)施，即出現(xiàn)“結(jié)”，則選擇面積最大的設(shè)施解“結(jié)”；若依然解不開(kāi)，則隨機(jī)選??；選擇與第一個(gè)設(shè)施具有最高級(jí)別關(guān)系（A級(jí)）的設(shè)施作為第二個(gè)進(jìn)入布置的設(shè)施。依次選擇E級(jí)、I級(jí)、；如果在同一關(guān)系級(jí)別中出現(xiàn)多個(gè)設(shè)施（“結(jié)”），選擇這些設(shè)施中TCR最大的設(shè)施先布置（解“結(jié)”），若TCR最大值有多個(gè)設(shè)施，則選擇面積最大的設(shè)施解“結(jié)”，若依然解不開(kāi)，則隨機(jī)選取。選擇與第一二部門(mén)為AA、AE、AI、A*的排

17、列順序選擇第三部門(mén)，解“結(jié)”的方法同。依次選擇直至結(jié)束。 在布置中，設(shè)施的形狀盡可能設(shè)計(jì)成正方形。5.*相對(duì)位置的確定： 放置原則：在所有可布置的位置中，選擇使進(jìn)入布置圖的設(shè)施與前面進(jìn)入的相鄰設(shè)施的關(guān)系值的和NCR最大的那個(gè)位置。 （NCR:Neighbor Closeness Rating）6.2.3*ALDEP布置算法*構(gòu)建型基于關(guān)系圖的多層布置方法 （自動(dòng)化布置設(shè)計(jì)程序） *與CORELAP法相似：構(gòu)建型、基于關(guān)系圖、也是每次選擇一個(gè)設(shè)施加入布置圖，按一定規(guī)則尋找其適合的位置，并對(duì)方案進(jìn)行評(píng)估。 *不同：CORELAP為單層；ALDEP為多層；設(shè)施的選擇次序；位置的確定法；方案評(píng)估的指標(biāo)

18、。1.*問(wèn)題：設(shè)一個(gè)物流節(jié)點(diǎn)由n個(gè)設(shè)施組成，已知各設(shè)施的作業(yè)面積需求及各設(shè)施間的關(guān)系等級(jí)。需確定一個(gè)設(shè)施布置方案，使各相鄰設(shè)施的關(guān)系值總和達(dá)到最大。 （與CORELAP的區(qū)別是優(yōu)化的目標(biāo)不同。）2.*布置質(zhì)量指標(biāo)：*評(píng)估思想：尋求相鄰設(shè)施的關(guān)系總和最大的布置為最后布置方案。 為強(qiáng)調(diào)相鄰設(shè)施的相互關(guān)系，在將關(guān)系等級(jí)轉(zhuǎn)換成關(guān)系值時(shí)，拉大了不同等級(jí)間數(shù)值的差距。3.*布置設(shè)施順序的確定隨機(jī)選取一個(gè)設(shè)施為第一個(gè)布置設(shè)施； （為優(yōu)化布置結(jié)果，擴(kuò)大布置范圍）隨后的選擇方法是根據(jù)與第一個(gè)設(shè)施的關(guān)系進(jìn)行排隊(duì)，直到排到設(shè)定的最低關(guān)系密切度TCR。 （TCR：Threshold Closeness Rating）

19、 如：若取TCR=E，則只選擇與先布置設(shè)施具有A、E關(guān)系的設(shè)施進(jìn)入布置排列。對(duì)于與先布置設(shè)施均勻?yàn)锳或E的布置設(shè)施，則隨機(jī)選擇進(jìn)入布置。4.*設(shè)施位置的確定：如p105，圖5-12，其中，設(shè)定的寬度即“掃描”寬度。6.2.4 *MultiPLE布置算法*改進(jìn)型、基于從至表的多層設(shè)施布置方法 （與Craft類(lèi)似）*MultiPLE與Craft：相同：改進(jìn)型，基于從至表，基于距離的目標(biāo)函數(shù)（搬運(yùn)成本），距離采用中心間折線(xiàn)距離，采用兩部門(mén)交換，每次迭代中選擇布置成本下降最大的方案。（最速下降法）區(qū)別：對(duì)P0進(jìn)行調(diào)整的方法不同，部門(mén)交換不局限于兩相鄰部門(mén)間，它通過(guò)空間填充曲線(xiàn)SFC實(shí)現(xiàn)。SFC曲線(xiàn)：P

20、106，空間填充曲線(xiàn)，如Hilbert曲線(xiàn)。*步驟：將規(guī)劃區(qū)域按要求劃分成若干面積相等的方形小單元，滿(mǎn)足每個(gè)設(shè)施至少包含一個(gè)單元，且每個(gè)單元只在一個(gè)設(shè)施之中；根據(jù)P0生產(chǎn)SFC，得到P0的布置順序矢量；計(jì)算P0中各設(shè)施中心間的折線(xiàn)距離dij和目標(biāo)函數(shù)值Z0；選擇任意兩個(gè)設(shè)施進(jìn)行逐個(gè)交換，生成新的布置順序矢量，選擇最小的布置作為這一輪的交換結(jié)果，記為P和Z；若Z1/9，b6/11.設(shè)：為貨架單位長(zhǎng)度，為貨架安慰長(zhǎng)度；則*倉(cāng)庫(kù)實(shí)長(zhǎng)=（ax=x），*倉(cāng)庫(kù)實(shí)寬=（by+y）（倉(cāng)庫(kù)的長(zhǎng)=ax+x單位長(zhǎng)度，倉(cāng)庫(kù)的寬=by+y單位長(zhǎng)度）*求解：注意：實(shí)際上x(chóng)，y應(yīng)取不小于和的最小整數(shù)。在數(shù)論中，設(shè)為一般實(shí)數(shù)

21、，不超過(guò)的最大整數(shù)即為，而=-稱(chēng)為的分?jǐn)?shù)部分。如：2.3=2，-3.5=-4，所以*當(dāng)解得結(jié)果為非整數(shù)時(shí)，?。?.*直接堆放方式（4）*直接堆放的尺寸：?jiǎn)栴}：已知貨堆長(zhǎng)度（通道寬度）、堆放層數(shù)和每堆的總數(shù)；去頂物品堆的寬度（深），以便最大程度利用空間？Kind提出一個(gè)簡(jiǎn)單公式得出一個(gè)近似的最佳深度，但要滿(mǎn)足一下前提條件：物品擺放滿(mǎn)足任意擺放規(guī)則；P163補(bǔ)充立即完成，且只有在庫(kù)存完全耗盡的時(shí)候進(jìn)行；物品按先進(jìn)先出順序周轉(zhuǎn)；物品平均提?。豢盏呢浳豢闪⒓词褂?。*建立模型：設(shè)Q每堆物品總數(shù)；通道寬度（貨堆長(zhǎng)度）；z貨堆分層丨；d貨堆深度（寬度）則： （該式由Kind與1975年提出）例題：設(shè)Q、和z

22、分別是60，,.7和3，則 與其他寬度計(jì)算結(jié)果相比，d的值是最優(yōu)解，該公式簡(jiǎn)單，但一些影響因素被忽略，如物品不是平均提取而是不定量提取的影響、或堆放時(shí)是否考慮將同類(lèi)堆放在附近等。（1）*直接堆放條件：物品不易損壞，包裝足夠承受2-3層的壓力，如飲料、計(jì)算機(jī)等；（2）*直接堆放方式：將物品按層次從底部直接堆放。 適用：周轉(zhuǎn)較快的物品。（倉(cāng)儲(chǔ)時(shí)間斷不必用貨架等。）（3）*直接堆放效率：當(dāng)層數(shù)過(guò)多，或?qū)挾冗^(guò)大時(shí)，堆放效率不高。 *蜂窩損失：由于無(wú)效利用存儲(chǔ)空間而使存儲(chǔ)區(qū)域能力損失的百分比。 *蜂窩損失空間：存儲(chǔ)位置中沒(méi)有被占據(jù)的區(qū)域。 當(dāng)存儲(chǔ)位置僅部分的堆積了物料，就出現(xiàn)了蜂窩損失。如：由于倉(cāng)庫(kù)側(cè)存

23、取先入先出原則，當(dāng)物品周轉(zhuǎn)速率不快或者每次S/R量不足一個(gè)貨堆時(shí)，空出的位置不能被其他物品所利用而出現(xiàn)空間損失，即為蜂窩損失。8.2.5*存儲(chǔ)原則1*五種倉(cāng)庫(kù)物品存儲(chǔ)原則隨機(jī)存儲(chǔ)原則：將運(yùn)入的物品放到任意可放的位置。隨機(jī)存儲(chǔ)和提取原則在實(shí)際中不是真正隨機(jī)的，操作人員傾向于優(yōu)先使用最近的空間。分類(lèi)存儲(chǔ)原則：將存儲(chǔ)空間劃分成若干個(gè)區(qū)域，每個(gè)區(qū)域存放特定的物品。*討論：在相同的S/R數(shù)量和頻率下，使用隨機(jī)存儲(chǔ)原則還是使用分類(lèi)存儲(chǔ)原則占用的存儲(chǔ)面積少？當(dāng)需存取的物品數(shù)量較大時(shí)，使用哪個(gè)原則存儲(chǔ)效率更高？（3）*CIO原則： 按物品COI值得遞減順序安排存儲(chǔ)位置，COI值越高的物品，越靠近I/O口布置。

24、所以物品的單次S/R量大存儲(chǔ)空間要求較少的物品放在I/O口附近。（4）*分級(jí)存儲(chǔ)原則：根據(jù)ABC原則將物品分為A,B,C三類(lèi)，A類(lèi)物品最靠近I/O口放置，B類(lèi)其次，以此類(lèi)推。（P149庫(kù)存ABC管理方法）ABC分類(lèi)：80%的S/R活動(dòng)是關(guān)于20%的物品的（A類(lèi)）；15%的S/R活動(dòng)是關(guān)于30%物品的（B類(lèi)）；55d%的S/R活動(dòng)和50%的物品相關(guān)。（P165）*如：運(yùn)動(dòng)會(huì)，班級(jí)團(tuán)隊(duì)總分的ABC分級(jí)。注：速記存儲(chǔ)原則和分類(lèi)原則是兩種極端原則，而COI原則和分級(jí)原則是某種程度上的折衷。（5）*混合存儲(chǔ)原則：根據(jù)經(jīng)驗(yàn)。直覺(jué)來(lái)操。*如：隨機(jī)存儲(chǔ)原則中，某存儲(chǔ)空間存儲(chǔ)不同的物品，但物品的擺放按COI原則

25、。（如：你們的抽屜）*混合存儲(chǔ)原則的優(yōu)點(diǎn)：提高單位時(shí)間的S/R次數(shù)，提高S/R設(shè)備利用率。2.*三種常用原則下的倉(cāng)庫(kù)布置模型：（1）*分類(lèi)原則布置*問(wèn)題：A倉(cāng)庫(kù)有p個(gè)I/O，可容納n個(gè)單位空間的物品，可供m種物品的存取，對(duì)于第i種物品，需要Si單位空間。建立倉(cāng)庫(kù)布置模型，以降低總體運(yùn)輸費(fèi)用。*理想的情況：當(dāng)時(shí)，可假設(shè)第m種物品占據(jù)個(gè)剩余空間，從而假設(shè)等式成立。而當(dāng)時(shí)，則問(wèn)題無(wú)法解決。（2）*特定條件下的COI原則布置*問(wèn)題：每種貨物以同樣的比例進(jìn)出I/O口點(diǎn)，且移動(dòng)貨物的單位距離的費(fèi)用與I/O點(diǎn)無(wú)關(guān)。*建立數(shù)學(xué)模型：*定義：Pk物品通過(guò)第k個(gè)I/O點(diǎn)進(jìn)出倉(cāng)庫(kù)的比例，k=1,2，p；（注：Pk對(duì)

26、任何一種貨物都成立，因?yàn)樗械呢浳锒家韵嗤谋壤褂肐/O點(diǎn)） fi物品i進(jìn)出倉(cāng)庫(kù)的頻率；Ci單位物品i移動(dòng)單位距離的費(fèi)用。（以fi，Ci代替fik，Cik）8.3*倉(cāng)庫(kù)操作存取與提取系統(tǒng)8.3.2*倉(cāng)庫(kù)提取系統(tǒng)分析1*訂單提取方法（最基本的）（1）*順序提?。阂淮雾樞蛱崛⊥暌粋€(gè)訂單上的貨物。針對(duì)大訂單，提取時(shí)操作者需穿越整個(gè)倉(cāng)庫(kù)。（2）*區(qū)域提?。焊鲄^(qū)域操作員值提取所負(fù)責(zé)區(qū)域的訂單。針對(duì)小訂單，提取時(shí)操作員被限制在制定區(qū)域內(nèi)*本章小結(jié)*倉(cāng)庫(kù)的功能：存儲(chǔ)貨物、運(yùn)輸中轉(zhuǎn)、響應(yīng)顧客需求 *倉(cāng)庫(kù)尺寸設(shè)計(jì)：掌握貨架方式存儲(chǔ)物品時(shí)尺寸的設(shè)計(jì)方法 *物品存儲(chǔ)原則：隨機(jī)存儲(chǔ)原則、分類(lèi)存儲(chǔ)原則、COI原則、分

27、級(jí)存儲(chǔ)原則、混合存儲(chǔ)原則 *分類(lèi)原則布置 *特定條件下的COI原則布置 *隨機(jī)存儲(chǔ)原則布置第九章9.2線(xiàn)路優(yōu)化模型*9.2.1*點(diǎn)點(diǎn)間運(yùn)輸最短路徑求解方法*最短路徑問(wèn)題的應(yīng)用：各種管道鋪設(shè)，線(xiàn)路安排，廠(chǎng)區(qū)布局，旅游，道路修筑，道路選擇。*最短路徑問(wèn)題常分為兩類(lèi)：（P186四類(lèi)，可合并）從起點(diǎn)到其他各點(diǎn)的最短路徑；所有任意兩點(diǎn)間的最短路徑。*連通圖：任何兩點(diǎn)間至少有一條鏈連接。*連通圖的最短路徑問(wèn)題：求兩點(diǎn)間長(zhǎng)度最短的路程。 長(zhǎng)度：路徑上各邊的權(quán)值之和。 權(quán)值：如費(fèi)用、影響等。1.*最短路徑問(wèn)題的描述： 設(shè)有一n個(gè)節(jié)點(diǎn)和m條弧的連通圖G（Vn，Em），圖中每條?。╥，j）都有一個(gè)權(quán)重Cij，則最

28、短路徑問(wèn)題為：在G（Vn，Em）中找到一條從節(jié)點(diǎn)v1到節(jié)點(diǎn)vn總權(quán)重最小的路徑。2.*建模： 設(shè)存在連通圖G（Vn，Em），權(quán)重C=(Cij)，i=1,2，.n；j=1,2，m 目標(biāo)函數(shù)：（L（A）為總費(fèi)用）其中AEm，A為從v1到vn的一條路徑。*建模：s.t（目的是問(wèn)題得到合理的、正確的解）；（1）兩點(diǎn)之間的弧線(xiàn)距離為整數(shù)（現(xiàn)有算法不需）；（2）在連通圖中，從任一端點(diǎn)vi到其他所有的斷點(diǎn)vj都有直接的路程，如存在不直接相連的斷點(diǎn)，則可設(shè)cij=，表示vi，vj間不吭能作為一個(gè)備選方案；（3）cij0；（4）連通圖是有方向性的 *3.求解主要算法：*Dijkstra算法、逐次逼近算法、Flo

29、yd算法等。（1）*Dijkstra算法基本思路： 在G（Vn，Em）中，求解從節(jié)點(diǎn)v1到vn的最短路徑時(shí)，先求出從v1出發(fā)的一條最短路徑，再參照它求出一條次短路徑，依次類(lèi)推，知道v1到vn的最短李靜求出為止。（vn為v1以外的任一節(jié)點(diǎn)時(shí)相同）*Djkisrtra算法的依據(jù)： *定理：如果序列式從v1到vn的最短路徑，則子序列也必然是從v1到vn-1的最短路徑。（2）*Dikjstra算法中的標(biāo)號(hào)：*標(biāo)號(hào)：在Dikjstra算法中用來(lái)標(biāo)記各節(jié)點(diǎn)的屬性的符號(hào)。對(duì)于每一個(gè)節(jié)點(diǎn)vj，都富裕一個(gè)標(biāo)號(hào)，標(biāo)號(hào)分為T(mén)標(biāo)號(hào)和S標(biāo)號(hào)兩種：*T標(biāo)號(hào)：表示從v1到vj的最短路權(quán)的上界，稱(chēng)為臨時(shí)標(biāo)號(hào)；*S標(biāo)號(hào)：表示從

30、v1到vj的最短路權(quán)，稱(chēng)為固定標(biāo)號(hào)。*注：已得到S標(biāo)號(hào)的點(diǎn)不再改變，算法的每一步把某一點(diǎn)的T標(biāo)號(hào)給位S標(biāo)號(hào)，直至vn變?yōu)镾標(biāo)號(hào)。Dijkstra算法中的標(biāo)號(hào)*：根據(jù)標(biāo)記確定節(jié)點(diǎn)vj的標(biāo)號(hào)屬性和標(biāo)記過(guò)程的不同，有兩種不同的Dijkstra算法：*標(biāo)號(hào)設(shè)定算法：（屬迭代算法）*思路：在每一步迭代中用試探性標(biāo)號(hào)標(biāo)記所欲的試探點(diǎn)，通過(guò)一系列的試探尋找該步中的最短路權(quán)，并將每一次迭代中得到的滿(mǎn)意的試探標(biāo)號(hào)設(shè)置為永久標(biāo)號(hào)。*適用：只適用于求解非負(fù)網(wǎng)絡(luò)中的最短路徑問(wèn)題。標(biāo)號(hào)設(shè)定Dijkstra算法的基本步驟：*設(shè)S為永久標(biāo)號(hào)頂點(diǎn)集，T為臨時(shí)標(biāo)號(hào)頂點(diǎn)集：*初始時(shí)，令S=v1，然后從T中選取到v1路權(quán)最小的vj

31、加入S即對(duì)vj加上一個(gè)永久的標(biāo)號(hào)，滿(mǎn)足（vj或與v1相連，或與S中最短路權(quán)頂點(diǎn)相連）其中：*重復(fù)，直到vn被加入到S中。根據(jù)對(duì)每個(gè)節(jié)點(diǎn)的標(biāo)記，可得到從v1到vn所需完成的行程（最小路權(quán)值）。對(duì)計(jì)算過(guò)程的逆向觀(guān)察，就可得到最短路徑*例2：解：直觀(guān)簡(jiǎn)化解法：*Dijkstra最短路表解法：（注意：lk（vj）的公式要熟，cij值可填入，但復(fù)雜。故cij可從圖獲得，即用表加圖的形式。）說(shuō)明：上圖易求最短距離，加下標(biāo)可標(biāo)記最短路徑，即加上一個(gè)代表上級(jí)節(jié)點(diǎn)的下表。V1到v7的最短路徑為：v1，v2，v3，v4，v5，v6，v7V1到v7的最短距離為：133.*求解：表上作業(yè)法；改進(jìn)方案用閉回路法對(duì)初始條

32、件解進(jìn)行優(yōu)化。*閉回路法步驟： 1*計(jì)算初始條件解運(yùn)輸方案下的總運(yùn)輸成本： 2*在運(yùn)輸表上選擇一個(gè)空格，填上大于0的數(shù)，并在表上尋找一個(gè)閉回路，在閉回路進(jìn)行供需平衡，在平衡之后，再計(jì)算運(yùn)輸成本，若總一年書(shū)成本下降，則進(jìn)行調(diào)整。反復(fù)進(jìn)行該過(guò)程，知道無(wú)法調(diào)整為止。則得到運(yùn)輸表中的解為最優(yōu)解。*注1：在某空格增加一個(gè)0后必須調(diào)整閉回路上的其他節(jié)點(diǎn)之一為空格。*注2：調(diào)整一個(gè)空格后，其余空格需重新檢查值，對(duì)所有空格均有時(shí)停止。*閉回路法原理：利用閉回路調(diào)整檢驗(yàn)初始調(diào)勻方案以求得最優(yōu)解，閉回路指從給定初始方案的任一空格出發(fā)，尋找一條除該空格外，其余均由有數(shù)字格為頂點(diǎn)組成的閉回路。（*閉回路的尋找：從給定

33、的初始方案的任一空格出發(fā)，沿水平或垂直方向前進(jìn)，當(dāng)碰到另一個(gè)有數(shù)字格后，便轉(zhuǎn)90度繼續(xù)前進(jìn)，知道回到原點(diǎn)出發(fā)）*注1：對(duì)每一空格可以找到且也只能找到唯一的閉回路*注2：閉回路也可能過(guò)某一數(shù)字格而不拐彎，因?yàn)樗尤朐擖c(diǎn)不能形成閉回路。9.2.2*多點(diǎn)間運(yùn)輸運(yùn)輸算法1.*問(wèn)題：是指起始點(diǎn)或目的點(diǎn)不唯一的運(yùn)輸調(diào)配問(wèn)題。 如產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題：總供應(yīng)能力=總需求，尋求最佳的配送路徑，使總運(yùn)輸成本降低。*目標(biāo)：尋找最低的總運(yùn)輸成本。2.*建立數(shù)學(xué)模型設(shè)：A=a1,a2,am為供應(yīng)能力矩陣 B=b1,b2,bn為需求矩陣 C=(cij)mn為運(yùn)輸距離或成本矩陣xij等于從供應(yīng)點(diǎn)i到需求點(diǎn)j的發(fā)送量作圖法1.

34、給v1表上其余頂點(diǎn)表上臨時(shí)值；2設(shè)vi為剛得到S標(biāo)號(hào)的頂點(diǎn)，則按：調(diào)整其余T標(biāo)號(hào)點(diǎn)的值。3.若T中沒(méi)有節(jié)點(diǎn)，則停止，否則：9.2.3*單回路運(yùn)輸TSP模型及求解2.*TSP模型（旅行商問(wèn)題）單回路運(yùn)輸問(wèn)題（典型） 對(duì)大規(guī)模的線(xiàn)路優(yōu)化問(wèn)題，無(wú)法獲得最優(yōu)解，周游通過(guò)啟發(fā)式算法獲得近優(yōu)解。（1）*問(wèn)題：給出n個(gè)頂點(diǎn)的網(wǎng)絡(luò)（又向或無(wú)向），要求找出一個(gè)包含所有n個(gè)頂點(diǎn)的具有最小消費(fèi)的環(huán)路。*回路：包含網(wǎng)絡(luò)中所有n個(gè)頂點(diǎn)的環(huán)路。TSP即要設(shè)法找到一條最小消費(fèi)的回路。*TSP的特點(diǎn)：任一點(diǎn)均可作為起點(diǎn)（終點(diǎn)）。（因?yàn)榛芈钒许旤c(diǎn)）1.*單回路運(yùn)輸問(wèn)題 在線(xiàn)路優(yōu)化中，設(shè)存在節(jié)點(diǎn)集D，選擇一條合適的路徑遍歷

35、所有節(jié)點(diǎn)，并要求閉合，且達(dá)到所行駛距離最短。*注：在運(yùn)輸決策中，主要用于單一車(chē)輛的路徑安排。*目標(biāo)：該車(chē)輛遍歷所有的節(jié)點(diǎn)（回路），且達(dá)到所行駛距離最短。*特點(diǎn)：?jiǎn)我恍裕ㄖ挥幸粋€(gè)回路）遍歷性（不可遺漏）。4.*最近插入啟發(fā)式算法*特點(diǎn)：可以得到相對(duì)較滿(mǎn)意的解*步驟：（1）找到c1k最小節(jié)點(diǎn)vk，形成一個(gè)子回路T=v1，vk，v1； （2）在剩下節(jié)點(diǎn)中，尋找離子回路中某一節(jié)點(diǎn)最近的節(jié)點(diǎn)vk； （3）在子回路中找到一條?。╥，j），使Cik+Ckj-Cij最小，則將節(jié)點(diǎn)vk插入到vi，vj之間，用心的弧（i，k）、（k，j）代替原來(lái)的?。╥，j），并將節(jié)點(diǎn)vk加入到子回路中； （4）重復(fù)步驟（2）（

36、3），知道所有節(jié)點(diǎn)都加入子回路中。則子回路即為一個(gè)TSP的解。3.*最近鄰點(diǎn)啟發(fā)式算法：*特點(diǎn)：簡(jiǎn)單，但精度低，其解一般作為進(jìn)一步優(yōu)化的初始解。*步驟：（1）從零點(diǎn)開(kāi)始，作為整個(gè)回路的起點(diǎn)（2）找到離剛加入到回路的上以頂點(diǎn)最近的一個(gè)頂點(diǎn)，并加入到回路中；（3）重復(fù)（2），知道A中的所有頂點(diǎn)都加入到回路中（4）將最后一個(gè)的頂點(diǎn)和起點(diǎn)連接。9.2.4*多回路運(yùn)輸VRP模型及求解1.*VRP模型：車(chē)輛線(xiàn)路安排問(wèn)題（不考慮時(shí)間要求） 多回路運(yùn)輸問(wèn)題即調(diào)配問(wèn)題，其核心問(wèn)題是車(chē)輛調(diào)度，而VRP模型是解決多回路運(yùn)輸問(wèn)題的一個(gè)成功的模型，稱(chēng)為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與研究熱點(diǎn)問(wèn)題。（1）*配送規(guī)劃問(wèn)題：“配

37、”，“送”*研究目標(biāo)：對(duì)一系列裝貨點(diǎn)和（或）需求點(diǎn)設(shè)計(jì)適當(dāng)?shù)穆肪€(xiàn)，使車(chē)輛有序的通過(guò)他們，在滿(mǎn)足一定月嫂調(diào)價(jià)下，達(dá)到一定優(yōu)化目標(biāo)。*即：多亮交通工具的服務(wù)對(duì)象的選擇和路徑確定。（3）*典型VRP模型：建模：目標(biāo)函數(shù)：S,t. Nm; 每一定單都要完成； 每輛車(chē)完成任務(wù)后之后都要回到v0點(diǎn)； 車(chē)輛的容量限制不能超過(guò)； 特殊問(wèn)題還需要考慮時(shí)間窗的限制； 運(yùn)輸規(guī)章的限制。 VRP問(wèn)題應(yīng)用很廣，按不同的分類(lèi)原則可把它分為不同的子問(wèn)題，建立不同的數(shù)學(xué)模型，并采用相應(yīng)的數(shù)學(xué)算法求解。VRP問(wèn)題的分類(lèi)：P207表8-23純裝（純卸或裝卸混合）問(wèn)題；對(duì)弧服務(wù)問(wèn)題（弧模型，即中國(guó)郵遞員問(wèn)題）要求：經(jīng)過(guò)各街道至少一

38、次，并使總路程最短。對(duì)點(diǎn)服務(wù)問(wèn)題（點(diǎn)模型，即旅游商問(wèn)題）；要求：過(guò)每個(gè)城市至少且只有一次，并使總路程最短單/多車(chē)場(chǎng)問(wèn)題。（3）典型VRP模型：*問(wèn)題：現(xiàn)有m輛相同的車(chē)輛，停在同一源點(diǎn)v0，需要給n個(gè)客戶(hù)供貨，顧客為v1，v2，vn；求所需車(chē)輛的數(shù)目N，各車(chē)輛的回路及回路內(nèi)的路徑安排和調(diào)度，使得運(yùn)輸總費(fèi)用C最小。*建模：（整數(shù)規(guī)劃模型） cij從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短距離（運(yùn)費(fèi)、時(shí)間等，cij只與運(yùn)輸距離有關(guān)）3.*節(jié)約算法（節(jié)約里程法） （貪婪算法）節(jié)約算法也稱(chēng)節(jié)約里程法，是Clarke和Wright在1964年提出的，也稱(chēng)C-W法，由于簡(jiǎn)單性和一定程度的實(shí)用性，稱(chēng)為廣泛實(shí)用的配送規(guī)劃近似算法，

39、是用來(lái)解決VRP模型最有名的啟發(fā)式算法。（1）*問(wèn)題：運(yùn)輸車(chē)輛數(shù)目不確定的VRP問(wèn)題，該算法對(duì)又向和無(wú)向問(wèn)題同樣有效。（2）*算法思路：核心思路是將運(yùn)輸問(wèn)題中存在的兩個(gè)回路（0,i，0）和（0，j，0）合并成一個(gè)回路（0，i，j，0）。若合并后使總運(yùn)輸距離下降，則稱(chēng)節(jié)約了運(yùn)輸距離。設(shè)只有兩個(gè)節(jié)點(diǎn)v1，v2，最簡(jiǎn)單的，分別配送，則距離為2c01+2c02；若改為單線(xiàn)配送，則距離為c01+c02+c12，節(jié)約距離為c01+c02-c120（也稱(chēng)節(jié)約里程，節(jié)約度）記為c12.（3）*節(jié)約算法步驟 已知v0擁有的車(chē)輛臺(tái)數(shù)為m及其載重噸Wi（i=1,2，.m）；需求點(diǎn)數(shù)n及其需貨量Ri（i=1,2，n）；每車(chē)每日最大運(yùn)程（或時(shí)間）為L(zhǎng)i（i=1,2，m）；v0，v1vn之間的距離（或時(shí)間）為cij（i-1,2，n-1。j=1,2，n。ij，i=0表示配送中心）。*目標(biāo)：求車(chē)輛應(yīng)用臺(tái)數(shù)k，車(chē)輛類(lèi)型及各車(chē)行走路徑（運(yùn)貨量及送貨次序），使總運(yùn)費(fèi)（距離或時(shí)間等）最小。（或?qū)嵼d率最高，用車(chē)數(shù)量最小等）s,t,Ri,Wi,Li均滿(mǎn)足。*節(jié)約算法 算法步驟：將車(chē)輛按Wi排序，W1W2Wm，