摘要： 針對(duì)跨層四向穿梭車作業(yè)空載率高、等待時(shí)間長(zhǎng)等問(wèn)題，需要充分優(yōu)化穿梭車和提升機(jī)的協(xié)作水平，考慮四向穿梭車和提升機(jī)在運(yùn)動(dòng)過(guò)程中的變速過(guò)程，以出入庫(kù)訂單任務(wù)的總時(shí)間最小為目標(biāo)，建立了四向穿梭車和提升機(jī)聯(lián)合調(diào)度的混合整數(shù)規(guī)劃模型。結(jié)合四向穿梭車和提升機(jī)在倉(cāng)庫(kù)揀選階段的實(shí)際約束，提出了一種改進(jìn)鯨魚優(yōu)化算法，并與模擬退火算法、基礎(chǔ)遺傳算法、改進(jìn)的黑猩猩優(yōu)化算法進(jìn)行了比較。結(jié)果表明，設(shè)計(jì)的算法求解質(zhì)量更好，并有效縮短了倉(cāng)庫(kù)揀選作業(yè)時(shí)間。

關(guān)鍵詞： 四向穿梭車；跨層；復(fù)合作業(yè)；路徑規(guī)劃；鯨魚優(yōu)化算法

中圖分類號(hào)： TP391；O224文獻(xiàn)標(biāo)識(shí)碼： A

Cross-layer Four-way Shuttle Warehouse Composite Operation Path Optimization

TIAN Menglong， ZHANG Jihui

（a. Institute of Complexity Science; b. Shandong Key Laboratory of Industrial Control Technology， Qingdao University， Qingdao 26607 China）

Abstract：In order to address the problems of high empty rate and long waiting time of cross-level four-way shuttle during its operations， it is necessary to fully optimize the level of cooperation between shuttles and hoisters. Considering the variable speed of the four-way shuttle and the hoister in the movement process， with the objective of minimizing the total operation time of the inbound and outbound order tasks， a mixed integer planning model for the joint scheduling of the four-way shuttle and the hoister is established. An improved whale optimization algorithm is proposed in combination with the actual constraints of the four-way shuttle and hoister in the warehouse order picking process， and compared with simulated annealing， genetic algorithm， and an improved chimpanzee optimization algorithm. The results show that the designed algorithm has much better solution quality and effectively reduces the time in completing given order picking task.

Keywords： four-way shuttle; cross layer; compound operation; path planning; the whale optimization algorithm

0 引言

隨著快遞物流業(yè)的迅速發(fā)展，傳統(tǒng)倉(cāng)庫(kù)已經(jīng)不能滿足日益增長(zhǎng)的貨物存儲(chǔ)要求，逐漸向自動(dòng)化、智能化方向發(fā)展。面對(duì)小批量、多種類的訂單情況，密集化倉(cāng)儲(chǔ)很大程度上緩解了企業(yè)的壓力?？鐚铀南虼┧筌嚭吞嵘龣C(jī)協(xié)同作業(yè)是智能化密集倉(cāng)儲(chǔ)的一種應(yīng)用類型。和傳統(tǒng)穿梭車相比，四向穿梭車不僅可以前后運(yùn)動(dòng)，而且可以左右運(yùn)動(dòng)，因此擁有更強(qiáng)的自主性和靈活性。四向穿梭車搭配提升機(jī)進(jìn)行跨層倉(cāng)庫(kù)作業(yè)的方式包括單入庫(kù)作業(yè)、單出庫(kù)作業(yè)和復(fù)合作業(yè)，其中，復(fù)合作業(yè)可以大大減少作業(yè)完成時(shí)間，因此跨層四向穿梭車倉(cāng)庫(kù)復(fù)合作業(yè)的路徑優(yōu)化研究變得特別重要。

目前，國(guó)內(nèi)外學(xué)者對(duì)四向穿梭車在倉(cāng)儲(chǔ)系統(tǒng)的流程及配置優(yōu)化進(jìn)行了研究。宋佼蓉［1］對(duì)四向穿梭車倉(cāng)儲(chǔ)系統(tǒng)的出入庫(kù)復(fù)合調(diào)度策略進(jìn)行了研究，并針對(duì)多層共享四向穿梭車作業(yè)模式，提出了動(dòng)態(tài)區(qū)域控制法；占翔南等［2］針對(duì)多深度四向穿梭車倉(cāng)儲(chǔ)系統(tǒng)存在多臺(tái)穿梭車同時(shí)作業(yè)造成的沖突死鎖問(wèn)題，對(duì)儲(chǔ)貨區(qū)制定了路徑定向策略；張經(jīng)天等［3］將提升機(jī)調(diào)度問(wèn)題轉(zhuǎn)化為含運(yùn)輸時(shí)間的柔性作業(yè)車間調(diào)度問(wèn)題，并考慮同層任務(wù)的執(zhí)行順序約束；何昕杰等［4］針對(duì)批量訂單出庫(kù)問(wèn)題，建立了訂單排序優(yōu)化模型，縮短了四向穿梭車與提升機(jī)之間的交互作業(yè)時(shí)間；段綠輝［5］針對(duì)系統(tǒng)任務(wù)調(diào)度過(guò)程中可能出現(xiàn)的穿梭車沖突問(wèn)題，提出了基于路徑時(shí)間窗的沖突類型判斷和沖突消除方案；劉瑞萍［6］針對(duì)四向穿梭車系統(tǒng)中存在的調(diào)度沖突問(wèn)題，通過(guò)動(dòng)態(tài)圖論構(gòu)建了一種基于時(shí)間窗法改進(jìn)的A*算法進(jìn)行路徑優(yōu)化；Mao［78］將提升機(jī)和穿梭車的并行性融入到四向穿梭車系統(tǒng)中，并研究了并聯(lián)式和串聯(lián)式兩種不同模式下的作業(yè)優(yōu)化問(wèn)題。

