自動(dòng)化立體倉(cāng)庫(kù)系統(tǒng)課程設(shè)計(jì)

1、目錄引言11自動(dòng)化立體倉(cāng)庫(kù)21.1概述22貨位優(yōu)化32.1設(shè)計(jì)條件32.2計(jì)算系數(shù)矩陣3 2.2.1符號(hào)假設(shè)3 2.2.2已知條件4 2.2.3公式計(jì)算過(guò)程42.3運(yùn)用匈牙利算法求解62.4總結(jié)133堆垛機(jī)路徑優(yōu)化153.1 設(shè)計(jì)條件153.2設(shè)計(jì)要求163.3設(shè)計(jì)方法163.4求解過(guò)程16 3.4.1最近鄰點(diǎn)法求堆垛機(jī)運(yùn)行路徑19 3.4.2最近插入法求堆垛機(jī)運(yùn)行路徑263.5 總結(jié)34參考文獻(xiàn)36引言自動(dòng)化立體倉(cāng)庫(kù)產(chǎn)生和發(fā)展是生產(chǎn)力高度發(fā)展和城市化進(jìn)程不斷發(fā)展結(jié)果。計(jì)算機(jī)的出現(xiàn)和應(yīng)用，自動(dòng)化倉(cāng)庫(kù)的產(chǎn)生。倉(cāng)庫(kù)空間向立體化方向發(fā)展個(gè)，貨位向空間延伸，高層貨架和與之配套的新型裝卸搬運(yùn)機(jī)械與周邊設(shè)

2、備出現(xiàn)，立體倉(cāng)庫(kù)產(chǎn)生。自動(dòng)化立體倉(cāng)庫(kù)是指在高層貨架用貨箱或托盤(pán)儲(chǔ)存貨物，用電子計(jì)算機(jī)管理和控制巷道式堆垛機(jī)及其它機(jī)械，不需要人工作業(yè)而實(shí)現(xiàn)收發(fā)作業(yè)的倉(cāng)庫(kù)。自動(dòng)化立體倉(cāng)庫(kù)是一種集信息、儲(chǔ)存、管理于一體的高技術(shù)密集型機(jī)電化產(chǎn)品，堆垛機(jī)和高層貨架是其關(guān)鍵設(shè)備。隨著電子技術(shù)與控制理論的發(fā)展，各種控制方法被引入堆垛機(jī)的控制。貨位優(yōu)化和巷道式堆垛機(jī)的路徑優(yōu)化成為自動(dòng)化立體倉(cāng)庫(kù)的必要工作，因此本次課程設(shè)計(jì)針對(duì)這兩點(diǎn)做出了詳細(xì)的介紹。貨位優(yōu)化是用來(lái)確定每一品規(guī)的恰當(dāng)儲(chǔ)存方式，在恰當(dāng)?shù)膬?chǔ)存方式下的空間儲(chǔ)位分配。貨位優(yōu)化追求不同設(shè)備和貨架類(lèi)型特征、貨品分組、貨位規(guī)劃、人工成本內(nèi)置等因素以實(shí)現(xiàn)最佳的貨位布局，能有效

3、掌握商品變化，將成本節(jié)約最大化。貨位優(yōu)化為正在營(yíng)運(yùn)的倉(cāng)庫(kù)挖掘效率和成本，并為一個(gè)建設(shè)中的配送中心或倉(cāng)庫(kù)提供營(yíng)運(yùn)前的關(guān)鍵管理作準(zhǔn)備。1自動(dòng)化立體倉(cāng)庫(kù)1.1概述自動(dòng)化立體倉(cāng)庫(kù)作為現(xiàn)代化物流系統(tǒng)中的重要組成部分,是一種多層存放貨物的高架倉(cāng)庫(kù)系統(tǒng),主要由高層貨架、巷道堆垛機(jī)、出入庫(kù)輸送設(shè)備、自動(dòng)控制與管理系統(tǒng)所組成。出入庫(kù)輔助設(shè)備及巷道堆垛機(jī)能夠在計(jì)算機(jī)管理下，完成貨物的出入庫(kù)作業(yè)、實(shí)施綜合庫(kù)房管理并與上級(jí)管理系統(tǒng)聯(lián)網(wǎng)，可以實(shí)現(xiàn)管理現(xiàn)代化、存取自動(dòng)化，能按指令自動(dòng)完成貨物的存取作業(yè),并能對(duì)庫(kù)存的貨物進(jìn)行自動(dòng)化管理,是企業(yè)實(shí)現(xiàn)現(xiàn)代化管理的重要手段。自動(dòng)立體倉(cāng)庫(kù)在工廠自動(dòng)化，彈性制造系統(tǒng)及電腦整合制造系統(tǒng)

4、的物流中占非常重要的位置。其目的不僅是為了儲(chǔ)存物料、零件、半成品、成品的倉(cāng)儲(chǔ)，更是密切配合制造工廠的產(chǎn)銷(xiāo)計(jì)劃與物料需求計(jì)劃，妥善安排生產(chǎn)所需合理數(shù)量的物料、零件，并盡量縮短其庫(kù)存時(shí)間及避免了發(fā)生缺料、滯料，籍高架搬運(yùn)車(chē)、輸送機(jī)、無(wú)人搬運(yùn)車(chē)等，然后保管成品而依銷(xiāo)售預(yù)定準(zhǔn)進(jìn)正確出貨，提升服務(wù)水平，事合了計(jì)劃、庫(kù)存、生產(chǎn)、出入物流的功能與管理，降低了生產(chǎn)成本。 其組成部分：（1）貨架:用于存儲(chǔ)貨物的鋼結(jié)構(gòu)。主要有焊接式貨架和組合式貨架兩種基本形式。（2）托盤(pán)（貨箱）：用于承載貨物的器具，亦稱(chēng)工位器具。（3）巷道堆垛機(jī):用于自動(dòng)存取貨物的設(shè)備。按結(jié)構(gòu)形式分為單立柱和雙立柱兩種基本形式；按服務(wù)方式分為直

