基于圖論的自動化立體倉庫堆垛機(jī)揀選路徑優(yōu)化

蔣麗琳，張 弛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)

0 引 言

自動化立體倉庫采用高層立體貨架儲存物資，結(jié)合電子計(jì)算機(jī)控制技術(shù)和人工控制，實(shí)現(xiàn)貨物的存儲、輸送、分發(fā)與管理等功能。與傳統(tǒng)倉庫相比，自動化立體倉庫具有周轉(zhuǎn)速度快、空間利用率高等優(yōu)點(diǎn)。揀選作業(yè)是自動化立體倉庫常用的作業(yè)方式。據(jù)統(tǒng)計(jì)[1]，目前國內(nèi)大多數(shù)倉儲中心仍屬于勞動密集型產(chǎn)業(yè)，其中與揀選作業(yè)直接相關(guān)的人力占50%以上，揀選作業(yè)的時(shí)間投入也占整個(gè)倉儲中心的30%～40%。因此，合理解決揀選作業(yè)優(yōu)化調(diào)度能在一定程度上提高自動化立體倉庫的運(yùn)作效率。揀選作業(yè)的效率主要與堆垛機(jī)運(yùn)行速度和揀選路徑的選擇有關(guān)。根據(jù)目前國情，揀選作業(yè)所使用的堆垛機(jī)需人工控制，速度一般要在人的可控制范圍內(nèi)，所以堆垛機(jī)的速度不能大幅提高。對揀選作業(yè)，國內(nèi)學(xué)者一般把單個(gè)貨架的揀選問題抽象成旅行商 （TSP）問題研究[2-3]，而實(shí)際揀選作業(yè)中，被揀選貨品一般分散在不同的貨架上。

本文結(jié)合國內(nèi)自動化立體倉庫的實(shí)際情況，把揀選路徑構(gòu)造為一種閉環(huán)作業(yè)路徑，運(yùn)用圖論的方法進(jìn)行路徑優(yōu)化，并對路徑的優(yōu)化效果進(jìn)行了比較。

1 揀選作業(yè)路徑模型

自動化立體倉庫的布局如圖1所示，圖1顯示了倉庫的部分區(qū)域，共五排十五列貨架，該倉庫出入口處于同一位置。圖中的每個(gè)小方格表示立體貨架的一個(gè)單元貨格的位置，方格中的數(shù)字代表單元貨格的行列編號。

在堆垛機(jī)揀選開始前，由系統(tǒng)根據(jù)實(shí)際情況給每臺堆垛機(jī)分配一定數(shù)量的貨位，被分配的貨位點(diǎn)用圖1中帶陰影的小方格表示。圖中的實(shí)心小黑點(diǎn)表示堆垛機(jī)從貨架上取貨時(shí)，需要在倉庫中停留的位置點(diǎn)。

所有貨位點(diǎn)可以匯集到同一張圖上，任意兩個(gè)貨位點(diǎn)之間可以相互連接，即任意兩點(diǎn)間都有一條路徑，于是貨位點(diǎn)和路徑構(gòu)成了一張完全圖，如圖2所示。

每兩點(diǎn)之間的路徑可以根據(jù)兩點(diǎn)之間的到達(dá)距離來賦權(quán)值，賦權(quán)值的求解公式可以表示為：

其中，Δxij表示兩貨位點(diǎn)之間在x方向的水平距離；Δyij表示兩貨位點(diǎn)之間在y方向的水平距離，i、j表示點(diǎn)的編號。堆垛機(jī)的運(yùn)動路徑圖可以用矩陣的形式表示為：

式中，vi表示第i點(diǎn)，aij表示第i點(diǎn)和第j點(diǎn)之間的距離。利用本文的方法，通過對各個(gè)目標(biāo)貨位點(diǎn)之間的距離矩陣的求解來實(shí)現(xiàn)路徑的優(yōu)化。

2 基于圖論的倉庫路徑優(yōu)化算法

分支定界法是解圖的有限搜索的重要方法，常常用于在一個(gè)有限可供選擇的解集F中，尋求其函數(shù)值為最大或最小的解。如何對解空間進(jìn)行系統(tǒng)地搜索，依據(jù)優(yōu)化的目標(biāo)，盡可能多地刪除一些不必要的搜索，這是分支定界的重要思想。

算法主要包含以下過程：

（1）任選初始可行解。即任選一條可行的回路，回路所含的各條路徑距離的總和給原問題建立了一個(gè)上界，任何最優(yōu)解均不可能超過這個(gè)上界。巡回路線總長公式可以表示為：

其中ΦT表示一條哈密頓回路，dij表示Vi到Vj的距離。

（2）確定下界。路徑矩陣的行、列簡化不影響最優(yōu)回路的方案，若簡化以后各行各列零元素構(gòu)成了原問題的下界，則該回路即為最優(yōu)哈密頓回路。

ai為i行簡化值，bj為j列簡化值。

（3）分支。若路徑矩陣簡化以后，零元素雖不能構(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）全體回路所對應(yīng)的頂點(diǎn)的下界值便可以在降階以后的費(fèi)用矩陣中用前述方法確定。

（5）分支定界終止。連續(xù)分支定界過程，最終必可得到一條過網(wǎng)絡(luò)全部頂點(diǎn)的哈密頓回路。若下界值不能剪除所有其他分支，即尚有一些分支頂點(diǎn)及其下屆值更小，則需要回溯這類頂點(diǎn)，繼續(xù)上述的分支。

3 算法實(shí)例

現(xiàn)以某立體倉庫中一臺堆垛機(jī)的單次揀選路徑為例，以說明上述算法的使用方法及有效性。

根據(jù)貨位分配原則，在揀選前首先給堆垛機(jī)分配需要揀選的貨位，由貨位點(diǎn)的位置簡化得到堆垛機(jī)的停留點(diǎn)，兩兩連接各停留點(diǎn)，構(gòu)成揀選路徑的完全圖模型，并根據(jù)公式 （1）為圖中每條路徑賦權(quán)值。路徑矩陣如下：

用分支定界的方法對以上數(shù)據(jù)進(jìn)行處理， 任取上界路徑為 ΦT=（1,2,3,4,5 ）， 則 Z（ ΦT）=100+125+90+145=460 即為上界值。

經(jīng)過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)的選取的影響較大。例如，對于最鄰近法，本實(shí)例的計(jì)算結(jié)果為｛（1,3）,（3,5）,（5,4）,（4,2）,（2,1）｝， 權(quán)值為Z'=25+55+145+155=380。所以本文所采用的方法在起點(diǎn)確定的情況下能得到更加精確的解。

4 結(jié)束語

通過分析及論證，本文建立了用于規(guī)模在15個(gè)以下的自動化立體倉庫揀選路徑算法，并通過與傳統(tǒng)算法結(jié)果比較，證明了本方法的優(yōu)化效果。

[1]陳伊菲，劉軍.倉儲揀選作業(yè)路徑VRP模型設(shè)計(jì)與應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2006(6)：209-212.

[2]劉增曉，馮占營，吳建,等.揀選式自動化立體倉堆垛機(jī)作業(yè)路徑簡易優(yōu)化算法[J].起重運(yùn)輸機(jī)械，2006(8)：49-51.

[3]常發(fā)亮，劉增曉，辛征,等.自動化立體倉庫揀選作業(yè)路徑優(yōu)化問題研究[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.圖論簡明教程[M].北京：清華大學(xué)出版社，2005.