3堆垛機路徑優(yōu)化課程設計

1、3 3 堆垛機路徑優(yōu)化堆垛機路徑優(yōu)化3.13.1 路徑優(yōu)化概述路徑優(yōu)化概述自動化立體倉庫有被稱為自動存取系統(tǒng)（AS/RS）,采用高層貨架以貨箱和托盤儲存貨物，用巷道式堆垛機以及其他機械設備進行作業(yè)，有電子計算機管理和控制，不需要人工搬運而實現(xiàn)收發(fā)作業(yè)的倉庫。自動化立體倉庫可以節(jié)省時間，提高勞動效率，如實現(xiàn)這一點最理想的方案是讓貨位達到最優(yōu)的同時，堆垛機路徑達到最優(yōu)。要想讓堆垛機的路徑達到最優(yōu)，可以利用最短路徑問題解決。由于問題中邊的權值往往可以從距離引申為其他沿路徑線性積累的度量，如：時間、花費等，所以最短路徑問題在實際生活中有著廣泛的應用，如：城市規(guī)劃、交通導航、網絡尋優(yōu)等。在自動化立體倉庫

2、中利用最短路的思想，采用一定的數(shù)學方法，求得最優(yōu)的路徑，充分利用這一最優(yōu)路徑，節(jié)約貨物的取送時間，提高工作效率，節(jié)省勞動力的費用支出，從而提高倉庫的管理水平。3.23.2 堆垛機的選擇堆垛機的選擇巷道式堆垛機又稱為巷道式堆垛起重機，是自動化立體倉庫的關鍵設備之一負責將托盤貨物送到貨架儲存和從貨架中取出。它主要有機架 （上下橫梁、立柱） 、運行機構、升降機構（載貨平臺、卷揚機）、取物裝置（伸縮貨板、伸縮貨叉、取物機械手）、電器控制設備（電力控制、檢測、安全保護）構成。根據(jù)不同倉庫的需要，我們對倉庫所配備的堆垛機月有所不同，我們可以根據(jù)堆垛機的結構，起重量劃分為不同的類型。1）按結構形式不同分類：

3、橋式堆垛機、有軌巷道式堆垛機。2）按起重量不同分類：輕型堆垛機、中型堆垛機、重型堆垛機。3.23.2 設計條件設計條件隨機從圖 2 中的 20 個貨格中抽出 8 個貨格的貨物，分別用節(jié)點vl,v2,v3,v4,v5，v6，v7，v8 表示。節(jié)點間的距離用公式jXj+,H求解。Vx4(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)圖 3.1 最終的貨位規(guī)劃圖vy貨格大小為 L(長)XW(寬)XH(高)=1mX1mX0.8m，節(jié)點間的距離用直角距離公式DV 求解。V、

4、V兩個節(jié)點的距離隨機從圖 3.1 中的 25 個貨格中212抽出 A、J、W、E、P、Y 個貨格的貨物，分別用節(jié)點 vl,v2,v3,v4,v5,v6 表示。節(jié)點間的距離用直角距離公式dj二h-_xixL+imyxH求解。3.23.2 設計要求設計要求(1) 繪出貨格和節(jié)點相對位置圖及節(jié)點相對距離表(需要列式詳細計算各dij的值)。(2) 詳細地寫出最近鄰點法和最近插入法的每一步驟及計算結果。(3) 分析兩種方法的結果。(4) 利用熟悉的計算機語言編程實現(xiàn)最近鄰點法和最近插入法，打出源程序代碼及結果，要求與手工計算的結果一致。(5) 設計結束后，談談自己的看法。3.33.3 設計方法設計方法分

5、別用最近鄰點法和最近插入法找出堆垛機存取 6 個托盤貨物的合理路線。在堆垛機開始揀選之前，由于設備及系統(tǒng)根據(jù)實際情況每臺堆垛機分配一定數(shù)量的貨位，被分配的貨位用陰影的小方格表示，圖中的實心小黑點表示堆垛機從貨架上取貨時，需要在倉庫中停留的位置點，可以選用的方法的有最近零點法、最近插入發(fā)和遺傳算法等。3.43.4 求解過程求解過程3.4.1 初始數(shù)據(jù)的計算初始數(shù)據(jù)的計算1.首先根據(jù)設計要求，繪出貨格和節(jié)點相對位置圖如圖 3.2、3.3 所示。從中選出的八個點分別是 AV（1,1）,DV（1,3）,FV3（2,2）,CV4（2,1）,HV5V圖 3.3 貨格的相對位置圖2.計算所有節(jié)點之間的相對距