國(guó)內(nèi)外學(xué)者在穿梭車跨層操作以及路徑優(yōu)化方面也有了很多研究。王姍姍等［9］將系統(tǒng)復(fù)合作業(yè)路徑優(yōu)化歸結(jié)為任務(wù)指派問(wèn)題，以完成一批揀貨任務(wù)的總時(shí)間最小為目標(biāo)建立優(yōu)化模型；湯洪濤等［10］提出改進(jìn)的人工蜂群算法，有效解決了跨層跨巷道穿梭車倉(cāng)儲(chǔ)系統(tǒng)的復(fù)合三維作業(yè)路徑優(yōu)化問(wèn)題；于巧玉等［11］將任務(wù)出庫(kù)期限引入調(diào)度策略，并使用蟻群粒子群雙層智能優(yōu)化算法對(duì)模型進(jìn)行求解；陳壽伍［12］借鑒不相關(guān)并行機(jī)的混合流水線模型的思想，建立了基于復(fù)合命令作業(yè)模式的以訂單任務(wù)總完成時(shí)間最小為目標(biāo)的任務(wù)調(diào)度模型；魯建廈等［13］建立了出入庫(kù)復(fù)合作業(yè)時(shí)間模型，并設(shè)計(jì)了基于復(fù)合作業(yè)的改進(jìn)人工魚群算法；楊瑋等［14］針對(duì)倉(cāng)庫(kù)資源配置涉及因素眾多難以優(yōu)化的問(wèn)題，提出了平均吞吐時(shí)間和成本集成的配置優(yōu)化方法；Wang等［15］應(yīng)用改進(jìn)的模擬退火算法求解多層穿梭車任務(wù)調(diào)度問(wèn)題；Zhu等［16］提出了均衡任務(wù)和改變緩沖區(qū)狀態(tài)兩種策略優(yōu)化方法，實(shí)驗(yàn)結(jié)果表明，考慮兩種優(yōu)化策略可以縮短揀選總時(shí)間。

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

1.1 問(wèn)題描述

跨層四向穿梭車倉(cāng)庫(kù)揀選作業(yè)由四向穿梭車、提升機(jī)、貨架、揀選站和軌道等設(shè)備完成。四向穿梭車負(fù)責(zé)運(yùn)載出入庫(kù)貨物，提升機(jī)負(fù)責(zé)運(yùn)載四向穿梭車進(jìn)行換層，通常位于每層的貨架外側(cè)；貨架實(shí)現(xiàn)高層密集倉(cāng)儲(chǔ)，可以容納更多的貨物；在揀選站處完成揀選工作?？鐚铀南虼┧筌噦}(cāng)儲(chǔ)系統(tǒng)的側(cè)視圖如圖1a所示、俯視圖如圖1b所示。

跨層揀選作業(yè)需要四向穿梭車和提升機(jī)協(xié)同完成，作業(yè)類別包括入庫(kù)作業(yè)和出庫(kù)作業(yè)。入庫(kù)作業(yè)的基本流程是：揀選站處補(bǔ)貨，由四向穿梭車運(yùn)載貨物，搭乘提升機(jī)到達(dá)指定層數(shù)的貨架進(jìn)行存儲(chǔ)。出庫(kù)作業(yè)的基本流程是：四向穿梭車在目標(biāo)貨架取到貨物后，搭乘提升機(jī)到第一層的揀選站由工作人員進(jìn)行揀選。作業(yè)方式包括單一出庫(kù)作業(yè)、單一入庫(kù)作業(yè)和復(fù)合作業(yè)。復(fù)合作業(yè)就是將出庫(kù)作業(yè)和入庫(kù)作業(yè)接替進(jìn)行，直至完成給定的作業(yè)任務(wù)。采用復(fù)合作業(yè)模式可以有效減少穿梭車的空運(yùn)載運(yùn)行時(shí)間與等待時(shí)間。

一個(gè)出庫(kù)作業(yè)和一個(gè)入庫(kù)作業(yè)可以組成最小規(guī)模的復(fù)合任務(wù)，它可以被劃分為4個(gè)階段：1）穿梭車運(yùn)載出庫(kù)貨物到達(dá)本層等待區(qū)，等待調(diào)用提升機(jī)；2）穿梭車運(yùn)載貨物到達(dá)揀選站進(jìn)行卸貨；3）穿梭車運(yùn)載入庫(kù)貨物到達(dá)第一層等待區(qū)，等待調(diào)用提升機(jī)；4）穿梭車運(yùn)載入庫(kù)貨物到達(dá)指定的目標(biāo)貨架進(jìn)行存貨（見(jiàn)圖2）。

當(dāng)控制中心生成訂單后，這些訂單會(huì)被分派給不同的四向穿梭車。在運(yùn)載貨物過(guò)程中會(huì)依據(jù)規(guī)則選擇搭乘不同的提升機(jī)，避免因分配不合理而產(chǎn)生過(guò)多的等待時(shí)間。具體流程：

