湯洪濤，程曉雅，李修琳，魯建廈，陳壽伍

(1.浙江工業(yè)大學(xué) 機(jī)械工程學(xué)院，浙江 杭州 310023；2.浙江工商大學(xué) 管理工程與電子商務(wù)學(xué)院，浙江 杭州 310018)

0 引言

跨層跨巷道穿梭車倉(cāng)儲(chǔ)系統(tǒng)(Tier-to-Tier and Aisle-to-Aisle Shuttle Based Storage and Retrieval System, TTAASBS/RS)是在多層穿梭車基礎(chǔ)上發(fā)展起來(lái)的快速存取、檢索系統(tǒng)，其主要依靠巷道口垂直方向上的提升機(jī)、垂直于巷道的轉(zhuǎn)載車和巷道內(nèi)穿梭車配合完成調(diào)度任務(wù)。作業(yè)方式包括單一入庫(kù)作業(yè)、單一出庫(kù)作業(yè)和復(fù)合作業(yè)。與傳統(tǒng)的每層一臺(tái)穿梭車倉(cāng)儲(chǔ)系統(tǒng)相比，穿梭車可以多層共用；與跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)相比，跨層跨巷道穿梭車又增加了水平方向自主運(yùn)行，實(shí)現(xiàn)多排共用，增加了系統(tǒng)的靈活性。出入庫(kù)復(fù)合作業(yè)因貼合實(shí)際作業(yè)模式，常被用于TTAASBS/RS，然而穿梭車跨層跨巷道的特點(diǎn)大大增加了調(diào)度的復(fù)雜性，有必要采用合理的調(diào)度策略來(lái)提高系統(tǒng)的吞吐性能，其中出入庫(kù)復(fù)合作業(yè)路徑對(duì)吞吐性能的影響舉足輕重。

多層穿梭車倉(cāng)儲(chǔ)系統(tǒng)是近年來(lái)發(fā)展起來(lái)的新型自動(dòng)化立體倉(cāng)庫(kù)，而且受到越來(lái)越多的關(guān)注。針對(duì)多層穿梭車倉(cāng)儲(chǔ)系統(tǒng)研究，牟善棟[1]首先對(duì)多層穿梭車建立多目標(biāo)任務(wù)調(diào)度模型，提出將多層穿梭車數(shù)學(xué)模型類比到流水線作業(yè)模型；王璐瑤等[2]指出影響多層穿梭車性能的主要因素為揀選臺(tái)前端輸送線，提出基于Robot的輸送系統(tǒng)，并運(yùn)用開(kāi)環(huán)排隊(duì)網(wǎng)絡(luò)驗(yàn)證其有效性；魯建廈等[3]對(duì)跨層穿梭車復(fù)合作業(yè)任務(wù)調(diào)度時(shí)間最小化進(jìn)行研究，利用改進(jìn)人工魚(yú)群算法求解最優(yōu)作業(yè)路徑；楊瑋等[4]對(duì)子母式穿梭車立體倉(cāng)庫(kù)三維路徑規(guī)劃問(wèn)題進(jìn)行研究，利用混合粒子算法求解一臺(tái)子母車作業(yè)路徑;魯建廈等[5]在子母穿梭車三維復(fù)合作業(yè)的基礎(chǔ)上考慮碳排放因素和作業(yè)時(shí)間對(duì)任務(wù)調(diào)度的影響，設(shè)計(jì)混合智能水滴算法求解模型，優(yōu)化子母車作業(yè)路徑；馬文凱等[6]對(duì)跨巷道多層穿梭車系統(tǒng)的性能進(jìn)行研究，利用進(jìn)化算法優(yōu)化跨巷道多層穿梭車倉(cāng)儲(chǔ)系統(tǒng)的存儲(chǔ)容量和揀選效率；LERHER[7]研究跨巷道穿梭車倉(cāng)儲(chǔ)系統(tǒng)，建立了單、雙指令情況下穿梭車的行程時(shí)間模型，并對(duì)時(shí)間模型進(jìn)行性能分析。以上跨層/跨巷道研究一般以單巷道/單層為研究對(duì)象，本文綜合考慮跨層跨巷道作業(yè)特點(diǎn)，開(kāi)展多層多巷道研究，使其更貼合實(shí)際作業(yè)方式。

倉(cāng)儲(chǔ)系統(tǒng)中的三維調(diào)度、貨位優(yōu)化、資源配置等問(wèn)題均被證明屬于NP難問(wèn)題[8]，因?yàn)椴捎镁_算法求解時(shí)效率低、耗時(shí)長(zhǎng)，所以越來(lái)越多的智能優(yōu)化算法被用于求解復(fù)雜問(wèn)題。人工蜂群(Artificial Bee Colony, ABC)算法于2005年由KARABOGA提出[9]。該算法具有包含參數(shù)少、鄰域搜索和全局搜索能力平衡、收斂速度快等優(yōu)點(diǎn)，在組合優(yōu)化問(wèn)題上得到了較廣泛的應(yīng)用，如混流裝配線作業(yè)排序問(wèn)題[10]、分布式柔性作業(yè)車間調(diào)度問(wèn)題[11]、模糊柔性作業(yè)車間調(diào)度問(wèn)題[12]等；另外，將ABC算法應(yīng)用于求解車輛路徑問(wèn)題(Vehicle Routing Problem, VRP)也有較多研究[13]，例如利用ABC算法求解考慮交通堵塞和重復(fù)路徑策略的VRP[14]、考慮碳排放策略VRP中的交叉對(duì)接配送問(wèn)題[15]及考慮車輛管理和多倉(cāng)庫(kù)路徑優(yōu)化的多倉(cāng)庫(kù)VRP等[16]。通過(guò)上述分析可知，雖然ABC算法在求解組合優(yōu)化問(wèn)題方面具有優(yōu)勢(shì)，但是在求解密集存儲(chǔ)系統(tǒng)路徑規(guī)劃問(wèn)題方面的應(yīng)用較少，因此本文采用改進(jìn)的ABC算法求解路徑規(guī)劃問(wèn)題數(shù)學(xué)模型。

本文以TTAASBS/RS出入庫(kù)復(fù)合作業(yè)為研究對(duì)象，從作業(yè)任務(wù)順序、作業(yè)路徑等角度對(duì)其路徑優(yōu)化進(jìn)行研究。穿梭車既跨層又跨巷道的作業(yè)方式可以節(jié)約系統(tǒng)成本、提高系統(tǒng)作業(yè)效率，但是大大增加了調(diào)度的復(fù)雜性。本文在考慮穿梭車、轉(zhuǎn)載車、提升機(jī)加減速度的情況下，以系統(tǒng)最小化最大任務(wù)完成時(shí)間為目標(biāo)，考慮TTAASBS/RS實(shí)際作業(yè)過(guò)程建立復(fù)合作業(yè)數(shù)學(xué)模型，基于改進(jìn)ABC算法求解不同出入庫(kù)作業(yè)任務(wù)數(shù)量的訂單行程時(shí)間，在貼合實(shí)際作業(yè)環(huán)境的情況下最小化出入庫(kù)作業(yè)的最大完成時(shí)間，提高存取效率。另外，分別與基本ABC算法、遺傳算法(Genetic Algorithm, GA)、改進(jìn)的蟻群算法、改進(jìn)的人工魚(yú)群算法在優(yōu)化效率、穩(wěn)定性等方面進(jìn)行綜合對(duì)比，驗(yàn)證本文算法的有效性。

1 問(wèn)題描述和數(shù)學(xué)模型

1.1問(wèn)題描述