6、離解：由貨格相對位置知，用X，y標示貨格 A,D,F,C,H,E,P,Q 的相對位置即AV1（1,1），DV2（1，3），F(xiàn)V3jHV5（3,3），EV6（4,3），PV7計算公式：計算公式：d d=ij計算兩點之間的相對距離：dddddddddd353637384546474856572,2)4,1),-y yxHdd14y y 一jidd1213dddd5867CV4QV82,1),(4,5),H二0.9,(1-1)ddddd1516171823242526L L 二1.1dd166878計算過程如下：d=1(1-1)Ix1.1+l(3-1)lx0.9=1.812d=(|2-1)|x1.1

7、+(|2-1)|x0.9=213ddd272834d=1(1-1)丨xl.l+l(l-l)lx0.9=1.114d=l(3-1)lx1.1+l(1-1)lx0.9二415d=l(4-1)lx1.1+l(3-1)lx0.9二5.216d=l(4-1)lx1.1+l(1-1)lx0.9二3.317d=l(5-1)lx1.1+l(4-1)lx0.9二7.118d=l(2-1)lx1.1+l(3-2)lx0.9二223d=l(2-1)lx1.1+l(1-3)lx0.9=2.924d=l(3-1)lx1.1+l(3-3)lx0.9二2.225d=l(4-1)lx1.1+l(3-3)lx0.9二3.326

8、d=l(4-1)lx1.1+l(1-3)lx0.9二5.127d=l(5-1)lx1.1+l(4-3)lx0.9二5.328d=l(2-2)lx1.1+l(1-2)lx0.9二0.934d=l(3-2)lx1.1+l(3-2)lx0.9二235d=l(4-2)lx1.1+l(3-2)lx0.9二3.136d=l(4-2)lx1.1+l(1-2)lx0.9二3.137d=l(5-2)lx1.1+l(4-2)lx0.9二5.138d=l(3-2)lx1.1+l(3-1)1x0.9二2,945d=l(4-2)1x1.1+l(3-1)1x0.9二446d=l(4-2)lx1.1+l(1-1)1x0.9

9、二2.247d=l(5-2)lx1.1+l(4-1)lx0.9二648d=l(4-3)lx1.1+l(3-3)lx0.9二1.156d=l(4-3)1x1.1+l(3-1)1x0.9二2.957d=l(5-3)lx1.1+l(4-3)lx0.9二3.158d=l(4-4)lx1.1+l(1-3)lx0.9二1.867d=l(5-4)lx1.1+l(4-3)lx0.9二268d=l(5-4)1x1.1+l(4-1)1x0.9二3.8783.根據(jù)兩節(jié)點的相對距離繪制節(jié)點相對距離表 3.1：表 3.1 節(jié)點相對距離表VVVVVVVV元素元素V1.87.1V5

10、.15.3V0.9V_2.942.26VV1.82V3.8V3.4.2 最近鄰點法求堆垛機運行路徑最近鄰點法求堆垛機運行路徑1、最近鄰點法的思路從零點開始，作為整個回路的起點。找到剛剛加入到回路中的頂點最近的一個頂點，并將其加入到回路當中。重復步驟，直到所有頂點都加入到回路中。最后，將最后一個的頂點和起點連接起來。2、應用過程如下：先將節(jié)點V加入到回路中，TV。如圖 3.4 所示。11V(2) 從節(jié)點V出發(fā)，比較節(jié)點 2、3、4、5、6、7、8 的距離，選擇其最小1值，加入到回路中。mind|iGN,1i8，且i工1二d二1.1將v加1i144(3) 從節(jié)

11、點V出發(fā)，在節(jié)點 5、6、7、8 中，找出離V最近的節(jié)點。44mind|iGN,1i8二d二09ji34V3-VV圖 3.6V加入回路V3這樣就可以將V加入到回路中，T二3V，V，V，如圖 3.6 所示。143V圖 3.4 加入節(jié)點VV4入到回路中，如圖 3.5 所示。V圖 3.5V4加入回路V（4）從節(jié)點v出發(fā)，觀察離v最近的節(jié)點。mind|i；N,1i8,二dd=2二2(5)從節(jié)點V出發(fā)，觀察V最近的節(jié)點。22mind|iGN,1i8,d2.22i25從節(jié)點v出發(fā)，觀察v最近的節(jié)點。mind|iGN,V1i8,d1.15i56選V加入到回路中，TV,V,V,V,V,V，如圖 3.8 所示。

