劉萬(wàn)強(qiáng), 周亞勤, 楊建國(guó), 尤 祥

(東華大學(xué) 機(jī)械工程學(xué)院, 上海 201620)

新型棋盤(pán)格密集倉(cāng)庫(kù)的出入庫(kù)貨位分配優(yōu)化

劉萬(wàn)強(qiáng), 周亞勤, 楊建國(guó), 尤 祥

(東華大學(xué) 機(jī)械工程學(xué)院, 上海 201620)

從提升有軌自動(dòng)化小車(chē)(RGV)出入庫(kù)作業(yè)效率的角度出發(fā), 在綜合考慮RGV加減速和行走方向改變所帶來(lái)的影響前提下, 對(duì)新型棋盤(pán)格密集倉(cāng)庫(kù)出入庫(kù)復(fù)合作業(yè)模式下的貨位分配問(wèn)題進(jìn)行研究, 設(shè)計(jì)了基于混合遺傳算法的出入庫(kù)貨位分配算法, 以對(duì)貨位分配問(wèn)題進(jìn)行求解.仿真試驗(yàn)結(jié)果證明,該算法能有效解決不同規(guī)模下新型棋盤(pán)格密集倉(cāng)庫(kù)的貨位分配問(wèn)題, 使RGV的整體作業(yè)效率提升40%左右, 并且具有貨架規(guī)模越大則效率提升越明顯的優(yōu)勢(shì).

棋盤(pán)格密集倉(cāng)庫(kù); 貨位分配; 遺傳算法(GA); 有軌自動(dòng)化小車(chē)(RGV)

新型棋盤(pán)格密集倉(cāng)庫(kù)是一種由多層棋盤(pán)格貨架(MCB)[1]和有軌自動(dòng)化小車(chē)(rail guided vehicle, RGV)組成的新型自動(dòng)化立體倉(cāng)庫(kù).其作為一種全新的倉(cāng)儲(chǔ)模式, 既能滿足貨物的密集式儲(chǔ)存, 又能滿足貨物的隨機(jī)存取, 具有巨大的市場(chǎng)應(yīng)用前景.在物流倉(cāng)儲(chǔ)行業(yè)中, 衡量自動(dòng)化倉(cāng)庫(kù)好壞的重要指標(biāo)是工作效率, 如何提升作業(yè)效率[2]成了新型棋盤(pán)格密集倉(cāng)庫(kù)亟待解決的問(wèn)題, 而貨位分配是實(shí)現(xiàn)自動(dòng)化倉(cāng)庫(kù)高效運(yùn)作的瓶頸.

國(guó)內(nèi)外學(xué)者對(duì)自動(dòng)化立體倉(cāng)庫(kù)的貨位分配進(jìn)行了大量的研究.肖建等[3]根據(jù)物料相關(guān)性及需求頻率, 研究多巷道倉(cāng)庫(kù)貨位分配的優(yōu)化問(wèn)題.楊朋[4]在提升堆垛機(jī)工作效率方面對(duì)多載具AS/RS(automated storage and retvieval system)的貨位優(yōu)化分配問(wèn)題進(jìn)行了研究. Chen等[5]根據(jù)停留持續(xù)時(shí)間的共享存儲(chǔ)原則,對(duì)貨位分配和交叉存取問(wèn)題進(jìn)行了研究.Pan等[6]提出一種基于啟發(fā)式的遺傳算法來(lái)求解貨位分配問(wèn)題, 通過(guò)平衡各采摘區(qū)的工作量來(lái)提高倉(cāng)儲(chǔ)作業(yè)效率.Onut等[7]在貨位布局設(shè)計(jì)模型方面, 對(duì)降低倉(cāng)庫(kù)年運(yùn)作成本進(jìn)行了研究.

