四向穿梭車(chē)式密集倉(cāng)儲(chǔ)入庫(kù)貨位分配方法研究

李 佳，何 非，謝剛偉，楊 洋，房逸鶴

1.南京理工大學(xué) 機(jī)械工程學(xué)院，南京 210094

2.南京小智智能科技有限公司，南京 210000

3.江蘇正貿(mào)倉(cāng)儲(chǔ)設(shè)備制造有限公司，南京 211111

在全球化和市場(chǎng)化的背景下，倉(cāng)儲(chǔ)物流行業(yè)已經(jīng)成為經(jīng)濟(jì)活動(dòng)中不可缺少的關(guān)鍵環(huán)節(jié)。貨位分配作為倉(cāng)儲(chǔ)運(yùn)輸環(huán)節(jié)的重要組成部分，對(duì)貨物的進(jìn)、出庫(kù)效率起著決定性作用[1]。合理的貨位分配方法可以有效地縮短工作時(shí)間，提高工作效率，延長(zhǎng)設(shè)備的使用時(shí)間。目前密集式存儲(chǔ)、自動(dòng)化倉(cāng)儲(chǔ)逐漸成為倉(cāng)儲(chǔ)行業(yè)的技術(shù)發(fā)展方向。四向穿梭車(chē)式密集倉(cāng)儲(chǔ)系統(tǒng)相較于傳統(tǒng)的巷道式存儲(chǔ)，倉(cāng)庫(kù)布局更加靈活，進(jìn)一步提高了存儲(chǔ)空間利用率。因此，對(duì)密集倉(cāng)儲(chǔ)貨位分配方法的研究有重要意義。

對(duì)于自動(dòng)化立體倉(cāng)庫(kù)的貨位分配問(wèn)題，國(guó)內(nèi)外學(xué)者研究主要以堆垛機(jī)系統(tǒng)和子母穿梭車(chē)系統(tǒng)[2]為主。針對(duì)堆垛式立體倉(cāng)庫(kù)，黃鵬等[3]以堆垛機(jī)運(yùn)行效率、貨架穩(wěn)定性和堆垛機(jī)負(fù)載均衡要求的貨位分配多目標(biāo)優(yōu)化模型，采用集成遺傳算法和延遲接受爬山算法的兩階段混合算法進(jìn)行優(yōu)化求解，算法解有較好的穩(wěn)定性和精度。對(duì)于雙向式自動(dòng)化立體倉(cāng)庫(kù)，蔡安江等[4]以出入庫(kù)效率、貨架重心和產(chǎn)品聚集度為目標(biāo)簡(jiǎn)歷貨位分配數(shù)學(xué)模型，使用引入動(dòng)態(tài)自適應(yīng)同步因子改進(jìn)混合蛙跳算法對(duì)模型進(jìn)行求解，解決了堆垛機(jī)選擇不同出入口對(duì)運(yùn)行時(shí)間的影響，取得良好效果。Wang等[5]針對(duì)子母穿梭車(chē)不同階段的服務(wù)進(jìn)行劃分，建立排隊(duì)網(wǎng)絡(luò)模型，并利用聚類(lèi)算法對(duì)商品進(jìn)行存儲(chǔ)區(qū)域劃分。上述研究方法可以有效解決堆垛式和子母穿梭車(chē)式立體倉(cāng)庫(kù)貨位分配問(wèn)題，但由于密集倉(cāng)儲(chǔ)貨位密集分布、穿梭車(chē)多軌道行駛的特點(diǎn)，分配貨位的離散程度、提升機(jī)的選擇策略等會(huì)嚴(yán)重影響倉(cāng)庫(kù)作業(yè)效率，此類(lèi)建模方法不適用于對(duì)多批次作業(yè)、四向穿梭車(chē)式密集倉(cāng)儲(chǔ)。