12、6143256如圖 3.9 所示。V 圖 3.9v加入到回路 V6(7)從節(jié)點V出發(fā)，觀察V最近的節(jié)點。mind|i；N,1iN8,二d二1.86iV67選V加入到回路中，T=V,V,V,V,V,V,V，如圖 3.971432567V圖T3.12 最近鄰點法求得的最終結果VVVVVVVV8VVV7(8)從節(jié)點V出發(fā)，觀察V最近的節(jié)點。發(fā)現(xiàn)V是最近的節(jié)點，也是最后一個節(jié)點，所以將將VV和V以及V和V直接相連。得到最后的解為 TV7881V,V,V,V,V,V,V,V,V,如圖 3.11 所示3.用最近鄰點發(fā)求的結果所以堆垛機的運行路線為：1T5T6T3T11T15T13T20即取送貨物的順序為：

13、ATCTFTDTHTETPTQ堆垛機總行駛距離為：F F 二1.1+0.9+2+2.2+1.1+1.8+7.1二3.4.3 最近插入法求堆垛機運行路線最近插入法求堆垛機運行路線1、最近插入法的思路vdvT衛(wèi)）先將節(jié)點1加入到回路中，找到1k最小的節(jié)點k，形成一個子回路，1k1。v在剩下的節(jié)點中，尋找一個離子回路中某一節(jié)點最近的節(jié)點k。在子回路中找到一條弧c訂，使得里程增量d+d-d最小。如果i,jvikvkjij有多條滿足條件， 任選一條， 然后將節(jié)點k插入到節(jié)點和vj 之間， 用兩條新的弧C,k）和 Ck,丿）代替原來的弧C,j），并將節(jié)點v加入到子回路中。重復步驟和，直到

14、所有的節(jié)點都加入到子回路中。2、應用過程v比較貨格相對距離表中從1出發(fā)的所有路徑的大小Vmind|ieN,1i8,且i畀=d=1.1這樣就由節(jié)點v和v構成的子回路，T=然后考慮剩下的節(jié)點v、v、v、235節(jié)點的最小距離mind|ieN,1i8,且iij這樣就由節(jié)點v，v，v，構成的子回路,143v，v、v、v到v和v中某一個67814畀=d=0.9T=v，v14v,v如圖31V14v，v如圖 3.13 所示。mind|ieNV,1i8,且i畀=d=1.8ij12由圖可知， 節(jié)點V有 3 個位置(條弧線)可以插入。 現(xiàn)在分析將V加入到哪合適： (1)插入到(1,4)間二 d d12+d d24+

15、d d14二1.8+2.9-1.1二4.7(2) 插入至【Q,3)間，A二 d d42+d d23+d d43二2.9+2-0.9二2(3) 插入至【6,3)間，&二d32+d d21+d31=2+1.8-2二1.8比較上面 3 種情況增量，插入到(3,1)之間的增量最小，所以將2節(jié)點插入到(3,1)(4)接著考慮剩下的節(jié)點V、V、V、V到V,V,V和V，某個節(jié)56781342點的最小距離：Vmind|ieN,1i8,且i1=d=2ij35由圖可知，節(jié)點V有 4 個位置(條弧線)可以插入。現(xiàn)在分析將V加入到哪里55合適：V8VVVV256V3VVVVV74V圖 3.15 由V1；V4,

16、V3,V2,構成的子回路所以結果為：T=(V1,V4,V3,V2,V1其子回路變?yōu)槿鐖D 3.15 所示的最小距離：(1)插入至【6.4)間，A二 d d15+d d54+d d14二4+2.9-1.1二6.8（2）插入至【（4,3）間，A二 C C45+C C53+C C43二2.9+2-0.9二4（3）插入至【（3,2）間，A=C C35+C C52+C C32二2+2.2-2二2.2（2）插入至【 （2,1）間，A=C C25+C C51+C C21=2.2+4-1.8二4.4比較上面 4 種情況增量，將V5插 入 到（3 , 2）間 增 量 最 小 ， 所 以 將 節(jié) 點V5節(jié) 點 加

17、入（5）接著考慮剩下的節(jié)點V、V、V到V,V，V，V和V，某個節(jié)67813452點的最小距離：Vmind|ieN,1i8,且iH1=d=1.1ijV56由圖可知，節(jié)點V有 4 個位置（條弧線）可以插入?，F(xiàn)在分析將V加入到哪里66合適：（1）插入至【（1.4）間，&二d d16+d d64+d d14二5.2+4-1.1二8.1（2）插入至【（4,3）間，二 d d46+d d63+C C43二4+3.1-0.9二6.2466343（3）插入至【（3,2）間，&二d36+d d65+d d35二3.1+1.1-2二2.2366535（4）插入到（2,1）間，&二d“+d“