但目前對(duì)自動(dòng)化立體倉(cāng)庫(kù)貨位分配的研究仍存在一些不足.多數(shù)研究假設(shè)搬運(yùn)設(shè)備為勻速運(yùn)動(dòng), 未考慮加減速度或行走方向改變的影響, 難以體現(xiàn)實(shí)際的作業(yè)特點(diǎn); 且目前多數(shù)研究?jī)H單獨(dú)考慮入庫(kù)貨物或出庫(kù)貨物的貨位分配, 并沒(méi)有考慮出入庫(kù)復(fù)合作業(yè)模式下的貨位分配. 因此, 本文從提升新型棋盤(pán)格密集倉(cāng)庫(kù)RGV作業(yè)效率的角度出發(fā), 綜合考慮RGV的加減速和行程方向改變的影響, 對(duì)新型棋盤(pán)格密集倉(cāng)庫(kù)出入庫(kù)復(fù)合作業(yè)模式下的貨位分配問(wèn)題進(jìn)行研究, 設(shè)計(jì)基于混合遺傳算法[8-10]的出入庫(kù)貨位分配算法, 對(duì)出入庫(kù)復(fù)合模式下的貨位分配進(jìn)行優(yōu)化.

1 貨位分配模型的建立

1.1貨位分配優(yōu)化問(wèn)題的定義

新型棋盤(pán)格密集倉(cāng)庫(kù)主要由棋盤(pán)格立體貨架、RGV和底層輸送裝置構(gòu)成(如圖1所示).其中, 棋盤(pán)格立體貨架由貨位和通道組成, RGV由母車(chē)和子車(chē)組成, 底層輸送裝置又由出庫(kù)輸送裝置和入庫(kù)輸送裝置組成, 出庫(kù)輸送裝置連接所有通道, 入庫(kù)輸送裝置僅連接入口通道.棋盤(pán)格立體貨架是一個(gè)三維立體貨架, 規(guī)模大小為M×N×K，其中M為總行數(shù)、N為總列數(shù)和K為總層數(shù). 每個(gè)貨位具有相同尺寸, 長(zhǎng)和寬同為x, 高為h.通道用于RGV子車(chē)的縱向升降并抓取貨物, 其中，入口通道既可用于貨物的出庫(kù)又可用于入庫(kù).

圖1 多層棋盤(pán)格立體貨架結(jié)構(gòu)圖Fig.1 Structure diagram of multilayers checkerboard based shelf

新型棋盤(pán)格密集倉(cāng)庫(kù)作業(yè)規(guī)則描述: (1) RGV母車(chē)在貨架頂層行走; (2) RGV子車(chē)在貨架通道中升降; (3) 棋盤(pán)格立體倉(cāng)庫(kù)在進(jìn)行出庫(kù)作業(yè)時(shí), RGV母車(chē)到達(dá)出庫(kù)貨位的相鄰?fù)ǖ? 子車(chē)通過(guò)通道運(yùn)行到貨物所在層取出貨物, 并通過(guò)該通道將貨物放置底層出庫(kù)輸送裝置完成出庫(kù); (4) 進(jìn)行入庫(kù)作業(yè)時(shí), RGV母車(chē)需先到達(dá)入口通道處, 通過(guò)子車(chē)抓取入庫(kù)輸送裝置上的貨物, 然后通過(guò)RGV母車(chē)運(yùn)至目標(biāo)貨位的相鄰?fù)ǖ? 子車(chē)通過(guò)該通道將貨物放置目標(biāo)貨位完成入庫(kù); (5) RGV母車(chē)作業(yè)時(shí)存在4個(gè)過(guò)程, 分別是加速、勻速、減速和停止前的爬行, 且行程方向每改變一次就增加一次加減速和爬行過(guò)程.

出入庫(kù)貨位分配優(yōu)化問(wèn)題, 即根據(jù)需要出入庫(kù)的貨物信息和貨架當(dāng)前儲(chǔ)存狀態(tài), 基于新型棋盤(pán)格密集倉(cāng)庫(kù)作業(yè)規(guī)則, 綜合考慮RGV母車(chē)加減速和行走方向改變對(duì)RGV母車(chē)行走效率的影響, 合理分配貨物的出入庫(kù)貨位, 并制定最優(yōu)任務(wù)執(zhí)行順序, 使RGV在最短時(shí)間內(nèi)完成所有出入庫(kù)任務(wù).

1.2約束條件

