余嘉雄，白紅星

(浙江凱樂(lè)士科技集團(tuán)股份有限公司，浙江 嘉興 314000)

近年來(lái)，為降低倉(cāng)儲(chǔ)成本，越來(lái)越多的企業(yè)選擇四向穿梭車自動(dòng)化立體倉(cāng)庫(kù)系統(tǒng)(以下簡(jiǎn)稱四向穿梭車系統(tǒng))來(lái)執(zhí)行物品的出入庫(kù)操作。在該系統(tǒng)中，多層高位貨架的緊密放置，極大程度保證了倉(cāng)庫(kù)的空間利用率，使物品存儲(chǔ)費(fèi)用得以降低；物品的存取操作利用四向穿梭車和提升機(jī)配合執(zhí)行，具有較高的取物速度和精準(zhǔn)度。但是該系統(tǒng)還存在能耗低、系統(tǒng)穩(wěn)定性不足、系統(tǒng)柔性低、任務(wù)執(zhí)行速率低等問(wèn)題。針對(duì)上述問(wèn)題，已經(jīng)有眾多專家學(xué)者提出改進(jìn)意見(jiàn)，如李麗等[1]從機(jī)構(gòu)設(shè)計(jì)的角度對(duì)穿梭車進(jìn)行優(yōu)化，提高了穿梭車的穩(wěn)定性；徐立云等[2]從穿梭車的沖突角度進(jìn)行分析，提出道路定向調(diào)度策略，使出入庫(kù)的效率得到提高；何昕杰等[3]對(duì)倉(cāng)庫(kù)物品進(jìn)行編碼，提出利用改進(jìn)后的遺傳算法對(duì)任務(wù)調(diào)度問(wèn)題進(jìn)行求解，實(shí)現(xiàn)對(duì)出庫(kù)時(shí)間的精準(zhǔn)控制。本文針對(duì)四向穿梭車任務(wù)執(zhí)行速率低的問(wèn)題，從穿梭車的沖突問(wèn)題出發(fā)，通過(guò)改進(jìn)作業(yè)時(shí)間調(diào)度的求解算法，提高作業(yè)調(diào)度對(duì)時(shí)間的精準(zhǔn)把控，從而使四向穿梭車系統(tǒng)具有較高的任務(wù)執(zhí)行速率。

1 四向穿梭車作業(yè)時(shí)間分析

1.1 四向穿梭車的作業(yè)流程

在四向穿梭車系統(tǒng)中，通過(guò)穿梭車和提升機(jī)之間的相互配合，即可實(shí)現(xiàn)對(duì)倉(cāng)庫(kù)貨架上任意物品的出庫(kù)操作[4]。四向穿梭車系統(tǒng)執(zhí)行出庫(kù)操作的流程：第一步，提升機(jī)運(yùn)送空閑穿梭車至出庫(kù)物品所在層；第二步，穿梭車前往物品對(duì)應(yīng)的位置，取貨并返回；第三步，提升機(jī)再運(yùn)送載貨穿梭車至出庫(kù)層[5-7]。下面將分別對(duì)這三步流程進(jìn)行分析。通過(guò)對(duì)穿梭車和提升機(jī)進(jìn)行運(yùn)動(dòng)學(xué)分析，得到兩者的速度和加速度的時(shí)間坐標(biāo)圖，如圖1所示。

圖1 穿梭車和提升機(jī)的速度、加速度時(shí)間坐標(biāo)圖

1.2 提升機(jī)接送空閑穿梭車時(shí)間模型

設(shè)提升機(jī)初始位于第x層，物品位于第y層。設(shè)置出庫(kù)層位于第1層，則提升機(jī)位于第x層的概率P1(x)為：

(1)

式中：N為貨架的層數(shù)。

由于物品的存儲(chǔ)為隨機(jī)放置，因此物品位于第y層的概率P2(y)為：

(2)

提升機(jī)從第x層移動(dòng)至第1層的距離H1(x)為：

