自動化立體倉庫系統(tǒng)課程設計

1、目錄TOC o 1-4 h z u HYPERLINK l _Toc297814593 引言 PAGEREF _Toc297814593 h 1 HYPERLINK l _Toc297814594 1自動化立體倉倉庫 PAGEREF _Toc297814594 h 2 HYPERLINK l _Toc297814595 1.1概述 PAGEREF _Toc297814595 h 22 HYPERLINK l _Toc297814599 2貨位優(yōu)化33 HYPERLINK l _Toc297814600 2.1設計條件件3 HYPERLINK l _Toc297814601 2.2計算系數數矩陣

2、3 HYPERLINK l _Toc297814602 2.2.11符號假設3 HYPERLINK l _Toc297814603 2.2.22已知條件4 HYPERLINK l _Toc297814604 2.2.33公式計算過過程4 HYPERLINK l _Toc297814605 2.3運用匈牙牙利算法求解解6 HYPERLINK l _Toc297814608 2.4總結113 HYPERLINK l _Toc297814609 3堆垛機路徑優(yōu)優(yōu)化15 HYPERLINK l _Toc297814610 3.1 設計計條件15 HYPERLINK l _Toc297814611 3.

3、2設計要求求16 HYPERLINK l _Toc297814612 3.3設計方法法16 HYPERLINK l _Toc297814613 3.4求解過程程16 HYPERLINK l _Toc297814614 3.4.11最近鄰點法法求堆垛機運運行路徑19 HYPERLINK l _Toc297814615 3.4.22最近插入法法求堆垛機運運行路徑26 HYPERLINK l _Toc297814616 3.5 總結34 HYPERLINK l _Toc297814617 參考文獻366 HYPERLINK l _Toc297814619 引言自動化立體倉庫庫產生和發(fā)展展是生產力高高

4、度發(fā)展和城城市化進程不不斷發(fā)展結果果。計算機的的出現和應用用，自動化倉倉庫的產生。倉倉庫空間向立立體化方向發(fā)發(fā)展個，貨位位向空間延伸伸，高層貨架架和與之配套套的新型裝卸卸搬運機械與與周邊設備出出現，立體倉倉庫產生。自動化立體倉庫庫是指在高層層貨架用貨箱箱或托盤儲存存貨物，用電電子計算機管管理和控制巷巷道式堆垛機機及其它機械械，不需要人人工作業(yè)而實實現收發(fā)作業(yè)業(yè)的倉庫。自動化立體倉庫庫是一種集信信息、儲存、管管理于一體的的高技術密集集型機電化產產品，堆垛機機和高層貨架架是其關鍵設設備。隨著電電子技術與控控制理論的發(fā)發(fā)展，各種控控制方法被引引入堆垛機的的控制。貨位位優(yōu)化和巷道道式堆垛機的的路徑優(yōu)化

5、成成為自動化立立體倉庫的必必要工作，因因此本次課程程設計針對這這兩點做出了了詳細的介紹紹。貨位優(yōu)化是用來來確定每一品品規(guī)的恰當儲儲存方式，在在恰當的儲存存方式下的空空間儲位分配配。貨位優(yōu)化化追求不同設設備和貨架類類型特征、貨貨品分組、貨貨位規(guī)劃、人人工成本內置置等因素以實實現最佳的 HYPERLINK /view/727829.htm 貨貨位布局，能能有效掌握商商品變化，將將成本節(jié)約最最大化。貨位優(yōu)化為正在在營運的倉庫庫挖掘效率和和成本，并為為一個建設中中的 HYPERLINK /view/397401.htm 配送中心心或倉庫提供供營運前的關關鍵管理作準準備。1自動化立體倉倉庫1.1概述自動

6、化立體倉庫庫作為 HYPERLINK /dangdai/ 現代化物流系系統(tǒng)中的重要要組成部分,是一種多層層存放貨物的的高架倉庫系系統(tǒng),主要由由高層貨架、巷巷道堆垛機、出出入庫輸送設設備、自動控控制與管理系系統(tǒng)所組成。出出入庫輔助設設備及巷道堆堆垛機能夠在在 HYPERLINK /pc/ 計算機管理下下，完成貨物物的出入庫作作業(yè)、實施綜綜合庫房管理理并與上級管管理系統(tǒng)聯網網，可以實現現管理現代化化、存取自動動化，能按指指令自動完成成貨物的存取取作業(yè),并能能對庫存的貨貨物進行自動動化管理,是是企業(yè)實現現現代化管理的的重要手段。自自動立體倉庫庫在工廠自動動化，彈性制制造系統(tǒng)及電電腦整合制造造系統(tǒng)的物

