3堆垛機(jī)路徑優(yōu)化課程設(shè)計(jì)

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

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

3、橋式堆垛機(jī)、有軌巷道式堆垛機(jī)。2）按起重量不同分類：輕型堆垛機(jī)、中型堆垛機(jī)、重型堆垛機(jī)。3.23.2 設(shè)計(jì)條件設(shè)計(jì)條件隨機(jī)從圖 2 中的 20 個(gè)貨格中抽出 8 個(gè)貨格的貨物，分別用節(jié)點(diǎn)vl,v2,v3,v4,v5，v6，v7，v8 表示。節(jié)點(diǎn)間的距離用公式j(luò)Xj+,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é)點(diǎn)間的距離用直角距離公式DV 求解。V、

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

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

6、離解：由貨格相對(duì)位置知，用X，y標(biāo)示貨格 A,D,F,C,H,E,P,Q 的相對(duì)位置即AV1（1,1），DV2（1，3），F(xiàn)V3jHV5（3,3），EV6（4,3），PV7計(jì)算公式：計(jì)算公式：d d=ij計(jì)算兩點(diǎn)之間的相對(duì)距離：dddddddddd353637384546474856572,2)4,1),-y yxHdd14y y 一jidd1213dddd5867CV4QV82,1),(4,5),H二0.9,(1-1)ddddd1516171823242526L L 二1.1dd166878計(jì)算過程如下：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é)點(diǎn)的相對(duì)距離繪制節(jié)點(diǎn)相對(duì)距離表 3.1：表 3.1 節(jié)點(diǎn)相對(duì)距離表VVVVVVVV元素元素V1.87.1V5

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

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

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

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

14、所有的節(jié)點(diǎn)都加入到子回路中。2、應(yīng)用過程v比較貨格相對(duì)距離表中從1出發(fā)的所有路徑的大小Vmind|ieN,1i8,且i畀=d=1.1這樣就由節(jié)點(diǎn)v和v構(gòu)成的子回路，T=然后考慮剩下的節(jié)點(diǎn)v、v、v、235節(jié)點(diǎn)的最小距離mind|ieN,1i8,且iij這樣就由節(jié)點(diǎn)v，v，v，構(gòu)成的子回路,143v，v、v、v到v和v中某一個(gè)67814畀=d=0.9T=v，v14v,v如圖31V14v，v如圖 3.13 所示。mind|ieNV,1i8,且i畀=d=1.8ij12由圖可知， 節(jié)點(diǎn)V有 3 個(gè)位置(條弧線)可以插入。 現(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é)點(diǎn)插入到(3,1)(4)接著考慮剩下的節(jié)點(diǎn)V、V、V、V到V,V,V和V，某個(gè)節(jié)56781342點(diǎn)的最小距離：Vmind|ieN,1i8,且i1=d=2ij35由圖可知，節(jié)點(diǎn)V有 4 個(gè)位置(條弧線)可以插入?，F(xiàn)在分析將V加入到哪里55合適：V8VVVV256V3VVVVV74V圖 3.15 由V1；V4,

16、V3,V2,構(gòu)成的子回路所以結(jié)果為：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é) 點(diǎn)V5節(jié) 點(diǎn) 加

17、入（5）接著考慮剩下的節(jié)點(diǎn)V、V、V到V,V，V，V和V，某個(gè)節(jié)67813452點(diǎn)的最小距離：Vmind|ieN,1i8,且iH1=d=1.1ijV56由圖可知，節(jié)點(diǎn)V有 4 個(gè)位置（條弧線）可以插入?，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é)點(diǎn)V節(jié)點(diǎn)加66入到（3,5）間，結(jié)果為：T=V1,V4,V3,V2,V5,V6,V1）其子回路則變?yōu)槿鐖D 3.17 所示（6）接著考慮剩下的節(jié)點(diǎn)V、V到V,V,V,V,V和V，某個(gè)節(jié)78134562點(diǎn)的最小距離：Vmind|ieN,1i8,且i舁=d=1.8ijV67V由圖可知，節(jié)點(diǎn)V有 4 個(gè)位置（條弧線）可以插入?，F(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é)點(diǎn)V7節(jié)點(diǎn)加入到（3,6）間，結(jié)果為：TfVJJfVJ 其子回路則變?yōu)槿鐖D 3.18（7）最后考慮剩下的節(jié)V到V,V，V，V,V，V、和V中某一節(jié)點(diǎn)的81345672jk.VVVVV2VVVVV4VV圖必 17 由構(gòu)成的子回路最小距離：Vmind|ieN,1i8,且iH1=d=2ij68有 7 個(gè)位置（條弧線）可以插入?，F(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所以堆垛機(jī)的運(yùn)行路線為1T5T6T13T20T15T11T3T1幾取送貨物次序?yàn)椋篈TCTFTPTQTETHTDTA總距離為： F F+1.1+0.9+3

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

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