現(xiàn)有的TTAASBS/RS由垂直提升機(jī)、巷道轉(zhuǎn)載車、穿梭車、軌道式存儲(chǔ)貨架、倉(cāng)庫(kù)管理系統(tǒng)(Warehouse Management System, WMS)和倉(cāng)庫(kù)控制系統(tǒng)(Warehouse Control System, WCS)等組成，其垂直于巷道方向，由轉(zhuǎn)載車搭載穿梭車進(jìn)行跨巷道作業(yè)，穿梭車在巷道內(nèi)進(jìn)行出入庫(kù)作業(yè)，垂直方向則由提升機(jī)完成貨物跨層運(yùn)輸。TTAASBS/RS平面如圖1所示。

圖2所示為T(mén)TAASBS/RS三維示意圖。圖中：x方向?yàn)榇怪毕锏婪较?，表示轉(zhuǎn)載車的運(yùn)動(dòng)方向；y方向?yàn)橄锏啦贾梅较?，表示穿梭車的運(yùn)動(dòng)方向；z方向?yàn)樘嵘龣C(jī)方向，提升機(jī)在z方向做上下運(yùn)動(dòng)。(x，y，z)對(duì)應(yīng)貨架的排列層。

一次完整的出入庫(kù)復(fù)合作業(yè)任務(wù)由取貨指令、出庫(kù)指令、入庫(kù)指令3次指令完成，其中取貨指令和出庫(kù)指令配合完成出庫(kù)作業(yè)。結(jié)合具體的出入庫(kù)任務(wù)，該TTAASBS/RS示意圖如圖3所示，作業(yè)流程如圖4所示，具體操作如下：

(1)取貨指令 當(dāng)有出庫(kù)指令下達(dá)時(shí)，判斷穿梭車當(dāng)前位置是否與出庫(kù)貨位同層。

1)若同層，則：①穿梭車運(yùn)行至巷道首處，調(diào)用轉(zhuǎn)載車；②轉(zhuǎn)載車搭載穿梭車至目標(biāo)巷道口；③轉(zhuǎn)載車釋放穿梭車(若取貨貨位在同巷道則不需要調(diào)用轉(zhuǎn)載車)，穿梭車運(yùn)行至出庫(kù)貨位進(jìn)行取貨作業(yè)。

2)若不同層，則：①穿梭車運(yùn)行至巷道首處，調(diào)用轉(zhuǎn)載車；②轉(zhuǎn)載車搭載穿梭車至提升機(jī)站臺(tái)調(diào)用提升機(jī)；③提升機(jī)搭載穿梭車運(yùn)行到出庫(kù)貨位所在層，調(diào)用轉(zhuǎn)載車；④轉(zhuǎn)載車搭載穿梭車至目標(biāo)巷道口處；⑤轉(zhuǎn)載車釋放穿梭車，穿梭車運(yùn)行至出庫(kù)貨位進(jìn)行取貨作業(yè)。

(2)出庫(kù)指令 ①穿梭車完成取貨任務(wù)后運(yùn)行至巷道口調(diào)用轉(zhuǎn)載車；②轉(zhuǎn)載車搭載穿梭車前往提升機(jī)站臺(tái)調(diào)用提升機(jī)，并等待提升機(jī)；③提升機(jī)搭載穿梭車前往原點(diǎn)，調(diào)用轉(zhuǎn)載車并等待；④轉(zhuǎn)載車搭載穿梭車至I/O點(diǎn)；⑤穿梭車在I/O口卸貨并載貨。

(3)入庫(kù)指令 ①穿梭車在I/O口完成取貨任務(wù)后運(yùn)行至巷道口，調(diào)用轉(zhuǎn)載車并等待；②轉(zhuǎn)載車搭載穿梭車前往提升機(jī)站臺(tái)調(diào)用提升機(jī)，并等待提升機(jī)；③提升機(jī)搭載穿梭車至入庫(kù)貨物所在層，調(diào)用轉(zhuǎn)載車并等待；④轉(zhuǎn)載車搭載穿梭車前往入庫(kù)貨位所在巷道口；⑤穿梭車運(yùn)行至入庫(kù)口，進(jìn)行入庫(kù)任務(wù)。

出入庫(kù)復(fù)合作業(yè)的簡(jiǎn)單表示如圖3a所示；當(dāng)進(jìn)行連續(xù)出庫(kù)/入庫(kù)作業(yè)時(shí)，考慮任務(wù)補(bǔ)齊，將I/O點(diǎn)和初始位置(在初始位置進(jìn)行一個(gè)虛擬入庫(kù)作業(yè))重合進(jìn)行連續(xù)出庫(kù)作業(yè)，如圖3所示；當(dāng)連續(xù)入庫(kù)任務(wù)的I/O點(diǎn)和初始位置(在初始位置做虛擬出庫(kù)作業(yè))重合時(shí)，相當(dāng)于系統(tǒng)只執(zhí)行單指令入庫(kù)任務(wù)，如圖3c所示。在圖3b和圖3c中，灰色部分為虛擬作業(yè)。

系統(tǒng)接收到任務(wù)分配后，如何使提升機(jī)、轉(zhuǎn)載車、穿梭車高效完成出入庫(kù)任務(wù)，是建立TTAASBS/RS任務(wù)調(diào)度的關(guān)鍵。因此，需要合理規(guī)劃提升機(jī)和轉(zhuǎn)載車、穿梭車的作業(yè)路徑，而建立合理正確的復(fù)合作業(yè)調(diào)度模型是研究路徑規(guī)劃的關(guān)鍵。

如圖4所示為系統(tǒng)出入庫(kù)復(fù)合作業(yè)流程圖，系統(tǒng)一次完整的出入庫(kù)復(fù)合作業(yè)任務(wù)調(diào)度分為出庫(kù)作業(yè)和入庫(kù)作業(yè)兩部分，兩部分又可以拆分為取貨指令、出庫(kù)指令、入庫(kù)指令3次指令變化，并將出庫(kù)作業(yè)和入庫(kù)作業(yè)拆分為3次節(jié)點(diǎn)變化過(guò)程，每一次節(jié)點(diǎn)變化都需要穿梭車和轉(zhuǎn)載車或穿梭車和提升機(jī)配合完成：①穿梭車由當(dāng)前位置運(yùn)行至出庫(kù)貨位所在位置；②穿梭車由出庫(kù)貨位所在位置運(yùn)行至出入庫(kù)節(jié)點(diǎn)(I/O口)；③穿梭車由出入庫(kù)節(jié)點(diǎn)(I/O口)運(yùn)行至入庫(kù)貨位所在位置。

TTAASBS/RS出入庫(kù)復(fù)合作業(yè)的3個(gè)指令，均可表示為穿梭車從起始位置經(jīng)過(guò)轉(zhuǎn)載車、提升機(jī)的配合運(yùn)行至目標(biāo)位置的過(guò)程(如圖3)，按照穿梭車的初始位置和目標(biāo)位置是否同層同巷道，將該過(guò)程分為4種情況，其中穿梭車與目標(biāo)任務(wù)同層同巷道、不同層同巷道的調(diào)度過(guò)程相同。

(1)同層同巷道 ①系統(tǒng)接收任務(wù)指令，并調(diào)度穿梭車；②穿梭車直接從當(dāng)前位置啟動(dòng)運(yùn)行到目標(biāo)位置。

(2)同層不同巷道 ①系統(tǒng)接收任務(wù)指令，并調(diào)度穿梭車；②穿梭車從當(dāng)前位置運(yùn)行至巷道首處，調(diào)用轉(zhuǎn)載車；③轉(zhuǎn)載車搭載穿梭車前往目標(biāo)巷道，轉(zhuǎn)載車釋放穿梭車；④穿梭車運(yùn)行到達(dá)目標(biāo)位置。