7、流流中占非常重重要的位置。其其目的不僅是是為了儲存物物料、零件、半半成品、成品品的倉儲，更更是密切配合合制造工廠的的產銷計劃與與物料需求計計劃，妥善安安排生產所需需合理數量的的物料、零件件，并盡量縮縮短其庫存時時間及避免了了發(fā)生缺料、滯滯料，籍高架架搬運車、輸輸送機、無人人搬運車等，然然后保管成品品而依銷售預預定準進正確確出貨，提升升服務水平，事事合了計劃、庫庫存、生產、出出入物流的功功能與管理，降降低了生產成成本。 其組成部分：（1） HYPERLINK /view/167019.htm 貨架:用用于存儲貨物物的鋼結構。主主要有焊接式式貨架和組合合式貨架兩種種基本形式。（2）托盤（貨貨箱）：

8、用于于承載貨物的的器具，亦稱稱工位器具。（3）巷道堆垛垛機:用于自自動存取貨物物的設備。按按結構形式分分為單立柱和和雙立柱兩種種基本形式；按服務方式式分為直道、彎彎道和轉移車車三種基本形形式。（4）輸送機系系統(tǒng):立體庫庫的主要外圍圍設備，負責責將貨物運送送到堆垛機或或從堆垛機將將貨物移走。輸輸送機種類非非常多，常見見的有輥道輸輸送機，鏈條條輸送機，升升降臺，分配配車，提升機機，皮帶機等等。（5）AGV系系統(tǒng):即自動動導向小車。根根據其導向方方式分為感應應式導向小車車和激光導向向小車。（6）自動控制制系統(tǒng):驅動動自動化立體體庫系統(tǒng)各設設備的自動控控制系統(tǒng)。以以采用現場總總線方式為控控制模式為主主

9、。（7）儲存 HYPERLINK /view/45136.htm 信息息管理系統(tǒng):亦稱中央計計算機管理系系統(tǒng)。是全自自動化立體庫庫系統(tǒng)的核心心。典型的自自動化立體庫庫系統(tǒng)均采用用大型的 HYPERLINK /view/7809.htm 數據據庫系統(tǒng)（如如ORACLLE，SYBBASE等）構構筑典型的客客戶機/服務務器體系，可可以與其他系系統(tǒng)（如 HYPERLINK /view/86915.htm ERRP系統(tǒng)等）聯聯網或集成。 2.貨位優(yōu)化 2.1設計條件件某自動化立體倉倉庫采用2行行3列的單元元貨格式貨架架存放貨物，一一共有6個貨貨格，每個貨貨格存放一個個托盤貨物。貨貨格以按列編編碼的形式進

10、進行編號，如如圖2.1所示。已已知其它參數數假定如下：假設堆垛機機在水平方向向的行駛速度度Vx=3.0m/s，在在垂直方向的的行駛速度VVy=2m/s；貨貨格大小為LL（長）W（寬）H（高）=1m1m0.8m；堆堆垛機初始狀狀態(tài)在原點00處；貨格jj的橫坐標和和縱坐標就是是其所在的列列和行，如貨貨格6的坐標標為（3，22）。現有66個托盤貨物物需要存放到到貨架上，貨貨物的出入庫庫頻率如表22.1所示。VyVy24613500Vx圖2.1原始貨貨格圖Vx表2.1 托盤盤貨物出入庫庫頻率表貨物頻率貨物頻率貨物頻率A9C18E7B39D14F25根據以上條件，利利用匈牙利算算法合理安排排各托盤貨物物

11、的存放位置置。2.2計算系數數矩陣2.2.1符號號假設1.為第i種貨貨物的出入庫庫頻率（次數數），i=A，B，CC，D，E，FF；2，分別為貨貨格j的橫坐坐標和縱坐標標，即貨格jj所在的列和和行（距離巷巷道口最近的的列記為第11列，最底層層記為第1層層），j=11，2，3，44，5，6；3為水平方向向的行駛速度度；4.為垂直方向向的行駛速度度；5.L為貨格的的長；6.W為貨格的的寬；7.H為貨格的的高；8.為堆垛機運運行之貨格jj所用時間，該時間是堆垛機行進過程中水平方向和垂直方向所用時間的最大值，j=1，2，3，4，5，6；9. 為堆垛機機將貨物i向向貨格j存取取時所花費的的時間。10. 公