針對(duì)四向穿梭車(chē)式自動(dòng)化密集倉(cāng)儲(chǔ)系統(tǒng)，付曉鋒等[6]在制定貨物入庫(kù)上架作業(yè)規(guī)則和流程的基礎(chǔ)上，提出了入庫(kù)上架過(guò)程的貨位分配算法。即以貨物出庫(kù)時(shí)搭載穿梭車(chē)和提升機(jī)的行走距離作為衡量下架出庫(kù)效率的指標(biāo)，將入庫(kù)周轉(zhuǎn)頻率較高的貨物存儲(chǔ)在下架出庫(kù)效率較高的貨道。該方法將倉(cāng)庫(kù)簡(jiǎn)單分區(qū)實(shí)現(xiàn)貨物分類(lèi)存放，并未考慮多穿梭車(chē)同時(shí)作業(yè)過(guò)程中的軌道擁堵、貨架穩(wěn)定性等因素。宋佼蓉等[7]基于四向穿梭車(chē)式全貨位密集倉(cāng)儲(chǔ)系統(tǒng)的實(shí)時(shí)貨位分配問(wèn)題，提出了貨位分配策略、原則以及優(yōu)化目標(biāo)，并以改進(jìn)的遺傳算法和A-star算法結(jié)合的方式進(jìn)行了算例的求解驗(yàn)證，但并未考慮密集倉(cāng)儲(chǔ)中貨架多深度對(duì)存取貨作業(yè)流程的影響。在現(xiàn)有針對(duì)密集型倉(cāng)儲(chǔ)貨位分配的研究中學(xué)者們通常將問(wèn)題簡(jiǎn)化，并未深入考慮多深度貨架對(duì)貨物出入庫(kù)流程帶來(lái)的影響。

近年來(lái)采用遺傳算法[8-9]、模擬退火算法[10]、粒子群算法[11]等優(yōu)化算法的貨位分配研究不斷增多。而混合蛙跳算法（shuffles frog leaping algorithm，SFLA）結(jié)合了模因算法和粒子群算法的優(yōu)勢(shì)[12]，計(jì)算速度快，尋優(yōu)能力強(qiáng)，目前已應(yīng)用于求解組合優(yōu)化問(wèn)題，但是基于混合蛙跳算法的貨位分配問(wèn)題的研究還相對(duì)較少。

本文在對(duì)密集倉(cāng)儲(chǔ)建模、獲取動(dòng)態(tài)的貨位信息基礎(chǔ)上，對(duì)倉(cāng)庫(kù)貨位進(jìn)行貨道劃分。首先通過(guò)貨物按類(lèi)分貨道進(jìn)行貨位分配、貨道內(nèi)制定貨格的優(yōu)先存儲(chǔ)位置的策略，減少出現(xiàn)貨物移位任務(wù)的可能性，簡(jiǎn)化穿梭車(chē)的作業(yè)流程和作業(yè)復(fù)雜度。其次通過(guò)建立以路徑最短、貨物分布均衡及貨架重心穩(wěn)定為目標(biāo)的數(shù)學(xué)模型，使用改進(jìn)的混合蛙跳算法得到了符合要求的貨位分配方案，實(shí)現(xiàn)貨物以貨道為單位的離散分布，極大提高了倉(cāng)庫(kù)的運(yùn)行效率。

1 問(wèn)題描述

1.1 密集倉(cāng)儲(chǔ)貨位分配問(wèn)題

如圖1所示，圖中為單層密集型倉(cāng)庫(kù)的貨位分布示意圖。密集倉(cāng)儲(chǔ)模式下的自動(dòng)化倉(cāng)庫(kù)主要由多層固定貨架、四向穿梭車(chē)和提升機(jī)組成。其中，四向穿梭車(chē)搭載貨物，通過(guò)軌道、空閑貨道和提升機(jī)，實(shí)現(xiàn)貨物的出入庫(kù)流程。在執(zhí)行出入庫(kù)作業(yè)時(shí)，多個(gè)穿梭車(chē)和提升機(jī)可同時(shí)工作。假定貨架垂直方向?yàn)閦方向，沿貨架主軌道方向?yàn)閥方向，沿貨位巷道方向?yàn)閤方向。

圖1 四向穿梭車(chē)式密集型倉(cāng)庫(kù)布局Fig.1 Layout of four-way shuttle storage and retrieval system