(3)不同層同巷道/不同層不同巷道 ①系統(tǒng)下達(dá)指令給穿梭車，穿梭車從當(dāng)前位置運(yùn)行至巷道首處調(diào)用轉(zhuǎn)載車；②轉(zhuǎn)載車搭載穿梭車前往提升機(jī)站臺(tái)，調(diào)用提升機(jī)；③釋放穿梭車，提升機(jī)搭載穿梭車至作業(yè)任務(wù)目標(biāo)層，調(diào)用轉(zhuǎn)載車；④轉(zhuǎn)載車搭載提升機(jī)至目標(biāo)巷道，釋放穿梭車；⑤穿梭車運(yùn)動(dòng)到目標(biāo)位置。

1.2 數(shù)學(xué)模型

根據(jù)跨層跨巷道多層穿梭車倉(cāng)儲(chǔ)系統(tǒng)運(yùn)行情況，提出如下假設(shè)：

(1)巷道兩側(cè)貨物隨機(jī)存放，采用隨機(jī)存儲(chǔ)原則，一次進(jìn)出復(fù)合作業(yè)中的入庫(kù)與出庫(kù)貨物位置已知。

(2)考慮垂直提升機(jī)、穿梭車、轉(zhuǎn)載車加減速運(yùn)動(dòng)，為方便計(jì)算，假設(shè)加(減)速度相同，且設(shè)備空載和負(fù)載時(shí)的移動(dòng)速度相同。

(3)穿梭車和轉(zhuǎn)載車均為單負(fù)載，即穿梭車一次只能攜帶一個(gè)貨物，提升機(jī)在一段時(shí)間只能搭載一輛穿梭車。

(4)系統(tǒng)中的穿梭車、轉(zhuǎn)載車和提升機(jī)均采用“上次完成任務(wù)處?？俊钡耐？坎呗?，即穿梭車、轉(zhuǎn)載車和提升機(jī)完成任務(wù)后會(huì)停留在原地，不會(huì)主動(dòng)做空行程運(yùn)動(dòng)。

(5)當(dāng)一個(gè)巷道有穿梭車進(jìn)行出入庫(kù)作業(yè)時(shí)即鎖死該巷道，不再允許其他穿梭車進(jìn)入。

(6)穿梭車或提升機(jī)執(zhí)行任務(wù)時(shí)不允許中斷，只有在該任務(wù)完成之后，才能開(kāi)始下一個(gè)任務(wù)。

(7)作業(yè)過(guò)程中不考慮設(shè)備故障及后續(xù)的重調(diào)度問(wèn)題。

為了更好地描述TTAASBS/RS的作業(yè)流程，定義數(shù)學(xué)模型中用到的主要參數(shù)，如表1所示。

表1 參數(shù)定義匯總表

已知1次出入庫(kù)復(fù)合作業(yè)任務(wù)可以轉(zhuǎn)化成3次節(jié)點(diǎn)的改變，因此將3次節(jié)點(diǎn)變化轉(zhuǎn)化為3次任務(wù)操作，分別為取貨任務(wù)、出庫(kù)任務(wù)(在出入庫(kù)節(jié)點(diǎn)先卸貨又再次取貨)、入庫(kù)任務(wù)。貨物出入庫(kù)作業(yè)單元編號(hào)為n=(1,2,3,…,N)，因此第n個(gè)作業(yè)單元又可拆分為第3n-2個(gè)任務(wù)、第3n-1個(gè)任務(wù)和第3n個(gè)任務(wù)。記b為作業(yè)任務(wù)序號(hào)，b=1,2,3,…,3N-2,3N-1，3N。設(shè)s為操作階段的代號(hào)，s=1,2,3,4,5，一個(gè)復(fù)合作業(yè)可以轉(zhuǎn)化為5個(gè)階段：①穿梭車從當(dāng)前位置至巷道首處；②轉(zhuǎn)載車搭載穿梭車至提升機(jī)處；③提升機(jī)搭載穿梭車運(yùn)行至目標(biāo)層處；④轉(zhuǎn)載車搭載穿梭車至目標(biāo)巷道；⑤轉(zhuǎn)載車釋放穿梭車，運(yùn)行至目標(biāo)位置處進(jìn)行存取貨作業(yè)。因此，本文研究的問(wèn)題可以轉(zhuǎn)化為五階段混合流水線調(diào)度問(wèn)題。其中：m1=m5=Q，且穿梭車作用在第1階段和第5階段。m2=m4=3，當(dāng)進(jìn)行跨層/跨巷道不跨層運(yùn)動(dòng)時(shí)，調(diào)用兩個(gè)實(shí)際轉(zhuǎn)載車，第3個(gè)設(shè)備為虛擬運(yùn)行的轉(zhuǎn)載車；當(dāng)進(jìn)行不跨層不跨巷道運(yùn)動(dòng)時(shí)，調(diào)用虛擬轉(zhuǎn)載車。例如s=2,k=1表示任務(wù)的第2階段采用實(shí)際運(yùn)行的轉(zhuǎn)載車。m3=3，當(dāng)發(fā)生跨層運(yùn)動(dòng)時(shí)調(diào)用的設(shè)備m1和m2為實(shí)際提升機(jī)，m3為虛擬提升機(jī)，選擇m3表示只進(jìn)行同層作業(yè)。wbb′sk為s階段機(jī)器k操作的兩個(gè)連續(xù)任務(wù)b和b′之間的準(zhǔn)備時(shí)間，即轉(zhuǎn)載車和提升機(jī)的空載時(shí)間都只發(fā)生在m1和m2實(shí)際設(shè)備中。

因此，TTAASBS/RS復(fù)合作業(yè)調(diào)度模型表示如下：

minCmax。

(1)

s.t.

(2)

tbsk≥0，b=1,2,3,…,3N,s=1,2，3,4,5;

(3)

tbs≥t(b-1)s，b=3n-1,3n,

n=1,2,…,N，s=1,2,3,4,5；

(4)

tbs+pbs≤tb(s+1)，

b=1,2,3,…,3N,s=1,2，3,4,5；

(5)

xb1k=xb5k，b=1,2,…,3N,k=1,2,…,Q；

(6)

xb3k=1，xb2k=1，

b=1,2,…,3N,k=1,2，3；

(7)

xb3k=1，xb2k≠xb4k，

b=1,2,…,3N，k=1，2;

(8)

xb1k=x(b-1)1kb，b=3n-1,3n,

n=1,2,…,N，k=1,2,…,Q;

(9)

xb33=1，xb2k=x(b-1)2k，b=3n-1,3n,

n=1,2,…,N，k=1,2，3;

(10)

xb3k=1,xb2k≠x(b-1)2k，b=3n-1,3n,

n=1,2,…,N，k=1，2;

(11)

tb′3-wbb′3k-(tb3+pb3)≥G(ybb′3k-1)，

b,b′=1,2,…,3N,k=1,2;

(12)

tb′1-(tb5+pb5)≥G(ybb′5k-1)，

b,b′=1,2,…,3N，k=1,2,…,Q；

(13)

tb′2-wbb′4k-(tb4+pb4)≥G(jbb′k-1)，

b,b′=1,2,…,3N,k=1，2；

(14)

tb′s-wbb′sk-(tbs+pbs)≥G(ybb′sk-1)，

b,b′=1,2,…,3N,k=1，2,s=2，4；

(15)

s=1,2,3，4,5,k=1,2,…,ms；

(16)

s=1,2,3，4,5,k=1,2,…,ms;

(17)

Cmax≥tb5+pb5,b=3n,n=1,2,…,N；

(18)

