蔣麗琳,張 弛JIANG Li-lin,ZHANG Chi
(1.上海理工大學(xué),上海 200093;2.上海汽車集團(tuán)股份有限公司商用車技術(shù)中心,上海 200438)
(1.University of Shanghai for Science and Technology,Shanghai 200093,China;2.Shanghai Automotive Industry Corporation,Shanghai 200438,China)
自動(dòng)化立體倉(cāng)庫(kù)采用高層立體貨架儲(chǔ)存物資,結(jié)合電子計(jì)算機(jī)控制技術(shù)和人工控制,實(shí)現(xiàn)貨物的存儲(chǔ)、輸送、分發(fā)與管理等功能。與傳統(tǒng)倉(cāng)庫(kù)相比,自動(dòng)化立體倉(cāng)庫(kù)具有周轉(zhuǎn)速度快、空間利用率高等優(yōu)點(diǎn)。揀選作業(yè)是自動(dòng)化立體倉(cāng)庫(kù)常用的作業(yè)方式。據(jù)統(tǒng)計(jì)[1],目前國(guó)內(nèi)大多數(shù)倉(cāng)儲(chǔ)中心仍屬于勞動(dòng)密集型產(chǎn)業(yè),其中與揀選作業(yè)直接相關(guān)的人力占50%以上,揀選作業(yè)的時(shí)間投入也占整個(gè)倉(cāng)儲(chǔ)中心的30%~40%。因此,合理解決揀選作業(yè)優(yōu)化調(diào)度能在一定程度上提高自動(dòng)化立體倉(cāng)庫(kù)的運(yùn)作效率。揀選作業(yè)的效率主要與堆垛機(jī)運(yùn)行速度和揀選路徑的選擇有關(guān)。根據(jù)目前國(guó)情,揀選作業(yè)所使用的堆垛機(jī)需人工控制,速度一般要在人的可控制范圍內(nèi),所以堆垛機(jī)的速度不能大幅提高。對(duì)揀選作業(yè),國(guó)內(nèi)學(xué)者一般把單個(gè)貨架的揀選問(wèn)題抽象成旅行商 (TSP)問(wèn)題研究[2-3],而實(shí)際揀選作業(yè)中,被揀選貨品一般分散在不同的貨架上。
本文結(jié)合國(guó)內(nèi)自動(dòng)化立體倉(cāng)庫(kù)的實(shí)際情況,把揀選路徑構(gòu)造為一種閉環(huán)作業(yè)路徑,運(yùn)用圖論的方法進(jìn)行路徑優(yōu)化,并對(duì)路徑的優(yōu)化效果進(jìn)行了比較。
自動(dòng)化立體倉(cāng)庫(kù)的布局如圖1所示,圖1顯示了倉(cāng)庫(kù)的部分區(qū)域,共五排十五列貨架,該倉(cāng)庫(kù)出入口處于同一位置。圖中的每個(gè)小方格表示立體貨架的一個(gè)單元貨格的位置,方格中的數(shù)字代表單元貨格的行列編號(hào)。
在堆垛機(jī)揀選開始前,由系統(tǒng)根據(jù)實(shí)際情況給每臺(tái)堆垛機(jī)分配一定數(shù)量的貨位,被分配的貨位點(diǎn)用圖1中帶陰影的小方格表示。圖中的實(shí)心小黑點(diǎn)表示堆垛機(jī)從貨架上取貨時(shí),需要在倉(cāng)庫(kù)中停留的位置點(diǎn)。
所有貨位點(diǎn)可以匯集到同一張圖上,任意兩個(gè)貨位點(diǎn)之間可以相互連接,即任意兩點(diǎn)間都有一條路徑,于是貨位點(diǎn)和路徑構(gòu)成了一張完全圖,如圖2所示。
每?jī)牲c(diǎn)之間的路徑可以根據(jù)兩點(diǎn)之間的到達(dá)距離來(lái)賦權(quán)值,賦權(quán)值的求解公式可以表示為:
其中,Δxij表示兩貨位點(diǎn)之間在x方向的水平距離;Δyij表示兩貨位點(diǎn)之間在y方向的水平距離,i、j表示點(diǎn)的編號(hào)。堆垛機(jī)的運(yùn)動(dòng)路徑圖可以用矩陣的形式表示為:
式中,vi表示第i點(diǎn),aij表示第i點(diǎn)和第j點(diǎn)之間的距離。利用本文的方法,通過(guò)對(duì)各個(gè)目標(biāo)貨位點(diǎn)之間的距離矩陣的求解來(lái)實(shí)現(xiàn)路徑的優(yōu)化。
分支定界法是解圖的有限搜索的重要方法,常常用于在一個(gè)有限可供選擇的解集F中,尋求其函數(shù)值為最大或最小的解。如何對(duì)解空間進(jìn)行系統(tǒng)地搜索,依據(jù)優(yōu)化的目標(biāo),盡可能多地刪除一些不必要的搜索,這是分支定界的重要思想。
算法主要包含以下過(guò)程:
(1)任選初始可行解。即任選一條可行的回路,回路所含的各條路徑距離的總和給原問(wèn)題建立了一個(gè)上界,任何最優(yōu)解均不可能超過(guò)這個(gè)上界。巡回路線總長(zhǎng)公式可以表示為:
其中ΦT表示一條哈密頓回路,dij表示Vi到Vj的距離。
(2)確定下界。路徑矩陣的行、列簡(jiǎn)化不影響最優(yōu)回路的方案,若簡(jiǎn)化以后各行各列零元素構(gòu)成了原問(wèn)題的下界,則該回路即為最優(yōu)哈密頓回路。
ai為i行簡(jiǎn)化值,bj為j列簡(jiǎn)化值。
(3)分支。若路徑矩陣簡(jiǎn)化以后,零元素雖不能構(gòu)成哈密頓回路,但仍可以從這些元素中選擇一些邊構(gòu)成回路。分支邊經(jīng)選定設(shè)為(i,j),則在以后的討論中可以不需要考慮,為此可以刪除(i,j)所在的行列元素。(i,j)邊入選回路以后,為了避免在今后的分析中,由于(i,j)邊被入選而使{(i,j),(j,i)}形成一個(gè)子回路。為此,降階后的費(fèi)用矩陣中dji=∞,稱此類弧為禁用弧。
含(i,j)全體回路所對(duì)應(yīng)的頂點(diǎn)的下界值便可以在降階以后的費(fèi)用矩陣中用前述方法確定。
(5)分支定界終止。連續(xù)分支定界過(guò)程,最終必可得到一條過(guò)網(wǎng)絡(luò)全部頂點(diǎn)的哈密頓回路。若下界值不能剪除所有其他分支,即尚有一些分支頂點(diǎn)及其下屆值更小,則需要回溯這類頂點(diǎn),繼續(xù)上述的分支。
現(xiàn)以某立體倉(cāng)庫(kù)中一臺(tái)堆垛機(jī)的單次揀選路徑為例,以說(shuō)明上述算法的使用方法及有效性。
根據(jù)貨位分配原則,在揀選前首先給堆垛機(jī)分配需要揀選的貨位,由貨位點(diǎn)的位置簡(jiǎn)化得到堆垛機(jī)的停留點(diǎn),兩兩連接各停留點(diǎn),構(gòu)成揀選路徑的完全圖模型,并根據(jù)公式 (1)為圖中每條路徑賦權(quán)值。路徑矩陣如下:
用分支定界的方法對(duì)以上數(shù)據(jù)進(jìn)行處理, 任取上界路徑為 ΦT=(1,2,3,4,5 ), 則 Z( ΦT)=100+125+90+145=460 即為上界值。
經(jīng)過(guò)Matlab編程計(jì)算, 得最優(yōu)哈密頓路徑為{(1,5),(5,3),(3,4),(4,2),(2,1)}, 該路徑的權(quán)值之和為Z=45+90+55+155=345。由此可見用此方法可以快速地得到比較精確的最優(yōu)路徑,該路徑如圖3所示,箭頭表示行進(jìn)方向。
計(jì)算哈密頓路徑常用的方法還有最鄰近法和局部搜索法,這兩種方法最大的優(yōu)點(diǎn)是求解的速度快,計(jì)算周期短,而最大的缺點(diǎn)在于所得結(jié)果的精確性受到初始點(diǎn)的選取的影響較大。例如,對(duì)于最鄰近法,本實(shí)例的計(jì)算結(jié)果為{(1,3),(3,5),(5,4),(4,2),(2,1)}, 權(quán)值為Z'=25+55+145+155=380。所以本文所采用的方法在起點(diǎn)確定的情況下能得到更加精確的解。
通過(guò)分析及論證,本文建立了用于規(guī)模在15個(gè)以下的自動(dòng)化立體倉(cāng)庫(kù)揀選路徑算法,并通過(guò)與傳統(tǒng)算法結(jié)果比較,證明了本方法的優(yōu)化效果。
[1]陳伊菲,劉軍.倉(cāng)儲(chǔ)揀選作業(yè)路徑VRP模型設(shè)計(jì)與應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2006(6):209-212.
[2]劉增曉,馮占營(yíng),吳建,等.揀選式自動(dòng)化立體倉(cāng)堆垛機(jī)作業(yè)路徑簡(jiǎn)易優(yōu)化算法[J].起重運(yùn)輸機(jī)械,2006(8):49-51.
[3]常發(fā)亮,劉增曉,辛征,等.自動(dòng)化立體倉(cāng)庫(kù)揀選作業(yè)路徑優(yōu)化問(wèn)題研究[J].系統(tǒng)工程理論與實(shí)踐,2007(2):139-143.
[4]高隨祥.圖論與網(wǎng)絡(luò)流理論[M].北京:高等教育出版社,2009.
[5]Kasyanov,V.N.Graph theory for programmers[M].北京:科學(xué)出版社,2006.
[6]Fred Buckley,Marty Lewinter.圖論簡(jiǎn)明教程[M].北京:清華大學(xué)出版社,2005.