基于圖論的自動化立體倉庫堆垛機揀選路徑優化

蔣麗琳，張 弛JIANG Li-lin,ZHANG Chi

（1.上海理工大學，上海 200093；2.上海汽車集團股份有限公司商用車技術中心，上海 200438）

(1.University of Shanghai for Science and Technology,Shanghai 200093,China;2.Shanghai Automotive Industry Corporation,Shanghai 200438,China)

0 引 言

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

本文結合國內自動化立體倉庫的實際情況，把揀選路徑構造為一種閉環作業路徑，運用圖論的方法進行路徑優化，并對路徑的優化效果進行了比較。

1 揀選作業路徑模型

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

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

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

每兩點之間的路徑可以根據兩點之間的到達距離來賦權值，賦權值的求解公式可以表示為：

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

式中，vi表示第i點，aij表示第i點和第j點之間的距離。利用本文的方法，通過對各個目標貨位點之間的距離矩陣的求解來實現路徑的優化。

2 基于圖論的倉庫路徑優化算法

分支定界法是解圖的有限搜索的重要方法，常常用于在一個有限可供選擇的解集F中，尋求其函數值為最大或最小的解。如何對解空間進行系統地搜索，依據優化的目標，盡可能多地刪除一些不必要的搜索，這是分支定界的重要思想。

算法主要包含以下過程：

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

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

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

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

（3）分支。若路徑矩陣簡化以后，零元素雖不能構成哈密頓回路，但仍可以從這些元素中選擇一些邊構成回路。分支邊經選定設為（i,j），則在以后的討論中可以不需要考慮，為此可以刪除（i,j）所在的行列元素。（i,j）邊入選回路以后，為了避免在今后的分析中，由于（i,j）邊被入選而使｛（i,j）,（j,i）｝形成一個子回路。為此，降階后的費用矩陣中dji=∞，稱此類弧為禁用弧。

含（i,j）全體回路所對應的頂點的下界值便可以在降階以后的費用矩陣中用前述方法確定。

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

3 算法實例

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

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

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

經過Matlab編程計算， 得最優哈密頓路徑為｛（1,5）,（5,3）,（3,4）,（4,2）,（2,1）｝， 該路徑的權值之和為Z=45+90+55+155=345。由此可見用此方法可以快速地得到比較精確的最優路徑，該路徑如圖3所示，箭頭表示行進方向。

計算哈密頓路徑常用的方法還有最鄰近法和局部搜索法，這兩種方法最大的優點是求解的速度快，計算周期短，而最大的缺點在于所得結果的精確性受到初始點的選取的影響較大。例如，對于最鄰近法，本實例的計算結果為｛（1,3）,（3,5）,（5,4）,（4,2）,（2,1）｝， 權值為Z'=25+55+145+155=380。所以本文所采用的方法在起點確定的情況下能得到更加精確的解。

4 結束語

通過分析及論證，本文建立了用于規模在15個以下的自動化立體倉庫揀選路徑算法，并通過與傳統算法結果比較，證明了本方法的優化效果。

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

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

[3]常發亮，劉增曉，辛征,等.自動化立體倉庫揀選作業路徑優化問題研究[J].系統工程理論與實踐，2007(2)：139-143.

[4]高隨祥.圖論與網絡流理論[M].北京：高等教育出版社，2009.

[5]Kasyanov,V.N.Graph theory for programmers[M].北京：科學出版社，2006.

[6]Fred Buckley,Marty Lewinter.圖論簡明教程[M].北京：清華大學出版社，2005.