跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)復(fù)合作業(yè)路徑規(guī)劃

魯建廈，陳壽伍，易文超，湯洪濤

(1.浙江工業(yè)大學(xué) 機(jī)械工程學(xué)院，浙江 杭州 310032；2.浙江匯智物流裝備技術(shù)有限公司，浙江 湖州 313028)

0 引言

跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)[1](Tier-to-Tier Multi-Shuttle Warehouse System, TTMSWS)是近年來(lái)出現(xiàn)的一種新型智能立體倉(cāng)庫(kù)。相比多層穿梭車倉(cāng)儲(chǔ)系統(tǒng)，穿梭車通過(guò)提升機(jī)實(shí)現(xiàn)跨層運(yùn)動(dòng)，以到達(dá)貨架的不同層工作，具有更高的柔性和魯棒性，從而減少穿梭車的數(shù)量。跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)存在兩種作業(yè)方式：①單一作業(yè)方式：?jiǎn)稳霂?kù)作業(yè)、單出庫(kù)作業(yè)；②復(fù)合作業(yè)方式：當(dāng)系統(tǒng)同時(shí)有出庫(kù)和入庫(kù)指令時(shí)，穿梭車即執(zhí)行出入庫(kù)交叉作業(yè)。為提高系統(tǒng)存儲(chǔ)效率，穿梭車采用復(fù)合作業(yè)方式運(yùn)作?？鐚哟┧筌噦}(cāng)儲(chǔ)系統(tǒng)中每個(gè)任務(wù)都可以選擇不同的穿梭車，導(dǎo)致穿梭車的路線選擇也不同，進(jìn)而有不同的任務(wù)作業(yè)時(shí)間，并會(huì)對(duì)提升機(jī)的移載過(guò)程產(chǎn)生影響，從而導(dǎo)致這些不同的組合、順序有不同的結(jié)果，因此在跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)中對(duì)多穿梭車和提升機(jī)的協(xié)同調(diào)度具有重要意義。

目前，為了適應(yīng)穿梭車式倉(cāng)儲(chǔ)系統(tǒng)的發(fā)展與應(yīng)用，國(guó)內(nèi)外學(xué)者進(jìn)行了相關(guān)研究。WANG等[2]提出基于穿梭車和提升機(jī)的任務(wù)作業(yè)時(shí)序模型，并利用非支配排序遺傳算法進(jìn)行求解。楊瑋等[3]在每層一臺(tái)穿梭車的立體倉(cāng)庫(kù)中，提出雙載式穿梭車路徑優(yōu)化問(wèn)題，建立了雙載式多層穿梭車倉(cāng)儲(chǔ)系統(tǒng)復(fù)合作業(yè)模型，并運(yùn)用混合植物繁殖算法對(duì)該模型進(jìn)行優(yōu)化求解。CARLO等[4]針對(duì)在多個(gè)巷道可共享使用兩個(gè)提升機(jī)的多層穿梭車立體倉(cāng)庫(kù)進(jìn)行了研究，以進(jìn)出庫(kù)作業(yè)時(shí)間最短為目標(biāo)函數(shù)建立調(diào)度模型，確定了兩個(gè)提升機(jī)的調(diào)用順序。ZHAO等[5]在Carlo的基礎(chǔ)上考慮了穿梭車與提升機(jī)的加減速特性。楊瑋等[6]針對(duì)子母式穿梭車倉(cāng)儲(chǔ)系統(tǒng)復(fù)合作業(yè)路徑優(yōu)化問(wèn)題，在提升機(jī)數(shù)量與子母穿梭車數(shù)量為1∶2的前提下，利用改進(jìn)的自適應(yīng)粒子群算法進(jìn)行了求解。郭紅麗[7]介紹了每層一臺(tái)穿梭車和m層n臺(tái)穿梭車兩種形式的自動(dòng)化立體倉(cāng)庫(kù)，對(duì)立體倉(cāng)庫(kù)的揀選作業(yè)進(jìn)行了分析。張娜[8]對(duì)單出庫(kù)的跨層穿梭車系統(tǒng)進(jìn)行建模，并采用Gurobi求解器進(jìn)行求解。Marchet等[9]完成了每層一臺(tái)穿梭車和m層n臺(tái)穿梭車兩種形式的自動(dòng)小車存取系統(tǒng)(Automated Vehicle Storage and Retrieval System, AVS/RS)研究，并利用仿真分析了不同自動(dòng)小車存取系統(tǒng)的配置下的立庫(kù)吞吐量。方彥軍等[10]研究了AVS/RS復(fù)合作業(yè)三維路徑優(yōu)化問(wèn)題，并采用改進(jìn)人工狼群算法求解，驗(yàn)證了算法的有效性。鄒霞等[11]針對(duì)集中式和分散式的自動(dòng)存儲(chǔ)系統(tǒng)(Automated Storage and Retrieval System, AS/RS)倉(cāng)儲(chǔ)中，考慮了設(shè)備的加減速，通過(guò)分析設(shè)備運(yùn)行時(shí)間模型研究了貨架結(jié)構(gòu)和訂單密度對(duì)系統(tǒng)的影響。

跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)相對(duì)于多層穿梭車倉(cāng)儲(chǔ)系統(tǒng)，能最大程度地避免訂單量較少而穿梭車閑置的情形并減少投資成本，目前在部分企業(yè)已得到使用。但是，國(guó)內(nèi)外對(duì)于跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)的相關(guān)文獻(xiàn)較少，在該類倉(cāng)儲(chǔ)系統(tǒng)的調(diào)度優(yōu)化中存在著較大的進(jìn)步空間。而關(guān)于穿梭車的跨層作業(yè)研究，多見于自動(dòng)小車存取系統(tǒng)和子母穿梭車存取系統(tǒng)，這對(duì)于跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)的研究有一定的參考價(jià)值。關(guān)于多層穿梭車倉(cāng)儲(chǔ)系統(tǒng)的已有文獻(xiàn)研究主要集中在單層作業(yè)模式下，對(duì)于跨層作業(yè)模式的研究很少，且其研究對(duì)象僅針對(duì)單出庫(kù)或單入庫(kù)任務(wù)，并且相關(guān)研究的模型中均未考慮設(shè)備的運(yùn)動(dòng)特性，與實(shí)際情況有較大誤差，求解方式多為規(guī)劃器求解或單一的優(yōu)化算法，對(duì)于跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)調(diào)度路徑規(guī)劃有一定的局限性。

倉(cāng)儲(chǔ)系統(tǒng)復(fù)合作業(yè)路徑規(guī)劃問(wèn)題是一個(gè)NP難問(wèn)題[12]，使用確定性算法獲得精確解是耗時(shí)且困難的，故學(xué)者通常采用智能算法求解。而由李曉磊[13]提出的通過(guò)構(gòu)造人工魚來(lái)模仿魚群覓食、聚群及追尾行為，實(shí)現(xiàn)尋優(yōu)的優(yōu)化算法——人工魚群算法(Artificial Fish Swarm Algorithm, AFSA)，因其具有初值魯棒性強(qiáng)、全局性、簡(jiǎn)單性等優(yōu)點(diǎn)而被廣泛應(yīng)用。目前，已有很多針對(duì)人工魚群算法的改進(jìn)算法及應(yīng)用實(shí)例：如馬憲民等[14]提出自適應(yīng)視野的改進(jìn)人工魚群算法，僅對(duì)人工魚的覓食視野進(jìn)行調(diào)整，求解路網(wǎng)最短路徑問(wèn)題。趙敏等[15]采用了步長(zhǎng)參數(shù)分解和柔性參數(shù)設(shè)置等改進(jìn)策略，提出了一種基于改進(jìn)ASFA求解柔性作業(yè)車間調(diào)度問(wèn)題(Flexible Job shop Scheduling Problem, FJSP)問(wèn)題；周永權(quán)等[16]引入交叉算子和去交叉策略對(duì)人工魚群算法進(jìn)行改進(jìn)，并將其用于解決旅行商問(wèn)題(Traveling Salesman Problem,TSP)。

本文從作業(yè)排序和作業(yè)路徑的角度，以跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)出入庫(kù)復(fù)合作業(yè)為研究對(duì)象，考慮提升機(jī)和穿梭車的加減速特性，根據(jù)倉(cāng)儲(chǔ)系統(tǒng)實(shí)際作業(yè)運(yùn)行過(guò)程建立TTMSWS出入庫(kù)復(fù)合作業(yè)數(shù)學(xué)模型，并設(shè)計(jì)了改進(jìn)人工魚群算法(Improved Artificial Fish Swarm Algorithm, IAFSA)，對(duì)不同條目訂單的出入庫(kù)作業(yè)問(wèn)題進(jìn)行優(yōu)化求解，力求在接近實(shí)際作業(yè)的情況下最小化出入庫(kù)的總行程時(shí)間。最后，將結(jié)果與遺傳算法和基本人工魚群算法對(duì)比，驗(yàn)證了算法的有效性。

1 TTMSWS路徑優(yōu)化問(wèn)題的描述與建模

1.1 問(wèn)題描述

跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)主要由穿梭車、提升機(jī)、軌道和存儲(chǔ)貨架等組成。其中，穿梭車在貨架軌道上運(yùn)行，負(fù)責(zé)貨物的水平搬運(yùn)，提升機(jī)安裝在巷道口，實(shí)現(xiàn)穿梭車的跨層運(yùn)動(dòng)。如圖1所示為其貨架立面圖。

圖2為穿梭車一次出入庫(kù)復(fù)合作業(yè)示意圖。其中X軸為巷道布置方向，代表穿梭車運(yùn)動(dòng)方向；Y軸為提升機(jī)布置方向，代表提升機(jī)運(yùn)行方向。提升機(jī)與穿梭車共同完成一次出入庫(kù)復(fù)合作業(yè)需要經(jīng)歷3次節(jié)點(diǎn)變化：