1）四向穿梭車執(zhí)行出庫(kù)任務(wù)，當(dāng)穿梭車接收到出庫(kù)指令時(shí)，首先判斷與目標(biāo)貨物位置是否位于同一層。

（1）穿梭車與貨物不同層：四向穿梭車前往本層巷道出入口的等待區(qū)，調(diào)用提升機(jī)；提升機(jī)到達(dá)四向穿梭車所在的貨架層，四向穿梭車搭乘提升機(jī)去往貨物所在的貨架層；四向穿梭車到達(dá)貨物所在的貨架層，規(guī)劃路線去目標(biāo)貨架取貨；四向穿梭車取到貨物后，前往本層巷道出入口的等待區(qū)，調(diào)用提升機(jī)；四向穿梭車搭乘提升機(jī)到達(dá)第一層后，去往揀選站。

（2）穿梭車與貨物同層：四向穿梭車直接去往目標(biāo)貨架取貨；四向穿梭車運(yùn)載貨物前往本層巷道出入口的等待區(qū)，調(diào)用提升機(jī)；四向穿梭車搭乘提升機(jī)到達(dá)第一層后，去往揀選站。

2）四向穿梭車執(zhí)行入庫(kù)任務(wù)，當(dāng)穿梭車接收到入庫(kù)指令時(shí)，首先判斷穿梭車是否需要提升機(jī)輔助操作。

（1）穿梭車需要提升操作：四向穿梭車在揀選站取貨后，去往第一層巷道出入口的等待區(qū)；四向穿梭車搭乘提升機(jī)到達(dá)貨物所在層；四向穿梭車運(yùn)載貨物去到指定的貨架進(jìn)行存貨操作。

（2）穿梭車不需要提升操作：四向穿梭車在揀選站取貨后，直接到第一層目標(biāo)貨架進(jìn)行存貨操作。

四向穿梭車和提升機(jī)的協(xié)同水平?jīng)Q定了一批出入庫(kù)任務(wù)的完成時(shí)間。在上述流程下，對(duì)貨物進(jìn)行分配，選擇其對(duì)應(yīng)的穿梭車、提升機(jī)以及揀選站，出發(fā)地和目的地都明確，在此基礎(chǔ)上進(jìn)行任務(wù)排序優(yōu)化。四向穿梭車、提升機(jī)和揀選站配合的復(fù)合流程如圖3所示。

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

根據(jù)跨層四向穿梭車倉(cāng)庫(kù)作業(yè)流程，作如下基本假設(shè)：1）出入庫(kù)貨物的貨位信息和四向穿梭車的位置是已知的；2）四向穿梭車一次只能運(yùn)輸一個(gè)貨物；3）提升機(jī)一次只能運(yùn)輸一輛四向穿梭車；4）當(dāng)四向穿梭車負(fù)載貨物到達(dá)揀選站時(shí)，它立即卸下貨物并裝載新貨物返回；5）不考慮發(fā)生故障問(wèn)題。

符號(hào)說(shuō)明：I：揀選站集合；G：提升機(jī)集合；J：四向穿梭車集合；K：出入庫(kù)任務(wù)集合；h：?jiǎn)挝淮尕?取貨時(shí)間；o o2：四向穿梭車的起始位置和終止位置；C1j，k：第j輛四向穿梭車從出庫(kù)貨位運(yùn)送任務(wù)k到達(dá)當(dāng)層出庫(kù)等待區(qū)的時(shí)間；C2j，k：第j輛四向穿梭車運(yùn)送任務(wù)k從提升機(jī)到達(dá)揀選站/存儲(chǔ)貨架的時(shí)間；C3j，k，g：第j輛四向穿梭車運(yùn)送任務(wù)k到達(dá)第g個(gè)提升機(jī)的時(shí)間；Dk，j：第j輛四向穿梭車運(yùn)送任務(wù)k在等待區(qū)的等待時(shí)間；ψk，j：第j輛四向穿梭車運(yùn)送任務(wù)k到揀選站的結(jié)束時(shí)間；τk，j：第j輛四向穿梭車運(yùn)送任務(wù)k的開(kāi)始時(shí)間；Wj：第j輛四向穿梭車完成所有運(yùn)輸任務(wù)的時(shí)間；Sk，j：出庫(kù)任務(wù)k到達(dá)揀選站的時(shí)間；M：一個(gè)足夠大的正數(shù)。

決策變量：Ui，k= 任務(wù)k分配給揀選站i0，其它；Lk，k′，j= k′在k之后立即由四向穿梭車j運(yùn)輸0，其它;ρk，j= k由四向穿梭車j運(yùn)輸0，其它;Zj，g= 四向穿梭車j由提升機(jī)g運(yùn)輸0，其它。

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

Minimize maxj∈JWj（1）

約束條件：

∑i∈IUi，k= k∈K（2）

∑j∈Jρk，j= k∈K（3）

∑j∈JZj，g= g∈G（4）

∑k∈KLk，k′，j=ρk′，j，k′∈K，j∈J（5）

∑k∈K∪{o1}Lo k，j=∑k∈K∪{o2}Lk，o2，j= j∈J（6）

ψk′，j≤τk，j+h+∑i∈IC1j，k·Ui，k+Dk，j+∑i∈IC2j，k·Ui，k+M·（1－Lk，k′，j），k∈K，j∈J，k′∈K（7）

ψk′，j≥τk，j+h+∑i∈IC1j，k·Ui，k+Dk，j+∑i∈IC2j，k·Ui，k－M·（1－Lk，k′，j），k∈K，j∈J，k′∈K（8）