根據(jù)RGV承載能力限制、單個(gè)貨位的存儲(chǔ)量限制以及貨架當(dāng)前存儲(chǔ)狀態(tài)等基本信息, 建立貨位分配問(wèn)題的約束條件:

(1) RGV在貨架頂層只能沿x、y軸方向直線行走;

(2) 一臺(tái)RGV每次只能搬運(yùn)一個(gè)貨物;

(3) 貨架中一個(gè)貨位只能存放一個(gè)貨物;

(4) 同種出庫(kù)貨物的數(shù)量應(yīng)不大于倉(cāng)庫(kù)中該種貨物的數(shù)量;

(5) 入庫(kù)貨物的數(shù)量應(yīng)不大于倉(cāng)庫(kù)中的空貨位數(shù)量;

(6) 入庫(kù)隊(duì)列和出庫(kù)隊(duì)列貨物的種類已知, 且兩個(gè)隊(duì)列之間無(wú)相同種類貨物, 否則直接從出庫(kù)隊(duì)列將貨物取走, 無(wú)須進(jìn)入倉(cāng)庫(kù);

(7) 由于行程方向的改變會(huì)增加RGV的加減速次數(shù), 從而降低RGV的整體行走效率.因此, 將RGV在起始點(diǎn)和目標(biāo)通道間行走時(shí)的方向改變次數(shù)限制為一次.

1.3目標(biāo)函數(shù)

貨位分配的最終目標(biāo)是使RGV以最短的時(shí)間toc執(zhí)行完所有出入庫(kù)任務(wù), 因此以RGV作業(yè)時(shí)間的總和作為目標(biāo)函數(shù).由于RGV作業(yè)時(shí)間分為RGV母車(chē)頂層的行走時(shí)間和子車(chē)的升降時(shí)間, 所以需分別對(duì)兩部分時(shí)間建立相應(yīng)的函數(shù)模型并求和.建立目標(biāo)函數(shù)模型將用到的變量符號(hào)及其定義如表1所示.

表1 變量符號(hào)及定義Table 1 Symbols and definitions

(1)RGV母車(chē)行走時(shí)間的計(jì)算模型.RGV母車(chē)在貨架頂層行走時(shí)分為4個(gè)階段, 如圖2所示.由于RGV母車(chē)停止前的爬行位移極短, 可忽略, 將模型簡(jiǎn)化成三個(gè)階段, 如圖3所示.RGV母車(chē)行走時(shí)又存在兩種行走狀態(tài)：行走距離較短時(shí), 達(dá)不到最大運(yùn)行速度的狀態(tài); 行走距離較大時(shí), 達(dá)到最大運(yùn)行速度的狀態(tài).

圖2 RGV母車(chē)速度-時(shí)間圖Fig. 2 Graph of RGV car motion-time

圖3 RGV母車(chē)速度-時(shí)間簡(jiǎn)化圖Fig. 3 Simplified graph of RGV car motion-time

RGV在執(zhí)行出入庫(kù)任務(wù)時(shí), 由于起始點(diǎn)和目標(biāo)通道常常不在一條直線上, 導(dǎo)致RGV母車(chē)行走方向發(fā)生改變, 需沿x(y)軸方向行走后, 需再沿y(x)軸方向行走.因此, 在計(jì)算RGV母車(chē)行走時(shí)間時(shí), 需對(duì)x、y兩個(gè)方向分別計(jì)算并求和.RGV母車(chē)在起始點(diǎn)和目標(biāo)通道間行走時(shí)間的計(jì)算模型如式(1)所示.

(1)

由于新型棋盤(pán)格密集倉(cāng)庫(kù)出庫(kù)作業(yè)和入庫(kù)作業(yè)的規(guī)則不同, 因此RGV執(zhí)行出庫(kù)任務(wù)和入庫(kù)任務(wù)時(shí), RGV母車(chē)的行走時(shí)間的計(jì)算方式不同.當(dāng)RGV執(zhí)行的第i個(gè)任務(wù)為出庫(kù)任務(wù)時(shí), RGV母車(chē)行走時(shí)間Ti為RGV母車(chē)從上一任務(wù)通道到出庫(kù)目標(biāo)通道的行走時(shí)間; 當(dāng)RGV執(zhí)行的第i個(gè)任務(wù)為入庫(kù)任務(wù)時(shí), RGV母車(chē)行走時(shí)間Ti為RGV母車(chē)從上一任務(wù)通道到入口通道的行走時(shí)間與從入口通道處到入庫(kù)目標(biāo)通道的行走時(shí)間之和.

