目錄TOC\o"1-4"\h\z\u引言 11自動化立體倉庫 21.1概述 22貨位優化 32.1設計條件 32.2計算系數矩陣 32.2.1符號假設 32.2.2已知條件 42.2.3公式計算過程 42.3運用匈牙利算法求解 62.4總結 133堆垛機途徑優化 153.1設計條件 153.2設計規定 163.3設計辦法 163.4求解過程 163.4.1近來鄰點法求堆垛機運營途徑 193.4.2近來插入法求堆垛機運營途徑 263.5總結 34參照文獻 36

引言自動化立體倉庫產生和發展是生產力高度發展和都市化進程不斷發展成果。計算機浮現和應用，自動化倉庫產生。倉庫空間向立體化方向發展個，貨位向空間延伸，高層貨架和與之配套新型裝卸搬運機械與周邊設備浮現，立體倉庫產生。自動化立體倉庫是指在高層貨架用貨箱或托盤儲存貨品，用電子計算機管理和控制巷道式堆垛機及其他機械，不需要人工作業而實現收發作業倉庫。自動化立體倉庫是一種集信息、儲存、管理于一體高技術密集型機電化產品，堆垛機和高層貨架是其核心設備。隨著電子技術與控制理論發展，各種控制辦法被引入堆垛機控制。貨位優化和巷道式堆垛機途徑優化成為自動化立體倉庫必要工作，因而本次課程設計針對這兩點做出了詳細簡介。貨位優化是用來擬定每一品規恰當儲存方式，在恰當儲存方式下空間儲位分派。貨位優化追求不同設備和貨架類型特性、貨品分組、貨位規劃、人工成本內置等因素以實現最佳貨位布局，能有效掌握商品變化，將成本節約最大化。貨位優化為正在營運倉庫挖掘效率和成本，并為一種建設中配送中心或倉庫提供營運前核心管理作準備。

1自動化立體倉庫1.1概述自動化立體倉庫作為當代化物流系統中重要構成某些,是一種多層存儲貨品高架倉庫系統,重要由高層貨架、巷道堆垛機、出入庫輸送設備、自動控制與管理系統所構成。出入庫輔助設備及巷道堆垛機可以在計算機管理下，完畢貨品出入庫作業、實行綜合庫房管理并與上級管理系統聯網，可以實現管理當代化、存取自動化，能按指令自動完畢貨品存取作業,并能對庫存貨品進行自動化管理,是公司實現當代化管理重要手段。自動立體倉庫在工廠自動化，彈性制造系統及電腦整合制造系統物流中占非常重要位置。其目不但是為了儲存物料、零件、半成品、成品倉儲，更是密切配合制造工廠產銷籌劃與物料需求籌劃，妥善安排生產所需合理數量物料、零件，并盡量縮短其庫存時間及避免了發生缺料、滯料，籍高架搬運車、輸送機、無人搬運車等，然后保管成品而依銷售預定準進對的出貨，提高服務水平，事合了籌劃、庫存、生產、出入物流功能與管理，減少了生產成本。其構成某些：（1）貨架:用于存儲貨品鋼構造。重要有焊接式貨架和組合式貨架兩種基本形式。（2）托盤（貨箱）：用于承載貨品器具，亦稱工位器具。（3）巷道堆垛機:用于自動存取貨品設備。按構造形式分為單立柱和雙立柱兩種基本形式；按服務方式分為直道、彎道和轉移車三種基本形式。（4）輸送機系統:立體庫重要外圍設備，負責將貨品運送到堆垛機或從堆垛機將貨品移走。輸送機種類非常多，常用有輥道輸送機，鏈條輸送機，升降臺，分派車，提高機，皮帶機等。（5）AGV系統:即自動導向小車。依照其導向方式分為感應式導向小車和激光導向小車。（6）自動控制系統:驅動自動化立體庫系統各設備自動控制系統。以采用現場總線方式為控制模式為主。（7）儲存信息管理系統:亦稱中央計算機管理系統。是全自動化立體庫系統核心。典型自動化立體庫系統均采用大型數據庫系統（如ORACLE，SYBASE等）構筑典型客戶機/服務器體系，可以與其她系統（如ERP系統等）聯網或集成。