C3j，k，g≥C1j，k+Dk，jk∈K，j∈J，g∈G（9）

τk′，j=Sk，j，j∈J，k∈K，k′∈K（10）

Wj≥τk，j+h+∑i∈IC1i，k·Ui，k+Dk，j+∑i∈IC2i，k·Ui，k+M·（ρk，j－1），j∈J，k∈K（11）

Ui，k，Lk，k′，j，ρk，j，Zj，g∈0， k，k′∈K∪o o2，j∈J，g∈G（12）

其中，式（1）為目標(biāo)函數(shù)，即最小化最大作業(yè)時(shí)間；式（2）表示每個(gè)貨物只能分配給一個(gè)揀選站；式（3）表示每個(gè)貨物只能由一個(gè)四向穿梭車運(yùn)輸；式（4）表示每輛四向穿梭車只能乘坐一個(gè)提升機(jī)；式（5）和式（6）確保四向穿梭車前后工作的連貫性；式（7）和式（8）表示下一個(gè)任務(wù)開(kāi)始的最早時(shí)間與最晚時(shí)間；式（9）表示當(dāng)四向穿梭車不能立即乘坐提升機(jī)時(shí)需要產(chǎn)生等待時(shí)間；式（10）確保在揀選站處前后任務(wù)時(shí)間的連續(xù)性；式（11）表示最后一個(gè)任務(wù)的完成時(shí)間約束；式（12）規(guī)定了變量的取值范圍。

2 算法描述

2.1 基本鯨魚優(yōu)化算法

鯨魚優(yōu)化算法（Whale Optimization Algorithm）模擬了座頭鯨的社會(huì)行為以及泡泡網(wǎng)捕食策略，該算法分為3個(gè)階段，即尋找獵物階段、包圍獵物階段和泡泡網(wǎng)捕食階段，算法步驟見(jiàn)文獻(xiàn)［17］。

2.2 改進(jìn)的離散鯨魚優(yōu)化算法

鯨魚優(yōu)化算法是應(yīng)用于連續(xù)領(lǐng)域，它與其他算法相比具有很強(qiáng)的競(jìng)爭(zhēng)力。在解決離散優(yōu)化問(wèn)題時(shí)，需要對(duì)其改進(jìn)。改進(jìn)的鯨魚算法在解決倉(cāng)庫(kù)作業(yè)問(wèn)題時(shí)要聯(lián)系實(shí)際，如生成初始種群采用特定策略；在泡泡網(wǎng)捕食階段采用多種鄰域搜索策略，以尋找更優(yōu)的目標(biāo)。

2.2.1 尋找獵物階段離散化

在連續(xù)領(lǐng)域鯨魚算法中，是當(dāng)前個(gè)體向種群中的隨機(jī)個(gè)體靠近探索，在離散鯨魚算法中，當(dāng)前出庫(kù)任務(wù)和入庫(kù)任務(wù)隨機(jī)向種群中某個(gè)體的出庫(kù)任務(wù)與入庫(kù)任務(wù)靠近，且出庫(kù)任務(wù)和入庫(kù)任務(wù)分開(kāi)操作，如圖4所示。

在圖4中，1～5為出庫(kù)任務(wù)，6～10為入庫(kù)任務(wù)，F(xiàn)1為當(dāng)前個(gè)體，F(xiàn)2為隨機(jī)個(gè)體。出庫(kù)任務(wù)選擇第三個(gè)位置點(diǎn)，F(xiàn)1的出庫(kù)任務(wù)5要變成任務(wù)1，在F1中檢索出任務(wù)1的位置進(jìn)行兩交換操作，可進(jìn)行多次交換操作，入庫(kù)任務(wù)也進(jìn)行相同操作，F(xiàn)1經(jīng)變換后成為F3。

2.2.2 包圍獵物階段離散化

包圍獵物階段是當(dāng)前個(gè)體向種群中的最優(yōu)個(gè)體靠近探索，在離散鯨魚算法中，當(dāng)前出庫(kù)任務(wù)和入庫(kù)任務(wù)向種群中最優(yōu)個(gè)體的出庫(kù)任務(wù)與入庫(kù)任務(wù)進(jìn)行靠近，且出庫(kù)任務(wù)和入庫(kù)任務(wù)分開(kāi)操作，如圖5所示。

在圖5中，1～5為出庫(kù)任務(wù)，6～10為入庫(kù)任務(wù)，F(xiàn)1為當(dāng)前個(gè)體，F(xiàn)2為最優(yōu)個(gè)體。入庫(kù)任務(wù)選擇第三個(gè)位置點(diǎn)進(jìn)行變換，F(xiàn)1的5號(hào)任務(wù)和F2的1號(hào)任務(wù)相對(duì)應(yīng)，F(xiàn)1將自身的5號(hào)任務(wù)和1號(hào)任務(wù)進(jìn)行兩交換，可進(jìn)行多次交換操作。出庫(kù)任務(wù)選擇第一個(gè)和第五個(gè)位置點(diǎn)進(jìn)行相同操作，F(xiàn)1經(jīng)變換后成為F3。

2.2.3 泡泡網(wǎng)捕食階段離散化