5、道、彎道和轉(zhuǎn)移車(chē)三種基本形式。（4）輸送機(jī)系統(tǒng):立體庫(kù)的主要外圍設(shè)備，負(fù)責(zé)將貨物運(yùn)送到堆垛機(jī)或從堆垛機(jī)將貨物移走。輸送機(jī)種類(lèi)非常多，常見(jiàn)的有輥道輸送機(jī)，鏈條輸送機(jī)，升降臺(tái)，分配車(chē)，提升機(jī)，皮帶機(jī)等。（5）AGV系統(tǒng):即自動(dòng)導(dǎo)向小車(chē)。根據(jù)其導(dǎo)向方式分為感應(yīng)式導(dǎo)向小車(chē)和激光導(dǎo)向小車(chē)。（6）自動(dòng)控制系統(tǒng):驅(qū)動(dòng)自動(dòng)化立體庫(kù)系統(tǒng)各設(shè)備的自動(dòng)控制系統(tǒng)。以采用現(xiàn)場(chǎng)總線方式為控制模式為主。（7）儲(chǔ)存信息管理系統(tǒng):亦稱(chēng)中央計(jì)算機(jī)管理系統(tǒng)。是全自動(dòng)化立體庫(kù)系統(tǒng)的核心。典型的自動(dòng)化立體庫(kù)系統(tǒng)均采用大型的數(shù)據(jù)庫(kù)系統(tǒng)（如ORACLE，SYBASE等）構(gòu)筑典型的客戶(hù)機(jī)/服務(wù)器體系，可以與其他系統(tǒng)（如ERP系統(tǒng)等）聯(lián)網(wǎng)或集

6、成。 2.貨位優(yōu)化 2.1設(shè)計(jì)條件某自動(dòng)化立體倉(cāng)庫(kù)采用2行3列的單元貨格式貨架存放貨物，一共有6個(gè)貨格，每個(gè)貨格存放一個(gè)托盤(pán)貨物。貨格以按列編碼的形式進(jìn)行編號(hào)，如圖2.1所示。已知其它參數(shù)假定如下：假設(shè)堆垛機(jī)在水平方向的行駛速度Vx=3.0m/s，在垂直方向的行駛速度Vy=2m/s；貨格大小為L(zhǎng)（長(zhǎng)）W（寬）H（高）=1m1m0.8m；堆垛機(jī)初始狀態(tài)在原點(diǎn)0處；貨格j的橫坐標(biāo)和縱坐標(biāo)就是其所在的列和行，如貨格6的坐標(biāo)為（3，2）?，F(xiàn)有6個(gè)托盤(pán)貨物需要存放到貨架上，貨物的出入庫(kù)頻率如表2.1所示。Vy2461350Vx圖2.1原始貨格圖表2.1 托盤(pán)貨物出入庫(kù)頻率表貨物頻率貨物頻率貨物頻率A9C

7、18E7B39D14F25根據(jù)以上條件，利用匈牙利算法合理安排各托盤(pán)貨物的存放位置。2.2計(jì)算系數(shù)矩陣2.2.1符號(hào)假設(shè)1.為第i種貨物的出入庫(kù)頻率（次數(shù)），i=A，B，C，D，E，F(xiàn)；2，分別為貨格j的橫坐標(biāo)和縱坐標(biāo)，即貨格j所在的列和行（距離巷道口最近的列記為第1列，最底層記為第1層），j=1，2，3，4，5，6；3為水平方向的行駛速度；4.為垂直方向的行駛速度；5.L為貨格的長(zhǎng)；6.W為貨格的寬；7.H為貨格的高；8.為堆垛機(jī)運(yùn)行之貨格j所用時(shí)間，該時(shí)間是堆垛機(jī)行進(jìn)過(guò)程中水平方向和垂直方向所用時(shí)間的最大值，j=1，2，3，4，5，6；9. 為堆垛機(jī)將貨物i向貨格j存取時(shí)所花費(fèi)的時(shí)間。10

8、. 公式為=max （2.1）11. 計(jì)算系數(shù)矩陣中的系數(shù)： = （2.2）2.2.2已知條件=9，=39，=18，=14，=7，=25；=3.0m/s, =2.0m/s；LWH=1m1m0.8m；貨格1的坐標(biāo)為（，）=(1,1)；貨格2的貨格為（，）=（1，2）；貨格3的坐標(biāo)為（，）=（2，1）；貨格4的坐標(biāo)為（，）=（2，2）；貨格5的坐標(biāo)為（，）=（3，1）；貨格6的坐標(biāo)為（，）=（3，2）。2.2.3公式計(jì)算過(guò)程1.計(jì)算： =max=max=1/3=max=max=2/5=max=max=2/3=max=max=2/3=max=max=1=max=max=12.計(jì)算系數(shù)矩陣中的系數(shù)：