(1)穿梭車從當(dāng)前節(jié)點(diǎn)運(yùn)行至出庫(kù)貨位節(jié)點(diǎn)；

(2)穿梭車從出庫(kù)貨位節(jié)點(diǎn)運(yùn)行至出入庫(kù)節(jié)點(diǎn)(I/O點(diǎn))；

(3)穿梭車從出入庫(kù)節(jié)點(diǎn)(I/O點(diǎn))運(yùn)行至入庫(kù)貨位節(jié)點(diǎn)。

對(duì)于出入庫(kù)復(fù)合作業(yè)過(guò)程中的3個(gè)指令，皆可以表示為穿梭車從初始位置運(yùn)行至目標(biāo)位置的過(guò)程。如圖3所示，該過(guò)程可分為穿梭車初始位置與目標(biāo)位置是否同層兩種情況。

(1)穿梭車初始位置與目標(biāo)位置同層

1)系統(tǒng)下達(dá)指令給穿梭車；

2)穿梭車從當(dāng)前位置(即上次任務(wù)終止的位置)啟動(dòng)，直接水平運(yùn)行至目標(biāo)位置。

(2)穿梭車初始位置與目標(biāo)位置不同層

1)系統(tǒng)下達(dá)指令給穿梭車；

2)穿梭車從當(dāng)前位置啟動(dòng)，水平運(yùn)行至該層提升機(jī)工作站臺(tái)處；

3)穿梭車請(qǐng)求提升機(jī)，并等待提升機(jī)到達(dá)該層；

4)穿梭車搭乘提升機(jī)垂直運(yùn)行至目標(biāo)位置所在層；

5)穿梭車從該層提升機(jī)工作站臺(tái)水平運(yùn)動(dòng)至目標(biāo)位置。

TTMSWS出入庫(kù)復(fù)合作業(yè)的每個(gè)指令可以視為3階段的混合流水作業(yè)[17]。

不同于一般的混合流水線調(diào)度問(wèn)題，TTMSWS特點(diǎn)如下：

(1)跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)的出入庫(kù)復(fù)合作業(yè)單元(將出庫(kù)任務(wù)和入庫(kù)任務(wù)結(jié)合作業(yè)定義為一個(gè)作業(yè)單元)之間存在一部分先后順序約束，即出庫(kù)任務(wù)優(yōu)先于入庫(kù)任務(wù)。

(2)一組出入庫(kù)復(fù)合作業(yè)單元中所用到的穿梭車為同一輛穿梭車。

(3)在執(zhí)行任務(wù)之前，必須將提升機(jī)移動(dòng)到指定位置。提升機(jī)的調(diào)整時(shí)間即提升機(jī)的空跑時(shí)間，取決于任務(wù)執(zhí)行序列。

(4)一組出入庫(kù)復(fù)合作業(yè)單元中，當(dāng)穿梭車執(zhí)行完某一階段的指令時(shí)，馬上開始下一階段的執(zhí)行，中間過(guò)程不中斷，直至該組出入庫(kù)復(fù)合作業(yè)單元執(zhí)行完畢。

1.2 TTMSWS復(fù)合作業(yè)模型建立

根據(jù)TTMSWS運(yùn)行現(xiàn)狀，為研究方便且不失一般性，假設(shè)如下：

(1)貨物采用隨機(jī)存儲(chǔ)策略，出庫(kù)貨物或入庫(kù)貨物都有一個(gè)確定的貨位；

(2)提升機(jī)和穿梭車運(yùn)動(dòng)過(guò)程均存在加(減)速度；

(3)提升機(jī)和穿梭車執(zhí)行完系統(tǒng)分配的任務(wù)后，若無(wú)新任務(wù)到達(dá)，則就近停止；

(4)設(shè)備空載和負(fù)載的移動(dòng)速度相同；

(5)對(duì)同一輛穿梭車或提升機(jī)同一時(shí)刻只能執(zhí)行一個(gè)任務(wù)；

(6)當(dāng)該層有穿梭車時(shí)，不允許其他穿梭車進(jìn)入；

(7)當(dāng)穿梭車或提升機(jī)開始執(zhí)行一個(gè)任務(wù)時(shí)，必須執(zhí)行完該任務(wù)，不允許中斷。