12、公式為=maax （2.1）11. 計算系系數矩陣中的的系數： = （22.2）2.2.2已知知條件=9，=39，=18，=14，=7，=25；=3.0m/ss, =2.0m/ss；LWH=1m1m0.8m；貨格1的坐標為為（，）=(1,1)；貨格格2的貨格為為（，）=（1，22）；貨格33的坐標為（，）=（2，1）；貨格4的坐標為（，）=（2，2）；貨格5的坐標為（，）=（3，1）；貨格6的坐標為（，）=（3，2）。2.2.3公式式計算過程1.計算： =max=maax=1/3=max=maax=2/5=max=maax=2/3=max=maax=2/3=max=maax=1=max=maa

13、x=12.計算系數矩矩陣中的系數數： =91/33=3, =391/3=113, =181/3=6, =141/3=114/3, =71/33=7/3， =251/3=25/3；=92/55=18/55， =392/5=778/5，=182/5=36/5， =142/5=228/5，=72/55=14/55， =252/5=110；=92/33=6， =392/3=226，=182/3=12， =142/3=28/3，=72/33=14/33， =252/3=550/3；=92/33=6， =392/3=226，=182/3=12， =142/3=28/3，=72/33=14/33， =252

14、/3=550/3；=91=99， =391=39，=181=18， =141=14，=71=77， =251=25；=91=99， =391=39，=181=18， =141=14，=71=77， =251=25；得到系數矩陣表表：貨物 表2.2系數矩矩陣表貨物貨格貨格ABCDEF1313614/37/325/3218/578/536/528/514/51036261228/314/350/346261228/314/350/359391814725693918147252.3運用匈牙牙利算法求解解1. 匈牙利算算法的步驟第一步：建等效效矩陣。（1）從系數矩矩陣的每行元元素中減去該該行的最小元

15、元素。（2）再從所得得系數矩陣的的每列元素中中減去該列的的最小元素。第二步：找獨立立0元素，進進行試指派。（1）從只有一一個0元素的的行（或列）開開始，給這個個0元素加括括號（0），表表示這行所代代表的貨格已已有一種貨物物分配。然后后劃去（0）所所在列（或行行）的其它00元素，記作作“”，表示這列列所代表的貨貨物已指派。（2）對只有一一個0元素的的列（或行）的的0元素加括括號（0），然然后劃去（00）所在行（或或列）的0元元素，記作“”。如果在（1），（22）兩步中，遇遇到每一行和和每一列都有有兩個或兩個個以上的0元元素，可任選選一個加括號號，同時把其其所在行和列列的0元素都都劃去。（3）重復

16、（11），（2）兩兩步，直到所所有0元素都都被加括號或或打叉。（4）加括號的的0元素即為為獨立0元素素，若其個數數m等于矩陣陣的階數n，則則已得到問題題的最優(yōu)解。若若mn，則則轉入第三步步。第三步：用最少少的直線覆蓋蓋所有0元素素。（1）對沒有獨獨立0元素的的行打“”。（2）對以打“”的行中所所含0元素的的列打“”。（3）再對（22），（3），直直到得不到新新的打“”的行、列列為止。（4）將沒有打打“”的行和和以打“”的列用用直線覆蓋，且且直線的數目目一定等于獨獨立0元素的的個數。轉第第四步。第四步：增加00元素。 從沒有被直線線覆蓋的元素素中找出最小小元素。未被被覆蓋的元素素都減去該最最小元

17、素，而而被兩條線覆覆蓋的元素都都加上該最小小元素，其它它元素不變。這這樣得到新系系數矩陣，轉轉第二步，重重新確定獨立立0元素。2.應用過程(1)給系數矩矩陣表乘以115， 從系數矩陣陣的每行元素素中減去該行行的最小元素素35、422、70、770、1055、105再從所得系系數矩陣的每每列元素中減減去該列的最最小元素，得得到等效矩陣陣。 （2）從只有有一個0元素素的第2行開開始，給這個個0元素加括括號（0），表表示這行所代代表的貨格已已有一種貨物物分配。然后后劃去（0）所所在列的其它它0元素，記記作“”，表示這列列所代表的貨貨物已指派。對只有一個0元素的第1列的0元素加括號（0），然后劃去（0

18、）所在行的0元素，記作“”。獨立0元素的個個數m=2矩陣的階數數n=6，轉轉入下一步。（3）用最少的的直線覆蓋所所有0元素。對第3、4、55、6行打“”。對第5列打“”。得不到新的打打“”的行、列，停停止。將沒有打“”的行和已打打“”的列用直線線覆蓋，且直直線的數目一一定等于獨立立0元素的個個數。 （4）增加0元元素從沒有被直線線覆蓋的元素素中找出最小小元素2。未未被覆蓋的元元素都減去該該最小元素，而而被兩條線覆覆蓋的元素都都加上該最小小元素，其它它元素不變。這這樣得到新系系數矩陣，然然后重新確定定獨立0元素素。 矩陣中獨立00元素的個數數m=3nn=6，用最最少的直線覆覆蓋所有0元元素。（5

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

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