(19)

(20)

(21)

其中：式(1)為復(fù)合作業(yè)模型的目標(biāo)，即最小化最大任務(wù)完成時(shí)間；式(2)在任何階段都只有一臺(tái)設(shè)備執(zhí)行任務(wù)；式(3)保證任務(wù)開(kāi)始時(shí)間的有效性；式(4)確保前一任務(wù)與后一任務(wù)之間的執(zhí)行順序，穿梭車不會(huì)從初始位置直接進(jìn)行到入庫(kù)作業(yè)；式(5)表示當(dāng)前任務(wù)的完成時(shí)間早于下一任務(wù)的開(kāi)始時(shí)間；式(6)表示一個(gè)任務(wù)的第1階段和第5階段由同一設(shè)備完成；式(7)表示k=1,2時(shí)對(duì)象為實(shí)際轉(zhuǎn)載車，同一任務(wù)的第2和第4階段為一實(shí)一虛轉(zhuǎn)載車進(jìn)行不跨層跨巷道運(yùn)動(dòng)，k=3時(shí)對(duì)象為虛擬轉(zhuǎn)載車，同一任務(wù)的第2和第4階段為同一設(shè)備進(jìn)行不跨層不跨巷道運(yùn)動(dòng)；式(8)表示同一任務(wù)的第2和第4階段由不同設(shè)備完成，此時(shí)為跨層作業(yè)；式(9)表示一次完整的出入庫(kù)復(fù)合作業(yè)的先后任務(wù)的階段1由同一穿梭車完成；式(10)表示同一作業(yè)單元的前后任務(wù)的階段的設(shè)備由k決定，對(duì)象為轉(zhuǎn)載車，當(dāng)k=3時(shí)不跨層運(yùn)動(dòng)由同一設(shè)備完成，對(duì)象為虛擬轉(zhuǎn)載車，當(dāng)k=1/2時(shí)為跨層運(yùn)動(dòng)，對(duì)象為實(shí)際轉(zhuǎn)載車；式(11)表示跨層時(shí)同一作業(yè)單元的前后任務(wù)的第2階段由不同設(shè)備完成，對(duì)象為實(shí)際轉(zhuǎn)載車；式(12)表示提升機(jī)前一任務(wù)結(jié)束時(shí)間早于后一任務(wù)開(kāi)始時(shí)間，規(guī)定了任務(wù)的前后作業(yè)關(guān)系；式(13)表示穿梭車前一任務(wù)結(jié)束時(shí)間早于后一任務(wù)開(kāi)始時(shí)間，規(guī)定了任務(wù)的前后作業(yè)關(guān)系；式(14)表示執(zhí)行同一任務(wù)過(guò)程中，第2階段的轉(zhuǎn)載車作業(yè)時(shí)間早于第4階段的轉(zhuǎn)載車作業(yè)時(shí)間；式(15)表示前后任務(wù)作業(yè)關(guān)系中，前一任務(wù)第2階段的轉(zhuǎn)載車作業(yè)時(shí)間早于后一任務(wù)的第2階段轉(zhuǎn)載車作業(yè)時(shí)間；式(16)和式(17)表示作業(yè)設(shè)備連接作業(yè)任務(wù)，每一作業(yè)設(shè)備都有緊前工序和后接任務(wù)；式(18)表示Cmax的作業(yè)時(shí)間超過(guò)每一次出入庫(kù)復(fù)合作業(yè)時(shí)間；式(19)～式(21)為變量申明定義。

2 算法描述

2.1 基本人工蜂群算法

ABC算法[17]是一種較新的優(yōu)化算法，其基本思想與自然界中蜜蜂的覓食行為類似。在ABC算法中總共有雇傭蜂、觀察蜂和偵查蜂3類蜜蜂，算法的搜索過(guò)程也分為3個(gè)階段，①雇傭蜂階段，主要負(fù)責(zé)尋找新的蜜源并記住蜜源信息，及時(shí)與觀察蜂分享蜜源信息，包括運(yùn)動(dòng)區(qū)域的位置和蜜源的花蜜量；②觀察蜂階段，決定根據(jù)雇傭蜂提供的信息選擇更好的食物來(lái)源，然后繼續(xù)在所選擇的食物源周圍尋找其他食物源，與花蜜較少的蜜源相比，花蜜越多的蜜源被觀察蜂選擇的可能性越高[18]；③偵查蜂階段，在蜜源附近隨機(jī)尋找下一個(gè)有價(jià)值的蜜源[19]。

ABC算法的具體操作如下：

i∈[1,SN]。

(22)

(2)雇傭蜂階段 雇傭蜂在其食物源附近確定新的蜜源，并識(shí)別和評(píng)估蜜源的質(zhì)量。如果新蜜源的質(zhì)量?jī)?yōu)于前一個(gè)蜜源，則從記憶中刪除前一個(gè)源信息，將新源的信息存儲(chǔ)在記憶中；否則，保留之前蜜源的信息。該階段被雇傭的蜜蜂用式(23)確定新蜜源，Xkj為第k個(gè)個(gè)體在第j維上選擇的位置，Vij只有在優(yōu)于Xij的情況下才會(huì)采用該位置。Vij為第i個(gè)個(gè)體在第j維上的當(dāng)前位置，

Vij=Xij+φij(Xij-Xkj)。

(23)

式中：φij為在[-1,1]之間選擇的隨機(jī)數(shù)；k為一個(gè)取[1,SN]之間隨機(jī)值的整數(shù)。通過(guò)改變Xij的一個(gè)參數(shù)即可找到Vij源。

(3)概率計(jì)算 所有雇傭蜂完成搜索后，會(huì)與在運(yùn)動(dòng)區(qū)域等待的觀察蜂分享信息。觀察蜂評(píng)估雇傭蜂傳遞的蜜源信息，并根據(jù)概率值選擇新的蜜源。同樣，如果新源的適應(yīng)度更優(yōu)，則將之前的位置信息從記憶中刪除，將新源信息保存在記憶中。觀察蜂對(duì)新源的選擇與pi概率值有關(guān)，

(24)

式中fitnessi為被雇傭的蜜蜂對(duì)第i個(gè)解的適應(yīng)度值的評(píng)價(jià)。

(25)

式中：fi為優(yōu)化問(wèn)題所特有的目標(biāo)函數(shù)值；abs為絕對(duì)值函數(shù)，文中fi≤0的情況不出現(xiàn)。

(4)觀察蜂階段 一旦在(3)中選擇了一個(gè)蜜源，觀察蜂更新方程將會(huì)采用與式(23)相同的更新方式進(jìn)一步挖掘新蜜源[21]，然后ABC算法將用貪婪選擇方案在觀察蜂及其子代之間選擇一個(gè)更好的。

(5)偵查蜂階段 引入預(yù)定的參數(shù)limit來(lái)決定是否放棄某一蜜源[22]。如果該蜜源不能被開(kāi)發(fā)，則被拋棄，并將對(duì)應(yīng)該蜜源的雇傭蜂轉(zhuǎn)化為偵查蜂去開(kāi)采下一蜜源。

2.2 改進(jìn)的人工蜂群算法

ABC算法在后期容易陷入局部最優(yōu)且收斂速度較慢[23]，因此進(jìn)行如下改進(jìn)：①在初始種群階段改進(jìn)了隨機(jī)生成個(gè)體和加入策略生成個(gè)體的生成方式，使初始種群多樣化；②在雇傭蜂階段引入重復(fù)優(yōu)先交叉操作(Repeat Precedence Operation Crossover, RPOX)交叉算子和變異算子，提高雇傭蜂階段搜索可行解的效率；③在觀察蜂階段引入動(dòng)態(tài)鄰域搜索；④設(shè)計(jì)了偵查蜂階段的食物源更新機(jī)制。圖5所示為改進(jìn)后的ABC算法流程圖。