(2) RGV子車(chē)升降時(shí)間的計(jì)算模型.RGV在進(jìn)行連續(xù)的出入庫(kù)混合作業(yè)時(shí), 存在如表2所示的多種不同作業(yè)工況, 并且每一種工況下RGV子車(chē)的行程時(shí)間計(jì)算公式都各不相同.如RGV在執(zhí)行出庫(kù)任務(wù)時(shí), 其前一任務(wù)為入庫(kù)任務(wù), 且前一任務(wù)與當(dāng)前執(zhí)行任務(wù)不在同一通道, 則RGV子車(chē)的行程路徑如圖4所示(虛線為子車(chē)路徑), 此時(shí)可根據(jù)式(2)計(jì)算子車(chē)的行程.

(2)

圖4 RGV子車(chē)行程路徑圖Fig.4 Travel path of RGV sub car

而當(dāng)上一個(gè)任務(wù)為出庫(kù)任務(wù)時(shí), 由于上一任務(wù)的結(jié)束位置點(diǎn)在底層輸送裝置處, 則RGV子車(chē)的提升行程變?yōu)?K+1)×h, 所以其子車(chē)總的行程計(jì)算公式就變?yōu)槭?3).

(3)

因此, 本文基于RGV子車(chē)多種作業(yè)工況, 建立子車(chē)行程時(shí)間的通用計(jì)算模型, 通過(guò)更改不同的參數(shù)來(lái)對(duì)應(yīng)計(jì)算不同工況下子車(chē)的行程時(shí)間, 每種工況的參數(shù)(α,β,θ)值如表2所示.

表2 RGV子車(chē)行程時(shí)間參數(shù)Table 2 Travel time parameters of RGV sub car

(3) RGV執(zhí)行完所有出入庫(kù)任務(wù)所用時(shí)間的計(jì)算模型如式(4)所示.

(4)

由于RGV在執(zhí)行第一個(gè)任務(wù)時(shí), RGV子車(chē)起始點(diǎn)為貨架頂層, 而其他任務(wù)的起始點(diǎn)不是在貨架底層, 就是在上一個(gè)貨物的入庫(kù)貨位處, 導(dǎo)致RGV子車(chē)執(zhí)行第一個(gè)任務(wù)的起始點(diǎn)和其他任務(wù)起始點(diǎn)不同, 所以t1需要單獨(dú)進(jìn)行計(jì)算.

2 基于混合遺傳算法的出入庫(kù)貨位分

配算法設(shè)計(jì)

新型棋盤(pán)格密集倉(cāng)庫(kù)的貨位分配問(wèn)題是一個(gè)組合優(yōu)化問(wèn)題, 主要依據(jù)RGV在某種貨位組合下完成出入庫(kù)任務(wù)時(shí)間的長(zhǎng)短來(lái)評(píng)判該貨位組合的優(yōu)劣.在進(jìn)行出入庫(kù)任務(wù)時(shí)間計(jì)算之前, 還需對(duì)RGV的執(zhí)行任務(wù)順序進(jìn)行優(yōu)化排序, 采用傳統(tǒng)的遺傳算法無(wú)法同時(shí)對(duì)棋盤(pán)格密集倉(cāng)庫(kù)出入庫(kù)貨位分配優(yōu)化問(wèn)題和RGV任務(wù)執(zhí)行順序優(yōu)化問(wèn)題進(jìn)行求解.因此, 本文設(shè)計(jì)基于混合遺傳算法的出入庫(kù)貨位分配算法, 同時(shí)對(duì)以上兩個(gè)問(wèn)題進(jìn)行求解, 采用遺傳算法對(duì)出入庫(kù)貨位的分配方案進(jìn)行尋優(yōu), 結(jié)合啟發(fā)式排序算法對(duì)RGV任務(wù)執(zhí)行順序進(jìn)行優(yōu)化, 基于優(yōu)化排序的結(jié)果, 根據(jù)式(4)計(jì)算RGV任務(wù)的執(zhí)行時(shí)間, 并將時(shí)間的倒數(shù)作為遺傳算法尋優(yōu)過(guò)程中的適應(yīng)度值, 整體的算法流程如圖5所示.