21、少少的直線覆蓋蓋所有0元素素。（9）增加0元元素從未被直線覆覆蓋的元素中中找出一個最最小元素100，未被覆蓋蓋的元素都減減去該最小元元素，而被兩兩條線覆蓋的的元素都加上上該最小元素素，其它元素素不變。這樣樣得到新系數數矩陣，然后后重新確定獨獨立0元素。 矩陣中獨立00元素的個數數m=5nn=6，用最最少的直線覆覆蓋所有0元元素。 （9）增加0元元素即從未被直線線覆蓋的元素素中找出一個個最小元素77，未被覆蓋蓋的元素都減減去該最小元元素，而被兩兩條線覆蓋的的元素都加上上該最小元素素，其它元素素不變。這樣樣得到新系數數矩陣，然后后重新確定獨獨立0元素。 矩陣中獨立00元素的個數數m=5nn=6，用

22、最最少的直線覆覆蓋所有0元元素。 (10）增加加0元素從未被直線覆覆蓋的元素中中找出一個最最小元素166，未被覆蓋蓋的元素都減減去該最小元元素，而被兩兩條線覆蓋的的元素都加上上該最小元素素，其它元素素不變。這樣樣得到新系數數矩陣，然后后重新確定獨獨立0元素。 m=n=6,所以可以得得到優(yōu)化方案案，將矩陣中中的非0元素素變?yōu)?，將將獨立0元素素變?yōu)?. 由解可可得最優(yōu)分配配方案：A貨貨物放5貨格格，B貨物放放1貨格，CC貨物放4貨貨格，D貨物物放3貨格，EE貨物放6貨貨格，F貨物物放2貨格。可以將得出的最優(yōu)分配方案繪制成圖2.2所示：VyVy2貨物F4貨物C6貨物E1貨物B3貨物D5貨物A圖2.

23、2貨物安放規(guī)劃圖0Vx圖2.2貨物安放規(guī)劃圖0Vx2.4總結面對成千上萬的的貨格，立體體倉庫的貨位位存儲優(yōu)化已已成為提高存存取效率、降降低成本的關關鍵，這需要要對不同貨物物在倉庫中的的存放位置進進行合理分配配，這可通過過利用匈牙利利算法來達到到此目的。通通過匈牙利算算法得到的貨貨位分配，可可以對倉庫中中的貨物儲位位進行進行整整合，使得貨貨物的在貨格格中的存放位位置最優(yōu)、取取放路徑最優(yōu)優(yōu)，從而達到到進貨和出貨貨時既經濟又又省時，同時時可使物品的的破損率達到到最低，這對對于提高企業(yè)業(yè)的品牌起重重要作用。通過這次課程設設計我也認識識到了貨位優(yōu)優(yōu)化對于一個個倉庫的重要要性，這次學學習使得我也也學習到了

24、很很多的物流知知識，對于老老師講解過程程中的關于自自動化立體倉倉庫的一些問問題也得到了了充分理解，這這次的課程設設計過程中也也讓我學到很很多，以及在在設計過程中中我們應該要要認真的積極極態(tài)度，以及及在整理課題題任務時要仔仔細，只有這這樣才能保證證我們在做事事情的過程中中會減少誤差差。3堆垛機路徑優(yōu)優(yōu)化最短路徑問題是是圖論中的一一個經典問題題。由于問題題中邊的權值值往往可以從從距離引申為為其他沿路徑徑線性積累的的度量，如：時間、花費費等，所以最最短路徑問題題在實際生活活中有著廣泛泛的應用。分層思想作為一一個重要的思思想，也有著著許多應用，特特別在是某些些高效的方法法中，如：動動態(tài)規(guī)劃中的的階段劃

25、分、圖圖論中基于求求阻塞流的最最大流算法等等。將分層思思想應用到最最短路徑問題題中，正是分分層思想和最最短路徑問題題的強強聯合合。因此正是是基于此問題題，將最短路路路徑用于堆堆垛機的路徑徑優(yōu)化，以下下便用最近鄰鄰點法和插入入法進行堆垛垛機的路徑優(yōu)優(yōu)化。 3.1 設計計條件VyVy4 (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)05 (C)9 (M)13 (P)17 (L)VxVx圖3.1 最終終的貨位規(guī)劃劃圖隨機從圖3.11中的20個個貨格中抽出出10個貨格格的貨