在離散鯨魚算法中，螺旋運(yùn)動(dòng)改成多種鄰域操作去探尋更優(yōu)秀的目標(biāo)。首先計(jì)算當(dāng)前個(gè)體和最優(yōu)個(gè)體之間的差異度，以差異度為參考確定鄰域搜索次數(shù)。差異度取為漢明距離，將兩個(gè)個(gè)體中的任務(wù)序列從頭到尾一一比較，不一樣的任務(wù)數(shù)量總和定義為差異度。以圖6為例，共有8處不同，因此F1與F2的差異度為8，進(jìn)而鄰域操作最大次數(shù)設(shè)定為8。

多次鄰域搜索可以探尋到更優(yōu)的個(gè)體，但尋找獵物階段和包圍獵物階段的操作容易早熟，從而導(dǎo)致算法陷入局部最優(yōu)，因此在捕食階段采用多種鄰域搜索方式防止陷入局部最優(yōu)，具體搜索操作：1）兩交換操作：將屬于不同四向穿梭車的任務(wù)進(jìn)行交換操作，或者是屬于同一輛四向穿梭車的不同任務(wù)進(jìn)行交換操作。2）插入操作：將屬于同一輛四向穿梭車的某個(gè)任務(wù)插入到另一處特定的位置。3）逆序操作：將屬于同一輛四向穿梭車的某段任務(wù)進(jìn)行逆序排列。4）變異操作：將屬于某輛四向穿梭車的某個(gè)任務(wù)分配給其他車輛。

泡泡網(wǎng)捕食階段具體步驟：

步驟1 計(jì)算當(dāng)前個(gè)體和最優(yōu)個(gè)體之間的差異度，確定最大鄰域搜索次數(shù)。

步驟2 判斷操作次數(shù)是否大于最大搜索次數(shù)，若大于最大搜索次數(shù)則結(jié)束，個(gè)體進(jìn)行一次逆序操作。

步驟3 多種鄰域搜索方式，以輪盤賭方式選擇一種操作。

步驟4 計(jì)算適應(yīng)度值，若適應(yīng)度值優(yōu)于原來(lái)的值，則保留更好的值，結(jié)束操作；若沒(méi)有優(yōu)于原來(lái)的值，則搜索次數(shù)加一，返回步驟2。

2.3 改進(jìn)的鯨魚優(yōu)化算法設(shè)計(jì)

傳統(tǒng)的鯨魚優(yōu)化算法應(yīng)用于連續(xù)領(lǐng)域，設(shè)計(jì)離散的鯨魚優(yōu)化算法可以更好地解決倉(cāng)庫(kù)作業(yè)問(wèn)題，算法流程如圖7所示。

2.3.1 編碼

本文采用三層整數(shù)編碼，第一層編碼代表出庫(kù)任務(wù)序列，第二層編碼代表入庫(kù)任務(wù)序列，第三層編碼代表四向穿梭車編號(hào)。本文主要研究復(fù)合作業(yè)路徑優(yōu)化，因此出庫(kù)作業(yè)數(shù)量和入庫(kù)作業(yè)數(shù)量相同，假設(shè)總?cè)蝿?wù)數(shù)量為N，出庫(kù)任務(wù)序列為1～N/2，入庫(kù)任務(wù)序列為1+N/2～N。在圖8中，總?cè)蝿?wù)數(shù)量為10，四向穿梭車數(shù)量為3。1～5為出庫(kù)任務(wù)，6～10為入庫(kù)任務(wù)，1號(hào)四向穿梭車執(zhí)行任務(wù)序列為5→7，2號(hào)四向穿梭車執(zhí)行任務(wù)序列為2→8→4→10，3號(hào)四向穿梭車執(zhí)行任務(wù)序列為3→6→1→9。在分配過(guò)程中，會(huì)發(fā)現(xiàn)穿梭車任務(wù)數(shù)量不全相等，任務(wù)較多的穿梭車會(huì)以一定概率將任務(wù)分配給任務(wù)最少的穿梭車，盡量達(dá)到任務(wù)均衡。

2.3.2 適應(yīng)度計(jì)算

本文以完成所有出入庫(kù)任務(wù)的最終時(shí)間為優(yōu)化目標(biāo)，則適應(yīng)度函數(shù)可表示為

fitness=T=minWmax

其中，T為完成所有出入庫(kù)訂單的最終時(shí)間；Wmax為所有四向穿梭車完成一批出入庫(kù)任務(wù)的最大時(shí)間。

2.3.3 初始種群生成

初始種群50%采用隨機(jī)生成的方式，剩下50%采用策略生成方式，策略為：當(dāng)四向穿梭車依次完成任務(wù)時(shí)，依次選擇層數(shù)最近的任務(wù)，縮短路程時(shí)間，即在完成入庫(kù)任務(wù)時(shí)，下一個(gè)出庫(kù)任務(wù)優(yōu)先選擇層數(shù)最近且距離最近的任務(wù)。這樣有助于算法收斂，策略引導(dǎo)尋找更優(yōu)的適應(yīng)度值。

2.3.4 迭代過(guò)程

1）當(dāng)p<0.5，A≥1時(shí)，為尋找獵物階段，當(dāng)前出庫(kù)任務(wù)和入庫(kù)任務(wù)隨機(jī)向種群中某個(gè)體的出庫(kù)任務(wù)與入庫(kù)任務(wù)靠近，且出庫(kù)任務(wù)和入庫(kù)任務(wù)分開(kāi)操作，互不干擾。四向穿梭車依概率產(chǎn)生變異，優(yōu)先分配給任務(wù)數(shù)量最少的穿梭車。