立體倉(cāng)庫(kù)貨位分配問(wèn)題中通常的優(yōu)化原則有效率優(yōu)先原則和貨架穩(wěn)定性原則[13]。但由于密集倉(cāng)儲(chǔ)貨位巷道內(nèi)貨格多深度密集型分布的特點(diǎn)，貨位分配問(wèn)題需要考慮貨物存放的密集程度對(duì)系統(tǒng)作業(yè)效率的影響。一方面，若簡(jiǎn)單地將貨物存放在距出入庫(kù)位置較近且較低層的貨位上，則貨物將在出入庫(kù)附近聚集，造成集中存放區(qū)軌道擁堵，嚴(yán)重影響作業(yè)效率。另一方面，若貨物以貨格為單位離散存儲(chǔ)，則穿梭車(chē)需要頻繁執(zhí)行貨物換位任務(wù)以運(yùn)輸沿x方向深處貨位上的貨物，增加了作業(yè)復(fù)雜度，降低了效率。故針對(duì)四向穿梭車(chē)式密集倉(cāng)儲(chǔ)系統(tǒng)的貨位分配問(wèn)題，需要在貨物分類(lèi)存放的基礎(chǔ)上考慮路徑最短、貨位分布均衡和貨架重心穩(wěn)定三個(gè)原則。

1.2 假設(shè)條件

四向穿梭車(chē)式密集倉(cāng)儲(chǔ)采用托盤(pán)集裝、密集存儲(chǔ)，通過(guò)單輛穿梭車(chē)搭載單個(gè)托盤(pán)貨物進(jìn)行作業(yè)。在倉(cāng)儲(chǔ)設(shè)備的作業(yè)流程中包括穿梭車(chē)的移貨、換層操作，這限制了貨物與貨盤(pán)、貨盤(pán)與貨位間存在著硬性尺寸匹配關(guān)系，故文中合理假設(shè)貨物與倉(cāng)儲(chǔ)設(shè)備等滿(mǎn)足數(shù)量、尺寸約束。在四向穿梭車(chē)實(shí)際作業(yè)中，由于貨架支撐結(jié)構(gòu)的限制，通常貨位上只能雙向通行。因此，針對(duì)密集倉(cāng)儲(chǔ)分配遇到的相關(guān)問(wèn)題和應(yīng)遵循的原則，為了便于模型的建立和問(wèn)題的研究，做出以下假設(shè)：

（1）整個(gè)密集存儲(chǔ)系統(tǒng)內(nèi)部單個(gè)貨位只能存儲(chǔ)一個(gè)托盤(pán)貨物，且貨位規(guī)格相同。

（2）存儲(chǔ)區(qū)域的貨格由于貨架的限制，只能雙向移動(dòng)，即沿x方向行駛。

（3）進(jìn)行貨位分配前，已知倉(cāng)儲(chǔ)系統(tǒng)內(nèi)剩余空閑貨位信息和待入庫(kù)貨物的周轉(zhuǎn)率、質(zhì)量等信息。

2 入庫(kù)優(yōu)化數(shù)學(xué)模型的構(gòu)建

2.1 四向穿梭車(chē)式貨架建模

四向穿梭車(chē)式貨架模型的主要參數(shù)如表1 所示。倉(cāng)庫(kù)中共有c層貨架，每層貨架有b排貨架巷道，每層有a列貨位。其中第z層y排x列的貨位坐標(biāo)記為：(x,y,z),x={1,2,…,a},y={1,2,…,b},z={1,2,…,c}。根據(jù)貨位的存儲(chǔ)狀態(tài)，得到動(dòng)態(tài)的空閑貨位集合D={(xi,yi,zi)|i=1,2,…,N}。

表1 參數(shù)與變量定義Table 1 Parameter and variable definitions

已知待入庫(kù)的第k種貨物的信息(nk,pk,mk),k=1,2,…,K。其中nk表示該類(lèi)貨物的數(shù)量，pk表示該類(lèi)貨物的周轉(zhuǎn)率，mk表示該類(lèi)貨物的質(zhì)量。定義貨位分配方案為T(mén)={T1,T2,…,TK}，其中Tk={(xi,yi,zi)|i=1,2,…,nk}，表示第k類(lèi)貨物在倉(cāng)庫(kù)中的位置坐標(biāo)，則T中的貨位坐標(biāo)集合為D的子集。

2.2 劃分貨道