在此基礎(chǔ)上，進(jìn)行參數(shù)與變量定義：已知每個(gè)出入庫(kù)復(fù)合作業(yè)必須依次經(jīng)過(guò)3個(gè)階段設(shè)備的操作。設(shè)i為操作階段索引，i=1,2,3，依此表示穿梭車從當(dāng)前位置至提升機(jī)所在位置的運(yùn)行階段，提升機(jī)搭載穿梭車至目標(biāo)層的運(yùn)行階段，穿梭車出提升機(jī)至到達(dá)目標(biāo)節(jié)點(diǎn)的運(yùn)行階段。因此，本文所研究的問(wèn)題可以轉(zhuǎn)化為三階段的混合流水線調(diào)度問(wèn)題，貨物出入庫(kù)復(fù)合作業(yè)單元為n(n=1,2,3,…,N)。則根據(jù)對(duì)穿梭車的作業(yè)指令分析，將每個(gè)作業(yè)單元都劃分為3個(gè)任務(wù)，即第n個(gè)作業(yè)單元可分為第3n-2個(gè)任務(wù)、第3n-1個(gè)任務(wù)和第3n個(gè)任務(wù)。記b為任務(wù)序號(hào)，b=1,2,3…,3n-2,3n-1,3n,…,3N-2,3N-1,3N，其中n為單元編號(hào)。s為階段編號(hào)，s=1,2,3；k為作業(yè)設(shè)備編號(hào)，k=1,2,…,ms；ms為第s階段的作業(yè)設(shè)備數(shù)，其中m1=m3=Q，表示第一階段和第三階段的設(shè)備數(shù)量即穿梭車的數(shù)量；m2=2，該階段的第一個(gè)設(shè)備為實(shí)際運(yùn)行的提升機(jī)，第二個(gè)為虛擬提升機(jī)，選擇該提升機(jī)表示該階段無(wú)需進(jìn)行跨層運(yùn)動(dòng)。tbs為任務(wù)b在s階段的開始時(shí)間；pbs為任務(wù)b在s階段的作業(yè)時(shí)間；wbb′sk為s階段機(jī)器k操作的兩個(gè)連續(xù)任務(wù)b和b′之間的準(zhǔn)備時(shí)間，而僅存在于第二階段的第一個(gè)設(shè)備中，即提升機(jī)在連續(xù)作業(yè)之間的空載時(shí)間；G為足夠大的數(shù)；Cmax為所有任務(wù)的最大完成時(shí)間。

因此，TTMSWS復(fù)合作業(yè)調(diào)度模型可以表示為

minCmax。

(1)

s.t.

(2)

tbs≥0;

b=1,2,3,…,3N;s=1,2,3;

(3)

tbs≥t(b-1)s;

b=3n-1,3n,n=1,2,…,N;

s=1,2,3;

(4)

tbs+pbs≤tb(s+1);

b=1,2,3,…,3N;s=1,2;

(5)

xb1k=xb3k;

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

(6)

xb1k=x(b-1)1k;

b=3n-1,3n,n=1,2,…,N；

k=1,2,…,Q;

(7)

tb′2-wbb′21-(tb2+pb2)≥G(ybb′21-1);

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

(8)

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

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

(9)

b=1,2,…,3N;s=1,2,3;k=1,2,…,ms;

(10)

b=1,2,…,3N;s=1,2,3;k=1,2,…,ms;

(11)

Cmax≥tb3+pb3;

b=3n,n=1,2,…,N;

(12)

(13)

(14)

其中：式(1)為調(diào)度性能指標(biāo)；式(2)確保每個(gè)任務(wù)在每個(gè)階段僅由一臺(tái)設(shè)備執(zhí)行；式(3)保證所有任務(wù)開始時(shí)間均在系統(tǒng)開始作業(yè)之后；式(4)保證屬于同一作業(yè)單元的3個(gè)任務(wù)的先后關(guān)系；式(5)定義了每個(gè)任務(wù)在不同階段開始時(shí)間的關(guān)系；式(6)保證每個(gè)任務(wù)的階段1和階段3由同一設(shè)備完成；式(7)保證同一單元的前后任務(wù)的階段1由同一設(shè)備完成，即式(6)和式(7)表明同一個(gè)單元由一輛穿梭車開始執(zhí)行至該單元結(jié)束；式(8)表示提升機(jī)連續(xù)的前后任務(wù)開始時(shí)間的關(guān)系；式(9)表示穿梭車連續(xù)的前后任務(wù)開始時(shí)間的關(guān)系；式(10)和式(11)表示在每臺(tái)設(shè)備作業(yè)序列中，每個(gè)任務(wù)最多有一個(gè)前序任務(wù)與后續(xù)任務(wù)。式(12)定義了Cmax，Cmax大于等于每一個(gè)作業(yè)單元的完成時(shí)間。式(13)和式(14)為變量取值定義。

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

2.1 基本人工魚群算法

人工魚群算法通過(guò)模擬魚的追尾、聚群和覓食等行為指導(dǎo)人工魚在解空間進(jìn)行尋優(yōu)。人工魚個(gè)體的狀態(tài)可表示為向量X=(x1,x2,…,xn)，代表問(wèn)題的一個(gè)解；人工魚當(dāng)前所在位置的食物濃度表示為Y=f(X)，即適應(yīng)度函數(shù)值。visual表示其視野范圍，移動(dòng)步長(zhǎng)為Step，魚群的擁擠度因子為δ，魚群中可以互相交換彼此間的信息，包括當(dāng)前位置、食物濃度等。魚群的具體行為描述如下：