H1(x)=(x-1)h

(3)

式中：h為單個(gè)貨位高度。

提升機(jī)從第1層移動(dòng)至第y層的距離H2(y)為：

H2(y)=(y-1)h

(4)

結(jié)合圖1可知，提升機(jī)從第x層移動(dòng)至第1層的時(shí)間t1(x)為：

(5)

式中：aL為提升機(jī)加減速度；vL為提升機(jī)最大速度。

提升機(jī)從第1層移動(dòng)至第y層的時(shí)間t2(y)為：

(6)

由此可知提升機(jī)接取空閑穿梭車并運(yùn)送至物品層的平均時(shí)間MT1為：

(7)

式中：tL為提升機(jī)運(yùn)送穿梭車的時(shí)間[6]。

1.3 穿梭車移動(dòng)取物時(shí)間模型

穿梭車只能通過(guò)橫向、縱向的導(dǎo)軌進(jìn)行移動(dòng)，因此設(shè)置合理的移動(dòng)軌跡能極大程度地縮短出庫(kù)時(shí)間。在常見(jiàn)的四向穿梭車系統(tǒng)中，一般為3個(gè)及以上巷道配置一個(gè)提升機(jī)。設(shè)AN為一個(gè)提升機(jī)服務(wù)的巷道數(shù)，當(dāng)AN為奇數(shù)時(shí)，設(shè)提升機(jī)的初始位置在(AN+1)/2個(gè)巷道處；當(dāng)AN為偶數(shù)時(shí)，設(shè)提升機(jī)的初始位置位于AN/2個(gè)巷道處。由于系統(tǒng)的出庫(kù)位置隨機(jī)，因此提升機(jī)取貨需要移動(dòng)z個(gè)巷道距離的概率P3(z)為：

(8)

執(zhí)行單次取物操作，穿梭車的橫向移動(dòng)距離Dc(z)為：

Dc(z)=z(2l+WSD)

(9)

式中：l為單個(gè)貨位的長(zhǎng)度；WSD為穿梭車縱向?qū)к墝挾取?/p>

執(zhí)行單次取物操作，穿梭車的橫向移動(dòng)時(shí)間t3(z)為：

(10)

式中：aS為穿梭車加減速度；vS為穿梭車最大速度。

由式(8)可得，執(zhí)行單次取物操作，穿梭車的平均換道時(shí)間tMCA為：

(11)

式中：tCA為穿梭車的換道時(shí)間。

假設(shè)物品的位置在第c列，執(zhí)行單次取物操作，穿梭車的縱向移動(dòng)距離DS(c)為：

DS(c)=c·W

(12)

式中：c為貨架的列數(shù)；W為單個(gè)貨位寬度。

執(zhí)行單次取物操作，穿梭車的縱向移動(dòng)時(shí)間t4(c)為：

(13)

因此，執(zhí)行單次取物操作，穿梭車的平均運(yùn)動(dòng)時(shí)間MT2為：

(14)

式中：tS為穿梭車的換道時(shí)間；C為穿梭車單次取物操作移動(dòng)的貨架列數(shù)。

1.4 提升機(jī)接送載物穿梭車時(shí)間模型

設(shè)提升機(jī)此時(shí)位于第x層，物品位于第y層，提升機(jī)從第x層移動(dòng)至第y層的距離H3(x,y)為：

H3(x,y)=|x-1|h

(15)

提升機(jī)從第y層移動(dòng)至第1層的距離H4(y)為：

H4(y)=H2(y)=(y-1)h

(16)

提升機(jī)從第x層移動(dòng)至第y層的時(shí)間t5(x,y)為：

(17)

提升機(jī)從第y層移動(dòng)至第1層的時(shí)間t6(y)為：

t6(y)=t2(y)

(18)

因此，提升機(jī)接取載物穿梭車并運(yùn)送至出庫(kù)層的時(shí)間MT3為：

(19)