密集型倉(cāng)庫(kù)單層貨架貨位布局如圖1所示，為提高貨物出入庫(kù)效率，單個(gè)存儲(chǔ)貨道通常只存儲(chǔ)單類(lèi)貨物，以避免在出庫(kù)作業(yè)時(shí)需要頻繁執(zhí)行貨物移位任務(wù)。故貨位分配時(shí)需要將貨位劃分貨道，并以貨道為單位分類(lèi)存儲(chǔ)貨物。此外，由于密集倉(cāng)儲(chǔ)中貨道內(nèi)貨格的多深度特點(diǎn)，通常采用先進(jìn)后出的堆棧式貨物存儲(chǔ)管理策略。執(zhí)行入庫(kù)作業(yè)時(shí)，應(yīng)優(yōu)先將貨物運(yùn)送至貨道深處，以減少后續(xù)貨物的入庫(kù)路徑長(zhǎng)度，并提高穿梭車(chē)作業(yè)時(shí)動(dòng)態(tài)避堵的能力。

綜上，定義單個(gè)貨道只存放一種貨物，從貨道最深處貨格開(kāi)始存儲(chǔ)貨物，并且優(yōu)先填滿(mǎn)當(dāng)前貨道再使用新貨道。最終貨位分配方案應(yīng)滿(mǎn)足約束條件，即每類(lèi)貨物所選的貨格總數(shù)不小于貨物總數(shù)。

2.3 優(yōu)化目標(biāo)的提出

根據(jù)密集倉(cāng)儲(chǔ)的實(shí)際需求，建立如下優(yōu)化模型。

（1）路徑最短

當(dāng)不考慮穿梭車(chē)存取貨物和轉(zhuǎn)向時(shí)間時(shí)，入庫(kù)貨物所分配貨位距入庫(kù)口越近，穿梭車(chē)從作業(yè)貨位到提升機(jī)的路徑越短，倉(cāng)庫(kù)的運(yùn)行效率越高。

由于密集倉(cāng)儲(chǔ)的軌道特點(diǎn)，穿梭車(chē)、提升機(jī)搭載貨物沿x、y或z方向移動(dòng)，故使用曼哈頓距離計(jì)算坐標(biāo)(xk,yk,zk)處貨位到i入庫(kù)口的距離。

假設(shè)倉(cāng)庫(kù)內(nèi)入庫(kù)口數(shù)量為L(zhǎng)，得到穿梭車(chē)的作業(yè)總路徑為：

（2）貨位分布均衡

密集型倉(cāng)儲(chǔ)中，穿梭車(chē)沿軌道、空閑的貨位巷道行走作業(yè)，其中軌道的暢通對(duì)倉(cāng)儲(chǔ)運(yùn)行效率至關(guān)重要。不同主軌道區(qū)域的存儲(chǔ)差別將極大影響穿梭車(chē)的擁堵情況，進(jìn)而影響倉(cāng)庫(kù)運(yùn)行效率。貨位分配方案在x、y方向上的離散程度將影響穿梭車(chē)在不同主軌道的行走頻率。同樣若某種貨物的貨位分配集中在某一層，也將極易造成擁堵，影響工作效率。

為避免周轉(zhuǎn)率較高的貨物在臨近的貨道聚集、穿梭車(chē)擁堵等情況發(fā)生，用貨道內(nèi)貨物的周轉(zhuǎn)率之和表示貨道的擁擠程度。以貨道x、y、z方向上貨道擁擠程度的標(biāo)準(zhǔn)差來(lái)反映貨位分布的均衡程度，其值越小表示該方向上的貨位分布越均衡。

式中，Xi、Yi、Zi分別表示第i列、排、層貨架的貨物的周轉(zhuǎn)率總和；Xˉ、Yˉ、Zˉ分別表示理想狀況下平均每列、排、層貨位的平均周轉(zhuǎn)率。

通過(guò)對(duì)三個(gè)方向的標(biāo)準(zhǔn)差進(jìn)行加成得到衡量貨位分配離散程度的函數(shù)：

（3）貨架重心穩(wěn)定