(1)覓食行為 人工魚個(gè)體在其視野范圍內(nèi)隨機(jī)選取一個(gè)位置Xj，若該位置所具有的食物濃度優(yōu)于當(dāng)前所在位置，則人工魚向該位置移動(dòng)一步;否則超過(guò)規(guī)定試探次數(shù)Try_number而找不到符合條件的Xj，則在其視野范圍內(nèi)隨機(jī)移動(dòng)一步。

(2)追尾行為 人工魚個(gè)體在其視野范圍內(nèi)找到食物濃度最佳的伙伴Xmax，并且該伙伴周圍不太擁擠，則向該位置隨機(jī)移動(dòng)一步;否則轉(zhuǎn)而執(zhí)行覓食行為。

(3)聚群行為 人工魚個(gè)體在其視野范圍內(nèi)找到處于中心位置的伙伴Xc，并且并且該伙伴周圍不太擁擠，則向該位置隨機(jī)移動(dòng)一步;否則轉(zhuǎn)而執(zhí)行覓食行為。

人工魚選擇其中最優(yōu)的行為，并將最優(yōu)位置及其對(duì)應(yīng)的食物濃度記錄在公告板中，當(dāng)達(dá)到最大迭代次數(shù)時(shí)，停止迭代并輸出公告板上的最優(yōu)解。

2.2 改進(jìn)的人工魚群算法設(shè)計(jì)

如圖4所示為IAFSA流程圖。本文在基本的人工魚群算法上，采用自適應(yīng)視野，并提出帶吸引性的覓食行為，同時(shí)引進(jìn)變鄰域搜索算子來(lái)尋找最優(yōu)解決方案。該算法中，AFSA通過(guò)魚群的追尾、聚群和覓食行為，來(lái)對(duì)公布板進(jìn)行更新，找到全局最優(yōu)解位置，當(dāng)算法陷入局部最優(yōu)時(shí)，利用變鄰域搜索算法(Variable Neighborhood Search, VNS)搜索該位置及其鄰域范圍，以此來(lái)使算法在早熟收斂時(shí)跳出局部最優(yōu)解。最后重復(fù)IAFSA的迭代過(guò)程，直到滿足終止條件。

2.2.1 采用自適應(yīng)視野

在基本AFSA中，所有人工魚的視野visual都是固定值。而人工魚視野是尋優(yōu)的重要參數(shù)。對(duì)于人工魚視野的改進(jìn)，其主要目的是在全局探索較優(yōu)解時(shí)，利用較大的視野充分開拓搜索空間，在局部搜索時(shí)，應(yīng)縮短視野，提高尋優(yōu)精度[18]?；诖?，本文結(jié)合全局最優(yōu)值，建立了考慮迭代與收斂速度的人工魚視野自適應(yīng)變化。

(14)

2.2.2 帶吸引性的覓食行為