18、+d“二1.1+3.32.2二2.2566252（5）插入至【（2,1）間，&二d26+d d61+d d二3.3+5.21.8二6.7266121比較上面 5 種情況增量，將V插入到（3,5）間增量最小，所以將節(jié)點V節(jié)點加66入到（3,5）間，結果為：T=V1,V4,V3,V2,V5,V6,V1）其子回路則變?yōu)槿鐖D 3.17 所示（6）接著考慮剩下的節(jié)點V、V到V,V,V,V,V和V，某個節(jié)78134562點的最小距離：Vmind|ieN,1i8,且i舁=d=1.8ijV67V由圖可知，節(jié)點V有 4 個位置（條弧線）可以插入。現(xiàn)在分析將V加入到哪77里合適：（1）插入至【（1.4）間

19、，&二d d17+d74+d14=3.3+3.1-1.1二5.3（2）插入至【（4,3）間，A二 d d47+d d73+C C43二2.2+3.1-0.9二4.4（3）插入到（3,6）間，&二d37+d d73+d d43二3.1+1.8-3.1二1.8（4）插入至【（6,5）間，&二d67+d d75+d d65二1.8+2.9-1.1二3.6677565（5）插入至【（5.2）間，A二 d d57+d d72+d d52二2.9+5.1-2.2二5.9（6）插入到（2,1）間，A二d27+d71+d21二5.1+3.31,8二6.6比較上面 6 種情況增量，將V7

20、插入到（3,6）間增量最小，所以將節(jié)點V7節(jié)點加入到（3,6）間，結果為：TfVJJfVJ 其子回路則變?yōu)槿鐖D 3.18（7）最后考慮剩下的節(jié)V到V,V，V，V,V，V、和V中某一節(jié)點的81345672jk.VVVVV2VVVVV4VV圖必 17 由構成的子回路最小距離：Vmind|ieN,1i8,且iH1=d=2ij68有 7 個位置（條弧線）可以插入。現(xiàn)在分析將v&加入到哪里最合適：（1）插入至【6.4）間，&二嘰+dA+d“二7.1+61.1二12188414（2）插入至【（4,3）間，二 d d48+d d83+C C43二6+5.10.9二10.2488343（3）插

21、入至【（3,6）間，A=d d38+d d86+d d365.1+23.1=4（4）插入至 0（6,7）間，Ad d68+d d87+d d752+688775（5）插入至【（5,2）間，Ad d55+d d82+d“3.1+558252（6）插入至【（2,1）間，Ad“+九+d“5.3+7.11.810.6288121（6）插入至【（7.5）間，A幾+d d 輕+d”3.8+788575所以堆垛機的運行路線為1T5T6T13T20T15T11T3T1幾取送貨物次序為：ATCTFTPTQTETHTDTA總距離為： F F+1.1+0.9+3

22、.1+3.8+2+1.1+2.2+1.816利用最近鄰點法所得的解所以堆垛機的運行路線為:1T5T6T3T11T15T13T20即取送貨物的順序為：ATCTFTDTHTETPTQ堆垛機總行駛距離為：F F1.1+0.9+2+2.2+1.1+1.8+7.116.2節(jié)省路線：比較上面 7 種情況增量，將V插入到（6,7）間增量最小，所以將節(jié)點V節(jié)點入到（6,7）間，結果為：T仝mmm 其子回路則變?yōu)槿鐖D 3.193.計算結果對比利用最近插入法所得的解 T-羅，VJf16.2160.2通過最終的結果對比，可得知，最近插入法所求得結果要優(yōu)于最近鄰點法所求得的結果。程序運行的最后結果如圖 3.19 所示

23、。3.53.5 總結總結通過這次的了解了什么是自動化立體倉庫貨位規(guī)劃和堆垛機路徑優(yōu)化問題，我所做的是堆垛機路徑優(yōu)化問題。通過這次的課程設計我懂得了堆垛機路線優(yōu)化的一些方法，并且通過使用不同的方法就行了堆垛機的線路優(yōu)化。是我印象深刻的是，當我最近鄰點法最近插入法來就行路線優(yōu)化是，的出來的結果完全不同。在堆垛機路線優(yōu)化問題上，最近插入法優(yōu)于最近鄰點法，但是過程比最近鄰點法復雜。堆垛機徑路的優(yōu)化是為了找到最佳的路線，提高揀貨效率，縮短揀貨距離、充分利用倉庫等作業(yè)效率改善指標來評定優(yōu)化的效果，要以最節(jié)省值的觀念來建立模型，在實際生活中，常常有最近鄰點法和最近插入法兩種方法。最近鄰點法是一種構造性啟發(fā)式算法。由于最近鄰點法能夠產生較優(yōu)解，所以可以利用它來構造禁忌搜索算法的初始解，從而更易于搜索到優(yōu)化問題的最優(yōu)解。最近鄰點法首先是從零點開始，作為整個回路的起點，再運用鄰點法的步驟，以距離最短的點為下一個點，依次將各點連起來，得到一條最短的路線。最近插入法是選取第一個點作為線路的種子點，再根據(jù)最近插入法