2.1基于遺傳算法的貨位尋優(yōu)

(1) 染色體編碼設(shè)計(jì).本文遺傳算法的染色體采用貨位編號(hào)進(jìn)行編碼, 編碼根據(jù)貨物種類分為多個(gè)片段.采用“入庫(kù)貨位+出庫(kù)貨位”的順序排列, 其長(zhǎng)度為入庫(kù)貨物數(shù)量和出庫(kù)貨物數(shù)量總和.為對(duì)出入庫(kù)任務(wù)類型和貨物的種類進(jìn)行標(biāo)識(shí), 設(shè)計(jì)貨物種類和任務(wù)類型的輔助字符串, 如圖6所示, 任務(wù)類型的輔助字符串中, 0表示出庫(kù), 1表示入庫(kù).

圖5 基于混合遺傳算法的出入庫(kù)貨位分配算法流程圖Fig.5 Flowchart of storage location assignment algorithm based on hybrid genetic algorithm

圖6 染色體編碼設(shè)計(jì)Fig.6 Design of chromosome coding

(2)初始種群生成.采用基于分片段貨位數(shù)量限制的隨機(jī)方法生成初始種群, 如圖6所示，在保證每個(gè)片段中貨位個(gè)數(shù)與對(duì)應(yīng)的出庫(kù)或入庫(kù)貨物數(shù)量相等的前提下, 從空位集合和存有該出庫(kù)貨物的貨位集合中隨機(jī)選取貨位組成染色體.對(duì)于種群規(guī)模的選擇, 取編碼長(zhǎng)度的2～4倍做為種群的規(guī)模.

(3) 染色體解碼.染色體解碼的目的是將貨位編號(hào)轉(zhuǎn)換成可用于適應(yīng)度值計(jì)算的貨位層坐標(biāo)和相鄰?fù)ǖ赖男辛凶鴺?biāo), 在每一條染色體隨機(jī)生成前, 算法數(shù)據(jù)模型中已保存與每一種貨物貨位編號(hào)集合相對(duì)應(yīng)的貨位坐標(biāo)集合.在隨機(jī)生成染色體后, 根據(jù)染色體對(duì)應(yīng)貨位坐標(biāo), 在貨架數(shù)據(jù)模型中搜索與貨位相鄰?fù)ǖ赖男辛凶鴺?biāo), 用通道的行列坐標(biāo)取代貨位的行列坐標(biāo), 從而實(shí)現(xiàn)染色體的解碼.

(4) 適應(yīng)度函數(shù)和種群選擇.本文將RGV執(zhí)行完所有出入庫(kù)任務(wù)所需時(shí)間的倒數(shù)作為算法的適應(yīng)度值.在計(jì)算RGV任務(wù)完成時(shí)間前, 需對(duì)RGV執(zhí)行任務(wù)的順序進(jìn)行優(yōu)化.本文采用啟發(fā)式排序算法對(duì)RGV執(zhí)行任務(wù)的順序進(jìn)行優(yōu)化, 并根據(jù)經(jīng)典輪盤(pán)賭的方法對(duì)種群的個(gè)體進(jìn)行選擇, 按照對(duì)應(yīng)的概率分布選取染色體遺傳到下一代.為了加速算法收斂, 采用精英保存策略, 將每代一定數(shù)量的最優(yōu)個(gè)體強(qiáng)行遺傳到下一代, 增加父體的選擇壓力, 提高最優(yōu)個(gè)體被選中的概率.

