王軍郝巖柱張楠/文

自動(dòng)倉庫三叉堆垛機(jī)揀選作業(yè)的優(yōu)化

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

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

自動(dòng)化立體庫、堆垛機(jī)、揀選作業(yè)優(yōu)化、節(jié)約算法

一、引言

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

在這當(dāng)中，如何解決路徑優(yōu)化問題是進(jìn)一步提高自動(dòng)化立體倉庫效率的關(guān)鍵，也是主要難題。本文通過節(jié)約算法對TSP問題求解來解決堆垛機(jī)揀選優(yōu)化問題，即解決在立體倉庫中三叉堆垛機(jī)配三叉貨物用時(shí)最短所對應(yīng)的三個(gè)貨位路徑。

二、系統(tǒng)概述

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

貨架采用牛腿貨架，每臺(tái)堆垛機(jī)可以對它的兩側(cè)貨架進(jìn)行取放貨操作。貨位長度為1000毫米，高度為400毫米，并且所有的貨位都是相同的。堆垛機(jī)可在水平方向上和垂直方向上同時(shí)運(yùn)動(dòng)，且其加減速是線性的，行走最大速度為180米/分，升降最大速度為60米/分。

圖1 ：天津卷煙廠的堆垛機(jī)系統(tǒng)

圖2 ：天津卷煙廠的輸送系統(tǒng)

三、 堆垛機(jī)揀選優(yōu)化算法

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

堆垛機(jī)揀選作業(yè)優(yōu)化指：在檢定出庫時(shí)調(diào)度系統(tǒng)調(diào)用優(yōu)化算法對搬運(yùn)任務(wù)重新排序，使三叉堆垛機(jī)取三個(gè)非連續(xù)貨位所用時(shí)間最短，從而提高工作效率。堆垛機(jī)揀選作業(yè)流程如圖3所示。

從圖3可以把堆垛機(jī)的揀選作業(yè)調(diào)度歸納成如下問題：設(shè)有3個(gè)揀選任務(wù)，即有3個(gè)貨位點(diǎn)等待堆垛機(jī)到達(dá)，堆垛機(jī)從出/入庫站臺(tái)處出發(fā)，分別到達(dá)3個(gè)貨位點(diǎn)，且每個(gè)貨位點(diǎn)只去1次，最后回到初始位置，求堆垛機(jī)運(yùn)行時(shí)間最短。

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

圖3 ：堆垛機(jī)揀選作業(yè)流程

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

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

在堆垛機(jī)執(zhí)行揀選作業(yè)時(shí)，假設(shè)堆垛機(jī)在水平方向上和垂直方向上都是以恒高速運(yùn)行，其制動(dòng)和起動(dòng)過程忽略不計(jì)。

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

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

表1 ：任意兩貨位間運(yùn)行時(shí)間

四、運(yùn)行結(jié)果

由于節(jié)約算法結(jié)構(gòu)清晰，程序易讀，而且正確性容易得到驗(yàn)證。本文通過C語言進(jìn)行程序設(shè)計(jì)，并把該算法成功應(yīng)用到堆垛機(jī)揀選作業(yè)系統(tǒng)中，程序運(yùn)行結(jié)果如下：

從程序運(yùn)行結(jié)果中，我們可以得出最優(yōu)解為 (8S,10S)，(13S,6S)，(3S,2S)，即堆垛機(jī)最優(yōu)路徑為從初始位置0到2號貨位，再到3號貨位，到1號貨位，最后返回到初始位置0處。最短時(shí)間為28秒。而通過表1組合排列法我們知道3個(gè)貨位共有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，用時(shí)分別為：

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秒；

由此可見運(yùn)行時(shí)間最大路徑之一為(8S,10S)，(3S,2S)，(13S,6S)， 最長時(shí)間為41秒。通過比較我們發(fā)現(xiàn)一個(gè)三叉堆垛機(jī)一次揀選配貨過程就可以節(jié)約13秒。

五、 結(jié)論

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

作者單位：1.上海煙草集團(tuán)有限責(zé)任公司天津卷煙廠；2.沈陽新松機(jī)器人自動(dòng)化股份有限公司