9、=91/3=3, =391/3=13, =181/3=6, =141/3=14/3, =71/3=7/3， =251/3=25/3；=92/5=18/5， =392/5=78/5，=182/5=36/5， =142/5=28/5，=72/5=14/5， =252/5=10；=92/3=6， =392/3=26，=182/3=12， =142/3=28/3，=72/3=14/3， =252/3=50/3；=92/3=6， =392/3=26，=182/3=12， =142/3=28/3，=72/3=14/3， =252/3=50/3；=91=9， =391=39，=181=18， =141=14

10、，=71=7， =251=25；=91=9， =391=39，=181=18， =141=14，=71=7， =251=25；得到系數(shù)矩陣表：貨物 表2.2系數(shù)矩陣表貨格ABCDEF1313614/37/325/3218/578/536/528/514/51036261228/314/350/346261228/314/350/359391814725693918147252.3運(yùn)用匈牙利算法求解1. 匈牙利算法的步驟第一步：建等效矩陣。（1）從系數(shù)矩陣的每行元素中減去該行的最小元素。（2）再?gòu)乃孟禂?shù)矩陣的每列元素中減去該列的最小元素。第二步：找獨(dú)立0元素，進(jìn)行試指派。（1）從只有一個(gè)0元素

11、的行（或列）開(kāi)始，給這個(gè)0元素加括號(hào)（0），表示這行所代表的貨格已有一種貨物分配。然后劃去（0）所在列（或行）的其它0元素，記作“”，表示這列所代表的貨物已指派。（2）對(duì)只有一個(gè)0元素的列（或行）的0元素加括號(hào)（0），然后劃去（0）所在行（或列）的0元素，記作“”。如果在（1），（2）兩步中，遇到每一行和每一列都有兩個(gè)或兩個(gè)以上的0元素，可任選一個(gè)加括號(hào)，同時(shí)把其所在行和列的0元素都劃去。（3）重復(fù)（1），（2）兩步，直到所有0元素都被加括號(hào)或打叉。（4）加括號(hào)的0元素即為獨(dú)立0元素，若其個(gè)數(shù)m等于矩陣的階數(shù)n，則已得到問(wèn)題的最優(yōu)解。若mn，則轉(zhuǎn)入第三步。第三步：用最少的直線覆蓋所有0元素。（

12、1）對(duì)沒(méi)有獨(dú)立0元素的行打“”。（2）對(duì)以打“”的行中所含0元素的列打“”。（3）再對(duì)（2），（3），直到得不到新的打“”的行、列為止。（4）將沒(méi)有打“”的行和以打“”的列用直線覆蓋，且直線的數(shù)目一定等于獨(dú)立0元素的個(gè)數(shù)。轉(zhuǎn)第四步。第四步：增加0元素。 從沒(méi)有被直線覆蓋的元素中找出最小元素。未被覆蓋的元素都減去該最小元素，而被兩條線覆蓋的元素都加上該最小元素，其它元素不變。這樣得到新系數(shù)矩陣，轉(zhuǎn)第二步，重新確定獨(dú)立0元素。2.應(yīng)用過(guò)程(1)給系數(shù)矩陣表乘以15， 從系數(shù)矩陣的每行元素中減去該行的最小元素35、42、70、70、105、105再?gòu)乃孟禂?shù)矩陣的每列元素中減去該列的最小元素，得到等

13、效矩陣。 （2）從只有一個(gè)0元素的第2行開(kāi)始，給這個(gè)0元素加括號(hào)（0），表示這行所代表的貨格已有一種貨物分配。然后劃去（0）所在列的其它0元素，記作“”，表示這列所代表的貨物已指派。對(duì)只有一個(gè)0元素的第1列的0元素加括號(hào)（0），然后劃去（0）所在行的0元素，記作“”。獨(dú)立0元素的個(gè)數(shù)m=2矩陣的階數(shù)n=6，轉(zhuǎn)入下一步。（3）用最少的直線覆蓋所有0元素。對(duì)第3、4、5、6行打“”。對(duì)第5列打“”。得不到新的打“”的行、列，停止。將沒(méi)有打“”的行和已打“”的列用直線覆蓋，且直線的數(shù)目一定等于獨(dú)立0元素的個(gè)數(shù)。 （4）增加0元素從沒(méi)有被直線覆蓋的元素中找出最小元素2。未被覆蓋的元素都減去該最小元素，

14、而被兩條線覆蓋的元素都加上該最小元素，其它元素不變。這樣得到新系數(shù)矩陣，然后重新確定獨(dú)立0元素。 矩陣中獨(dú)立0元素的個(gè)數(shù)m=3n=6，用最少的直線覆蓋所有0元素。（5）增加0元素從未被直線覆蓋的元素中找出一個(gè)最小元素，未被覆蓋的元素都減去該最小元素，而被兩條線覆蓋的元素都加上該最小元素，其它元素不變。這樣得到新系數(shù)矩陣，然后重新確定獨(dú)立0元素。 矩陣中獨(dú)立0元素的個(gè)數(shù)m=3n=6，用最少的直線覆蓋所有0元素.（6）增加0元素從未被直線覆蓋的元素中找出一個(gè)最小元素5，未被覆蓋的元素都減去該最小元素，而被兩條線覆蓋的元素都加上該最小元素，其它元素不變。這樣得到新系數(shù)矩陣，然后重新確定獨(dú)立0元素。矩