(5) 交叉算子和變異算子.為了避免產(chǎn)生不可行解, 采用基于固定交配位的雙親雙子方法進(jìn)行交叉, 如圖7所示, 隨機(jī)選擇1～T, 其中T為染色體編碼按照設(shè)計(jì)結(jié)構(gòu)劃分的基因片段數(shù)(如上例中片段個(gè)數(shù)為4), 然后將待交配的兩個(gè)父代的第t個(gè)基因片段進(jìn)行交換, 其他基因片段不變, 產(chǎn)生兩個(gè)子代.隨機(jī)選擇染色體片段中的某個(gè)貨位, 用貨架中與該片段相對(duì)應(yīng)的可用貨位替換該貨位, 實(shí)現(xiàn)染色體的變異操作, 這種變異方法能夠向染色體中添加新貨位, 從而改變貨位分配方案, 有利于豐富種群個(gè)體多樣性.

圖7 交叉操作Fig.7 Crossover operation

2.2啟發(fā)式排序算法設(shè)計(jì)

對(duì)出入庫(kù)任務(wù)進(jìn)行排序的目的是為了減少RGV母車(chē)在頂層的行程和子車(chē)在通道內(nèi)的行程, 從而增加RGV整體作業(yè)效率.為減少RGV母車(chē)在各目標(biāo)通道間的行走路程, 可結(jié)合基于最近鄰策略(NN)[11]的排序方法對(duì)RGV母車(chē)到達(dá)通道的先后進(jìn)行排序, 且位于同一通道的任務(wù)由RGV母車(chē)連續(xù)執(zhí)行. 而RGV子車(chē)在同一通道內(nèi)執(zhí)行多個(gè)任務(wù)時(shí), 子車(chē)按照貨位的層數(shù)從上往下執(zhí)行任務(wù), 所走路程最短.

基于以上棋盤(pán)格密集倉(cāng)庫(kù)RGV作業(yè)的特點(diǎn), 進(jìn)行出入庫(kù)混合模式下的任務(wù)排序優(yōu)化算法設(shè)計(jì), 算法流程如下:

(1) 獲取外層染色體的貨位編號(hào)、解碼得到的貨位位置及相鄰?fù)ǖ牢恢玫刃畔?

(2) 循環(huán)比較出入庫(kù)隊(duì)列中第i～n, 將行列坐標(biāo)信息相同的貨位排在一起;

(3) 將(2)中相鄰?fù)煌ǖ赖呢浳话雌渌趯訑?shù), 從高到低依次排序, 高的貨位排在低的貨位前面;

(4) 將相鄰?fù)煌ǖ赖呢浳蛔鳛橐粋€(gè)整體, 根據(jù)各個(gè)通道與RGV母車(chē)起始點(diǎn)之間的距離, 采用基于最近鄰策略(NN)的排序方法, 對(duì)RGV母車(chē)到達(dá)各通道的先后順序進(jìn)行排列.

RGV按照以上出入庫(kù)貨位的排列順序, 依次到達(dá)各個(gè)貨位完成出入庫(kù)任務(wù), 調(diào)用式(4)計(jì)算RGV完成任務(wù)的時(shí)間.

3 測(cè)試案例與分析

選用貨架規(guī)模為6×8×4棋盤(pán)格密集倉(cāng)庫(kù)進(jìn)行案例測(cè)試, 其中，6為貨架的行數(shù), 8為貨架的列數(shù), 4為貨架的層數(shù).密集倉(cāng)庫(kù)共140個(gè)貨位, 13個(gè)通道, 其中貨位的長(zhǎng)和寬均為0.4 m, 貨位的高度為0.6 m, RGV母車(chē)在頂層行走的速度為2 m/s, 加速度為1.5 m/s2, RGV子車(chē)速度為1.5 m/s2.貨位的狀態(tài)分布如圖8所示, 將三維貨架分層展開(kāi), 其中, 圖8(a)～(d)依次為為貨架的第1～4層; 入口通道1個(gè)(32號(hào)貨位右邊), RGV?？空?個(gè)(100號(hào)貨位對(duì)應(yīng)的貨架頂層處); 其方格內(nèi)字母表示所儲(chǔ)存的貨物類型, 帶有編號(hào)且沒(méi)有字母的方格表示為空貨位, 白色的方格為通道.根據(jù)棋盤(pán)格密集倉(cāng)庫(kù)當(dāng)前儲(chǔ)存狀態(tài), 進(jìn)行出入庫(kù)作業(yè).出庫(kù)任務(wù)為貨物A、B、C、G, 出庫(kù)數(shù)量分別為3、3、2、1; 入庫(kù)任務(wù)為貨物D、E、F, 入庫(kù)數(shù)量分別為2、2、1.