式中：P4(z)為提升機(jī)在第z層的概率；P5(y)為任務(wù)目標(biāo)在y層的概率。

2 四向穿梭車系統(tǒng)任務(wù)調(diào)度研究

2.1 任務(wù)調(diào)度建模

通過(guò)上述流程分析可以看出，提升機(jī)的運(yùn)輸任務(wù)分為兩種類型：一是接送空閑穿梭車，二是接送載物穿梭車。為保證貨物進(jìn)出庫(kù)的總體效率，設(shè)定提升機(jī)接送空閑穿梭車A后，優(yōu)先響應(yīng)為停留在原地等待穿梭車A取物，在將載物穿梭車A接送至出庫(kù)層后才能響應(yīng)其他穿梭車的運(yùn)輸申請(qǐng)。為符合現(xiàn)場(chǎng)實(shí)際，設(shè)定出庫(kù)層位于第1層，提升機(jī)的的初始位置也位于第1層。為避免穿梭車之間發(fā)生碰撞，一個(gè)巷道只允許一輛穿梭車進(jìn)入，且默認(rèn)本次取物結(jié)束時(shí)穿梭車和提升機(jī)的位置為下一次取件的初始位置。為計(jì)算方便，忽略穿梭車的交接耗時(shí)。

對(duì)于單次出庫(kù)任務(wù)，設(shè)穿梭車在導(dǎo)軌上移動(dòng)的總距離為SS，結(jié)合圖1得穿梭車運(yùn)行時(shí)間tSS為：

(20)

同理，設(shè)提升機(jī)運(yùn)送穿梭車移動(dòng)的總距離為SL，則提升機(jī)運(yùn)行時(shí)間tSL為：

(21)

若穿梭車移動(dòng)i列，則穿梭車在導(dǎo)軌上移動(dòng)的總距離SS為：

SS=i·W

(22)

由于穿梭車的取物過(guò)程為一個(gè)來(lái)回，需要跨越兩次巷道，因此穿梭車跨i個(gè)巷道取物的運(yùn)行距離又可表達(dá)為：

SS=i(2l+WSD)

(23)

設(shè)穿梭車來(lái)回跨越巷道的數(shù)量為i和j，則穿梭車的橫向運(yùn)行時(shí)間tS,c為

tS,c=tS,c,i+tS,c,j+2g·tCA

(24)

式中：tS,c,i為穿梭車跨越i個(gè)巷道的時(shí)間；tS,c,j為穿梭車跨越j(luò)個(gè)巷道的時(shí)間；g=i+j，取值范圍為0，1，2。

若某任務(wù)位于第p層，則提升機(jī)執(zhí)行該任務(wù)需要移動(dòng)的層數(shù)為2p，結(jié)合式(15)、(16)，可得提升機(jī)執(zhí)行該任務(wù)的SL為：

SL=2|p|h

(25)

圖2 提升機(jī)出庫(kù)作業(yè)時(shí)序圖

設(shè)某提升機(jī)編號(hào)為K。由圖2可得，K執(zhí)行第m個(gè)任務(wù)所需時(shí)間tK,m為：

(26)

計(jì)算提升機(jī)K完成第m個(gè)任務(wù)的時(shí)刻TK,m為：

(27)

(28)

分析穿梭車的取貨過(guò)程，結(jié)合圖2可知，提升機(jī)執(zhí)行所有出庫(kù)任務(wù)的總用時(shí)Ttotal為：

(29)

式中：M為執(zhí)行任務(wù)的總數(shù)。

式(29)即為任務(wù)調(diào)度模型的目標(biāo)函數(shù)[7]。

2.2 系統(tǒng)沖突解決策略