15、陣中獨(dú)立0元素的個(gè)數(shù)m=4n=6，用最少的直線覆蓋所有0元素。（7）增加0元素從未被直線覆蓋的元素中找出一個(gè)最小元素20，未被覆蓋的元素都減去該最小元素，而被兩條線覆蓋的元素都加上該最小元素，其它元素不變。這樣得到新系數(shù)矩陣，然后重新確定獨(dú)立0元素。 矩陣中獨(dú)立0元素的個(gè)數(shù)m=4n=6，用最少的直線覆蓋所有0元素。（8）增加0元素從未被直線覆蓋的元素中找出一個(gè)最小元素4，未被覆蓋的元素都減去該最小元素，而被兩條線覆蓋的元素都加上該最小元素，其它元素不變。這樣得到新系數(shù)矩陣，然后重新確定獨(dú)立0元素。 矩陣中獨(dú)立0元素的個(gè)數(shù)m=5n=6，用最少的直線覆蓋所有0元素。（9）增加0元素從未被直線覆蓋的

16、元素中找出一個(gè)最小元素10，未被覆蓋的元素都減去該最小元素，而被兩條線覆蓋的元素都加上該最小元素，其它元素不變。這樣得到新系數(shù)矩陣，然后重新確定獨(dú)立0元素。 矩陣中獨(dú)立0元素的個(gè)數(shù)m=5n=6，用最少的直線覆蓋所有0元素。 （9）增加0元素即從未被直線覆蓋的元素中找出一個(gè)最小元素7，未被覆蓋的元素都減去該最小元素，而被兩條線覆蓋的元素都加上該最小元素，其它元素不變。這樣得到新系數(shù)矩陣，然后重新確定獨(dú)立0元素。 矩陣中獨(dú)立0元素的個(gè)數(shù)m=5n=6，用最少的直線覆蓋所有0元素。 (10）增加0元素從未被直線覆蓋的元素中找出一個(gè)最小元素16，未被覆蓋的元素都減去該最小元素，而被兩條線覆蓋的元素都加上

17、該最小元素，其它元素不變。這樣得到新系數(shù)矩陣，然后重新確定獨(dú)立0元素。 m=n=6,所以可以得到優(yōu)化方案，將矩陣中的非0元素變?yōu)?，將獨(dú)立0元素變?yōu)?. 由解可得最優(yōu)分配方案：A貨物放5貨格，B貨物放1貨格，C貨物放4貨格，D貨物放3貨格，E貨物放6貨格，F(xiàn)貨物放2貨格。可以將得出的最優(yōu)分配方案繪制成圖2.2所示：Vy2貨物F4貨物C6貨物E1貨物B3貨物D5貨物A圖2.2貨物安放規(guī)劃圖0Vx2.4總結(jié)面對(duì)成千上萬(wàn)的貨格，立體倉(cāng)庫(kù)的貨位存儲(chǔ)優(yōu)化已成為提高存取效率、降低成本的關(guān)鍵，這需要對(duì)不同貨物在倉(cāng)庫(kù)中的存放位置進(jìn)行合理分配，這可通過(guò)利用匈牙利算法來(lái)達(dá)到此目的。通過(guò)匈牙利算法得到的貨位分配，可

18、以對(duì)倉(cāng)庫(kù)中的貨物儲(chǔ)位進(jìn)行進(jìn)行整合，使得貨物的在貨格中的存放位置最優(yōu)、取放路徑最優(yōu)，從而達(dá)到進(jìn)貨和出貨時(shí)既經(jīng)濟(jì)又省時(shí)，同時(shí)可使物品的破損率達(dá)到最低，這對(duì)于提高企業(yè)的品牌起重要作用。通過(guò)這次課程設(shè)計(jì)我也認(rèn)識(shí)到了貨位優(yōu)化對(duì)于一個(gè)倉(cāng)庫(kù)的重要性，這次學(xué)習(xí)使得我也學(xué)習(xí)到了很多的物流知識(shí)，對(duì)于老師講解過(guò)程中的關(guān)于自動(dòng)化立體倉(cāng)庫(kù)的一些問(wèn)題也得到了充分理解，這次的課程設(shè)計(jì)過(guò)程中也讓我學(xué)到很多，以及在設(shè)計(jì)過(guò)程中我們應(yīng)該要認(rèn)真的積極態(tài)度，以及在整理課題任務(wù)時(shí)要仔細(xì)，只有這樣才能保證我們?cè)谧鍪虑榈倪^(guò)程中會(huì)減少誤差。3堆垛機(jī)路徑優(yōu)化最短路徑問(wèn)題是圖論中的一個(gè)經(jīng)典問(wèn)題。由于問(wèn)題中邊的權(quán)值往往可以從距離引申為其他沿路徑線性

19、積累的度量，如：時(shí)間、花費(fèi)等，所以最短路徑問(wèn)題在實(shí)際生活中有著廣泛的應(yīng)用。分層思想作為一個(gè)重要的思想，也有著許多應(yīng)用，特別在是某些高效的方法中，如：動(dòng)態(tài)規(guī)劃中的階段劃分、圖論中基于求阻塞流的最大流算法等。將分層思想應(yīng)用到最短路徑問(wèn)題中，正是分層思想和最短路徑問(wèn)題的強(qiáng)強(qiáng)聯(lián)合。因此正是基于此問(wèn)題，將最短路路徑用于堆垛機(jī)的路徑優(yōu)化，以下便用最近鄰點(diǎn)法和插入法進(jìn)行堆垛機(jī)的路徑優(yōu)化。 3.1 設(shè)計(jì)條件Vy4 (G)8 (K)12 (T)16 (N)20 (Q)3 (D)7 (J)11 (H)15 (E)19 (S)2 (B)6 (F)10 (I)14 (V)18 (R)01 (A)5 (C)9 (M)1