(a) 第1層

(b) 第2層

(c) 第3層

(d) 第4層

利用本文提出的混合遺傳算法進(jìn)行求解, 遺傳算法種群規(guī)模取30, 交叉率取0.8, 變異率取0.1, 最大迭代次數(shù)取400.遺傳算法尋優(yōu)過(guò)程如圖9所示.

圖9 種群迭代變化曲線圖Fig.9 Population iteration change curve

在算法迭代開(kāi)始時(shí)的平均作業(yè)時(shí)間較大, 然后迅速下降, 染色體的擇優(yōu)速度很快, 在100次左右獲得了穩(wěn)定解, 且后續(xù)各代種群均被有效地控制在較優(yōu)水平, 算法的運(yùn)行時(shí)間為0.388 s, 算法運(yùn)行效率很高.算法求解得到的RGV任務(wù)執(zhí)行順序?yàn)? E-G-D-C-C-D-B-B-B-F-A-A-A-E, 對(duì)應(yīng)的出入庫(kù)分配貨位為: 98-125-126-132-27-26-130-25-19-48-76-83-88-66, RGV完成所有出入庫(kù)任務(wù)的時(shí)間為67.35 s.

在不同貨架規(guī)模下, 為測(cè)試算法對(duì)貨位分配的優(yōu)化效果, 設(shè)計(jì)如下試驗(yàn)數(shù)值: 倉(cāng)庫(kù)貨架規(guī)模為12×16×4、18×20×6、24×26×8, 每種貨架規(guī)模下隨機(jī)生成20種貨物的初始分布, 分別對(duì)每種試驗(yàn)方案進(jìn)行50次仿真試驗(yàn), 并與隨機(jī)貨位分配下RGV執(zhí)行完出入庫(kù)任務(wù)的時(shí)間進(jìn)行對(duì)比, 對(duì)比結(jié)果如表3所示.從表3中數(shù)據(jù)可以看出，采用基于混合遺傳算法的貨位分配算法求解新型棋盤(pán)格密集倉(cāng)庫(kù)貨位分配問(wèn)題, 可以大大提升RGV作業(yè)效率, 且貨架規(guī)模越大則效率提升越明顯.從表3中最后一行可以看出, 在最大貨架規(guī)模情況下, 算法平均運(yùn)行時(shí)間為4.806 s, 算法運(yùn)行效率很高.

表3 不同貨架規(guī)模下RGV作業(yè)效率提升程度Table 3 RGV efficiency improvement on shelves with different sizes

4 結(jié) 語(yǔ)

本文對(duì)新型棋盤(pán)格立體倉(cāng)庫(kù)出入庫(kù)復(fù)合模式下的貨位分配問(wèn)題進(jìn)行了研究, 從提升RGV出入庫(kù)作業(yè)效率的角度出發(fā), 針對(duì)出入庫(kù)貨位選擇和RGV任務(wù)執(zhí)行順序兩個(gè)優(yōu)化問(wèn)題, 設(shè)計(jì)了基于混合遺傳算法的出入庫(kù)貨位分配算法, 并且設(shè)計(jì)了多組試驗(yàn)數(shù)值來(lái)檢驗(yàn)算法的求解效果.結(jié)果證明, 本文提出的算法能夠有效地解決新型棋盤(pán)格立體倉(cāng)庫(kù)的出入庫(kù)貨位分配問(wèn)題, 使RGV的作業(yè)效率得到大幅度提升, 算法運(yùn)行效率很高, 并且具有貨架規(guī)模越大則效率提升越明顯的優(yōu)勢(shì).