2.貨位優化

2.1設計條件某自動化立體倉庫采用2行3列單元貨格式貨架存儲貨品，一共有6個貨格，每個貨格存儲一種托盤貨品。貨格以按列編碼形式進行編號，如圖2.1所示。已知其他參數假定如下：假設堆垛機在水平方向行駛速度Vx=3.0m/s，在垂直方向行駛速度Vy=2m/s；貨格大小為L（長）×W（寬）×H（高）=1m×1m×0.8m；堆垛機初始狀態在原點0處；貨格j橫坐標和縱坐標就是其所在列和行，如貨格6坐標為（3，2）。既有6個托盤貨品需要存儲到貨架上，貨品出入庫頻率如表2.1所示。VyVy24613500Vx圖2.1原始貨格圖Vx表2.1托盤貨品出入庫頻率表貨品頻率貨品頻率貨品頻率A9C18E7B39D14F25依照以上條件，運用匈牙利算法合理安排各托盤貨品存儲位置。2.2計算系數矩陣2.2.1符號假設1.為第i種貨品出入庫頻率（次數），i=A，B，C，D，E，F；2．，分別為貨格j橫坐標和縱坐標，即貨格j所在列和行（距離巷道口近來列記為第1列，最底層記為第1層），j=1，2，3，4，5，6；3．為水平方向行駛速度；4.為垂直方向行駛速度；5.L為貨格長；6.W為貨格寬；7.H為貨格高；8.為堆垛機運營之貨格j所用時間，該時間是堆垛機行進過程中水平方向和垂直方向所用時間最大值，j=1，2，3，4，5，6；9.為堆垛機將貨品i向貨格j存取時所耗費時間。10.公式為=max（2.1）11.計算系數矩陣中系數：=（2.2）2.2.2已知條件=9，=39，=18，=14，=7，=25；=3.0m/s，=2.0m/s；L×W×H=1m×1m×0.8m；貨格1坐標為（，）=(1,1)；貨格2貨格為（，）=（1，2）；貨格3坐標為（，）=（2，1）；貨格4坐標為（，）=（2，2）；貨格5坐標為（，）=（3，1）；貨格6坐標為（，）=（3，2）。2.2.3公式計算過程1.計算：=max=max=1/3=max=max=2/5=max=max=2/3=max=max=2/3=max=max=1=max=max=12.計算系數矩陣中系數：==9×1/3=3，==39×1/3=13，==18×1/3=6，==14×1/3=14/3，==7×1/3=7/3，==25×1/3=25/3；==9×2/5=18/5，==39×2/5=78/5，==18×2/5=36/5，==14×2/5=28/5，==7×2/5=14/5，==25×2/5=10；==9×2/3=6，==39×2/3=26，==18×2/3=12，==14×2/3=28/3，==7×2/3=14/3，==25×2/3=50/3；==9×2/3=6，==39×2/3=26，==18×2/3=12，==14×2/3=28/3，==7×2/3=14/3，==25×2/3=50/3；==9×1=9，==39×1=39，==18×1=18，==14×1=14，==7×1=7，==25×1=25；==9×1=9，==39×1=39，==18×1=18，==14×1=14，==7×1=7，==25×1=25；得到系數矩陣表：貨品表2.2系數矩陣表貨品貨格貨格ABCDEF1313614/37/325/3218/578/536/528/514/51036261228/314/350/346261228/314/350/359391814725693918147252.3運用匈牙利算法求解1.匈牙利算法環節第一步：建等效矩陣。（1）從系數矩陣每行元素中減去該行最小元素。（2）再從所得系數矩陣每列元素中減去該列最小元素。第二步：找獨立0元素，進行試指派。（1）從只有一種0元素行（或列）開始，給這個0元素加括號（0），表達這行所代表貨格已有一種貨品分派。然后劃去（0）所在列（或行）其他0元素，記作“”，表達這列所代表貨品已指派。（2）對只有一種0元素列（或行）0元素加括號（0），然后劃去（0）所在行（或列）0元素，記作“”。如果在（1），（2）兩步中，遇到每一行和每一列均有兩個或兩個以上0元素，可任選一種加括號，同步把其所在行和列0元素都劃去。（3）重復（1），（2）兩步，直到所有0元素都被加括號或打叉。（4）加括號0元素即為獨立0元素，若其個數m等于矩陣階數n，則已得到問題最優解。若m<n，則轉入第三步。第三步：用至少直線覆蓋所有0元素。（1）對沒有獨立0元素行打“√”。（2）對以打“√”行中所含0元素列打“√”。（3）再對（2），（3），直到得不到新打“√”行、列為止。（4）將沒有打“√”行和以打“√”列用直線覆蓋，且直線數目一定等于獨立0元素個數。轉第四步。第四步：增長0元素。從沒有被直線覆蓋元素中找出最小元素。未被覆蓋元素都減去該最小元素，而被兩條線覆蓋元素都加上該最小元素，其他元素不變。這樣得到新系數矩陣，轉第二步，重新擬定獨立0元素。2.應用過程(1)給系數矩陣表乘以15，從系數矩陣每行元素中減去該行最小元素35、42、70、70、105、105．再從所得系數矩陣每列元素中減去該列最小元素，得到等效矩陣。（2）①從只有一種0元素第2行開始，給這個0元素加括號（0），表達這行所代表貨格已有一種貨品分派。然后劃去（0）所在列其他0元素，記作“”，表達這列所代表貨品已指派。②對只有一種0元素第1列0元素加括號（0），然后劃去（0）所在行0元素，記作“”。獨立0元素個數m=2<矩陣階數n=6，轉入下一步。（3）用至少直線覆蓋所有0元素。①對第3、4、5、6行打“√”。②對第5列打“√”。③得不到新打“√”行、列，停止。④將沒有打“√”行和已打“√”列用直線覆蓋，且直線數目一定等于獨立0元素個數。√√√√√√√√√√√√（4）增長0元素①從沒有被直線覆蓋元素中找出最小元素2。未被覆蓋元素都減去該最小元素，而被兩條線覆蓋元素都加上該最小元素，其他元素不變。這樣得到新系數矩陣，然后重新擬定獨立0元素。 ②矩陣中獨立0元素個數m=3＜n=6，用至少直線覆蓋所有0元素。√√（5）增長0元素①從未被直線覆蓋元素中找出一種最小元素８，未被覆蓋元素都減去該最小元素，而被兩條線覆蓋元素都加上該最小元素，其他元素不變。這樣得到新系數矩陣，然后重新擬定獨立0元素。②矩陣中獨立0元素個數m=3＜n=6，用至少直線覆蓋所有0元素.√√√√（6）增長0元素①從未被直線覆蓋元素中找出一種最小元素5，未被覆蓋元素都減去該最小元素，而被兩條線覆蓋元素都加上該最小元素，其他元素不變。這樣得到新系數矩陣，然后重新擬定獨立0元素。√√②矩陣中獨立0元素個數m=4＜n=6，用至少直線覆蓋所有0元素。√√②矩陣中獨立0元素個數m=4＜n=6，用至少直線覆蓋所有0元素。 （7）增長0元素①從未被直線覆蓋元素中找出一種最小元素20，未被覆蓋元素都減去該最小元素，而被兩條線覆蓋元素都加上該最小元素，其他元素不變。這樣得到新系數矩陣，然后重新擬定獨立0元素。②矩陣中獨立0元素個數m=4＜n=6，用至少直線覆蓋所有0元素。√√√√√√（8）增長0元素①從未被直線覆蓋元素中找出一種最小元素4，未被覆蓋元素都減去該最小元素，而被兩條線覆蓋元素都加上該最小元素，其他元素不變。這樣得到新系數矩陣，然后重新擬定獨立0元素。②矩陣中獨立0元素個數m=5＜n=6，用至少直線覆蓋所有0元素。√√（9）增長0元素①從未被直線覆蓋元素中找出一種最小元素10，未被覆蓋元素都減去該最小元素，而被兩條線覆蓋元素都加上該最小元素，其他元素不變。這樣得到新系數矩陣，然后重新擬定獨立0元素。②矩陣中獨立0元素個數m=5＜n=6，用至少直線覆蓋所有0元素。√√√√√√√√ （9）增長0元素①即從未被直線覆蓋元素中找出一種最小元素7，未被覆蓋元素都減去該最小元素，而被兩條線覆蓋元素都加上該最小元素，其他元素不變。這樣得到新系數矩陣，然后重新擬定獨立0元素。②矩陣中獨立0元素個數m=5＜n=6，用至少直線覆蓋所有0元素。√√√√√√(10）增長0元素①從未被直線覆蓋元素中找出一種最小元素16，未被覆蓋元素都減去該最小元素，而被兩條線覆蓋元素都加上該最小元素，其他元素不變。這樣得到新系數矩陣，然后重新擬定獨立0元素。②m=n=6,因此可以得到優化方案，將矩陣中非0元素變為0，將獨立0元素變為1.由解可得最優分派方案：A貨品放5貨格，B貨品放1貨格，C貨品放4貨格，D貨品放3貨格，E貨品放6貨格，F貨品放2貨格。可以將得出最優分派方案繪制成圖2.2所示：VyVy2貨品F4貨品C6貨品E1貨品B3貨品D5貨品A圖2.2貨品安放規劃圖0Vx圖2.2貨品安放規劃圖0Vx2.4總結面對成千上萬貨格，立體倉庫貨位存儲優化已成為提高存取效率、減少成本核心，這需要對不同貨品在倉庫中存儲位置進行合理分派，這可通過運用匈牙利算法來達到此目。通過匈牙利算法得到貨位分派，可以對倉庫中貨品儲位進行進行整合，使得貨品在貨格中存儲位置最優、取放途徑最優，從而達到進貨和出貨時既經濟又省時，同步可使物品破損率達到最低，這對于提高公司品牌起重要作用。通過這次課程設計我也結識到了貨位優化對于一種倉庫重要性，這次學習使得我也學習到了諸多物流知識，對于教師解說過程中關于自動化立體倉庫某些問題也得到了充分理解，這次課程設計過程中也讓我學到諸多，以及在設計過程中咱們應當要認真積極態度，以及在整頓課題任務時要仔細，只有這樣才干保證咱們在做事情過程中會減少誤差。

3堆垛機途徑優化最短途徑問題是圖論中一種典型問題。由于問題中邊權值往往可以從距離引申為其她沿途徑線性積累度量，如：時間、耗費等，因此最短途徑問題在實際生活中有著廣泛應用。分層思想作為一種重要思想，也有著許多應用，特別在是某些高效辦法中，如：動態規劃中階段劃分、圖論中基于求阻塞流最大流算法等。將分層思想應用到最短途徑問題中，正是分層思想和最短途徑問題強強聯合。因而正是基于此問題，將最短路途徑用于堆垛機途徑優化，如下便用近來鄰點法和插入法進行堆垛機途徑優化。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最后貨位規劃圖隨機從圖3.1中20個貨格中抽出10個貨格貨品，分別用節點V，V，V，V，V，V，V，V，V，V表達。節點間距離用直角距離公式:式(3.1）。3.2設計規定（1）繪出貨格和節點相對位置圖及節點相對距離表（需先列式計算各值）；（2）詳細地寫出近來鄰點法和近來插入法每一環節及計算成果。（3）分析兩種辦法成果。（4）設計結束后，談談自己看法。3.3設計辦法分別用近來鄰點法和近來插入法找出堆垛機存取10個托盤貨品合理路線。在堆垛機開始揀選之前，由于設備及系統依照實際狀況每臺堆垛機分派一定數量貨位，被分派貨位用陰影小方格表達，圖中實心小黑點表達堆垛機從貨架上取貨時，需要在倉庫中停留位置點，可以選用辦法有近來零點法、近來插入發和遺傳算法等。3.4求解過程一方面依照設計規定，繪出貨格和節點相對位置圖如圖3.2、3.3所示：VyVy 4(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圖3.3節點相對位置引用d=|x-x|×L+|y-y|×H式(3.1）計算節點間距離dv1v2=|xv2-xv1|×L+|yv2-yv1|×H=|1-1|×1+|3-1|×0.8=0.8dv1v3=|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-yv1|×H=|4-1|×1+|3-1|×0.8=4.6dv1v9=|xv9-xv1|×L+|yv9-yv1|×H=|5-1|×1+|1-1|×0.8=4dv1v10=|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=2.8dv2v7=|xv7-xv2|×L+|yv7-yv2|×H=|4-1|×1+|2-3|×0.8=3.8dv2v8=|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-xv3|×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.8dv3v9=|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.8dv4v5=|xv5-xv4|×L+|yv5-yv4|×H=|3-2|×1+|2-4|×0.8=2.6dv4v6=|xv6-xv4|×L+|yv6-yv4|×H=|3-2|×1+|4-4|×0.8=1.8dv4v7=|xv7-xv4|×L+|yv7-yv4|×H=|4-2|×1+|2-4|×0.8=4.4dv4v8=|xv8-xv4|×L+|yv8-yv4|×H=|4-2|×1+|3-4|×0.8=2.8dv4v9=|xv9-xv4|×L+|yv9-yv4|×H=|5-2|×1+|1-4|×0.8=5.4dv4v10=|xv10-xv4|×L+|yv10-yv4|×H=|5-2|×1+|3-4|×0.8=3.8dv5v6=|xv6-xv5|×L+|yv6-yv5|×H=|3-3|×1+|4-2|×0.8=0.8dv5v7=|xv7-xv5|×L+|yv7-yv5|×H=|4-3|×1+|2-2|×0.8=1.8dv5v8=|xv8-xv5|×L+|yv8-yv5|×H=|4-3|×1+|3-2|×0.8=1.8dv5v9=|xv9-xv5|×L+|yv9-yv5|×H=|5-3|×1+|1-2|×0.8=2.8dv5v10=|xv10-xv5|×L+|yv10-yv5|×H=|5-3|×1+|3-2|×0.8=2.8dv6v7=|xv7-xv6|×L+|yv7-yv6|×H=|4-3|×1+|2-4|×0.8=2.6dv6v8=|xv8-xv6|×L+|yv8-yv6|×H=|4-3|×1+|3-4|×0.8=1dv6v9=|xv9-xv6|×L+|yv9-yv6|×H=|5-3|×1+|1-4|×0.8=3.6dv6v10=|xv10-xv6|×L+|yv10-yv6|×H=|5-3|×1+|3-4|×0.8=2dv7v8=|xv8-xv7|×L+|yv8-yv7|×H=|4-4|×1+|3-2|×0.8=1.6dv7v9=|xv9-xv7|×L+|yv9-yv7|×H=|5-4|×1+|1-2|×0.8=1dv7v10=|xv10-xv7|×L+|yv10-yv7|×H=|5-4|×1+|3-2|×0.8=2.6dv8v9=|xv9-xv8|×L+|yv9-yv8|×H=|5-4|×1+|1-3|×0.8=2.6dv8v10=|xv10-xv8|×L+|yv10-yv8|×H=|5-4|×1+|3-3|×0.8=1dv9v10=|xv10-xv9|×L+|yv10-yv9|×H=|5-5|×1+|3-1|×0.8=1.6依照兩節點相對距離繪制節點相對距離表3.1：表3.1節點相對距離表節點VVVVVVVVVVV—0.81.83.42.83.634.645.6V—12.622.83.83.84.84.8V—1.611.82.82.83.83.8V—2.61.84.42.85.43.8V—0.81.81.82.82.8V—2.613.62V—1.612.6V—2.61V—1.6V—3.4.1近來鄰點法求堆垛機運營途徑1近來鄰點法1.1近來鄰點法思路從零點開始，作為整個回路起點。找到離剛剛加入到回路頂點近來一種頂點，并將其加入到回路中。重復環節（2），直到所有頂點都加入到回路中。最后，將最后一種加入頂點和起點連接起來。應用過程V1（1）先將節點v1加入到回路中，T={v1}。V1 圖3.4加入節點v（2）從節點v1出發，在節點2、3、4、5、6、7、8、9、10中，找出離v1近來節點。Min因而將節點v2加入到回路中，T1={v1,v2}。V10V10V9V8V7V6V5V4V3V2V1圖3.5運營路線（3）從節點v2出發，在節點3、4、5、6、7、8、9、10中，找出離v2近來節點。Min因而就可以將v3加入到回路中，T2={v1,v2,v3}。V10V10V9V8V7V6V5V4V3V2V1圖3.6運營路線（4）從節點v3出發，在節點4、5、6、7、8、9、10中，找出離v3近來節點。Min因而就可以將v5加入到回路中，T3={v1,v2,v3,v5}V10V10V9V8V7V6V5V4V3V2V1圖3.7運營路線（5）從節點v5出發，在節點4、6、7、8、9、10中，找出離v5近來節點。Min因而就可以將v6加入到回路中，T4={v1,v2,v3,v5,v6}V10V10V9V8V7V6V5V4V3V2V1圖3.8運營路線 （6）從節點v6出發，在節點4、7、8、9、10中，找出離v6近來節點。Min因而就可以將v8加入到回路中，T5={v1,v2,v3,v5,v6,v8}V10V10V9V8V7V6V5V4V3V2V1圖3.9運營路線（7）從節點v8出發，在節點4、7、9、10中，找出離v8近來節點。Min因而就可以將v10加入到回路中，T6={v1,v2,v3,v5,,v6，v8，v10}V10V10V9V8V7V6V5V4V3V2V1圖3.10運營路線(8)從節點v10出發，在節點4、7、9中，找出離v10近來節點。Min因而就可以將v9加入到回路中，T7={v1,v2,v3,v5,v6,v8，v10,v9}形成如圖3.11所示運營路線V10V10V9V8V7V6V5V4V3V2V1圖3.11運營路線(9)從節點v9出發，在節點4、7中，找出離v9近來節點。Min因而就可以將v7加入到回路中，T8={v1,v2,v3,v5,v6,v8，v10,v9,v7}形成如圖3.12所示運營路線V10V10V9V8V7V6V5V4V3V2V1圖3.12運營路線(10)將最后點v4，,v1連接起來得到最后運營路線圖,T9={v1,v2,v3,v5,v6,v8，v10,v9,v7,v4,v1}V10V10V9V8V7V6V5V4V3V2V1圖3.13最后運營線路圖因此堆垛機運營路線為：1→2→6→10→11→15→19→17→13→8即取送貨品順序為：A→B→F→I→H→E→S→L→P→K堆垛機總行駛距離為：Z=0.8+1+1+0.8+1+1+1.6+1+4.4+3.4=163.4.2近來插入法求堆垛機運營途徑2近來插入法2.1近來插入法思路（1）先將節點v1加入到回路中，找到d1k最小節點vk，形成一種子回路，T={v1,vk,v1}。（2）在剩余節點中，尋找一種離子回路中某一節點近來節點vk。（3）在子回路中找到一條弧（i,j）,使得里程增量最小。如果有多條滿足條件，任選一條，然后將節點vk插入到節點vi和vj之間，用兩條新弧（i,k）和（k,j）代替本來弧（i,j）,并將節點vk加入到子回路中。（4）重復環節（2）和（3），直到所有節點都加入到子回路中。2.2應用過程（1）比較貨格相對距離表中從v1出發所有途徑大小 Min這樣就由節點v1和v2構成子回路，T={v1,v2,v1}V10V10V9V8V7V6V5V4V3V2V1圖3.14由v1和v2構成子回路（2）然后考慮剩余節點、、、、、、，到和中某一種節點最小距離；Min由于對稱性，無論將3插入到1和2之間來回途徑中，成果都是同樣，任選其一,這樣構成一種新子回路T={v1,v2，v3,v1}V10V10V8V7V6V5V4V3V2V1V9圖3.15由v1,v2和v3構成子回路（3）接著考慮剩余節點、、、、、，到、和中某一種節點最小距離；Min（4）由圖3.15可知，節點有3個位置（條弧線）可以插入。當前分析將加入到哪里適當：①插入到（1,2）間，△=d15+d52-d12=2.8+2-0.8=4②插入到（2,3）間，△=d25+d53-d23=2+1-1=2③插入到（3,1）間，△=d35+d51-d31=1+2.8-1.8=2比較上面3種狀況增量，插入（2,3）或（3,1）之間增量最小，任選其一，將節點加入到（2,3），因此成果為：T={v1,v2,v5v3，v1}其子回路V10V10V9V8V7V6V5V4V3V2V1圖3.16由v1,v2,v3和v5構成字回路（5）接著考慮剩余節點、、、、，到、、和中某一節點最小距離；Min（6）由圖3.16可知，節點有4個位置（條弧線）可以插入。當前分析將加入到哪里適當：①插入到（1,2）間，△=d16+d-d12=3.6+2.8-0.8=5.6②插入到（2,5）間，△=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）之間，則成果為：T={v1,v2,v,v，v，v1}其子回路則變為如圖3.17所示：V10V10V9V8V7V6V5V4V3V2V1圖3.17由v1,v2,v,v，v構成子回路(7)接著考慮剩余節點、、、，到、、、、中某一節點最小距離Min（8）由圖3.17可知，節點有5個位置（條弧線）可以插入。當前分析將加入到哪里適當：①插入到（1,2）間，△=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）之間，則成果為：T={、、、、、、}其子回路則變為圖3.18所示：V10V10V9V8V7V6V5V4V3V2V1圖3.18由、、、、、構成子回路（9）接著剩余節點、、，到、、、、、中某一節點最小距離Min（10）由圖3.18可知有6個位置（條弧線）可以插入。當前分析將加入到哪里適當：①插入到（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）之間增量最小，任選其一，因此將節點加入到（8,5）間，成果為：T={、、、、、、、}其子回路則變為圖3.19所示：V10V10V9V8V7V6V5V4V3V2V1圖3.19、、、、、、構成子回路（11）接著考慮剩余節點、、到、、、、、、中某一節點最小距離；Min（12）由圖3.19可知有7個位置（條弧線）可以插入。當前分析將加入到哪里適當：①插入到（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+d-d=1.6+3.4-1.8=3.2比較上面7種狀況增量，插入到（2,6）之間增量最小，因此將節點加入到（2,6）間，成果為：T={、、、、、、、、}其子回路則變圖3.20所示：V10V10V9V8V7V6V5V4V3V2V1圖3.20、、、、、、、構成子回路（13）接著考慮剩余節點、到、、、、、、、中某一節點最小距離；Min（14）由圖3.20可知有8個位置（條弧線）可以插入。當前分析將加入到哪里適當：①插入到（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-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）之間增量最小，任選其一，因此將節點加入到（10，5）間，成果為：T={、、、、、、、、、}其子回路如圖3.21所示：V10V10V9V8V7V6V5V4V3V2V1圖3.21、、、、、、、、構成子回路（15）最后考慮剩余節點到、、、、、、、、中某一節點最小距離；Min（16）有9個位置（條弧線）可以插入。當前分析將加入到哪里適當：①插入到（1,2）