26、物，分分別用節(jié)點VV，V，V，V，V，V，V，V，V，V表示。節(jié)點點間的距離用用直角距離公公式: 式(3.1）。3.2設計要求求（1）繪出貨格格和節(jié)點相對對位置圖及節(jié)節(jié)點相對距離離表（需先列列式計算各的的值）；（2）詳細地寫寫出最近鄰點點法和最近插插入法的每一一步驟及計算算結果。（3）分析兩種種方法的結果果。（4）設計結束束后，談談自自己的看法。 3.3設計方法法分別用最近鄰點點法和最近插插入法找出堆堆垛機存取110個托盤貨貨物的合理路路線。在堆垛垛機開始揀選選之前，由于于設備及系統(tǒng)統(tǒng)根據實際情情況每臺堆垛垛機分配一定定數量的貨位位，被分配的的貨位用陰影影的小方格表表示，圖中的的實心小黑點點表

27、示堆垛機機從貨架上取取貨時，需要要在倉庫中停停留的位置點點，可以選用用的方法的有有最近零點法法、最近插入入發(fā)和遺傳算算法等。3.4求解過程程首先根據設計要要求，繪出貨貨格和節(jié)點相相對位置圖如如圖3.2、33.3所示：VyVy4 (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)VxoVxo圖3.2 貨格格的相對位置置圖V10V10V9V8V7V6V5V4V3V2V1 圖33.3 節(jié)點點的相對位置置引用d=|x-x|L+|y-yy

28、|H 式(3.1）計算算節(jié)點間距離離dv1v2=|xv2-xv1|L+|yv22-yv1|H=|1-11|1+|3-1|0.8=0.8 dv1v33=|xv3-xv1|L+|yv33-yv1|H=|2-11|1+|1-1|0.8=1.8dv1v4=|xv4-xv1|L+|yv44-yv1|H=|2-11|1+|4-11|0.8=33.4dv1v5=|xv5-xv1|L+|yv55-yv1|H=|3-11|1+|2-11|0.8=2.8dv1v6=|xv6-xv1|L+|yv66-yv1|H=|3-1|1+|4-11|0.8=3.6dv1v7=|xv7-xv1|L+|yv77-yv1|H=|4-

29、11|1+|2-11|0.8=33dv1v8=|xv8-xv1|L+|yv88-yv1|H=|4-11|1+|3-11|0.8=44.6 dv1v99=|xv9-xv1|L+|yv99-yv1|H=|5-11|1+|1-11|0.8=4 dv1v110=|xv100-xv1|L+|yv110-yv1|H=|5-11|1+|3-11|0.8=55.6dv2v3=|xv3-xv2|L+|yv33-yv2|H=|2-1|1+|1-3|0.8=11dv2v4=|xv4-xv2|L+|yv44-yv2|H=|2-1|1+|4-33|0.8=2.6dv2v5=|xv5-xv2|L+|yv55-yv2|H=

30、|3-1|1+|2-3|0.8=22dv2v6=|xv6-xv2|L+|yv66-yv2|H=|3-11|1+|4-33|0.8=22.8dv2v7=|xv7-xv2|L+|yv77-yv2|H=|4-1|1+|2-33|0.8=33.8 dv2v88=|xv8-xv2|L+|yv88-yv2|H=|4-1|1+|3-33|0.8=33.8dv2v9=|xv9-xv2|L+|yv99-yv2|H=|5-1|1+|1-33|0.8=44.8dv2v10=|xv100-xv2|L+|yv110-yv2|H=|5-1|1+|3-33|0.8=44.8dv3v4=|xv4-xv3|L+|yv44-yv

31、3|H=|2-2|1+|4-11|0.8=1.6dv3v5=|xv5-xv3|L+|yv55-yv3|H=|3-2|1+|2-11|0.8=1dv3v6=|xv6-xv3|L+|yv66-yv3|H=|3-22|1+|4-11|0.8=1.8dv3v7=|xv7-xv3|L+|yv77-yv3|H=|4-2|1+|2-11|0.8=2.8dv3v8=|xv8-xv3|L+|yv88-yv3|H=|4-2|1+|3-11|0.8=2.8 dv3v99=|xv9-xv3|L+|yv99-yv3|H=|5-2|1+|1-11|0.8=3.8dv3v10=|xv100-xv3|L+|yv110-yv3

32、|H=|5-2|1+|3-11|0.8=3.8 dv4v55=|xv5-xv4|L+|yv55-yv4|H=|3-2|1+|2-44|0.8=2.6 dv4v66=|xv6-xv4|L+|yv66-yv4|H=|3-22|1+|4-44|0.8=1.8 dv4v77=|xv7-xv4|L+|yv77-yv4|H=|4-2|1+|2-44|0.8=44.4 dv4v88=|xv8-xv4|L+|yv8-yv4|H=|4-2|1+|3-44|0.8=2.8 dv4v99=|xv9-xv4|L+|yv9-yv4|H=|5-22|1+|1-44|0.8=5.4 dv4v110=|xv10-xv4|L+

33、|yv10-yv4|H=|5-2|1+|3-44|0.8=33.8 dv5v66=|xv6-xv5|L+|yv66-yv5|H=|3-33|1+|4-22|0.8=0.8 dv5v77=|xv7-xv5|L+|yv77-yv5|H=|4-3|1+|2-22|0.8=1.8 dv5v88=|xv8-xv5|L+|yv8-yv5|H=|4-3|1+|3-22|0.8=11.8 dv5v99=|xv9-xv5|L+|yv9-yv5|H=|5-3|1+|1-22|0.8=2.8 dv5v110=|xv10-xv5|L+|yv10-yv5|H=|5-3|1+|3-22|0.8=2.8 dv6v77=|x

34、v7-xv6|L+|yv77-yv6|H=|4-3|1+|2-44|0.8=2.6 dv6v88=|xv8-xv6|L+|yv8-yv6|H=|4-3|1+|3-44|0.8=11 dv6v99=|xv9-xv6|L+|yv9-yv6|H=|5-3|1+|1-4|0.8=3.6 dv6v110=|xv10-xv6|L+|yv10-yv6|H=|5-3|1+|3-44|0.8=22 dv7v88=|xv8-xv7|L+|yv8-yv7|H=|4-44|1+|3-22|0.8=11.6 dv7v99=|xv9-xv7|L+|yv99-yv7|H=|5-44|1+|1-22|0.8=1 dv7v11

35、0=|xv10-xv7|L+|yv10-yv7|H=|5-44|1+|3-22|0.8=2.6 dv8v99=|xv9-xv8|L+|yv9-yv8|H=|5-44|1+|1-33|0.8=2.6 dv8v110=|xv10-xv8|L+|yv10-yv8|H=|5-44|1+|3-33|0.8=1 dv9v10=|xv10-xv9|L+|yv10-yv9|H=|5-5|1+|3-11|0.8=1.6根據兩節(jié)點的相相對距離繪制制節(jié)點相對距距離表3.11：表3.1 節(jié)點點相對距離表表節(jié)點VVVVVVVVVVV2.83.634.645.6V12.64.84.8V1.63.83.8VV2.82.8V

36、2.613.62V1.612.6V2.61V1.6V3.4.1最近近鄰點法求堆堆垛機運行路路徑1 最近鄰點法法1.1 最近鄰鄰點法的思路路從零點開始，作作為整個回路路的起點。找到離剛剛加入入到回路的頂頂點最近的一一個頂點，并并將其加入到到回路中。重復步驟（2），直直到所有頂點點都加入到回回路中。最后，將最后一一個加入的頂頂點和起點連連接起來。 應用過程V1（1）先將節(jié)點點v1加入到回路路中，T=v1。V1圖3.4 加入入節(jié)點v（2） 從節(jié)點點v1出發(fā)，在節(jié)點點2、3、44、5、6、77、8、9、110中，找出出離v1 最近的節(jié)點。Min 因此將節(jié)點vv2加入到回路路中，T1=v1,v2。V10

37、V10V9V8V7V6V5V4V3V2V1圖 3.5 運運行路線（3）從節(jié)點vv2出發(fā)，在節(jié)節(jié)點3、4、55、6、7、88、9、100中，找出離離v2最近的節(jié)點點。Min因此就可以將vv3加入到回路路中，T2=v1,v2,v3。V10V10V9V8V7V6V5V4V3V2V1圖 3.6 運運行路線（4）從節(jié)點vv3出發(fā)，在節(jié)節(jié)點4、5、66、7、8、99、10中，找找出離v3最近的節(jié)點點。Min因此就可以將vv5加入到回路路中，T3=v1,v2,v3,v5V10V10V9V8V7V6V5V4V3V2V1圖 3.7 運運行路線（5）從節(jié)點vv5出發(fā)，在節(jié)節(jié)點4、6、7、88、9、100中，找出離

38、離v5最近的節(jié)點點。Min因此就可以將vv6加入到回路路中，T4=v1,v2,v3,v5,v6V10V10V9V8V7V6V5V4V3V2V1圖 3.8 運運行路線（6） 從節(jié)點點v6出發(fā)，在節(jié)節(jié)點4、7、8、99、10中，找找出離v6最近的節(jié)點點。Min因此就可以將vv8加入到回路路中，T5=v1,v2,v3,v5,v6,v8V10V10V9V8V7V6V5V4V3V2V1圖 3.9 運運行路線（7） 從節(jié)點點v8出發(fā)，在節(jié)節(jié)點4、7、9、100中，找出離離v8最近的節(jié)點點。Min因此就可以將vv10加入到回回路中，T66=v1,v2,v3,v5,v6，v8，v10V10V10V9V8V7V

39、6V5V4V3V2V1圖 3.10 運行路線(8)從節(jié)點vv10出發(fā)，在在節(jié)點4、77、9中，找出離離v10最近的節(jié)節(jié)點。Min因此就可以將vv9加入到回路路中，T7=v1,v2,v3,v5,v6,v8，v10,v9形成如圖33.11所示示的運行路線線V10V10V9V8V7V6V5V4V3V2V1圖 3.11 運行路線(9)從節(jié)點vv9出發(fā)，在節(jié)節(jié)點4、7中，找找出離v9最近的節(jié)點點。Min因此就可以將vv7加入到回路路中，T8=v1,v2,v3,v5,v6,v8，v10,v9,v7形成如圖33.12所示示的運行路線線V10V10V9V8V7V6V5V4V3V2V1圖 3.12 運行路線(1

40、0)將最后后的點v4, ,v1連接起來得得到最后的運運行路線圖,T9=vv1,v2,v3,v5,v6,v8，v10,v9,v7 ,v4,v1V10V10V9V8V7V6V5V4V3V2V1圖 3.13 最終運行線線路圖所以堆垛機運行行路線為：11261011151917138即取送貨物次序序為：ABFIHESLPK堆垛機總行駛距距離為：Z=0.8+11+1+0.8+1+11+1.6+1+4.44+3.4=163.4.2最近近插入法求堆堆垛機運行路路徑2 最近插入法法2.1 最近插插入法的思路路（1）先將節(jié)點點v1加入到回路路中，找到dd1k最小的節(jié)節(jié)點vk ，形成一一個子回路，TT=v1 ,v

41、k ,v1。（2）在剩下的的節(jié)點中，尋尋找一個離子子回路中某一一節(jié)點最近的的節(jié)點vk 。（3）在子回路路中找到一條條弧（i,jj）,使得里里程增量最小小。如果有多多條滿足條件件，任選一條條，然后將節(jié)節(jié)點vk插入到節(jié)點點vi和vj之間，用兩兩條新的?。╥i,k）和（k,jj）代替原來的的?。╥,jj）,并將節(jié)點點vk加入到子回回路中。（4）重復步驟驟（2）和（33），直到所所有的節(jié)點都都加入到子回回路中。2.2 應用過過程（1）比較貨格格相對距離表表中從v1出發(fā)的所有有路徑的大小小Minn這樣就由節(jié)點vv1和v2構成的子回回路，T=v1,v2,v1V10V10V9V8V7V6V5V4V3V2V1

42、圖3.14 由由v1和v2構成的子回回路（2）然后考慮慮剩下的節(jié)點點、 ，到和中某一個節(jié)節(jié)點的最小距距離；Min由于對稱性，無無論將3插入入到1和2之之間往返路徑徑中，結果都都是一樣的，任選其一,這樣構成一個新的子回路T=v1,v2, v3,v1V10V10V8V7V6V5V4V3V2V1V9圖3.15 由由v1,v2和v3構成的子回回路（3）接著考慮慮剩下的節(jié)點點、 ，到、和中 某一一個節(jié)點的最最小距離； Min（4）由圖3.15可知，節(jié)節(jié)點有3個位位置（條弧線線）可以插入入?，F在分析析將加入到哪哪里合適：插入到（1,2）間，=d15+d52-d12=2.88+2-0.8=4插入到（2,3）

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

44、.6+22.8-0.8=5.66插入到（2,5）間，= d+d-d=2.8+00.8-2=1.6插入到（3,5）間，= d+d-d=1.88+0.8-1=1.66插入到（3,1）間，= d+d-d=1.88+3.6-1.8=33.6比較上面4種情情況增量，將將插入（2,5）或（3,55）之間的增增量最小，任任選其一，將將v5插入（2,5）之間，則則結果為：TT= v1,v2,v,v，v，v1其子回路則則變?yōu)槿鐖D33.17所示示：V10V10V9V8V7V6V5V4V3V2V1圖3.17 由由v1,v2,v,v，v構成的子子回路(7) 接著考考慮剩下的節(jié)節(jié)點、 ，到、中某一節(jié)點點的最小距離離Mi

45、n（8）由圖3.17可知，節(jié)節(jié)點有5個位位置（條弧線線）可以插入入。現在分析析將加入到哪哪里合適：插入到（1,2）間，= d18+d-d12=4.6+33.8-0.8=7.66插入到（2,6）間，= d+d-d=3.8+11-2.8=2插入到（6,5）間，= d+d-d=1+1.88-0.8=2插入到（5,3）間，= d+d-d=1.8+22.8-1=3.6插入到（3,1）間，= d+d-d=2.8+44.6-1.8=5.66比較上面5種情情況增量，可可將插入（6,5）或（22,6）之間的增增量最小，任任選其一，若若將插入（6,5）之間，則則結果為：TT=、其子回路則則變?yōu)閳D3.18所所示：V