密集型倉(cāng)儲(chǔ)的貨位分布較為集中，貨物質(zhì)量分布不均勻、重心較高等會(huì)影響貨架的力學(xué)性能及穩(wěn)定性。并且提升機(jī)運(yùn)輸貨物換層時(shí)，作業(yè)能耗與貨物質(zhì)量成正比，質(zhì)量較小的貨物放在低層有利于減少能耗?？紤]到貨位均衡的原則，在此主要降低倉(cāng)庫(kù)內(nèi)貨物整體z方向的重心，以提高貨架的穩(wěn)定性并降低提升機(jī)能耗。

式中，mxyz表示在第z層y排x列貨位上的貨物質(zhì)量；H表示該貨位的高度。

2.4 入庫(kù)貨位優(yōu)化的數(shù)學(xué)模型

由上述目標(biāo)函數(shù)及約束條件，可建立如下自動(dòng)化倉(cāng)庫(kù)貨位多目標(biāo)優(yōu)化模型：

由于上文中三個(gè)目標(biāo)函數(shù)的量綱、數(shù)值范圍存在較大差異，故分別根據(jù)各個(gè)分目標(biāo)函數(shù)的最優(yōu)解fimin和最差解fimax，根據(jù)式（11）對(duì)目標(biāo)函數(shù)進(jìn)行歸一化。

為了簡(jiǎn)化模型求解，對(duì)各目標(biāo)進(jìn)行主觀賦權(quán)，采用層次分析法（analytic hierarchy process，AHP）構(gòu)造判斷矩陣求得特征向量，經(jīng)過(guò)一致性檢驗(yàn)確定特征向量的有效性后，得到各優(yōu)化目標(biāo)的權(quán)值αi。使用權(quán)重系數(shù)法將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題。

3 基于改進(jìn)的混合蛙跳算法的入庫(kù)貨位分配

SFLA 中，問(wèn)題的解X用青蛙的位置表示，虛擬青蛙的種群集合為可能解的集合。SFLA算法具體流程如下：產(chǎn)生初始種群P后，種群中的解按照適應(yīng)度值排序，將整個(gè)種群劃分為s個(gè)模因組；然后執(zhí)行局部搜索和模因組重構(gòu)，重復(fù)初始化之后的各個(gè)步驟，直到滿(mǎn)足終止條件。

SFLA有算法概念簡(jiǎn)單、控制參數(shù)少、易于實(shí)現(xiàn)的優(yōu)點(diǎn)，目前已應(yīng)用于求解旅行商、調(diào)度問(wèn)題，但在解決高維優(yōu)化問(wèn)題時(shí)易出現(xiàn)早熟、解精度不夠的情況[14]。并且對(duì)于約束較為復(fù)雜的問(wèn)題，SFLA在尋找最優(yōu)解的過(guò)程中，根據(jù)青蛙的移動(dòng)步長(zhǎng)更新青蛙個(gè)體極易不滿(mǎn)足約束條件而用最優(yōu)解替代，最終無(wú)法充分發(fā)揮算法的優(yōu)越性。因此，本文借鑒遺傳算法求解離散優(yōu)化問(wèn)題采用的交叉、變異算子方法[15]，提出一種改進(jìn)的SFLA算法以解決在貨道約束條件下的密集倉(cāng)儲(chǔ)貨位分配問(wèn)題。

3.1 編碼及解碼

根據(jù)倉(cāng)庫(kù)地圖和貨道劃分標(biāo)準(zhǔn)，進(jìn)行貨道的劃分，得到空閑貨道總個(gè)數(shù)為N，采用十進(jìn)制數(shù)對(duì)貨道進(jìn)行編號(hào)。假設(shè)當(dāng)前倉(cāng)庫(kù)內(nèi)有n個(gè)空閑貨道(n≤N)，將n個(gè)貨道的編號(hào)隨機(jī)排列，即貨位編碼長(zhǎng)度為n。