20、3 (P)17 (L)Vx圖3.1 最終的貨位規(guī)劃圖隨機(jī)從圖3.1中的20個(gè)貨格中抽出10個(gè)貨格的貨物，分別用節(jié)點(diǎn)V，V，V，V，V，V，V，V，V，V表示。節(jié)點(diǎn)間的距離用直角距離公式: 式(3.1）。3.2設(shè)計(jì)要求（1）繪出貨格和節(jié)點(diǎn)相對(duì)位置圖及節(jié)點(diǎn)相對(duì)距離表（需先列式計(jì)算各的值）；（2）詳細(xì)地寫(xiě)出最近鄰點(diǎn)法和最近插入法的每一步驟及計(jì)算結(jié)果。（3）分析兩種方法的結(jié)果。（4）設(shè)計(jì)結(jié)束后，談?wù)勛约旱目捶ā?3.3設(shè)計(jì)方法分別用最近鄰點(diǎn)法和最近插入法找出堆垛機(jī)存取10個(gè)托盤(pán)貨物的合理路線。在堆垛機(jī)開(kāi)始揀選之前，由于設(shè)備及系統(tǒng)根據(jù)實(shí)際情況每臺(tái)堆垛機(jī)分配一定數(shù)量的貨位，被分配的貨位用陰影的小方格表示，