四向穿梭車系統(tǒng)中，穿梭車有相向沖突、節(jié)點(diǎn)沖突、同向沖突、追及沖突4種沖突類型。為實(shí)現(xiàn)運(yùn)送過(guò)程中的沖突類型判斷，從左到右將橫向?qū)к壣系墓?jié)點(diǎn)、路徑依次進(jìn)行編碼，對(duì)于處在同一層的多個(gè)穿梭車，構(gòu)建沖突路徑和時(shí)間的路徑時(shí)間窗。假設(shè)一個(gè)四向穿梭車系統(tǒng)中有2個(gè)提升機(jī)、6組貨架，構(gòu)建的路徑時(shí)間窗如圖3所示。

由于從圖3中可以直接得到容易出現(xiàn)沖突的節(jié)點(diǎn)，因此需要基于迭代時(shí)間窗構(gòu)建沖突消除模型，即將穿梭車的時(shí)間窗進(jìn)行整體移位，進(jìn)而消除沖突。首先判斷發(fā)生沖突的穿梭車的任務(wù)等級(jí)，將任務(wù)等級(jí)低的穿梭車進(jìn)行整體時(shí)間窗移位；對(duì)于同任務(wù)等級(jí)的沖突，根據(jù)到達(dá)沖突位置節(jié)點(diǎn)的時(shí)間順序，將后到的穿梭車進(jìn)行整體時(shí)間窗移位。

圖3 基于路徑時(shí)間窗的沖突判斷

1)當(dāng)出現(xiàn)相向沖突或節(jié)點(diǎn)沖突時(shí)，系統(tǒng)可能出現(xiàn)死鎖，其移位過(guò)程如下：

①先找到發(fā)生沖突的節(jié)點(diǎn)，并推算需要進(jìn)行移位的穿梭車的上一節(jié)點(diǎn)位置。

②計(jì)算兩個(gè)穿梭車到達(dá)沖突節(jié)點(diǎn)的時(shí)刻，設(shè)兩個(gè)不同的優(yōu)先級(jí)時(shí)刻分別為T2和T1，則移位時(shí)刻tm為：

tm=T2-T1+t0

(30)

式中：t0為穿梭車安全緩沖時(shí)長(zhǎng)，根據(jù)穿梭車和系統(tǒng)反應(yīng)時(shí)間自行設(shè)定。

③將移位穿梭車的整體時(shí)間窗向后移動(dòng)tm時(shí)刻。

2)對(duì)于同向沖突和追及沖突，可以直接將后抵達(dá)沖突節(jié)點(diǎn)的穿梭車進(jìn)行移位。其移位過(guò)程如下：

①尋找存在沖突的路徑和節(jié)點(diǎn)。

②計(jì)算所有沖突時(shí)長(zhǎng)，記最大值tc,max，得移位時(shí)長(zhǎng)為：

tm=tc,max+t0

(31)

③將移位穿梭車的整體時(shí)間窗向后移動(dòng)tm時(shí)刻。

基于上述分析，設(shè)計(jì)避免沖突等待時(shí)間的計(jì)算流程，如圖4所示。

2.3 系統(tǒng)任務(wù)調(diào)度優(yōu)化

由于四向穿梭車的系統(tǒng)任務(wù)調(diào)度主要是指定提升機(jī)對(duì)穿梭車進(jìn)行運(yùn)送，對(duì)于這類問(wèn)題，傳統(tǒng)的離散粒子群算法無(wú)法直接應(yīng)用，需要進(jìn)行相關(guān)優(yōu)化[8]。

假設(shè)四向穿梭車系統(tǒng)中存在2個(gè)提升機(jī)，需要將8個(gè)物品出庫(kù)，為實(shí)現(xiàn)物品定位，對(duì)物品序號(hào)和維度進(jìn)行編碼，X-Y表示第X號(hào)物品第Y個(gè)維度，隨機(jī)選取8個(gè)物品的坐標(biāo)，并分配給提升機(jī)，得到圖5。

圖5 物品編碼與提升機(jī)分配