46、10V10V9V8V7V6V5V4V3V2V1圖3.18 由由、構成的子回回路（9）接著剩下下的節(jié)點、，到、中某一節(jié)點點的最小距離離Min（10）由圖33.18可知知有6個位置置（條弧線）可可以插入?，F現在分析將加加入到哪里合合適： 插入到（1,2）間，= d+d-d12=5.6+44.8-0.8=9.66插入到（2,6）間，= d+d-d=4.88+2-2.8=4插入到（6,8）間，= d+d-d=2+11-1=2插入到（8,5）間，= d+d-d=1+22.8-1.8=2插入到（5,3）間，= d+d-d=2.88+3.8-1=5.66插入到（3,1）間，= d+d-d=3.88+5.6-

47、1.8=77.6比較上面6種情情況增量，插插入到（6,8）或（8,5）之間的增增量最小，任任選其一，所所以將節(jié)點加加入到（8,5）間，結果果為：T=、其子回路則則變?yōu)閳D3.19所所示：V10V10V9V8V7V6V5V4V3V2V1圖3.19 、構成的子回回路 （111）接著考慮慮剩下的節(jié)點點、到、中某一節(jié)點點的最小距離離；Min（12）由圖33.19可知知有7個位置（條條弧線）可以以插入?，F在在分析將加入入到哪里合適適： 插入到（1,2）間，= d+d-d12=3.44+2.6-0.8=55.2插入到（2,6）間，= d+d-d=2.66+1.8-2.8=11.6插入到（6,8）間，= d+