21、圖中的實(shí)心小黑點(diǎn)表示堆垛機(jī)從貨架上取貨時(shí)，需要在倉(cāng)庫(kù)中停留的位置點(diǎn)，可以選用的方法的有最近零點(diǎn)法、最近插入發(fā)和遺傳算法等。3.4求解過(guò)程首先根據(jù)設(shè)計(jì)要求，繪出貨格和節(jié)點(diǎn)相對(duì)位置圖如圖3.2、3.3所示：Vy4 (G)8 (K)12 (T)16 (N)20 (Q)3 (D)7 (J)11 (H)15 (E)19 (S)2 (B)6 (F)10 (I)14 (V)18 (R)1 (A)5 (C)9 (M)13 (P)17 (L)Vxo圖3.2 貨格的相對(duì)位置圖V10V9V8V7V6V5V4V3V2V1 圖3.3 節(jié)點(diǎn)的相對(duì)位置引用d=|x-x|L+|y-y|H 式(3.1）計(jì)算節(jié)點(diǎn)間距離dv1v2

22、=|xv2-xv1|L+|yv2-yv1|H=|1-1|1+|3-1|0.8=0.8 dv1v3=|xv3-xv1|L+|yv3-yv1|H=|2-1|1+|1-1|0.8=1.8dv1v4=|xv4-xv1|L+|yv4-yv1|H=|2-1|1+|4-1|0.8=3.4dv1v5=|xv5-xv1|L+|yv5-yv1|H=|3-1|1+|2-1|0.8=2.8dv1v6=|xv6-xv1|L+|yv6-yv1|H=|3-1|1+|4-1|0.8=3.6dv1v7=|xv7-xv1|L+|yv7-yv1|H=|4-1|1+|2-1|0.8=3dv1v8=|xv8-xv1|L+|yv8-yv

23、1|H=|4-1|1+|3-1|0.8=4.6 dv1v9=|xv9-xv1|L+|yv9-yv1|H=|5-1|1+|1-1|0.8=4 dv1v10=|xv10-xv1|L+|yv10-yv1|H=|5-1|1+|3-1|0.8=5.6dv2v3=|xv3-xv2|L+|yv3-yv2|H=|2-1|1+|1-3|0.8=1dv2v4=|xv4-xv2|L+|yv4-yv2|H=|2-1|1+|4-3|0.8=2.6dv2v5=|xv5-xv2|L+|yv5-yv2|H=|3-1|1+|2-3|0.8=2dv2v6=|xv6-xv2|L+|yv6-yv2|H=|3-1|1+|4-3|0.8

24、=2.8dv2v7=|xv7-xv2|L+|yv7-yv2|H=|4-1|1+|2-3|0.8=3.8 dv2v8=|xv8-xv2|L+|yv8-yv2|H=|4-1|1+|3-3|0.8=3.8dv2v9=|xv9-xv2|L+|yv9-yv2|H=|5-1|1+|1-3|0.8=4.8dv2v10=|xv10-xv2|L+|yv10-yv2|H=|5-1|1+|3-3|0.8=4.8dv3v4=|xv4-xv3|L+|yv4-yv3|H=|2-2|1+|4-1|0.8=1.6dv3v5=|xv5-xv3|L+|yv5-yv3|H=|3-2|1+|2-1|0.8=1dv3v6=|xv6-x

25、v3|L+|yv6-yv3|H=|3-2|1+|4-1|0.8=1.8dv3v7=|xv7-xv3|L+|yv7-yv3|H=|4-2|1+|2-1|0.8=2.8dv3v8=|xv8-xv3|L+|yv8-yv3|H=|4-2|1+|3-1|0.8=2.8 dv3v9=|xv9-xv3|L+|yv9-yv3|H=|5-2|1+|1-1|0.8=3.8dv3v10=|xv10-xv3|L+|yv10-yv3|H=|5-2|1+|3-1|0.8=3.8 dv4v5=|xv5-xv4|L+|yv5-yv4|H=|3-2|1+|2-4|0.8=2.6 dv4v6=|xv6-xv4|L+|yv6-yv

26、4|H=|3-2|1+|4-4|0.8=1.8 dv4v7=|xv7-xv4|L+|yv7-yv4|H=|4-2|1+|2-4|0.8=4.4 dv4v8=|xv8-xv4|L+|yv8-yv4|H=|4-2|1+|3-4|0.8=2.8 dv4v9=|xv9-xv4|L+|yv9-yv4|H=|5-2|1+|1-4|0.8=5.4 dv4v10=|xv10-xv4|L+|yv10-yv4|H=|5-2|1+|3-4|0.8=3.8 dv5v6=|xv6-xv5|L+|yv6-yv5|H=|3-3|1+|4-2|0.8=0.8 dv5v7=|xv7-xv5|L+|yv7-yv5|H=|4-3|

27、1+|2-2|0.8=1.8 dv5v8=|xv8-xv5|L+|yv8-yv5|H=|4-3|1+|3-2|0.8=1.8 dv5v9=|xv9-xv5|L+|yv9-yv5|H=|5-3|1+|1-2|0.8=2.8 dv5v10=|xv10-xv5|L+|yv10-yv5|H=|5-3|1+|3-2|0.8=2.8 dv6v7=|xv7-xv6|L+|yv7-yv6|H=|4-3|1+|2-4|0.8=2.6 dv6v8=|xv8-xv6|L+|yv8-yv6|H=|4-3|1+|3-4|0.8=1 dv6v9=|xv9-xv6|L+|yv9-yv6|H=|5-3|1+|1-4|0.8=

28、3.6 dv6v10=|xv10-xv6|L+|yv10-yv6|H=|5-3|1+|3-4|0.8=2 dv7v8=|xv8-xv7|L+|yv8-yv7|H=|4-4|1+|3-2|0.8=1.6 dv7v9=|xv9-xv7|L+|yv9-yv7|H=|5-4|1+|1-2|0.8=1 dv7v10=|xv10-xv7|L+|yv10-yv7|H=|5-4|1+|3-2|0.8=2.6 dv8v9=|xv9-xv8|L+|yv9-yv8|H=|5-4|1+|1-3|0.8=2.6 dv8v10=|xv10-xv8|L+|yv10-yv8|H=|5-4|1+|3-3|0.8=1 dv9v1

29、0=|xv10-xv9|L+|yv10-yv9|H=|5-5|1+|3-1|0.8=1.6根據(jù)兩節(jié)點(diǎn)的相對(duì)距離繪制節(jié)點(diǎn)相對(duì)距離表3.1：表3.1 節(jié)點(diǎn)相對(duì)距離表節(jié)點(diǎn)VVVVVVVVVVV0.81.83.42.83.634.645.6V12.622.83.83.84.84.8V1.611.82.82.83.83.8V2.61.84.42.85.43.8V0.81.81.82.82.8V2.613.62V1.612.6V2.61V1.6V3.4.1最近鄰點(diǎn)法求堆垛機(jī)運(yùn)行路徑1 最近鄰點(diǎn)法1.1 最近鄰點(diǎn)法的思路（1） 從零點(diǎn)開(kāi)始，作為整個(gè)回路的起點(diǎn)。（2） 找到離剛剛加入到回路的頂點(diǎn)最近的一個(gè)頂點(diǎn)

30、，并將其加入到回路中。（3） 重復(fù)步驟（2），直到所有頂點(diǎn)都加入到回路中。（4） 最后，將最后一個(gè)加入的頂點(diǎn)和起點(diǎn)連接起來(lái)。1.2 應(yīng)用過(guò)程V1（1）先將節(jié)點(diǎn)v1加入到回路中，T=v1。圖3.4 加入節(jié)點(diǎn)v（2） 從節(jié)點(diǎn)v1出發(fā)，在節(jié)點(diǎn)2、3、4、5、6、7、8、9、10中，找出離v1 最近的節(jié)點(diǎn)。Min 因此將節(jié)點(diǎn)v2加入到回路中，T1=v1,v2。V10V9V8V7V6V5V4V3V2V1圖 3.5 運(yùn)行路線（3）從節(jié)點(diǎn)v2出發(fā)，在節(jié)點(diǎn)3、4、5、6、7、8、9、10中，找出離v2最近的節(jié)點(diǎn)。Min因此就可以將v3加入到回路中，T2=v1,v2,v3。V10V9V8V7V6V5V4V3V2

31、V1圖 3.6 運(yùn)行路線（4）從節(jié)點(diǎn)v3出發(fā)，在節(jié)點(diǎn)4、5、6、7、8、9、10中，找出離v3最近的節(jié)點(diǎn)。Min因此就可以將v5加入到回路中，T3=v1,v2,v3,v5V10V9V8V7V6V5V4V3V2V1圖 3.7 運(yùn)行路線（5）從節(jié)點(diǎn)v5出發(fā)，在節(jié)點(diǎn)4、6、7、8、9、10中，找出離v5最近的節(jié)點(diǎn)。Min因此就可以將v6加入到回路中，T4=v1,v2,v3,v5,v6V10V9V8V7V6V5V4V3V2V1圖 3.8 運(yùn)行路線（6） 從節(jié)點(diǎn)v6出發(fā)，在節(jié)點(diǎn)4、7、8、9、10中，找出離v6最近的節(jié)點(diǎn)。Min因此就可以將v8加入到回路中，T5=v1,v2,v3,v5,v6,v8V10

32、V9V8V7V6V5V4V3V2V1圖 3.9 運(yùn)行路線（7） 從節(jié)點(diǎn)v8出發(fā)，在節(jié)點(diǎn)4、7、9、10中，找出離v8最近的節(jié)點(diǎn)。Min因此就可以將v10加入到回路中，T6=v1,v2,v3,v5,v6，v8，v10V10V9V8V7V6V5V4V3V2V1圖 3.10 運(yùn)行路線(8)從節(jié)點(diǎn)v10出發(fā)，在節(jié)點(diǎn)4、7、9中，找出離v10最近的節(jié)點(diǎn)。Min因此就可以將v9加入到回路中，T7=v1,v2,v3,v5,v6,v8，v10,v9形成如圖3.11所示的運(yùn)行路線V10V9V8V7V6V5V4V3V2V1圖 3.11 運(yùn)行路線(9)從節(jié)點(diǎn)v9出發(fā)，在節(jié)點(diǎn)4、7中，找出離v9最近的節(jié)點(diǎn)。Min因此

33、就可以將v7加入到回路中，T8=v1,v2,v3,v5,v6,v8，v10,v9,v7形成如圖3.12所示的運(yùn)行路線V10V9V8V7V6V5V4V3V2V1圖 3.12 運(yùn)行路線(10)將最后的點(diǎn)v4, ,v1連接起來(lái)得到最后的運(yùn)行路線圖,T9=v1,v2,v3,v5,v6,v8，v10,v9,v7 ,v4,v1V10V9V8V7V6V5V4V3V2V1圖 3.13 最終運(yùn)行線路圖所以堆垛機(jī)運(yùn)行路線為：1261011151917138即取送貨物次序?yàn)椋篈BFIHESLPK堆垛機(jī)總行駛距離為：Z=0.8+1+1+0.8+1+1+1.6+1+4.4+3.4=163.4.2最近插入法求堆垛機(jī)運(yùn)行路

