四向穿梭車式密集倉儲入庫貨位分配方法研究

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

1.南京理工大學 機械工程學院，南京 210094

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

3.江蘇正貿倉儲設備制造有限公司，南京 211111

在全球化和市場化的背景下，倉儲物流行業已經成為經濟活動中不可缺少的關鍵環節。貨位分配作為倉儲運輸環節的重要組成部分，對貨物的進、出庫效率起著決定性作用[1]。合理的貨位分配方法可以有效地縮短工作時間，提高工作效率，延長設備的使用時間。目前密集式存儲、自動化倉儲逐漸成為倉儲行業的技術發展方向。四向穿梭車式密集倉儲系統相較于傳統的巷道式存儲，倉庫布局更加靈活，進一步提高了存儲空間利用率。因此，對密集倉儲貨位分配方法的研究有重要意義。

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

針對四向穿梭車式自動化密集倉儲系統，付曉鋒等[6]在制定貨物入庫上架作業規則和流程的基礎上，提出了入庫上架過程的貨位分配算法。即以貨物出庫時搭載穿梭車和提升機的行走距離作為衡量下架出庫效率的指標，將入庫周轉頻率較高的貨物存儲在下架出庫效率較高的貨道。該方法將倉庫簡單分區實現貨物分類存放，并未考慮多穿梭車同時作業過程中的軌道擁堵、貨架穩定性等因素。宋佼蓉等[7]基于四向穿梭車式全貨位密集倉儲系統的實時貨位分配問題，提出了貨位分配策略、原則以及優化目標，并以改進的遺傳算法和A-star算法結合的方式進行了算例的求解驗證，但并未考慮密集倉儲中貨架多深度對存取貨作業流程的影響。在現有針對密集型倉儲貨位分配的研究中學者們通常將問題簡化，并未深入考慮多深度貨架對貨物出入庫流程帶來的影響。

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

本文在對密集倉儲建模、獲取動態的貨位信息基礎上，對倉庫貨位進行貨道劃分。首先通過貨物按類分貨道進行貨位分配、貨道內制定貨格的優先存儲位置的策略，減少出現貨物移位任務的可能性，簡化穿梭車的作業流程和作業復雜度。其次通過建立以路徑最短、貨物分布均衡及貨架重心穩定為目標的數學模型，使用改進的混合蛙跳算法得到了符合要求的貨位分配方案，實現貨物以貨道為單位的離散分布，極大提高了倉庫的運行效率。

1 問題描述

1.1 密集倉儲貨位分配問題

如圖1所示，圖中為單層密集型倉庫的貨位分布示意圖。密集倉儲模式下的自動化倉庫主要由多層固定貨架、四向穿梭車和提升機組成。其中，四向穿梭車搭載貨物，通過軌道、空閑貨道和提升機，實現貨物的出入庫流程。在執行出入庫作業時，多個穿梭車和提升機可同時工作。假定貨架垂直方向為z方向，沿貨架主軌道方向為y方向，沿貨位巷道方向為x方向。

圖1 四向穿梭車式密集型倉庫布局Fig.1 Layout of four-way shuttle storage and retrieval system

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

1.2 假設條件

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

（1）整個密集存儲系統內部單個貨位只能存儲一個托盤貨物，且貨位規格相同。

（2）存儲區域的貨格由于貨架的限制，只能雙向移動，即沿x方向行駛。

（3）進行貨位分配前，已知倉儲系統內剩余空閑貨位信息和待入庫貨物的周轉率、質量等信息。

2 入庫優化數學模型的構建

2.1 四向穿梭車式貨架建模

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

表1 參數與變量定義Table 1 Parameter and variable definitions

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

2.2 劃分貨道

密集型倉庫單層貨架貨位布局如圖1所示，為提高貨物出入庫效率，單個存儲貨道通常只存儲單類貨物，以避免在出庫作業時需要頻繁執行貨物移位任務。故貨位分配時需要將貨位劃分貨道，并以貨道為單位分類存儲貨物。此外，由于密集倉儲中貨道內貨格的多深度特點，通常采用先進后出的堆棧式貨物存儲管理策略。執行入庫作業時，應優先將貨物運送至貨道深處，以減少后續貨物的入庫路徑長度，并提高穿梭車作業時動態避堵的能力。

綜上，定義單個貨道只存放一種貨物，從貨道最深處貨格開始存儲貨物，并且優先填滿當前貨道再使用新貨道。最終貨位分配方案應滿足約束條件，即每類貨物所選的貨格總數不小于貨物總數。

2.3 優化目標的提出

根據密集倉儲的實際需求，建立如下優化模型。

（1）路徑最短

當不考慮穿梭車存取貨物和轉向時間時，入庫貨物所分配貨位距入庫口越近，穿梭車從作業貨位到提升機的路徑越短，倉庫的運行效率越高。