已知貨道編碼序列后，通過(guò)解碼確定每個(gè)貨物的貨位分配。首先，根據(jù)貨道序列得到對(duì)應(yīng)貨道內(nèi)的貨位數(shù)量、坐標(biāo)等信息，然后將貨物依次從序列頭部對(duì)應(yīng)貨道開(kāi)始存儲(chǔ)，直至存放完所有貨物，即滿(mǎn)足式的約束條件。最終存儲(chǔ)貨物的編碼子序列為當(dāng)前貨道序列的有效貨位編碼序列，即為當(dāng)前編碼的貨位分配方案。該方案使得待分配的貨物能夠全部存儲(chǔ)于分配貨架巷道內(nèi)。例如圖2 所示，現(xiàn)有10 個(gè)待入庫(kù)貨物A、10 個(gè)待入庫(kù)貨物B，對(duì)其的貨物編號(hào)為1、2。已知空閑貨位的編碼為（1，3，2，5，4，9…），通過(guò)對(duì)貨道貨位數(shù)量的計(jì)算，得到該條編碼的方案為1貨物準(zhǔn)備放入1、3貨道，2貨物準(zhǔn)備放入2、5 貨道。其中，將（1，3，2，5）視為該條編碼的有效編碼序列。

圖2 編碼和解碼規(guī)則Fig.2 Encoding and decoding rules

3.2 算法原理

初始化種群生成N個(gè)體，通過(guò)解碼計(jì)算出個(gè)體適應(yīng)度后，將種群內(nèi)個(gè)體按照適應(yīng)度值降序排序，按式（13）劃分為s個(gè)子群：

其中，i=1,2,…,s,j=1,2,…,m,m為子群中個(gè)體的數(shù)目。

SFLA 通常以子群內(nèi)最差解Pworse為優(yōu)化對(duì)象，通過(guò)模因組內(nèi)的局部搜索產(chǎn)生新解，具體過(guò)程如下：首先確定組內(nèi)最優(yōu)解Pbest、最差解Pworse以及全局最優(yōu)解PB，然后根據(jù)式（14）、（15），利用Pbest和Pworse產(chǎn)生新個(gè)體Pnew：

式中，rand(0,1)表示在區(qū)間[0，1]上服從均勻分布的隨機(jī)數(shù)。若Pnew優(yōu)于Pworse，則替換最差解Pworse；否則，隨機(jī)產(chǎn)生新解替換Pworse。重復(fù)以上步驟，直到達(dá)到設(shè)定的迭代次數(shù)。

其中，也有文獻(xiàn)在子群內(nèi)隨機(jī)選擇兩個(gè)非劣解產(chǎn)生新個(gè)體Pnew[16]，或在式（14）移動(dòng)步長(zhǎng)中加入動(dòng)態(tài)自適應(yīng)同步因子[4]。本文選用Pworse為優(yōu)化對(duì)象，結(jié)合遺傳算法（genetic algorithm，GA）采用一種新的優(yōu)化迭代方法。

（1）交叉

進(jìn)行交叉操作時(shí)，設(shè)計(jì)了動(dòng)態(tài)自適應(yīng)同步因子更新個(gè)體基因。按照式（16）從Pworse的有效編碼序列中隨機(jī)選取w個(gè)編號(hào)記為W={p1,p2,…,pw}，其中g(shù)為當(dāng)前種群迭代次數(shù)。

將Pbest中與W相同的編號(hào)移動(dòng)到Pbest編碼序列的末尾，即在Pbest的有效編碼序列中剔除編號(hào)為W的因子，如圖3示例所示得到新個(gè)體Pnew。

圖3 交叉因子算法Fig.3 Crossover operation algorithm

（2）變異

本文的變異操作為隨機(jī)排列n個(gè)貨道，生成隨機(jī)編碼序列。

具體局部搜索過(guò)程描述如下：

步驟1按照適應(yīng)度值排序結(jié)果，選擇當(dāng)前模因組內(nèi)最優(yōu)解Pbest、最差解Pworse，將Pworse作為優(yōu)化對(duì)象。

步驟2設(shè)定交叉概率pc。進(jìn)行交叉操作時(shí)，從Pworse的有效編碼序列中隨機(jī)選取編號(hào)序列W，在Pbest的有效編碼序列中剔除W內(nèi)的因子，得到新個(gè)體Pnew。

步驟3設(shè)定變異概率pm。進(jìn)行變異操作時(shí)，隨機(jī)生成新個(gè)體Pnew。

步驟4比較Pnew和Pworse。若Pnew優(yōu)于Pworse，則更新最差解Pworse；否則，用全局最優(yōu)解PB直接替換Pworse。