通常魚群會(huì)趨向于水塘中食物越多的位置，食物越多，該位置對(duì)于魚群個(gè)體的吸引性就越強(qiáng)，故提出帶吸引性的覓食行為，在原覓食行為的基礎(chǔ)上加入全局最優(yōu)信息。即在人工魚隨機(jī)移動(dòng)狀態(tài)Xj(Yj

Xi|next=comb(Xj,Xbest)。

(15)

具體實(shí)現(xiàn)方式：比較Xj和Xbest解序列，保留兩序列中都出現(xiàn)的連續(xù)n個(gè)序列放入Xi|next，其余部分按Xi排列填充并去除重復(fù)節(jié)點(diǎn)。

2.2.3 引入變鄰域搜索策略

在算法的不斷迭代下，人工魚群中的人工魚個(gè)體會(huì)逐漸游向相同或近似的位置，即表現(xiàn)為人工魚個(gè)體的編碼會(huì)趨向相同的情況。所以在每次的迭代中，魚群中并不一定能產(chǎn)生更優(yōu)的狀態(tài)，將沒(méi)有產(chǎn)生更優(yōu)狀態(tài)的迭代稱為無(wú)效迭代[19]。為了改善人工魚群算法陷入多次無(wú)效迭代，本文基于VNS[20]的思想，對(duì)人工魚進(jìn)行擾動(dòng)，用多種鄰域結(jié)構(gòu)，系統(tǒng)改變其鄰域，拓展搜索范圍，增強(qiáng)算法跳出局部最優(yōu)的能力。

根據(jù)TTMSWS的編碼特點(diǎn)，本文設(shè)置了3種鄰域結(jié)構(gòu)：

(1)Swap鄰域 在去除標(biāo)志位的人工魚解序列中隨機(jī)選擇兩個(gè)不同位置x和y，為保證人工魚的合法性，此時(shí)x和y必須都為奇數(shù)或偶數(shù)，即對(duì)應(yīng)的任務(wù)類型需一致，都為出庫(kù)任務(wù)或入庫(kù)任務(wù)，互換其對(duì)應(yīng)的任務(wù)。

(2)Insert鄰域 將一組出入庫(kù)作業(yè)視作一個(gè)復(fù)合單元，即在編碼中將其作為單元數(shù)組(cell array)，則原人工魚的解序列可視作包含cell數(shù)組的數(shù)組形式，在該數(shù)組中隨機(jī)選擇兩個(gè)不同的位置x和y，把位置x對(duì)應(yīng)的cell數(shù)組插入位置y中。

(3)2-opt鄰域 同(2)中對(duì)人工魚解序列的操作，形成新的數(shù)組形式，在該數(shù)組中隨機(jī)選擇兩個(gè)不同的位置x和y，將x到y(tǒng)之間的路徑翻轉(zhuǎn)其編號(hào)后添加到新路徑中，其余路徑不變。

2.3 求解TTMSWS路徑的改進(jìn)人工魚群算法設(shè)計(jì)

2.3.1 編碼

基于TTMSWS調(diào)度模型的特點(diǎn)，采用出入庫(kù)混合整數(shù)編碼方式，編碼序號(hào)代表任務(wù)的編號(hào)。若存在X個(gè)出庫(kù)任務(wù)和Y個(gè)入庫(kù)任務(wù)，則當(dāng)X=Y時(shí)，直接可進(jìn)行出入庫(kù)復(fù)合作業(yè)；而當(dāng)X≠Y時(shí)，則利用(0,0)(I/O節(jié)點(diǎn))將出入庫(kù)任務(wù)補(bǔ)充完整后再進(jìn)行出入庫(kù)復(fù)合作業(yè)。假設(shè)出入庫(kù)復(fù)合作業(yè)任務(wù)為N對(duì)，即存在N個(gè)出庫(kù)任務(wù)和N個(gè)入庫(kù)任務(wù)，將N個(gè)出庫(kù)任務(wù)隨機(jī)編碼為1～N，N個(gè)入庫(kù)任務(wù)則隨機(jī)編碼為N+1～2N，每條人工魚的編碼第奇數(shù)個(gè)元素為出庫(kù)任務(wù)，第偶數(shù)個(gè)元素為入庫(kù)貨位。例如X=(x1,x2,…,x2k-1,x2k,…,x2n-1,x2n)，其中x2k-1為出庫(kù)任務(wù)，x2k為入庫(kù)任務(wù)，即調(diào)度時(shí)按照順序依次進(jìn)行x1,x2,…,x2k-1,x2k,…,x2n-1,x2n對(duì)應(yīng)的出庫(kù)任務(wù)和入庫(kù)任務(wù)。在解中的偶數(shù)位置插入標(biāo)志位以區(qū)分不同穿梭車的任務(wù)執(zhí)行序列。

圖5為復(fù)合作業(yè)人工魚編碼方式，采用3個(gè)穿梭車執(zhí)行10組出入庫(kù)任務(wù)，標(biāo)志位-1用以將各穿梭車的執(zhí)行任務(wù)分開，穿梭車1的執(zhí)行任務(wù)序列為2→12→10→20→8→14，穿梭車2的執(zhí)行任務(wù)序列為1→13→5→18→7→17→6→11，穿梭車3的執(zhí)行任務(wù)序列為3→16→4→19→9→15。

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

本文目標(biāo)是完成所有任務(wù)的作業(yè)時(shí)間最短，即求解極小化問(wèn)題，則適應(yīng)度函數(shù)為：

fitness=T=Cmax。

(16)

式中Cmax為人工魚個(gè)體代表的所有任務(wù)完成的最大時(shí)間。

2.3.3 TTMSWS調(diào)度模型的IAFSA算法步驟

具體算法步驟如下：

步驟1初始化種群和參數(shù)。

步驟2開始迭代。先執(zhí)行追尾行為，若追尾失敗，則執(zhí)行聚群行為；若聚群失敗，則執(zhí)行覓食行為。

步驟3計(jì)算人工魚的適應(yīng)度值,并在公告板記錄最優(yōu)值。

步驟4視野參數(shù)更新。根據(jù)公布板更新情況，進(jìn)行人工魚視野的自適應(yīng)更新。

步驟5變鄰域搜索算子。若滿足條件，則執(zhí)行變鄰域搜索，并更新公布板;否則轉(zhuǎn)步驟6。

步驟6判斷是否達(dá)到最大迭代次數(shù)，若達(dá)到則輸出公告板最優(yōu)解，否則轉(zhuǎn)步驟2。

其核心偽代碼如下:

Begin

1.AF_Initialization：%算法初始化

2.人工魚數(shù)量、人工魚初始視野、擁擠度因子、最大試探次數(shù)等相關(guān)參數(shù)初始化

3.令當(dāng)前迭代次數(shù)為gen=1，Ybest=inf;%Ybest為公告板最優(yōu)值

4.初始化人工魚群個(gè)體X;

5.%進(jìn)入人工魚群迭代過(guò)程：

6.while gen≤Max_gen%當(dāng)達(dá)到預(yù)設(shè)的最大迭代次數(shù)，則停止循環(huán)

7. for i =1:n

8. [Xi,flag1]=AF_follow(X,n,visual,δ); %嘗試追尾行為，以flag1標(biāo)記追尾行為結(jié)果，若為1則表示追尾成功，否則表示追尾失敗

9. if flag1 == 0 %追尾失敗

10. [Xi,flag2]=AF_swarm(X,n,visual,δ); %嘗試聚群行為，以flag2標(biāo)記追尾行為結(jié)果，若為1則表示追尾成功，否則表示追尾失敗

11. if flag2 == 0 %聚群失敗

12. Xi=AF_prey(X,n,visual,δ); %進(jìn)行覓食行為

13. end

14. end

15. Xnew_best=Xi; %魚群經(jīng)過(guò)追尾、聚群、覓食后得到的最優(yōu)解

16. bulletin_update; %將得到的最優(yōu)解與公告板進(jìn)行比較

17. visual_update; %根據(jù)公告板更新情況對(duì)人工魚視野進(jìn)行更新

18. if 公告板未更新

19. beststep=beststep+1; %beststep記錄連續(xù)失效的迭代次數(shù)

20. else

21. beststep=1; %連續(xù)失效迭代次數(shù)重置為1

22. end

23. if beststep=Invalid_gen%當(dāng)連續(xù)失效迭代次數(shù)達(dá)到預(yù)設(shè)的最大連續(xù)失效次數(shù)時(shí)，執(zhí)行鄰域搜索

24. 保留公布板的最優(yōu)解，將其作為當(dāng)前解Xcur;

25. 定義鄰域結(jié)構(gòu)集合N={Nk,k=1,2,3};

26. for i = 1:L %L表示鄰域搜索次數(shù)

27. 在Xcur的鄰域集合N中隨機(jī)選擇一個(gè)進(jìn)行擾動(dòng)并生成解x′，令Xcur=x′;

28. 尋找Xcur的局部最優(yōu)解x″，令Xcur=x″；若Xcur

29. end

30. end

31. end

32.end

33.可視化結(jié)果

End

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

根據(jù)實(shí)際項(xiàng)目中的設(shè)備性能參數(shù)以及跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)的存儲(chǔ)規(guī)格，本文研究設(shè)置了跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)的模擬場(chǎng)景，貨架層數(shù)為15層，深度為60個(gè)儲(chǔ)位，穿梭車數(shù)量為3，其余具體跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)的參數(shù)設(shè)置如表1所示。