在此，引入同維度粒子位置塊[9]，將提升機(jī)中同一維度中的所有序號(hào)作為一個(gè)整體，即位置塊，再利用離散粒子群算法，對(duì)編碼進(jìn)行速度作用，引入速度算子[10]。設(shè)物體的移動(dòng)速度中包含多個(gè)速度算子，將速度算子V={0,0,2,0}作用于圖5，得到圖6所示轉(zhuǎn)換圖。

圖6 速度算子作用轉(zhuǎn)換圖

按照?qǐng)D6所示的方法將位置塊的位置進(jìn)行轉(zhuǎn)換，可以實(shí)現(xiàn)對(duì)提升機(jī)傳送穿梭車的順序優(yōu)化。由于速度算子的作用是將整個(gè)維度進(jìn)行整體移動(dòng)，因此維度編碼對(duì)任務(wù)調(diào)度影響較大。為解決不合理的維度編碼導(dǎo)致任務(wù)調(diào)度中各提升機(jī)無(wú)法收斂的問(wèn)題，需要對(duì)維度編碼[11]進(jìn)行研究。

由于在四向穿梭車的實(shí)際應(yīng)用中，貨架列數(shù)一般遠(yuǎn)大于貨架層數(shù)，因此任務(wù)調(diào)度中出庫(kù)任務(wù)的列數(shù)影響較大。為此，本文根據(jù)列數(shù)排序與維度編碼進(jìn)行匹配，當(dāng)列數(shù)相同時(shí)，優(yōu)先對(duì)序號(hào)小的進(jìn)行出庫(kù)[12]。以30個(gè)出庫(kù)任務(wù)為例，設(shè)共有50列貨架，將各提升機(jī)與需要執(zhí)行的出庫(kù)編碼進(jìn)行配對(duì)[13]，得到表1。

表1 30個(gè)出庫(kù)任務(wù)與其對(duì)應(yīng)的提升機(jī)任務(wù)

根據(jù)上文所述方法對(duì)表1中的內(nèi)容進(jìn)行編碼，得到的初始編碼如圖7所示。

假設(shè)最優(yōu)的速度算子V={0，1，0，0，0，0，3，0，0，0，5，0，0，8，4}，根據(jù)上文的位置塊轉(zhuǎn)換方法，可對(duì)圖7的編碼進(jìn)行轉(zhuǎn)換，得到圖8所示的編碼。

圖7 根據(jù)列數(shù)排序得到的初始編碼

通過(guò)算法計(jì)算可以得到同維度間發(fā)生位置互換的概率pe。設(shè)pe=2，對(duì)圖8所示編碼進(jìn)行同維度位置互換，得到圖9所示的編碼。

圖8 根據(jù)最優(yōu)的速度算子轉(zhuǎn)換得到的編碼

圖9 同維度位置互換所得的編碼

為得到完成任務(wù)的最大時(shí)長(zhǎng)，使數(shù)據(jù)最為可靠，本文將任務(wù)均分給2臺(tái)提升機(jī)，即每一臺(tái)提升機(jī)任務(wù)執(zhí)行量相等。為極大地降低任務(wù)耗時(shí)，任一個(gè)任務(wù)都選擇預(yù)測(cè)路線最短的提升機(jī)。

由于傳統(tǒng)的離散粒子群(discrete particle swarm optimization，DPSO)算法只能單獨(dú)得到個(gè)體最優(yōu)值，不同個(gè)體間缺少交流，在迭代后期，容易喪失局部搜索能力。為解決這類問(wèn)題，本文將對(duì)DPSO 算法進(jìn)行改進(jìn)。改進(jìn)步驟如下：

1)在進(jìn)行迭代的過(guò)程中，從位置塊中隨機(jī)選擇編碼，編碼i被選中的概率為Ps,i。

2)引入遺傳算法(genetic algorithm,GA)中的選擇交叉操作，將隨機(jī)選中穿梭車來(lái)回跨越巷道的數(shù)量編碼i和編碼j兩兩配對(duì)，按照概率Pc進(jìn)行隨機(jī)交叉互換，保留交叉前后適應(yīng)值較高的編碼組。