由于密集倉儲的軌道特點，穿梭車、提升機搭載貨物沿x、y或z方向移動，故使用曼哈頓距離計算坐標(xk,yk,zk)處貨位到i入庫口的距離。

假設倉庫內入庫口數量為L，得到穿梭車的作業總路徑為：

（2）貨位分布均衡

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

為避免周轉率較高的貨物在臨近的貨道聚集、穿梭車擁堵等情況發生，用貨道內貨物的周轉率之和表示貨道的擁擠程度。以貨道x、y、z方向上貨道擁擠程度的標準差來反映貨位分布的均衡程度，其值越小表示該方向上的貨位分布越均衡。

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

通過對三個方向的標準差進行加成得到衡量貨位分配離散程度的函數：

（3）貨架重心穩定

密集型倉儲的貨位分布較為集中，貨物質量分布不均勻、重心較高等會影響貨架的力學性能及穩定性。并且提升機運輸貨物換層時，作業能耗與貨物質量成正比，質量較小的貨物放在低層有利于減少能耗。考慮到貨位均衡的原則，在此主要降低倉庫內貨物整體z方向的重心，以提高貨架的穩定性并降低提升機能耗。

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

2.4 入庫貨位優化的數學模型

由上述目標函數及約束條件，可建立如下自動化倉庫貨位多目標優化模型：

由于上文中三個目標函數的量綱、數值范圍存在較大差異，故分別根據各個分目標函數的最優解fimin和最差解fimax，根據式（11）對目標函數進行歸一化。

為了簡化模型求解，對各目標進行主觀賦權，采用層次分析法（analytic hierarchy process，AHP）構造判斷矩陣求得特征向量，經過一致性檢驗確定特征向量的有效性后，得到各優化目標的權值αi。使用權重系數法將多目標優化問題轉化為單目標優化問題。

3 基于改進的混合蛙跳算法的入庫貨位分配

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

SFLA有算法概念簡單、控制參數少、易于實現的優點，目前已應用于求解旅行商、調度問題，但在解決高維優化問題時易出現早熟、解精度不夠的情況[14]。并且對于約束較為復雜的問題，SFLA在尋找最優解的過程中，根據青蛙的移動步長更新青蛙個體極易不滿足約束條件而用最優解替代，最終無法充分發揮算法的優越性。因此，本文借鑒遺傳算法求解離散優化問題采用的交叉、變異算子方法[15]，提出一種改進的SFLA算法以解決在貨道約束條件下的密集倉儲貨位分配問題。

3.1 編碼及解碼

根據倉庫地圖和貨道劃分標準，進行貨道的劃分，得到空閑貨道總個數為N，采用十進制數對貨道進行編號。假設當前倉庫內有n個空閑貨道(n≤N)，將n個貨道的編號隨機排列，即貨位編碼長度為n。

已知貨道編碼序列后，通過解碼確定每個貨物的貨位分配。首先，根據貨道序列得到對應貨道內的貨位數量、坐標等信息，然后將貨物依次從序列頭部對應貨道開始存儲，直至存放完所有貨物，即滿足式的約束條件。最終存儲貨物的編碼子序列為當前貨道序列的有效貨位編碼序列，即為當前編碼的貨位分配方案。該方案使得待分配的貨物能夠全部存儲于分配貨架巷道內。例如圖2 所示，現有10 個待入庫貨物A、10 個待入庫貨物B，對其的貨物編號為1、2。已知空閑貨位的編碼為（1，3，2，5，4，9…），通過對貨道貨位數量的計算，得到該條編碼的方案為1貨物準備放入1、3貨道，2貨物準備放入2、5 貨道。其中，將（1，3，2，5）視為該條編碼的有效編碼序列。

圖2 編碼和解碼規則Fig.2 Encoding and decoding rules

3.2 算法原理

初始化種群生成N個體，通過解碼計算出個體適應度后，將種群內個體按照適應度值降序排序，按式（13）劃分為s個子群：

其中，i=1,2,…,s,j=1,2,…,m,m為子群中個體的數目。

SFLA 通常以子群內最差解Pworse為優化對象，通過模因組內的局部搜索產生新解，具體過程如下：首先確定組內最優解Pbest、最差解Pworse以及全局最優解PB，然后根據式（14）、（15），利用Pbest和Pworse產生新個體Pnew：

式中，rand(0,1)表示在區間[0，1]上服從均勻分布的隨機數。若Pnew優于Pworse，則替換最差解Pworse；否則，隨機產生新解替換Pworse。重復以上步驟，直到達到設定的迭代次數。

其中，也有文獻在子群內隨機選擇兩個非劣解產生新個體Pnew[16]，或在式（14）移動步長中加入動態自適應同步因子[4]。本文選用Pworse為優化對象，結合遺傳算法（genetic algorithm，GA）采用一種新的優化迭代方法。

（1）交叉