表1 跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)參數(shù)表

為驗(yàn)證IAFSA求解該問(wèn)題的有效性，隨機(jī)生成20個(gè)出入庫(kù)任務(wù)對(duì)，30個(gè)出入庫(kù)任務(wù)對(duì)，50個(gè)出入庫(kù)任務(wù)對(duì)跨層穿梭車的出入庫(kù)復(fù)合作業(yè)進(jìn)行分析。其中20個(gè)出入庫(kù)任務(wù)對(duì)列表如表2所示。

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

續(xù)表2

復(fù)合作業(yè)時(shí)間計(jì)算：設(shè)出庫(kù)貨物i和入庫(kù)貨物j坐標(biāo)分別為(xi,yi)和(xj,yj)，則穿梭車初始位置即上一入庫(kù)作業(yè)結(jié)束位置為(xj-1,yj-1)，復(fù)合作業(yè)時(shí)間如下所示：

Tij=

(17)

式中：t1為穿梭車從初始位置運(yùn)行至提升機(jī)站臺(tái)的時(shí)間，t2為穿梭車前往取出庫(kù)貨物過(guò)程中等待提升機(jī)的時(shí)間，t3為穿梭車從當(dāng)前所在層搭載提升機(jī)運(yùn)行至出庫(kù)貨物所在層的時(shí)間，t4為穿梭車從提升機(jī)站臺(tái)運(yùn)行至出庫(kù)貨物i所在位置的時(shí)間，t5為穿梭車前往取入庫(kù)貨物過(guò)程中等待提升機(jī)的時(shí)間，t6為穿梭搭載提升機(jī)從出庫(kù)貨物所在層到達(dá)I/O站臺(tái)并返回入庫(kù)貨物所在層的時(shí)間，t7為穿梭車從提升機(jī)站臺(tái)運(yùn)行至入庫(kù)貨物所在位置的時(shí)間，t8為提升機(jī)裝(卸)穿梭車的時(shí)間，t9為穿梭車裝(卸)貨物的時(shí)間,t10為穿梭車從當(dāng)前位置運(yùn)行至出庫(kù)貨物所在位置的時(shí)間。其中t2和t5為穿梭車等待提升機(jī)的時(shí)間，與設(shè)定的作業(yè)任務(wù)序列有關(guān)；t1、t3、t4、t6、t7和t10可根據(jù)設(shè)備運(yùn)動(dòng)距離及其速度、加速度計(jì)算；t8和t9為定值。

根據(jù)程序隨機(jī)得到各穿梭車一組出入庫(kù)復(fù)合作業(yè)任務(wù)序列為：穿梭車1的作業(yè)任務(wù)序列為：1→29→2→28→11→22→15→30→6→40→20→24→19→23；穿梭車2的作業(yè)任務(wù)序列為：14→32→18→35→13→38→16→31→10→27→9→36；穿梭車3的作業(yè)任務(wù)序列為：8→33→4→34→5→21→17→39→7→37→12→25→3→26。其作業(yè)時(shí)間總和為482.3 s。