2.2.1 初始種群生成

ABC算法的初始種群為隨機(jī)生成，其優(yōu)劣差異較大，種群質(zhì)量難以保證，而初始種群的質(zhì)量又會(huì)對(duì)種群的收斂速度和最終結(jié)果產(chǎn)生影響。因此本文提出隨機(jī)生成和策略選擇相結(jié)合的方式生成初始種群，即初始種群中35%的個(gè)體采用原始的隨機(jī)生成方式，15%的個(gè)體采用規(guī)則選擇，即每一次出庫(kù)任務(wù)和入庫(kù)任務(wù)優(yōu)先選擇距離較近的進(jìn)行匹配，構(gòu)成一次復(fù)合作業(yè)任務(wù)；剩余的50%個(gè)體采用策略選擇方式，即穿梭車在選擇出入庫(kù)復(fù)合作業(yè)任務(wù)時(shí)，盡量選擇距其最近的任務(wù)對(duì)先進(jìn)行作業(yè)，以縮短穿梭車空跑時(shí)間。

2.2.2 雇傭蜂操作

(1)交叉操作

傳統(tǒng)的ABC算法中，雇傭蜂主要在發(fā)現(xiàn)的食物源周圍搜索可行解，并采用貪婪法則更新蜜源，產(chǎn)生的無(wú)效搜索較多，在一定程度上影響了算法的搜索效率。因此，改進(jìn)雇傭蜂的重點(diǎn)應(yīng)放在如何提高搜索效率，即提高雇傭蜂的有效搜索次數(shù)[24]上。本文設(shè)計(jì)了一種基于改進(jìn)的RPOX交叉算子[25]來(lái)改進(jìn)雇傭蜂操作階段，如圖6所示，其中以10對(duì)出入庫(kù)復(fù)合作業(yè)任務(wù)對(duì)為例：

步驟1隨機(jī)產(chǎn)生一組出入庫(kù)任務(wù)數(shù)對(duì)0

步驟2隨機(jī)選擇兩個(gè)父代個(gè)體p1和p2，從p1中選擇k個(gè)出入庫(kù)任務(wù)對(duì)組成集合N1，在p2中揀選剩余的n-k個(gè)出入庫(kù)任務(wù)對(duì)組成集合N2。

步驟3分別將N1和N2對(duì)應(yīng)的復(fù)合作業(yè)任務(wù)對(duì)從父代p1和p2復(fù)制子代，復(fù)制過(guò)程中保證對(duì)應(yīng)的編碼不變。

步驟4C1和C2剩余位置的出入庫(kù)位置編碼做以下規(guī)定：出庫(kù)作業(yè)任務(wù)由后往前推，第2個(gè)位置補(bǔ)到第1個(gè)位置；入庫(kù)作業(yè)任務(wù)補(bǔ)位規(guī)則由前往后推，p1的第1個(gè)位置補(bǔ)到C1的第2個(gè)位置；穿梭車補(bǔ)位規(guī)則與出庫(kù)作業(yè)任務(wù)相同。

(2)變異操作

改進(jìn)的變異操作應(yīng)用到ABC算法可以使雇傭蜂搜索食物源的范圍更廣，本文設(shè)計(jì)一種適用于3層編碼的變異操作能夠增強(qiáng)ABC算法的搜索能力，減少非法解，如圖7所示。

步驟1本文出庫(kù)作業(yè)與入庫(kù)作業(yè)一同構(gòu)成一次復(fù)合作業(yè)任務(wù)，因此變異針對(duì)的主要是穿梭車編號(hào)，隨機(jī)選擇穿梭車編號(hào)中的任意兩點(diǎn)位置，并從穿梭車集合中挑選可供替換的穿梭車序號(hào)。

步驟2將原穿梭車編號(hào)替換成新的穿梭車編號(hào)。若被替換的穿梭車處于被占用階段，則視為非法解，替換為其他合法穿梭車。

2.2.3 觀察蜂操作

在算法迭代過(guò)程中，ABC算法搜索最優(yōu)蜜源的本質(zhì)是蜜蜂執(zhí)行鄰域搜索的過(guò)程，觀察蜂會(huì)逐漸向蜜源豐富區(qū)域靠近，在編碼中表現(xiàn)為雇傭蜂搜索范圍受限導(dǎo)致蜜源質(zhì)量?jī)?yōu)化幅度有減弱的趨勢(shì)。為了使ABC算法每次迭代均有效，采用改進(jìn)動(dòng)態(tài)鄰域搜索算法來(lái)增強(qiáng)觀察蜂階段的搜索能力，具體如下：

(1)變換鄰域結(jié)構(gòu) 在個(gè)體的出入庫(kù)作業(yè)編號(hào)和穿梭車作業(yè)編號(hào)隨機(jī)指定兩個(gè)位置進(jìn)行交換，得到新的出入庫(kù)作業(yè)任務(wù)順序。

(2)插入鄰域結(jié)構(gòu) 將某一隨機(jī)出入庫(kù)作業(yè)編號(hào)插入個(gè)體的出入庫(kù)作業(yè)向量指定的位置。

(3)分配鄰域結(jié)構(gòu) 將指定出入庫(kù)任務(wù)隨機(jī)分配到就近的穿梭車進(jìn)行作業(yè)，以減少空跑時(shí)間。

(4)變異鄰域結(jié)構(gòu) 采用錦標(biāo)賽選擇的方式，通過(guò)個(gè)體競(jìng)爭(zhēng)決定此時(shí)需完成的出入庫(kù)任務(wù)由哪輛穿梭車執(zhí)行或是否由該穿梭車執(zhí)行[26]。

基于動(dòng)態(tài)鄰域操作改進(jìn)觀察峰的搜索操作過(guò)程如圖8所示，具體為：在一次鄰域結(jié)構(gòu)操作結(jié)束之后，比較子代個(gè)體與父代個(gè)體的適應(yīng)度值。若子代個(gè)體適應(yīng)度值優(yōu)于父代個(gè)體，則保留子代個(gè)體，結(jié)束鄰域搜索；若子代個(gè)體仍劣于父代個(gè)體，則繼續(xù)進(jìn)行下一鄰域操作，直到得到更優(yōu)個(gè)體。

2.2.4 偵查蜂操作

偵察蜂在蜂巢的主要任務(wù)是搜索新蜜源，對(duì)偵查蜂階段的改進(jìn)主要集中在如何避免算法陷入局部最優(yōu)以及新蜜源的更新機(jī)制。設(shè)置公告欄并在偵查蜂搜索之前調(diào)用公告欄，以便公告欄記錄當(dāng)前最優(yōu)蜜源對(duì)應(yīng)的解和出入庫(kù)作業(yè)任務(wù)時(shí)間。結(jié)合路徑規(guī)劃問(wèn)題對(duì)偵查蜂進(jìn)行如下改進(jìn)操作：

(1)單一對(duì)比 利用初始種群規(guī)則初始化偵查蜂蜂群，將初始化后的食物源適應(yīng)度值與全局最優(yōu)解對(duì)比，若全局最優(yōu)解劣于初始化后的食物源，則考慮更新舊食物源。

(2)全局對(duì)比 初始化后的食物源再與所有食物源集合的解對(duì)比，如果優(yōu)于食物源最差解，則直接替換食物源最差解部分。經(jīng)過(guò)兩次對(duì)比，即可保留較好的食物源并記錄在公告欄。

2.3 改進(jìn)人工蜂群算法設(shè)計(jì)