進行交叉操作時，設計了動態自適應同步因子更新個體基因。按照式（16）從Pworse的有效編碼序列中隨機選取w個編號記為W={p1,p2,…,pw}，其中g為當前種群迭代次數。

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

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

（2）變異

本文的變異操作為隨機排列n個貨道，生成隨機編碼序列。

具體局部搜索過程描述如下：

步驟1按照適應度值排序結果，選擇當前模因組內最優解Pbest、最差解Pworse，將Pworse作為優化對象。

步驟2設定交叉概率pc。進行交叉操作時，從Pworse的有效編碼序列中隨機選取編號序列W，在Pbest的有效編碼序列中剔除W內的因子，得到新個體Pnew。

步驟3設定變異概率pm。進行變異操作時，隨機生成新個體Pnew。

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

步驟5是否達到模因組迭代次數。若是，輸出更新后的模因組；否則轉到步驟1，直至完成局部搜索。

3.3 算法步驟

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

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

步驟1設置參數。

步驟2初始化種群P，計算根據式（12）計算個體適應度。

步驟3根據適應度值對種群個體排序，根據式（13）劃分模因組。

步驟4局部搜索。對每個模因組按3.2節的策略進行個體的更新，直到達到局部搜索次數。

步驟5重新混合各個模因組中的所有個體，更新種群中最優個體。

步驟6是否達到種群迭代次數。若是，則輸出PB作為迭代后的最優解；否則，轉到步驟3。

4 實例驗證分析

4.1 算法驗證

以圖1所示的倉庫布局為例進行實驗，該倉庫的數據如表2所示。其中單個貨位的長和寬、軌道的寬度均為1個距離單位，相鄰貨位或相鄰的軌道和貨位間的距離忽略不計。由于貨架的結構限制，貨格位置處穿梭車無法在y方向上行走。已知待入庫的貨物信息如表3所示。

表2 密集型倉庫數據Table 2 Dense storage data

表3 待入庫貨物信息Table 3 Inbound cargo information

根據已知的倉庫數據，可整理得到貨位的數據信息，如圖5所示。

圖5 貨位信息Fig.5 Location information

為便于分析和驗證算法結果，將貨位信息可視化。如圖6（a）所示，將連通的貨位劃分為同一貨道。在單個貨道內所需入庫時間最長的貨位為貨道最深處，即圖6（b）中單個貨道中顏色最深的貨位。

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

為驗證和分析各個目標函數的優化效果，首先分別將各目標函數在Python中進行仿真。分別僅考慮第一、二、三目標函數，得到的貨位分配結果如圖7～圖9 所示。其中用顏色深淺表示貨物周轉率、質量大小，貨位顏色越深表示此處存放貨物周轉率越大或質量越大。

圖7 第一目標函數的仿真結果Fig.7 Simulation results of first objective function

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

圖8 第二目標函數的仿真結果Fig.8 Simulation results of second objective function

圖9 第三目標函數的仿真結果Fig.9 Simulation results of third objective function

4.2 實驗結果與分析

在上文驗證各目標函數、算法可行性的基礎上，針對表2數據的倉庫，對表3中的貨物分配貨位。

根據公司對該目標的重視程度，采用層次分析法計算得到權重(α1,α2,α3)為（0.291，0.418，0.291），建立評價函數。為了對比算法的優越性，采用標準遺傳算法GA、混合蛙跳算法SFLA 和改進的混合蛙跳算法SFLA-GA分別進行計算。算法參數如表4所示。

表4 算法參數Fig.4 Algorithm parameter table

運用所建立的密集倉儲貨位分配模型并結合GA、SFLA 及SFLA-GA 算法對該貨位分配任務進行仿真求解，其算法迭代過程目標函數值變化如圖10所示。

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

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

表5 算法結果數據對比Table 5 Algorithm resultcomparison table

圖11 為最終的貨位分配方案，在多目標函數的約束下，周轉率較大的貨物優先存放于距提升機較近的貨位中，沿貨架x、y、z方向的周轉率分布均衡，質量較大的貨物更多地存放在底層貨架上。進一步驗證了SFLAGA在處理密集式倉儲貨位分配問題的有效性和優越性。

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

5 結束語

本文重點研究密集倉儲下的貨位分配問題，針對密集倉儲的貨位分布特點劃分貨道，在此基礎上對倉庫貨位分配問題建立了多目標優化模型，分別采用改進的混合蛙跳算法、混合蛙跳算法和遺傳算法進行了仿真求解。實驗結果表明：

（1）所提優化算法能夠響應密集倉儲的貨位分布特征，符合實際倉儲作業需求。

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

本文所提出的模型與算法可以有效解決四向穿梭車式密集倉儲入庫貨位分配問題，但并沒有考慮到出入庫混批的復雜情況。在今后需進一步對出入庫混批情形下的貨位分配方法進行研究，算法性能也有待進一步提升。