2）當(dāng)p<0.5，A<1時(shí)，為包圍獵物階段，當(dāng)前出庫(kù)任務(wù)和入庫(kù)任務(wù)向種群中最優(yōu)個(gè)體的出庫(kù)任務(wù)與入庫(kù)任務(wù)靠近，且出庫(kù)任務(wù)和入庫(kù)任務(wù)分開(kāi)操作。四向穿梭車依概率產(chǎn)生變異，優(yōu)先分配給任務(wù)數(shù)量最少的穿梭車。

3）當(dāng)p≥0.5時(shí)，為泡泡網(wǎng)捕食階段，計(jì)算當(dāng)前個(gè)體和最優(yōu)個(gè)體之間的差異度，以差異度為參考確定鄰域搜索次數(shù)。采用多種鄰域操作選擇并多次擾動(dòng)，且出庫(kù)任務(wù)和入庫(kù)任務(wù)分開(kāi)操作。

2.3.5 種群多樣性

在算法過(guò)程中，為避免算法因種群相似陷入局部最優(yōu)，每完成一次迭代，以適應(yīng)度值為依據(jù)從小到大排列，將最后N/2個(gè)體舍棄，采用隨機(jī)方式生成N/2新種群，完成種群的更新，保持種群的多樣性。

2.3.6 停止條件

當(dāng)算法運(yùn)行次數(shù)達(dá)到最大迭代次數(shù)時(shí)，算法停止。

3 算例分析

以某物流配送倉(cāng)儲(chǔ)運(yùn)行情況為例，驗(yàn)證算法的有效性。該倉(cāng)儲(chǔ)系統(tǒng)配備有1個(gè)高層密集貨架、2個(gè)提升機(jī)、4個(gè)四向穿梭車和2個(gè)揀選站。貨架層數(shù)為20，橫排貨架數(shù)為21，縱深貨格數(shù)為50，設(shè)備運(yùn)行參數(shù)如表1所示。

在計(jì)算時(shí)間時(shí)，考慮四向穿梭車和提升機(jī)的變加（減）速運(yùn)動(dòng)，忽略四向穿梭車轉(zhuǎn)彎時(shí)的速度變化。vo代表速度，xo代表行使路程，ao代表加速度，to代表時(shí)間。在完成一次任務(wù)時(shí)穿梭車和提升機(jī)達(dá)到各自最大速度，勻速運(yùn)行后再減速至0，其時(shí)間計(jì)算可表示為to=xovo+voao；在完成一次任務(wù)時(shí)穿梭車和提升機(jī)未達(dá)到各自最大速度，未進(jìn)入勻速階段減速至0，其時(shí)間計(jì)算可表示為to=4xo/ao。運(yùn)用求時(shí)間的兩個(gè)公式，可以求出完成整個(gè)任務(wù)作業(yè)的時(shí)間。

選取某次實(shí)際的任務(wù)訂單作為測(cè)試數(shù)據(jù)，數(shù)據(jù)如表2所示，用以求解模型最小完成時(shí)間并驗(yàn)證改進(jìn)鯨魚優(yōu)化算法的有效性。在表2中，有40個(gè)出入庫(kù)任務(wù)，其中1～20為出庫(kù)任務(wù)，21～40為入庫(kù)任務(wù)，合并成復(fù)合任務(wù)共20個(gè)。

隨機(jī)分配任務(wù)：穿梭車1任務(wù)為：14→33→12→28→3→32→7→26→8→37；穿梭車2任務(wù)為：1→29→20→39→19→34→18→30→13→24；穿梭車3任務(wù)為：16→35→4→36→10→23→2→22→5→31；穿梭車4任務(wù)為：11→40→15→38→6→25→9→27→17→21，最終完成時(shí)間為326.9 s。用改進(jìn)的鯨魚優(yōu)化算法進(jìn)行計(jì)算，揀選時(shí)間有效減少，優(yōu)化后的方案如下，穿梭車1任務(wù)為：13→33→1→21→18→23→6→35→15→38；穿梭車2任務(wù)為：19→39→16→34→4→28→11→22→2→29；穿梭車3任務(wù)為：5→36→10→37→14→25→20→40→8→24；穿梭車4任務(wù)為：9→31→17→26→12→32→3→27→7→30，最終完成時(shí)間為258.4 s。與隨機(jī)方案相比，時(shí)間縮短了68.5 s，優(yōu)化效率提升了20.9%。

為了驗(yàn)證算法的有效性，將本文算法與基礎(chǔ)遺傳算法、改進(jìn)模擬退火算法和改進(jìn)黑猩猩優(yōu)化算法進(jìn)行對(duì)比實(shí)驗(yàn)。遺傳算法采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，具有更好的全局尋優(yōu)能力；模擬退火算法的優(yōu)點(diǎn)在于它能夠跳出局部最優(yōu)解，找到全局最優(yōu)解。相比一般的貪心算法，模擬退火算法不會(huì)受限于局部最優(yōu)解，而是具有一定的概率接受更優(yōu)解；黑猩猩優(yōu)化算法是根據(jù)黑猩猩群體圍捕獵物時(shí)個(gè)體的能力不同和社會(huì)激勵(lì)行為而提出的元啟發(fā)式算法，黑猩猩優(yōu)化算法與鯨魚算法都是群體智能算法，搜索機(jī)制不同，黑猩猩算法將狩獵過(guò)程分為探索階段和開(kāi)發(fā)階段，可以有效提高算法的搜索速度和精度，在解決優(yōu)化問(wèn)題時(shí)具有一定的競(jìng)爭(zhēng)力。