利用改進(jìn)人工魚群算法進(jìn)行優(yōu)化。根據(jù)對(duì)魚群算法參數(shù)的分析[21]，選擇人工魚數(shù)量n=10，人工魚初始視野visual0=10，最小視野visualmin=1，擁擠度因子δ=8，最大試探次數(shù)Try_number=20，最大無(wú)效迭代次數(shù)Invalid_gen=5，人工魚群最大迭代次數(shù)Max_gen=200。優(yōu)化后所得的一組出入庫(kù)復(fù)合作業(yè)任務(wù)序列為：穿梭車1：12→29→20→26→18→33→4→30→11→35→13→21→7→32；穿梭車2：17→22→19→24→1→38→16→27→5→36→8→31→2→28；穿梭車3：6→34→15→23→14→40→10→37→9→39→3→25。其作業(yè)時(shí)間總和為349.1 s。

為驗(yàn)證算法求解該問(wèn)題的有效性，分別用經(jīng)典啟發(fā)式算法——遺傳算法、基本人工魚群算法和改進(jìn)人工魚群算法對(duì)其出入庫(kù)復(fù)合作業(yè)調(diào)度進(jìn)行對(duì)比，其中遺傳算法參數(shù)為：種群規(guī)模size=500，交叉概率pc=0.8，交叉算子選用部分匹配交叉，變異概率pm=0.1，變異算子選用交換變異；基本人工魚群算法參數(shù)為：人工魚數(shù)量n=10，人工魚視野visual=10，擁擠度因子δ=8，最大試探次數(shù)Try_number=20。為比較算法運(yùn)行時(shí)間，將算法終止條件統(tǒng)一設(shè)置為連續(xù)迭代100次最優(yōu)值不變；采用MATLAB編程，測(cè)試環(huán)境為WIN 10系統(tǒng)、CPU為i5-7200U、內(nèi)存為4 G，并進(jìn)行30次運(yùn)算，結(jié)果如表3所示。

表3 3種算法的實(shí)驗(yàn)結(jié)果

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

由表3和圖6可知，遺傳算法收斂較快，但很快陷入局部最優(yōu)，求解精度差；基本人工魚群算法在前期具備一定的搜索能力，但其搜索能力有限，容易陷入局部最優(yōu)，無(wú)法使魚群集中在最優(yōu)值附近；本文提出的改進(jìn)人工魚群算法，采用了自適應(yīng)視野與改進(jìn)覓食行為，加快收斂速度且增強(qiáng)了局部搜索能力，且變鄰域算子的加入，使得魚群能跳出局部最優(yōu)，較之其他兩種算法其求解精度優(yōu)勢(shì)較大，且對(duì)比基本人工魚群算法，其平均運(yùn)行時(shí)間相差不大，說(shuō)明了其能在增強(qiáng)求解精度的同時(shí)也保證了運(yùn)算速度。

進(jìn)一步驗(yàn)證算法的有效性與穩(wěn)定性，利用3種算法對(duì)不同任務(wù)量求解。表4為30任務(wù)對(duì)和50任務(wù)對(duì)的作業(yè)規(guī)模下運(yùn)行30次的實(shí)驗(yàn)結(jié)果。

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

由上述求解結(jié)果可以看出，遺傳算法隨著任務(wù)規(guī)模的增大，其算法平均收斂迭代次數(shù)增加十分明顯，且其優(yōu)化效率也有一定的損失；而本文提出的改進(jìn)人工魚群算法，在任務(wù)規(guī)模增大時(shí)，仍保持良好的優(yōu)化效率，且解的標(biāo)準(zhǔn)偏差在隨任務(wù)規(guī)模增大時(shí)，其效果更加明顯，故能說(shuō)明本文提出的改進(jìn)人工魚群算法求解該問(wèn)題的有效性和穩(wěn)定性。

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

針對(duì)TTMSWS出入庫(kù)復(fù)合作業(yè)問(wèn)題，分析其出入庫(kù)復(fù)合作業(yè)流程，考慮提升機(jī)與穿梭車的加減速，建立以出入庫(kù)復(fù)合作業(yè)時(shí)間最短為目標(biāo)的調(diào)度模型。針對(duì)該問(wèn)題，本文提出利用改進(jìn)人工魚群算法進(jìn)行求解。仿真實(shí)驗(yàn)結(jié)果表明，所建立的調(diào)度時(shí)間數(shù)學(xué)模型及改進(jìn)的人工魚群算法是可行有效的，在一定程度上能夠減少作業(yè)時(shí)間，提高倉(cāng)儲(chǔ)作業(yè)效率。未來(lái)將結(jié)合跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)的資源配置和企業(yè)投資等方面進(jìn)行深入研究，在最小化資源配置和投資成本的條件下，滿足企業(yè)倉(cāng)儲(chǔ)與運(yùn)行效率。