ABC算法的設(shè)計(jì)和具體問(wèn)題關(guān)系密切，下面對(duì)ABC算法求解TTAASBS/RS出入庫(kù)庫(kù)復(fù)合作業(yè)的關(guān)鍵技術(shù)進(jìn)行說(shuō)明，并給出算法流程。

2.3.1 編碼

利用ABC算法求解出入庫(kù)復(fù)合作業(yè)任務(wù)調(diào)度問(wèn)題時(shí)需對(duì)問(wèn)題進(jìn)行編碼，合適的編碼方式有助于簡(jiǎn)化問(wèn)題?；赥TAASBS/RS模型特性，采用出入庫(kù)混合整數(shù)編碼，編碼序號(hào)表示出入庫(kù)任務(wù)的編號(hào)和穿梭車作業(yè)編碼。假設(shè)有S對(duì)復(fù)合作業(yè)任務(wù)，則存在S個(gè)入庫(kù)任務(wù)和S個(gè)出庫(kù)任務(wù)，其中將S個(gè)出庫(kù)任務(wù)隨機(jī)編碼為1～S，S個(gè)入庫(kù)任務(wù)隨機(jī)編碼為S+1～2S，當(dāng)出庫(kù)任務(wù)數(shù)≠入庫(kù)任務(wù)數(shù)時(shí)，考慮任務(wù)補(bǔ)齊，將I/O點(diǎn)(0，0，0)位置做為虛擬的出庫(kù)(入庫(kù))作業(yè)位置，相當(dāng)于系統(tǒng)只執(zhí)行單指令出/入庫(kù)任務(wù)。

確定了穿梭車的任務(wù)序號(hào)就確定了轉(zhuǎn)載車的任務(wù)序列。其中穿梭車的數(shù)量為4個(gè)，分散在整個(gè)倉(cāng)庫(kù)系統(tǒng)。穿梭車的任務(wù)配比不固定，只確定每輛穿梭車的最小任務(wù)數(shù)量，若其出現(xiàn)故障，則改變最小作業(yè)數(shù)量，并保留浮動(dòng)任務(wù)數(shù)量，具體任務(wù)匹配數(shù)量由實(shí)驗(yàn)得出。例如，4輛穿梭車處理40個(gè)任務(wù)，在求解過(guò)程中，將求解問(wèn)題看作多旅行商問(wèn)題，每個(gè)穿梭車分配的最小任務(wù)數(shù)為8，剩余8個(gè)任務(wù)作為浮動(dòng)任務(wù)隨機(jī)分配。若車輛有故障，則只調(diào)整穿梭車的最小作業(yè)任務(wù)數(shù)量，例如由3輛穿梭車進(jìn)行出入庫(kù)作業(yè)，將最小任務(wù)數(shù)調(diào)整至12，剩余4個(gè)作為浮動(dòng)任務(wù)隨機(jī)分配給3個(gè)穿梭車。出入庫(kù)編號(hào)確定轉(zhuǎn)載車的編碼，如表3所示，出庫(kù)作業(yè)編號(hào)為2，對(duì)應(yīng)的出庫(kù)位置為(5,7,4)，位于第4層，采用編號(hào)為4的轉(zhuǎn)載車；入庫(kù)作業(yè)編號(hào)為33，對(duì)應(yīng)的入庫(kù)位置為(7,20,12)，對(duì)應(yīng)編號(hào)為12的轉(zhuǎn)載車。

圖9所示為ABC算法編碼方式，其中采用4個(gè)穿梭車執(zhí)行20對(duì)出入庫(kù)復(fù)合作業(yè)任務(wù)，穿梭車1執(zhí)行12→36→20→31→16→33→1→23→17→32→15→38,穿梭車2執(zhí)行14→27→5→30→19→21→6→25,穿梭車3執(zhí)行8→28→3→22→4→34→13→37→2→29,穿梭車4執(zhí)行9→26→11→24→18→38→7→40→20→39。

2.3.2 適應(yīng)度函數(shù)

本文以完成所有訂單內(nèi)復(fù)合作業(yè)的調(diào)度總時(shí)間最小為優(yōu)化目標(biāo)，則適應(yīng)度函數(shù)可表示為

fitness=T=minCmax。

式中：T為完成訂單內(nèi)所有出入庫(kù)作業(yè)的時(shí)間；Cmax為人工蜂群代表的完成所有任務(wù)的最大完成時(shí)間。

2.3.3 算法步驟

步驟1初始化蜜蜂種群，包括最大迭代次數(shù)MaxCycle、蜜源和總?cè)阂?guī)模SN，以及蜜源改善的最大搜索次數(shù)limit。

步驟2采用隨機(jī)選擇和規(guī)則選擇進(jìn)行種群初始化，種群規(guī)模為蜜蜂的個(gè)數(shù)。

步驟3評(píng)價(jià)所有蜜源適應(yīng)度并進(jìn)行排序，排名靠前的成為雇傭蜂，排名靠后的為觀察蜂，一般雇傭蜂和觀察蜂的數(shù)量為SN的一半。

步驟4雇傭蜂階段。雇傭蜂通過(guò)局部搜索尋找新的蜜源，結(jié)合設(shè)計(jì)的雇傭蜂階段交叉變異產(chǎn)生的新解重新計(jì)算適應(yīng)度函數(shù)值，然后根據(jù)貪婪準(zhǔn)則選擇更好的適應(yīng)度函數(shù)值所對(duì)應(yīng)的蜜源。

步驟5觀察蜂階段。引用動(dòng)態(tài)鄰域搜索增強(qiáng)觀察蜂搜索操作，觀察蜂根據(jù)適應(yīng)度值判斷是否跟隨雇傭蜂前往蜜源。

步驟6偵查蜂階段。如果雇傭蜂和觀察蜂在蜜源搜索次數(shù)超過(guò)limit時(shí)仍未找到更佳蜜源，則視為放棄該蜜源，對(duì)應(yīng)蜜蜂轉(zhuǎn)化成偵查蜂。

步驟7記錄當(dāng)前迭代次數(shù)的最優(yōu)適應(yīng)度值并記錄在公告欄，判斷是否滿足停止準(zhǔn)則，若滿足則停止算法，否則轉(zhuǎn)步驟3。

核心偽代碼如下：

Begin

1 %初始化算法

2 對(duì)初始種群、雇傭蜂、觀察蜂、蜜源、偵查蜂最大搜索次數(shù)等參數(shù)進(jìn)行初始化；

3 初始化路徑,x,y,z分別對(duì)應(yīng)轉(zhuǎn)載車、穿梭車、提升機(jī)運(yùn)行方向；

4 %開(kāi)始迭代人工蜂群

5 While(iter≤MaxCycle)

6 %雇傭蜂模式

7 for i=1:Foodnumber %Foodnumber為雇傭蜂數(shù)量為蜜源的一半

8 對(duì)雇傭蜂階段進(jìn)行交叉變異操作；

9 FitnessSol=calculateFitness(route_next); %計(jì)算新蜜源的適應(yīng)度函數(shù)

10 if(FitnessSol >Fitness(i))%若能找到更好的蜜源，則搜索次數(shù)清零；

11 trial(i)=0；

12 else

13 trial(i)=trial(i)+1;%若超過(guò)設(shè)定的limit次數(shù)，則雇傭蜂變?yōu)閭刹榉洌?/p>

14 end

15 end

16 i=1；

17 p(1)=fitness(i)/sum(fitness(i))；

18 for i=2:Foodnumber

19 p(i)=p(i-1)+fitness(i)/sum(fitness(i))；

20 end

21 %觀察蜂模式

22 for i=1:Foodnumber