比較實(shí)驗(yàn)中，算法參數(shù)設(shè)置如下：遺傳算法采用種群規(guī)模為50，迭代次數(shù)為500，交叉概率為0.8，變異概率為0.1；模擬退火算法采用外層最大迭代次數(shù)為500，內(nèi)層循環(huán)次數(shù)為15，初始溫度為1 000，冷卻因子為0.99；改進(jìn)黑猩猩優(yōu)化算法通過(guò)一定的概率改變?nèi)蝿?wù)序列，比如插入，兩交換，逆序和改變四向穿梭車編號(hào)等，概率為0.8。這4種算法全部采用三層編碼，在此基礎(chǔ)上對(duì)這4種算法進(jìn)行分析比較，每個(gè)算法進(jìn)行20次運(yùn)算，取最優(yōu)值。利用MATLAB R2018b實(shí)現(xiàn)提出的改進(jìn)鯨魚優(yōu)化算法，并在Intel（R） Core（TM） i512500H CPU @ 2.50GHz處理器及RAM 8.00GB電腦上運(yùn)行，結(jié)果見(jiàn)表3，分析對(duì)比見(jiàn)圖9。

由表3和圖9可以看出，4種算法都可以改善適應(yīng)度值，但改善的效果各不相同。對(duì)比這4種算法，可以發(fā)現(xiàn)：在求解算例中，模擬退火算法的收斂速度很快，但是后期的尋優(yōu)能力較弱。它在處理復(fù)雜模型時(shí)，雖然能很快收斂，但很難跳出局部最優(yōu)解，這意味著將需要更多的時(shí)間來(lái)尋找最優(yōu)解；基礎(chǔ)遺傳算法在求解此問(wèn)題上收斂速度和求解質(zhì)量都不算太好，遺傳算法易陷入局部最優(yōu)，導(dǎo)致求解精度差；改進(jìn)黑猩猩優(yōu)化算法在局部搜索能力上表現(xiàn)較好，但最后求解質(zhì)量欠佳；本文提出的改進(jìn)鯨魚優(yōu)化算法前期收斂速度較快，較其他3種算法，全局搜索能力表現(xiàn)較好，在求解此模型上有很好的效果。

在不同的規(guī)模下，改進(jìn)鯨魚優(yōu)化算法較其他3種算法均表現(xiàn)出更好的求解質(zhì)量。為了進(jìn)一步驗(yàn)證算法的有效性，增加出入庫(kù)任務(wù)數(shù)量，求解結(jié)果如表4所示。

根據(jù)表4中的數(shù)據(jù)，可以對(duì)比分析50和80兩種規(guī)模作業(yè)在4種算法下的求解情況。隨著任務(wù)量的增加，各個(gè)算法都可以優(yōu)化工作時(shí)間，并且其求解均值都小于隨機(jī)生成的均值。仔細(xì)對(duì)比這4種算法，可以發(fā)現(xiàn)改進(jìn)鯨魚優(yōu)化算法求解質(zhì)量較好，其求解最優(yōu)值和優(yōu)化效率都好于其余3種算法，算法對(duì)比見(jiàn)圖10和圖11。這說(shuō)明在處理任務(wù)量較大的問(wèn)題時(shí)，改進(jìn)鯨魚優(yōu)化算法具有更好的性能?；A(chǔ)遺傳算法容易陷入局部最優(yōu)，收斂容易早熟，缺少探索新解的能力。模擬退火算法在前期可以很快收斂到最優(yōu)解，但后期求解效果不佳。改進(jìn)黑猩猩算法收斂速度較模擬退火算法慢，但求解質(zhì)量要好于模擬退火算法。因此，改進(jìn)鯨魚優(yōu)化算法在求解四向穿梭車跨層倉(cāng)庫(kù)作業(yè)問(wèn)題上具有很好的性能。

4 結(jié)語(yǔ)

跨層四向穿梭車倉(cāng)庫(kù)復(fù)合作業(yè)路徑規(guī)劃涉及多方面要素，未來(lái)可以進(jìn)一步研究的方向有：1）跨層倉(cāng)庫(kù)作業(yè)效率受制于四向穿梭車和提升機(jī)的數(shù)量搭配，增加提升機(jī)的數(shù)量會(huì)提高揀選效率，但如果提升機(jī)數(shù)量過(guò)多，又會(huì)導(dǎo)致能耗的增加，設(shè)備數(shù)量配置問(wèn)題可作為下一步研究的方向。2）隨著四向穿梭車數(shù)量的增多，可深入研究四向穿梭車無(wú)死鎖控制。3）本文未考慮四向穿梭車在運(yùn)行過(guò)程中發(fā)生故障問(wèn)題后的任務(wù)重新分配問(wèn)題，以及充電的問(wèn)題，這些可作為繼續(xù)研究的內(nèi)容。

參考文獻(xiàn)：

［1］宋佼蓉. 四向穿梭車式密集倉(cāng)儲(chǔ)系統(tǒng)作業(yè)流程優(yōu)化研究［D］.北京：北京郵電大學(xué)， 2021.

SONG J R. Research on operation process optimization of four-way shuttle intensive storage system［D］. Beijing： Beijing University of Posts and Telecommunications， 2021.

［2］占翔南，徐立云，凌旭峰，等. 多深度四向穿梭車倉(cāng)儲(chǔ)系統(tǒng)調(diào)度優(yōu)化［J］.計(jì)算機(jī)集成制造系統(tǒng)， 2022， 28（8）： 24962507.

