自動倉庫三叉堆垛機揀選作業的優化

王軍郝巖柱張楠/文

自動倉庫三叉堆垛機揀選作業的優化

王軍1郝巖柱2張楠2/文

自動化立體倉庫的廣泛應用要求計算機化的控制算法去支持其調度和揀選決策。本文針對一個三叉堆垛機揀選順序的問題進行研究，涉及一個三叉堆垛機存取操作，目標是通過算法計算，最大限度地減少堆垛機完成揀選任務單所需的時間。實踐證明，研究堆垛機揀選作業優化問題對自動化立體倉庫工作效率的提高具有重要意義。本文所研究的算法已經成功應用到上海煙草集團有限責任公司天津卷煙廠項目中。

自動化立體庫、堆垛機、揀選作業優化、節約算法

一、引言

自動化立體倉庫得到越來越廣泛的應用，主要原因在于它可靠性高且人為干預少，不僅能實現計算機智能管理，減少重復操作，還能避免一些有危險的人工操作，具有很大的經濟優勢。自動化立體倉庫的應用極大的提高了生產與配送效率，但同樣也存在一些難以解決的問題。如，每個項目中的貨位排序調度，為堆垛機產生揀選任務列表，以及管理規劃問題，都是自動化立體倉庫優化作業的目標。

在這當中，如何解決路徑優化問題是進一步提高自動化立體倉庫效率的關鍵，也是主要難題。本文通過節約算法對TSP問題求解來解決堆垛機揀選優化問題，即解決在立體倉庫中三叉堆垛機配三叉貨物用時最短所對應的三個貨位路徑。

二、系統概述

上海煙草集團有限責任公司天津卷煙廠自動化立體倉庫分為托盤區與料箱區：托盤庫由2個巷道組成，共4排×25列×18層=1800個貨位；料箱庫由4個巷道組成，共8排×48列×62層=23808個貨位，每個貨位一只料箱。檢定系統每日檢定15000只單相表，每日入庫20000只新表，因此采用三叉堆垛機來提高出入庫效率。

貨架采用牛腿貨架，每臺堆垛機可以對它的兩側貨架進行取放貨操作。貨位長度為1000毫米，高度為400毫米，并且所有的貨位都是相同的。堆垛機可在水平方向上和垂直方向上同時運動，且其加減速是線性的，行走最大速度為180米/分，升降最大速度為60米/分。

圖1 ：天津卷煙廠的堆垛機系統

圖2 ：天津卷煙廠的輸送系統

三、 堆垛機揀選優化算法

檢定出庫流程：倉儲系統接收生產系統下達的檢定計劃。當生產系統下達計劃（檢定單元）啟動命令、檢定單元批次要料信號及要料數量，倉儲系統自動分配出庫貨位生成搬運任務，由堆垛機、上層輸送機將指定貨位的料箱搬運至主輸送線上，經固定條碼1識讀校驗檢定料箱。校驗失敗的料箱輸送到異常處理工位，等待人工處理；正確的料箱輸送至檢定車間入口經固定條碼2進行分揀，再自動輸送到檢定單元暫存區。

堆垛機揀選作業優化指：在檢定出庫時調度系統調用優化算法對搬運任務重新排序，使三叉堆垛機取三個非連續貨位所用時間最短，從而提高工作效率。堆垛機揀選作業流程如圖3所示。

從圖3可以把堆垛機的揀選作業調度歸納成如下問題：設有3個揀選任務，即有3個貨位點等待堆垛機到達，堆垛機從出/入庫站臺處出發，分別到達3個貨位點，且每個貨位點只去1次，最后回到初始位置，求堆垛機運行時間最短。

這一問題類似于旅行商問題(TSP)。旅行商問題一般可描述為：1名旅行商從1個城市出發，訪遍n個城市1次且僅1次后返回原出發城市，求總距離最短的巡回路徑。現在，將TSP問題應用到堆垛機揀選作業控制系統上，即尋找1條巡回路徑T=(t1,t2, ,tn)，使得下列目標函數最小：

圖3 ：堆垛機揀選作業流程

通過上面目標函數可以看出，其解的搜索空間隨著揀選貨位數n的增加而增大，因此我們采用節約算法對其求解。

TSP問題求解：任意2個揀選貨位點之間的距離：貨位點以(x,y)表示，其中x為列，y為層，將2個貨位點i(x1,y1)和j(x2,y2)的運行時間表示為。初始位置坐標為(1,1)，用點0表示。設堆垛機從初始位置出發執行一批任務，這批任務包含3個揀選貨位，分別為(10,6)，(25,26)，(40,16)。執行完任務后，堆垛機回到初始位置(1,1)。將上述3個貨位分別用1、2、3代表。

在堆垛機執行揀選作業時，假設堆垛機在水平方向上和垂直方向上都是以恒高速運行，其制動和起動過程忽略不計。

將上述貨位(10,6)，(25,26)，(40,16)，以及行走最大速度為180米/分（3000毫米/秒），升降最大速度為60米/分（1000毫米/秒），貨位長度為1000毫米，高度為400毫米，代入上述公式即可得如下數據：

揀選貨位相對初始位置的運行時間坐標為(3S,2S)，(8S,10S)，(13S,6S)。表1為兩貨位間運行時間表。

表1 ：任意兩貨位間運行時間

四、運行結果

由于節約算法結構清晰，程序易讀，而且正確性容易得到驗證。本文通過C語言進行程序設計，并把該算法成功應用到堆垛機揀選作業系統中，程序運行結果如下：

從程序運行結果中，我們可以得出最優解為 (8S,10S)，(13S,6S)，(3S,2S)，即堆垛機最優路徑為從初始位置0到2號貨位，再到3號貨位，到1號貨位，最后返回到初始位置0處。最短時間為28秒。而通過表1組合排列法我們知道3個貨位共有6條路徑，分別為0-1-2-3-0、0-1-3-2-0、0-2-1-3-0、0-2-3-1-0、0-3-1-2-0、0-3-2-1-0，用時分別為：

3+8+5+13=29秒；

3+10+5+10=28秒；

10+8+10+13=41秒；

10+5+10+3=28秒；

13+10+8+10=41秒；

13+5+8+3=29秒；

由此可見運行時間最大路徑之一為(8S,10S)，(3S,2S)，(13S,6S)， 最長時間為41秒。通過比較我們發現一個三叉堆垛機一次揀選配貨過程就可以節約13秒。

五、 結論

在本文中，我們基于節約算法對TSP問題進行求解來解決自動化立體倉庫中堆垛機揀選作業問題。該算法是通過C程序編寫的，它能快速計算出堆垛機最短運行時間相應的路徑。實驗和工程應用表明：用TSP問題去解決自動化立體倉庫中堆垛機揀選作業問題是完全可行的，該應用能有效提高自動化立體倉庫堆垛機揀選作業的工作效率。

作者單位：1.上海煙草集團有限責任公司天津卷煙廠；2.沈陽新松機器人自動化股份有限公司