34、徑2 最近插入法2.1 最近插入法的思路（1）先將節(jié)點(diǎn)v1加入到回路中，找到d1k最小的節(jié)點(diǎn)vk ，形成一個(gè)子回路，T=v1 ,vk ,v1。（2）在剩下的節(jié)點(diǎn)中，尋找一個(gè)離子回路中某一節(jié)點(diǎn)最近的節(jié)點(diǎn)vk 。（3）在子回路中找到一條?。╥,j）,使得里程增量最小。如果有多條滿(mǎn)足條件，任選一條，然后將節(jié)點(diǎn)vk插入到節(jié)點(diǎn)vi和vj之間，用兩條新的?。╥,k）和（k,j）代替原來(lái)的?。╥,j）,并將節(jié)點(diǎn)vk加入到子回路中。（4）重復(fù)步驟（2）和（3），直到所有的節(jié)點(diǎn)都加入到子回路中。2.2 應(yīng)用過(guò)程（1）比較貨格相對(duì)距離表中從v1出發(fā)的所有路徑的大小Min這樣就由節(jié)點(diǎn)v1和v2構(gòu)成的子回路，T=v1

35、,v2,v1V10V9V8V7V6V5V4V3V2V1圖3.14 由v1和v2構(gòu)成的子回路（2）然后考慮剩下的節(jié)點(diǎn)、 ，到和中某一個(gè)節(jié)點(diǎn)的最小距離；Min由于對(duì)稱(chēng)性，無(wú)論將3插入到1和2之間往返路徑中，結(jié)果都是一樣的，任選其一,這樣構(gòu)成一個(gè)新的子回路T=v1,v2, v3,v1V10V8V7V6V5V4V3V2V1V9圖3.15 由v1,v2和v3構(gòu)成的子回路（3）接著考慮剩下的節(jié)點(diǎn)、 ，到、和中 某一個(gè)節(jié)點(diǎn)的最小距離； Min（4）由圖3.15可知，節(jié)點(diǎn)有3個(gè)位置（條弧線）可以插入。現(xiàn)在分析將加入到哪里合適：插入到（1,2）間，=d15+d52-d12=2.8+2-0.8=4插入到（2,3）

36、間，= d25+d53-d23=2+1-1=2插入到（3,1）間，= d35+d51-d31=1+2.8-1.8=2比較上面3種情況增量，插入（2,3）或（3,1）之間的增量最小，任選其 一，將節(jié)點(diǎn)加入到（2,3），所以結(jié)果為：T=v1,v2,v5 v3，v1其子回路V10V9V8V7V6V5V4V3V2V1圖3.16 由v1,v2,v3和v5構(gòu)成的字回路（5）接著考慮剩下的節(jié)點(diǎn)、 ，到、和中某一節(jié)點(diǎn)的最小距離；Min（6）由圖3.16可知，節(jié)點(diǎn)有4個(gè)位置（條弧線）可以插入?，F(xiàn)在分析將加入到哪里合適：插入到（1,2）間，= d16+d-d12=3.6+2.8-0.8=5.6插入到（2,5）間，