交叉互換中各編碼互換示意圖如圖10所示。

圖10 交叉互換中各編碼互換示意圖

編碼進(jìn)行交叉互換操作時(shí)，首先選取維度不同的幾組編碼，使其位置塊交叉互換。其次引入遺傳算法中的變異操作[14]檢測(cè)全局極值，當(dāng)編碼組無(wú)法進(jìn)行迭代改善時(shí)，對(duì)該編碼組所有編碼進(jìn)行初始化操作，即隨機(jī)重組分配，概率為Pv。

基于GA-DPSO算法的流程圖如圖11所示。

圖11 基于GA-DPSO算法的流程圖

改進(jìn)后的GA-DPSO算法能夠?qū)崿F(xiàn)各編碼間的信息交流和共享，且能夠更快得到目標(biāo)函數(shù)的最優(yōu)解，具有較高的收斂速度，在迭代后期，搜索能力也不會(huì)降低。

3 實(shí)例分析

由于提升機(jī)數(shù)量和穿梭車數(shù)量都會(huì)對(duì)任務(wù)調(diào)度速率造成影響，因此在實(shí)際的單個(gè)作業(yè)中，一般配置2個(gè)提升機(jī)和8個(gè)穿梭車進(jìn)行調(diào)度求解。本文選取某物流倉(cāng)庫(kù)為實(shí)驗(yàn)對(duì)象，隨機(jī)提取50,100,150個(gè)出庫(kù)物品，并對(duì)其編碼。再根據(jù)優(yōu)化后的算法計(jì)算出概率、時(shí)間、速率等具體參數(shù)，將這些參數(shù)輸入任務(wù)調(diào)度模型即可得到任務(wù)調(diào)度結(jié)果。為驗(yàn)證本文改進(jìn)后的GA-DPSO算法的效果，引入傳統(tǒng)DPSO算法和GA算法，將3種算法的任務(wù)調(diào)度結(jié)果進(jìn)行對(duì)比，得到表2。

表2 不同訂單數(shù)量下3種算法的調(diào)度結(jié)果

從表2可以看出，GA-DPSO算法的均值和標(biāo)準(zhǔn)差都最小，優(yōu)化效率最高，由此可以證明本文改進(jìn)的GA-DPSO算法具有更高的執(zhí)行速率、更高的穩(wěn)定性和更好的優(yōu)化能力。

基于表2，繪出不同訂單數(shù)量下3種算法的迭代曲線，如圖12所示。

圖12 不同訂單數(shù)量下3種算法的迭代曲線

從圖12可以看出，本文改進(jìn)的GA-DPSO算法具有更快的迭代收斂速度，且由于引入了交叉變異操作，更容易得到全局最優(yōu)解。

綜上所述，本文改進(jìn)的GA-DPSO算法基本能夠?qū)崿F(xiàn)設(shè)計(jì)要求，能夠有效地提高四向穿梭車系統(tǒng)運(yùn)行的穩(wěn)定性。

4 結(jié)束語(yǔ)

綜上可知，優(yōu)化后的四向穿梭車作業(yè)調(diào)度模型求解算法具有較高的穩(wěn)定性，能夠有效提高四向穿梭車系統(tǒng)的出入庫(kù)效率，具有一定的應(yīng)用價(jià)值。但本文并未涉及穿梭車和提升機(jī)的移動(dòng)速度突變等情況的誤差修正，在四向穿梭車系統(tǒng)連續(xù)作業(yè)超過(guò)一定時(shí)長(zhǎng)后，會(huì)出現(xiàn)調(diào)度優(yōu)勢(shì)減弱的情況，因此需要定期進(jìn)行系統(tǒng)重啟或調(diào)度清零操作；且本文只對(duì)四向穿梭車作業(yè)調(diào)度模型求解算法進(jìn)行優(yōu)化，并未對(duì)調(diào)度模型和穿梭車進(jìn)行改進(jìn)，因此還有很大的改進(jìn)空間。