步驟5是否達(dá)到模因組迭代次數(shù)。若是，輸出更新后的模因組；否則轉(zhuǎn)到步驟1，直至完成局部搜索。

3.3 算法步驟

所述算法的基本流程圖如圖4所示，具體步驟如下：

圖4 改進(jìn)混合蛙跳算法流程圖Fig.4 Operation flow of improved shuffles frog leaping algorithm

步驟1設(shè)置參數(shù)。

步驟2初始化種群P，計(jì)算根據(jù)式（12）計(jì)算個(gè)體適應(yīng)度。

步驟3根據(jù)適應(yīng)度值對(duì)種群個(gè)體排序，根據(jù)式（13）劃分模因組。

步驟4局部搜索。對(duì)每個(gè)模因組按3.2節(jié)的策略進(jìn)行個(gè)體的更新，直到達(dá)到局部搜索次數(shù)。

步驟5重新混合各個(gè)模因組中的所有個(gè)體，更新種群中最優(yōu)個(gè)體。

步驟6是否達(dá)到種群迭代次數(shù)。若是，則輸出PB作為迭代后的最優(yōu)解；否則，轉(zhuǎn)到步驟3。

4 實(shí)例驗(yàn)證分析

4.1 算法驗(yàn)證

以圖1所示的倉(cāng)庫(kù)布局為例進(jìn)行實(shí)驗(yàn)，該倉(cāng)庫(kù)的數(shù)據(jù)如表2所示。其中單個(gè)貨位的長(zhǎng)和寬、軌道的寬度均為1個(gè)距離單位，相鄰貨位或相鄰的軌道和貨位間的距離忽略不計(jì)。由于貨架的結(jié)構(gòu)限制，貨格位置處穿梭車(chē)無(wú)法在y方向上行走。已知待入庫(kù)的貨物信息如表3所示。

表2 密集型倉(cāng)庫(kù)數(shù)據(jù)Table 2 Dense storage data

表3 待入庫(kù)貨物信息Table 3 Inbound cargo information

根據(jù)已知的倉(cāng)庫(kù)數(shù)據(jù)，可整理得到貨位的數(shù)據(jù)信息，如圖5所示。

圖5 貨位信息Fig.5 Location information

為便于分析和驗(yàn)證算法結(jié)果，將貨位信息可視化。如圖6（a）所示，將連通的貨位劃分為同一貨道。在單個(gè)貨道內(nèi)所需入庫(kù)時(shí)間最長(zhǎng)的貨位為貨道最深處，即圖6（b）中單個(gè)貨道中顏色最深的貨位。

圖6 貨位信息可視化Fig.6 Visualization of cargo location information

為驗(yàn)證和分析各個(gè)目標(biāo)函數(shù)的優(yōu)化效果，首先分別將各目標(biāo)函數(shù)在Python中進(jìn)行仿真。分別僅考慮第一、二、三目標(biāo)函數(shù)，得到的貨位分配結(jié)果如圖7～圖9 所示。其中用顏色深淺表示貨物周轉(zhuǎn)率、質(zhì)量大小，貨位顏色越深表示此處存放貨物周轉(zhuǎn)率越大或質(zhì)量越大。

圖7 第一目標(biāo)函數(shù)的仿真結(jié)果Fig.7 Simulation results of first objective function

由圖7（a）、圖8（a）、圖9（a）可見(jiàn)，各目標(biāo)函數(shù)均在240 代左右收斂，函數(shù)值降低了大約20%。即在三次迭代中，貨物分別按照周轉(zhuǎn)率、質(zhì)量大小有規(guī)則存放。分析具體貨位分布方案得：在圖7（b）中，根據(jù)第一目標(biāo)函數(shù)的約束，貨物按照周轉(zhuǎn)率大小依次存放于離提升機(jī)較近的貨位上，并且周轉(zhuǎn)率較大的貨物更靠近提升機(jī)；在圖8（b）中，在第二目標(biāo)函數(shù)的約束下，貨物根據(jù)周轉(zhuǎn)率大小在x、y、z方向上較均勻分布，不存在圖7（b）、圖9（b）中貨物聚集的情況；在圖9（c）中，質(zhì)量較大的貨物優(yōu)先存放于低層貨架，高層貨架貨位中更多為質(zhì)量較輕的貨物。綜上，充分證明了目標(biāo)函數(shù)及算法的有效性。