[1] 楊建國(guó), 符鵬程, 吳平平, 等.多層棋盤(pán)格式立體貨架及其貨位排布算法研究[J].工程設(shè)計(jì)學(xué)報(bào), 2015, 22(3): 211-218.

[2] 孫嘉煒.立體倉(cāng)庫(kù)出入庫(kù)貨位優(yōu)化模型與算法研究[D].沈陽(yáng): 東北大學(xué)信息科學(xué)與工程學(xué)院, 2013.

[3] 肖建, 鄭力.考慮需求相關(guān)性的多巷道倉(cāng)庫(kù)貨位分配問(wèn)題[J].計(jì)算機(jī)集成制造系統(tǒng), 2008,14(12): 2447-2451.

[4] 楊朋. 多載具自動(dòng)化存取系統(tǒng)貨位分配與作業(yè)調(diào)度研究[D].北京: 清華大學(xué)工業(yè)工程系, 2011.

[5] CHEN L, LANGEVIN A, RIOPEI D. The storage location assignment and interleaving problem in an automated storage /retrieval system with shared storage [J]. International Journal of Production Research, 2010, 48(4): 991-1011.

[6] PAN C H, SHIH P H, WU M H, et al. A storage assignment heuristic method based on genetic algorithm for a pick-and-pass warehousing system [J]. Computers & Industrial Engineering, 2015, 81: 1-13.

[7] ONUT S, TUZKAYA U R, DOGAC B. A particle swarm optimization algorithm for the multiple-level warehouse layout design problem [J]. Computers and Industrial Engineering, 2008, 54(4): 783-799.

[8] 鄭紅星, 于凱.基于混合遺傳算法的混堆箱區(qū)內(nèi)場(chǎng)橋調(diào)度研究[J].交通運(yùn)輸系統(tǒng)工程與信息, 2013,13(5): 150-158.

[9] 馬永杰, 蔣兆遠(yuǎn), 楊志民.基于遺傳算法的自動(dòng)化倉(cāng)庫(kù)的動(dòng)態(tài)貨位分配[J].西南交通大學(xué)學(xué)報(bào), 2008,43(3): 415-421.

[10] 馬永杰, 云文霞.遺傳算法研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究, 2012,29(4): 1201-1206.

[11] 饒衛(wèi)振, 金淳, 黃英藝.求解TSP問(wèn)題的最近鄰域與插入混合算法[J].系統(tǒng)工程理論與實(shí)踐, 2011, 31(8): 1419-1428.

(責(zé)任編輯:杜佳)

OptimizationofAllocationAssignmentofNewCheckerboardIntensiveWarehouse

LIUWanqiang,ZHOUYaqing,YANGJianguo,YOUXiang

(College of Mechanical Engineering, Donghua University, Shanghai 201620, China)

In order to improve the efficiency of rail guided vehicle (RGV) in warehousing operation, allocation assignment has been carried out for the new checkerboard Intensive warehouse with the consideration of the influence of RGV acceleration and deceleration. Allocation assignment algorithm based on nested genetic algorithm is designed to solve the allocation problem. Simulation experiments show that the algorithm can effectively solve the allocation problem of checkerboard warehouse under various scales, so that the overall operating efficiency of RGV increased by about 40%, and the larger the shelf size, the more obviously the efficiency increases.

checkerboard intensive warehouse; allocation assignment; genetic algorithm (GA); rail guided vehicle (RGV)

K 826.16

A

1671-0444 (2017)04-0496-07

2017-04-05

上海市自然科學(xué)基金資助項(xiàng)目(15ZR1400600)；上海倉(cāng)儲(chǔ)物流設(shè)備工程技術(shù)研究中心資助項(xiàng)目(17DZ2283800)

劉萬(wàn)強(qiáng)(1992—)，男，四川資陽(yáng)人，碩士研究生，研究方向?yàn)橹悄軅}(cāng)儲(chǔ).E-mail:987557046@qq.com

周亞勤(聯(lián)系人)，女，副教授，E-mail: zhouyaqin@dhu.edu.cn