48、d-d=1.88+2.8-1=3.66插入到（8,10）間，= d+d-d=2.88+3.8-1=5.66插入到（100，5）間，= d+d-d=3.88+2.6-2.8=33.6插入到（5,3）間，= d+d-d=2.66+1.6-1=3.22插入到(3，11)間，= d+d-d=1.66+3.4-1.8=33.2比較上面7種情情況增量，插插入到（2,6）之間的的增量最小，所以將節(jié)點加入到（2,6）間，結果為：T=、其子回路則變圖3.20所示：V10V10V9V8V7V6V5V4V3V2V1圖3.20 、構成的子回回路（13）接著考考慮剩下的節(jié)節(jié)點、到、中某一節(jié)點點的最小距離離；Min（14

49、）由圖33.20可知知有8個位置（條條弧線）可以以插入?，F在在分析將加入入到哪里合適適： 插入到（1,2）間，= d+d-d12=4+44.8-0.8=8插入到（2,4）間，= d+d-d=4.88+5.4-2.6=77.6插入到（4,6）間，= d+d-d=5.44+3.6-1.8=77.2插入到（6,8）間，= d+d-d=3.66+2.6-1=5.22插入到（8，110）間，= d+d-d=1+11.6-1=1.6插入到（100,5）間，= d+d-d=1.66+2.8-2.8=11.6插入到(5，33)間，= d+d-d=2.88+3.8-1=5.66插入到(3，11)間，= d+d-d=3.88+4-1.8=6比較上面8種情情況增量，插插入到（8,10）和（110,5）之之間的增量最最小，任選其其一，所以將將節(jié)點加入到到（10，55）間，結果果為：T=、其子回路路如圖3.21所所示：V10V10V9V8V7V6V5V4V3V2V1圖3.21 、構成的子回回路（15）最后考考慮剩下的節(jié)節(jié)點到、中某