圖8 第二目標(biāo)函數(shù)的仿真結(jié)果Fig.8 Simulation results of second objective function

圖9 第三目標(biāo)函數(shù)的仿真結(jié)果Fig.9 Simulation results of third objective function

4.2 實(shí)驗(yàn)結(jié)果與分析

在上文驗(yàn)證各目標(biāo)函數(shù)、算法可行性的基礎(chǔ)上，針對(duì)表2數(shù)據(jù)的倉(cāng)庫(kù)，對(duì)表3中的貨物分配貨位。

根據(jù)公司對(duì)該目標(biāo)的重視程度，采用層次分析法計(jì)算得到權(quán)重(α1,α2,α3)為（0.291，0.418，0.291），建立評(píng)價(jià)函數(shù)。為了對(duì)比算法的優(yōu)越性，采用標(biāo)準(zhǔn)遺傳算法GA、混合蛙跳算法SFLA 和改進(jìn)的混合蛙跳算法SFLA-GA分別進(jìn)行計(jì)算。算法參數(shù)如表4所示。

表4 算法參數(shù)Fig.4 Algorithm parameter table

運(yùn)用所建立的密集倉(cāng)儲(chǔ)貨位分配模型并結(jié)合GA、SFLA 及SFLA-GA 算法對(duì)該貨位分配任務(wù)進(jìn)行仿真求解，其算法迭代過(guò)程目標(biāo)函數(shù)值變化如圖10所示。

圖10 算法迭代曲線Fig.10 Algorithm iteration curve

分析圖10、表5，隨著迭代次數(shù)的增加，目標(biāo)函數(shù)不斷變化，SFLA-GA算法在300代左右達(dá)到最優(yōu)。并且相比于GA、SFLA，SFLA-GA 迭代效果顯著，說(shuō)明其更逼近最優(yōu)解，足以證明SFLA-GA算法的有效性和優(yōu)越性。

表5 算法結(jié)果數(shù)據(jù)對(duì)比Table 5 Algorithm resultcomparison table

圖11 為最終的貨位分配方案，在多目標(biāo)函數(shù)的約束下，周轉(zhuǎn)率較大的貨物優(yōu)先存放于距提升機(jī)較近的貨位中，沿貨架x、y、z方向的周轉(zhuǎn)率分布均衡，質(zhì)量較大的貨物更多地存放在底層貨架上。進(jìn)一步驗(yàn)證了SFLAGA在處理密集式倉(cāng)儲(chǔ)貨位分配問(wèn)題的有效性和優(yōu)越性。

圖11 改進(jìn)的混合蛙跳算法的貨位分配方案Fig.11 Location allocation of improved shuffles frog leaping algorithm

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

本文重點(diǎn)研究密集倉(cāng)儲(chǔ)下的貨位分配問(wèn)題，針對(duì)密集倉(cāng)儲(chǔ)的貨位分布特點(diǎn)劃分貨道，在此基礎(chǔ)上對(duì)倉(cāng)庫(kù)貨位分配問(wèn)題建立了多目標(biāo)優(yōu)化模型，分別采用改進(jìn)的混合蛙跳算法、混合蛙跳算法和遺傳算法進(jìn)行了仿真求解。實(shí)驗(yàn)結(jié)果表明：

（1）所提優(yōu)化算法能夠響應(yīng)密集倉(cāng)儲(chǔ)的貨位分布特征，符合實(shí)際倉(cāng)儲(chǔ)作業(yè)需求。

（2）相比于混合蛙跳算法與遺傳算法，所提算法具有更好的搜索速度和更優(yōu)解。通過(guò)對(duì)混合蛙跳算法局部搜索策略的改進(jìn)，提高了搜索得到新解的效率，提高了算法效率。

本文所提出的模型與算法可以有效解決四向穿梭車(chē)式密集倉(cāng)儲(chǔ)入庫(kù)貨位分配問(wèn)題，但并沒(méi)有考慮到出入庫(kù)混批的復(fù)雜情況。在今后需進(jìn)一步對(duì)出入庫(kù)混批情形下的貨位分配方法進(jìn)行研究，算法性能也有待進(jìn)一步提升。