37、= d+d-d=2.8+0.8-2=1.6插入到（3,5）間，= d+d-d=1.8+0.8-1=1.6插入到（3,1）間，= d+d-d=1.8+3.6-1.8=3.6比較上面4種情況增量，將插入（2,5）或（3,5）之間的增量最小，任選其一，將v5插入（2,5）之間，則結(jié)果為：T= v1,v2,v,v，v，v1其子回路則變?yōu)槿鐖D3.17所示：V10V9V8V7V6V5V4V3V2V1圖3.17 由v1,v2,v,v，v構(gòu)成的子回路(7) 接著考慮剩下的節(jié)點(diǎn)、 ，到、中某一節(jié)點(diǎn)的最小距離Min（8）由圖3.17可知，節(jié)點(diǎn)有5個(gè)位置（條弧線）可以插入。現(xiàn)在分析將加入到哪里合適：插入到（1,2）

38、間，= d18+d-d12=4.6+3.8-0.8=7.6插入到（2,6）間，= d+d-d=3.8+1-2.8=2插入到（6,5）間，= d+d-d=1+1.8-0.8=2插入到（5,3）間，= d+d-d=1.8+2.8-1=3.6插入到（3,1）間，= d+d-d=2.8+4.6-1.8=5.6比較上面5種情況增量，可將插入（6,5）或（2,6）之間的增量最小，任選其一，若將插入（6,5）之間，則結(jié)果為：T=、其子回路則變?yōu)閳D3.18所示：V10V9V8V7V6V5V4V3V2V1圖3.18 由、構(gòu)成的子回路（9）接著剩下的節(jié)點(diǎn)、，到、中某一節(jié)點(diǎn)的最小距離Min（10）由圖3.18可知有

39、6個(gè)位置（條弧線）可以插入?，F(xiàn)在分析將加入到哪里合適： 插入到（1,2）間，= d+d-d12=5.6+4.8-0.8=9.6插入到（2,6）間，= d+d-d=4.8+2-2.8=4插入到（6,8）間，= d+d-d=2+1-1=2插入到（8,5）間，= d+d-d=1+2.8-1.8=2插入到（5,3）間，= d+d-d=2.8+3.8-1=5.6插入到（3,1）間，= d+d-d=3.8+5.6-1.8=7.6比較上面6種情況增量，插入到（6,8）或（8,5）之間的增量最小，任選其一，所以將節(jié)點(diǎn)加入到（8,5）間，結(jié)果為：T=、其子回路則變?yōu)閳D3.19所示：V10V9V8V7V6V5V4

40、V3V2V1圖3.19 、構(gòu)成的子回路 （11）接著考慮剩下的節(jié)點(diǎn)、到、中某一節(jié)點(diǎn)的最小距離；Min（12）由圖3.19可知有7個(gè)位置（條弧線）可以插入?，F(xiàn)在分析將加入到哪里合適： 插入到（1,2）間，= d+d-d12=3.4+2.6-0.8=5.2插入到（2,6）間，= d+d-d=2.6+1.8-2.8=1.6插入到（6,8）間，= d+d-d=1.8+2.8-1=3.6插入到（8,10）間，= d+d-d=2.8+3.8-1=5.6插入到（10，5）間，= d+d-d=3.8+2.6-2.8=3.6插入到（5,3）間，= d+d-d=2.6+1.6-1=3.2插入到(3，1)間，= d

41、+d-d=1.6+3.4-1.8=3.2比較上面7種情況增量，插入到（2,6）之間的增量最小，所以將節(jié)點(diǎn)加入到（2,6）間，結(jié)果為：T=、其子回路則變圖3.20所示：V10V9V8V7V6V5V4V3V2V1圖3.20 、構(gòu)成的子回路（13）接著考慮剩下的節(jié)點(diǎn)、到、中某一節(jié)點(diǎn)的最小距離；Min（14）由圖3.20可知有8個(gè)位置（條弧線）可以插入?，F(xiàn)在分析將加入到哪里合適： 插入到（1,2）間，= d+d-d12=4+4.8-0.8=8插入到（2,4）間，= d+d-d=4.8+5.4-2.6=7.6插入到（4,6）間，= d+d-d=5.4+3.6-1.8=7.2插入到（6,8）間，= d+d

42、-d=3.6+2.6-1=5.2插入到（8，10）間，= d+d-d=1+1.6-1=1.6插入到（10,5）間，= d+d-d=1.6+2.8-2.8=1.6插入到(5，3)間，= d+d-d=2.8+3.8-1=5.6插入到(3，1)間，= d+d-d=3.8+4-1.8=6比較上面8種情況增量，插入到（8,10）和（10,5）之間的增量最小，任選其一，所以將節(jié)點(diǎn)加入到（10，5）間，結(jié)果為：T=、其子回路如圖3.21所示：V10V9V8V7V6V5V4V3V2V1圖3.21 、構(gòu)成的子回路（15）最后考慮剩下的節(jié)點(diǎn)到、中某一節(jié)點(diǎn)的最小距離；Min（16）有9個(gè)位置（條弧線）可以插入?，F(xiàn)在分析將加入到哪里合適： 插入到（1,2）間，= d+d-d12=3+3.8-0.8=6插入到（2,4）