ZHAN X N， XU L Y， LING X F， et al. Scheduling optimization of multi-depth four-way shuttle truck storage system［J］. Computer Integrated Manufacturing Systems， 2022， 28（8）： 24962507.

［3］張經(jīng)天，馬瑩，翁迅，等. 四向穿梭車系統(tǒng)的提升機(jī)調(diào)度優(yōu)化［J］.北京郵電大學(xué)學(xué)報(bào)， 2022， 45（1）： 1925，81.

ZHANG J T， MA Y， WENG X， et al. Elevator scheduling optimization of four-way shuttle system［J］. Journal of Beijing University of Posts and Telecommunications， 2022， 45（1）： 1925，81.

［4］何昕杰，周少武，張紅強(qiáng)，等. 基于改進(jìn)遺傳算法的四向穿梭車系統(tǒng)訂單排序優(yōu)化［J］.系統(tǒng)仿真學(xué)報(bào)，2021，33（9）： 21662179.

HE X J， ZHOU S W， ZHANG H Q， et al. Order ordering optimization of four-way shuttle system based on improved genetic algorithm［J］. Journal of System Simulation， 202 33（9）： 21662179.

［5］段綠輝. 四向穿梭車系統(tǒng)配置優(yōu)化與調(diào)度算法研究［D］.長(zhǎng)春：吉林大學(xué)， 2020.

DUAN L H. Research on configuration optimization and scheduling algorithm of four-way shuttle system［D］. Changchun： Jilin University， 2020.

［6］劉瑞萍. 四向穿梭車倉(cāng)儲(chǔ)系統(tǒng)調(diào)度優(yōu)化研究［D］.長(zhǎng)春：吉林大學(xué)， 2020.

LIU R P. Study on scheduling optimization of four-way shuttle storage system［D］. Changchun： Jilin University， 2020.

［7］MAO J， CHENG J， LI X， et al. Modelling analysis of a four-way shuttle-based storage and retrieval system on the basis of operation strategy［J］. Applied Sciences， 2023， 13（5）： 3306.

［8］MAO J， CHENG J， LI X， et al. Research on scheduling optimization of four-way shuttle-based storage and retrieval systems［J］. Scientific Reports， 2023， 13（1）： 3999.

［9］王姍姍，張紀(jì)會(huì). 穿梭車倉(cāng)儲(chǔ)系統(tǒng)復(fù)合作業(yè)路徑優(yōu)化［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 202 18（1）： 6372.

WANG S S， ZHANG J H. Shuttle storage system complex operation path optimization［J］. Complex Systems and Complexity Science， 202 18（1）： 6372.

［10］ 湯洪濤，程曉雅，李修琳，等. 跨層跨巷道穿梭車倉(cāng)儲(chǔ)系統(tǒng)復(fù)合作業(yè)路徑優(yōu)化［J］.計(jì)算機(jī)集成制造系統(tǒng)， 2022， 28（6）： 18881902.

TANG H T， CHENG X Y， LI X L， et al. Optimization of complex operation path of cross-floor cross-roadway shuttle storage system［J］. Computer Integrated Manufacturing Systems， 2022， 28（6）： 18881902.

［11］ 于巧玉，吳耀華，王艷艷. 跨層穿梭車雙提升機(jī)系統(tǒng)料箱揀選任務(wù)調(diào)度［J］.計(jì)算機(jī)工程與應(yīng)用， 2020， 56（20）： 270278.

YU Q Y， WU Y H， WANG Y Y. Task scheduling of hopper picking in cross-floor shuttle double hoist system［J］. Computer Engineering and Applications， 2020， 56（20）： 270278.

［12］ 陳壽伍. 跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)資源配置與任務(wù)調(diào)度研究［D］.杭州：浙江工業(yè)大學(xué)， 2020.

CHEN S W. Research on resource allocation and task scheduling of cross-layer shuttle storage system［D］. Hangzhou： Zhejiang University of Technology， 2020.

［13］ 魯建廈，陳壽伍，易文超，等. 跨層穿梭車倉(cāng)儲(chǔ)系統(tǒng)復(fù)合作業(yè)路徑規(guī)劃［J］.計(jì)算機(jī)集成制造系統(tǒng)， 202 27（6）： 17991808.

LU J S， CHEN S W， YI W C， et al. Cross-layer shuttle storage system complex operation path planning［J］. Computer Integrated Manufacturing Systems， 202 27（6）： 17991808.

［14］ 楊瑋，吳瑩瑩，王婷. 子母式穿梭車倉(cāng)儲(chǔ)系統(tǒng)配置優(yōu)化問(wèn)題研究［J］.計(jì)算機(jī)工程與應(yīng)用， 202 57（4）： 258265.

YANG W， WU Y Y， WANG T. Research on optimization of the configuration of the shuttle-carrier storage system ［J］. Computer Engineering and Applications， 202 57（4）： 258265.

［15］ WANG Y， ZHANG R， LIU H， et al. Task scheduling model of double-deep multi-tier shuttle system［J］. Processes， 2019， 7（9）： 604.

［16］ ZHU H， WANG M， GAO H. Modeling and optimizing based on OTCPN in multi-tier shuttle warehousing system［J］. Mathematical Problems in Engineering， 2022（1）： 9773212.

［17］ MIRJALILI S， LEWIS A. The whale optimization algorithm［J］. Advances in Engineering Software， 2016， 95： 5167.

（責(zé)任編輯 耿金花）