23 if(rand

24 改進(jìn)后雇傭蜂對(duì)第1個(gè)蜜源進(jìn)行開(kāi)采；

25 FitnessSol=calculateFitness(route_next); %計(jì)算新蜜源的適應(yīng)度函數(shù)

26 if(FitnessSo1>Fitness(i)) %若能找到更好的蜜源，則搜索次數(shù)清零；

27 trial(i)=0;

28 else

29 trial(i)=trial(i)+1；

30 end

31 else

32 for i=2:Foodnumber

33 if(p(i-1)

34 改進(jìn)后雇傭蜂對(duì)第i個(gè)蜜源進(jìn)行開(kāi)采；

35 FitnessSol=calculateFitness(route_next); %計(jì)算新蜜源的適應(yīng)度函數(shù)

36 if(FitnessSo1>Fitness(i)) %若能找到更好的蜜源，則搜索次數(shù)清零

37 trial(i)=0;

38 else

39 trial(i)=trial(i)+1;

40 break

41 end

42 end

43 end

44 end

45 end

46 ind=find(Fitness==max(Fitness))；%記錄此時(shí)更優(yōu)的解

47 %偵查蜂階段

48 ind=find(trial==max(trial));

49 ind=ind(end);

50 if(trial(ind)>limit) %若搜索次數(shù)超過(guò)極限值，則進(jìn)行隨機(jī)搜索產(chǎn)生新的解

51 trial(i)=0； %表示產(chǎn)生了新解，未被開(kāi)采

52 對(duì)偵查蜂進(jìn)行最優(yōu)值對(duì)比操作；

53 %程序運(yùn)行完一次，記錄這一次的最優(yōu)時(shí)間

54 end

55 end

56 可視化視圖

End

3 仿真實(shí)驗(yàn)研究

為驗(yàn)證改進(jìn)的ABC算法在求解TTAASBS/RS路徑規(guī)劃問(wèn)題的有效性，采集和設(shè)計(jì)自動(dòng)化立體倉(cāng)儲(chǔ)中設(shè)備的性能參數(shù)，以滿足TTAASBS/RS的存儲(chǔ)規(guī)格。貨架層數(shù)為18，排數(shù)為14，深度為40列儲(chǔ)位，穿梭車數(shù)量為4，轉(zhuǎn)載車的數(shù)量為貨架層數(shù)18，提升機(jī)的數(shù)量為2，其余TTAASBS/RS的參數(shù)設(shè)置如表2所示。

表2 TTAASBS/RS參數(shù)表

用程序分別隨機(jī)生成20對(duì)復(fù)合作業(yè)任務(wù)，為了使實(shí)驗(yàn)結(jié)果真實(shí)有效，又增加30對(duì)和50對(duì)復(fù)合任務(wù)對(duì)分別進(jìn)行仿真研究。表3所示為20個(gè)復(fù)合作業(yè)任務(wù)對(duì)，分為出庫(kù)任務(wù)與入庫(kù)任務(wù)。

表3 出入庫(kù)任務(wù)表

根據(jù)穿梭車是否跨層跨巷道將復(fù)合作業(yè)時(shí)間分為3類，分別為跨層作業(yè)(跨巷道和不跨巷道)、不跨層跨巷道作業(yè)和不跨層不跨巷道作業(yè)，假定出庫(kù)貨位a和入庫(kù)貨位b的坐標(biāo)分別為(xa,ya,za)和(xb,yb,zb)，則穿梭車以上一入庫(kù)作業(yè)位置(xb-1,yb-1,zb-1)為初始位置開(kāi)始作業(yè)，完成一次完整的出入庫(kù)作業(yè)任務(wù)所需要的時(shí)間為

(26)

一次完整的出入庫(kù)作業(yè)任務(wù)示意圖如圖10所示。

圖10和式(26)中：t1，t8，t14，t18為穿梭車單獨(dú)運(yùn)行時(shí)間，t3，t7_1，t7_2，t13為穿梭車結(jié)合轉(zhuǎn)載車運(yùn)行時(shí)間，t5，t11為提升機(jī)結(jié)合穿梭車運(yùn)行時(shí)間，虛線表示未發(fā)生實(shí)際運(yùn)動(dòng)，以上運(yùn)動(dòng)時(shí)間與設(shè)備運(yùn)行距離以及速度、加減速度有關(guān)；t2，t6，t9，t12為穿梭車等待轉(zhuǎn)載車的時(shí)間，t4，t10為等待提升機(jī)的時(shí)間，在圖中已標(biāo)出；t15為提升機(jī)裝(卸)穿梭車時(shí)間，t16為轉(zhuǎn)載車裝(卸)穿梭車時(shí)間，t17為穿梭車裝(卸)貨物時(shí)間，t15，t16，t17為定值。

采用程序?yàn)楦鞔┧筌嚪謩e隨機(jī)分配一組出入庫(kù)復(fù)合作業(yè)任務(wù)順序：穿梭車1為12→36→14→40→20→39→8→28，穿梭車2為16→33→9→26→19→21→11→24→1→23→5→30，穿梭車3為3→22→6→25→17→32→4→34→18→35，穿梭車4為13→37→15→38→7→40→2→29→10→39。最終花費(fèi)時(shí)間為792.4 s。

采用基本ABC算法為穿梭車分配如下出入庫(kù)復(fù)合作業(yè)任務(wù)順序：穿梭車1為7→22→14→27→2→26→10→35；穿梭車2為18→38→4→28→15→31→17→30→11→39，穿梭車3為3→40→8→37→12→25→20→24→1→33→6→23，穿梭車4為19→32→13→34→16→21→5→29→9→36。最終花費(fèi)時(shí)間為664.2 s。

采用改進(jìn)的ABC算法進(jìn)行優(yōu)化，根據(jù)文獻(xiàn)[27]對(duì)ABC算法參數(shù)進(jìn)行分析，設(shè)置改進(jìn)后的ABC算法參數(shù)為：初始蜜源SN=80，F(xiàn)oodnumber=SN/2，偵查蜂蜂群搜索最大搜索次數(shù)limit=100，MaxCycle=500，并采用相應(yīng)的交叉變異操作。優(yōu)化后的作業(yè)順序如下：穿梭車1為3→27→14→40→7→34→17→33→15→36，穿梭車2為8→26→10→29→18→30→6→21→1→24，穿梭車3為5→39→9→25→13→35→2→31→11→28，穿梭車4為4→32→12→22→19→37→16→39→20→23。最終花費(fèi)時(shí)間為633.5 s，結(jié)果如表4所示。

表4 原始作業(yè)任務(wù)與改進(jìn)后作業(yè)任務(wù)對(duì)比

如表4所示，當(dāng)原始路徑隨機(jī)分配時(shí)，穿梭車分配任務(wù)數(shù)量不均衡，任務(wù)序列未優(yōu)化，導(dǎo)致完成所有任務(wù)所需的時(shí)間較長(zhǎng)；基本ABC算法在一定程度上優(yōu)化了任務(wù)完成時(shí)間，但是單個(gè)穿梭車分配的任務(wù)個(gè)數(shù)相對(duì)不均衡；改進(jìn)的ABC算法優(yōu)化了穿梭車的作業(yè)任務(wù)數(shù)，使單個(gè)穿梭車分配的任務(wù)數(shù)量更加均衡，進(jìn)一步縮短了作業(yè)任務(wù)總時(shí)間。

為驗(yàn)證算法有效性，將本文算法分別與基本ABC算法、GA、改進(jìn)的蟻群算法[28]、改進(jìn)的人工魚(yú)群算法[3]對(duì)出入庫(kù)復(fù)合作業(yè)調(diào)度進(jìn)行實(shí)驗(yàn)對(duì)比。給定GA的交叉、變異規(guī)則，規(guī)定采用部分映射交叉，交叉概率pc=0.8，選用非均勻變異，變異概率pm=0.1，種群規(guī)模size=500；對(duì)5種算法進(jìn)行綜合比對(duì)，分別記錄5種算法求解的最優(yōu)值和解的標(biāo)準(zhǔn)偏差，以20對(duì)復(fù)合作業(yè)任務(wù)對(duì)為實(shí)驗(yàn)基礎(chǔ)，采用MATLAB 2017編程，運(yùn)行30次，并在每次迭代100次不改變最優(yōu)值時(shí)記錄該最優(yōu)值，結(jié)果如表5所示。

表5 5種算法針對(duì)20個(gè)任務(wù)對(duì)的實(shí)驗(yàn)結(jié)果

圖11所示為算例的5種算法各獨(dú)立運(yùn)行30次的平均收斂過(guò)程曲線。

由表5和圖11，結(jié)合本文問(wèn)題分析可知：GA因收斂較慢且容易陷入局部最優(yōu)，導(dǎo)致求解精度差、效率低；基本ABC算法具有較強(qiáng)的全局搜索能力，然而由于隨機(jī)鄰域搜索導(dǎo)致雇傭蜂搜索能力低，以及觀察蜂更新形式具有局限性等問(wèn)題，使得求解精度較差；改進(jìn)的蟻群算法雖然能夠較快接近最優(yōu)解，但是在求解復(fù)雜問(wèn)題時(shí)存在局限性，跳出最優(yōu)解的能力較弱且求解時(shí)間較長(zhǎng)，需要迭代更多次數(shù)才能達(dá)到相對(duì)最優(yōu)解，求解精度劣于改進(jìn)人工魚(yú)群算法；改進(jìn)的人工魚(yú)群算法在求解最優(yōu)值方面相對(duì)其他3種算法雖然在尋優(yōu)上具有一定優(yōu)勢(shì)，但是相對(duì)本文改進(jìn)ABC算法，求解精度較低、算法運(yùn)行時(shí)間更長(zhǎng)。本文改進(jìn)的ABC算法，通過(guò)改進(jìn)初始種群生成以及雇傭蜂階段的交叉變異操作，使算法的全局搜索能力更優(yōu)，而且在觀察峰階段采用鄰域搜索及時(shí)跳出局部最優(yōu)去搜索更優(yōu)解，較其他4種算法具有更強(qiáng)的全局搜索能力和跳出局部最優(yōu)解的能力，相對(duì)于改進(jìn)的人工魚(yú)群算法具有更強(qiáng)的最優(yōu)值求解能力。

在不同任務(wù)量下，改進(jìn)ABC算法較其他5種算法均表現(xiàn)出更優(yōu)的穩(wěn)定性和求解效率。為更進(jìn)一步驗(yàn)證算法有效性，增加復(fù)合作業(yè)任務(wù)對(duì)數(shù)，求解結(jié)果如表6所示。

表6 5種算法在不同規(guī)模下的實(shí)驗(yàn)結(jié)果

30個(gè)任務(wù)對(duì)和50個(gè)任務(wù)對(duì)的作業(yè)規(guī)模算法迭代如圖12和圖13所示。

從表6、圖12和圖13可見(jiàn)，隨著任務(wù)量的增加，5種算法的優(yōu)越性更加明顯，其最優(yōu)解均值都不同程度地小于隨機(jī)生成解的均值。然而對(duì)比5種算法可以發(fā)現(xiàn)，改進(jìn)后的ABC算法的求解精度和優(yōu)化效率均高于其他4種算法。改進(jìn)的蟻群算法在前期求解質(zhì)量較好，后期跳出局部最優(yōu)的能力不足，且求解穩(wěn)定性不如其他改進(jìn)算法，求解效果不如改進(jìn)的人工魚(yú)群算法；改進(jìn)的人工魚(yú)群算法在求解效率上明顯弱于ABC算法，由于求解的任務(wù)量增大，改進(jìn)的人工魚(yú)群算法為確保求解精度導(dǎo)致收斂速度較慢，以至于后期求解效果不佳;而改進(jìn)后的ABC算法在求解復(fù)雜的倉(cāng)儲(chǔ)調(diào)度問(wèn)題方面能夠保證求解精度和求解穩(wěn)定性，證明了其在求解該類問(wèn)題時(shí)具有優(yōu)勢(shì)。

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

本文對(duì)TTAASBS/RS復(fù)合作業(yè)路徑進(jìn)行研究，為提高TTAASBS/RS的出入庫(kù)復(fù)合作業(yè)效率，對(duì)該系統(tǒng)復(fù)合作業(yè)三維路徑進(jìn)行研究；為貼合實(shí)際倉(cāng)儲(chǔ)系統(tǒng)的運(yùn)行規(guī)律，考慮穿梭車、轉(zhuǎn)載車和提升機(jī)的加減速度，將設(shè)備運(yùn)行規(guī)律類比到混合流水線模型，并建立了三任務(wù)五階段的復(fù)合作業(yè)調(diào)度模型；而且設(shè)計(jì)了改進(jìn)的ABC算法對(duì)該模型進(jìn)行仿真求解，并通過(guò)實(shí)驗(yàn)與其他改進(jìn)算法進(jìn)行對(duì)比。

實(shí)例仿真結(jié)果表明，改進(jìn)的ABC算法在求解跨層跨巷道復(fù)合作業(yè)路徑規(guī)劃問(wèn)題上具有優(yōu)越性，其算法效率較基本GA、基本ABC算法、改進(jìn)人工魚(yú)群、改進(jìn)蟻群算法有較大提升，能夠提高算法效率，優(yōu)化作業(yè)路徑。

TTAASBS/RS復(fù)合作業(yè)路徑優(yōu)化涉及多方面要素，可以進(jìn)一步研究的方向如下：

(1)穿梭車、轉(zhuǎn)載車和提升機(jī)三者之間存在能力匹配問(wèn)題。實(shí)際工程應(yīng)用中穿梭車數(shù)量的配置比較靈活，當(dāng)任務(wù)規(guī)模變大時(shí)，首先可以考慮提高每輛穿梭車的最小作業(yè)任務(wù)數(shù)量，其次考慮不超出提升機(jī)能力的情況下增加穿梭車數(shù)量。若超出提升機(jī)的能力，則考慮增加提升機(jī)數(shù)量來(lái)緩解瓶頸，此時(shí)需要重新調(diào)整模型結(jié)構(gòu)。

(2)本文案例研究中，穿梭車、轉(zhuǎn)載車和提升機(jī)三者之間能力平衡。為了降低模型的復(fù)雜度，本文模型假設(shè)“一旦穿梭車進(jìn)入某一巷道，就鎖死該巷道”，避免了同一巷道出現(xiàn)兩輛穿梭車的情況。然而，理論上存在兩輛穿梭車在同一巷道執(zhí)行任務(wù)的情況，可進(jìn)一步深入研究。

(3)本文未考慮穿梭車運(yùn)行過(guò)程中發(fā)生故障后剩余任務(wù)的分配問(wèn)題，可作為繼續(xù)研究的內(nèi)容。

(4)本文轉(zhuǎn)載車的數(shù)量設(shè)定為每層一臺(tái)，未來(lái)可結(jié)合跨層跨巷道倉(cāng)儲(chǔ)系統(tǒng)的資源配置進(jìn)行深入研究，使轉(zhuǎn)載車的數(shù)量最少，并研究最優(yōu)的轉(zhuǎn)載車和穿梭車數(shù)量配比。