基于粒子群算法的立體倉庫貨位優(yōu)化研究

郭 娟，錢吳永 （江南大學 商學院，江蘇 無錫214122）

0 引 言

對物流企業(yè)而言，構(gòu)建完善的物流系統(tǒng)是其保持較高競爭力的必要條件，而立體倉庫作為物流系統(tǒng)的重要組成部分，對其進行優(yōu)化是很有必要的。立體倉庫最主要的功能就是對貨物進行儲存和保管以保障企業(yè)正常的生產(chǎn)經(jīng)營活動。如今企業(yè)生產(chǎn)運作受市場需求的影響越來越大，而傳統(tǒng)的貨位分配方式通常是將貨物就近放至附近空貨架，對于貨物出入庫頻率及客戶需求的動態(tài)性缺乏考慮，且由于存儲的貨物數(shù)量龐大、品種繁多，如果在進行倉儲作業(yè)之前不能對貨物存儲的貨位進行合理的規(guī)劃，勢必會導致倉儲作業(yè)過程中發(fā)生擁堵或者作業(yè)中斷問題，影響倉庫作業(yè)效率，導致整個物流供應體系效率的降低。因此，為了提高倉儲作業(yè)效率，降低倉庫運營成本，需對立體倉庫貨位分配進行優(yōu)化。

近年來，自動化立體倉庫貨位優(yōu)化是國內(nèi)外研究的熱點，許多學者對自動化立體倉庫的貨位優(yōu)化及求解算法已有了大量研究。Thonemann（1998） 提出在隨機環(huán)境中基于貨物周轉(zhuǎn)率和貨物分類進行貨位分配的方法[1]；馬永杰（2008） 等人基于隨機存儲策略，以堆垛機行駛時間為優(yōu)化控制目標，采用Pareto 遺傳算法求解該優(yōu)化問題[2]；Kim（2012） 等將貨位再分配問題定義為一個多物料流問題，以最短運輸距離和庫存成本為目標，提出基于模擬退火的貨位分配問題模型與算法求解[3]；陳璐（2012）提出了一個混合整數(shù)規(guī)劃模型對貨位分配和存取路徑優(yōu)化進行求解，并利用禁忌搜索算法和Hungarian 算法對所求解進行改進[4]；曹萌萌（2013） 等人以貨架穩(wěn)定性和出入庫效率為目標建立汽車零件自動化立體倉庫貨位優(yōu)化模型，最后通過混合遺傳算法對該問題進行求解[5]；鄧愛民（2013） 等以入庫效率高、貨物相似性、移動距離短為目標提出基于遺傳算法的醫(yī)藥行業(yè)立體倉庫貨位優(yōu)化模型并求解[6]；張璐璐（2015） 以汽車零部件倉儲系統(tǒng)為研究對象，通過給貨位和貨品賦值，建立系數(shù)矩陣的方法，設(shè)計貨位優(yōu)化方案，并利用Petri 網(wǎng)進行出入庫操作的優(yōu)化，最后為貨位優(yōu)化方案提出相應保障措施[7]；李鵬飛（2017）等人提出以出入庫效率和貨架穩(wěn)定性為優(yōu)化目標的自動化立體倉庫協(xié)同遺傳算法優(yōu)化模型，有效提升了自動化立體倉庫的作業(yè)效率[8]；陳雪以自動化立體倉庫的貨架穩(wěn)定性、貨物相關(guān)性和相關(guān)產(chǎn)品的存放為優(yōu)化目標，提出改進粒子群算法進行求解，最后通過Flexsim 仿真系統(tǒng)進行模擬，驗證該方法的有效性[9]；陳元文（2013） 等人以堆垛機運行時間最短和貨架重心最低為目標建立優(yōu)化模型，并利用基于混合偏好的遺傳算法對多目標問題求解，證明該方法能較大提高特定環(huán)境下立體倉庫的出庫效率并降低貨架重心[12]。

在對貨位分配問題進行研究時，以往學者大多基于自動化立體倉庫為研究對象，以貨架穩(wěn)定性和貨物出入庫效率為目標建立多目標貨位分配模型，在設(shè)計求解算法時，多采用遺傳算法。由于市場需求的不確定性增加，生產(chǎn)制造型企業(yè)由傳統(tǒng)的生產(chǎn)驅(qū)動向訂單驅(qū)動模式轉(zhuǎn)變，為了保證倉儲作業(yè)效率，貨位分配也要隨著貨物出入庫頻率的變化而發(fā)生相應改變。在此前提下，本文以立體倉庫貨位優(yōu)化為研究對象，以貨架穩(wěn)定性、貨物相關(guān)性和出入庫效率為研究目標，建立了多目標貨位優(yōu)化模型，采用粒子群算法求解，通過優(yōu)化前后對比，驗證了模型和算法的合理性和有效性。

1 模型建立

1.1 多目標貨位優(yōu)化問題假設(shè)

假設(shè)立體倉庫中的貨架有a 排、b 列、c 層，每個坐標代表一個存儲單元。其中x 表示排，y 表示列，z 表示貨架層數(shù)，即位于x 排y 列z 層的貨物位置可以表示為（x,y ,z ），出庫區(qū)表示為（0,0,1 ）。建立立體倉庫貨位分配模型時，假設(shè)條件如下：

（1） 立體倉庫中每個貨架的貨位大小和尺寸均相同，且每個貨位只能存放一件標準化包裝的貨物；

（2） 貨物都儲存在托盤中，托盤尺寸與貨架相匹配；

（3） 立體倉庫內(nèi)巷道載貨入口與出口均在同一側(cè)，即只有一側(cè)通道可供作業(yè)人員進行倉儲作業(yè)；

（4） 立體倉庫采用分類隨機存儲策略，即首先將貨物按照不同類型進行分類，每類貨物都有對應的存儲區(qū)域，最后采取隨機存儲的方式在每類貨物各自的區(qū)域內(nèi)實施入庫操作，隨機存儲策略可以經(jīng)常發(fā)生改變，根據(jù)某一時間段內(nèi)貨物的出入庫情況對貨位進行動態(tài)分配；

（5） 貨物揀選時間忽略不計，只考慮揀選時作業(yè)人員操作叉車行進的時間；

（6） 系統(tǒng)中對各類貨物的需求是不確定的，但是部分貨物的需求具有相關(guān)性，因此會優(yōu)先將這部分貨物儲存在相鄰貨架；

（7） 該立體倉庫為單端口的出入庫方式，即每排貨架的貨物出入庫為（0,0,1 ）位置都為這一個。

1.2 貨位優(yōu)化模型的建立

本文涉及到的相關(guān)符號含義如表1 所示：

表1 參數(shù)符號設(shè)定

倉庫操作人員在貨架間的叉車速度與熟練度不同都會導致模型結(jié)果不準確，因此，假設(shè)作業(yè)人員作業(yè)時橫向與縱向的叉車速度均為相同的固定值，倉儲作業(yè)人員的熟練度相同。

倉儲作業(yè)按其流程可劃分為入庫作業(yè)和出庫作業(yè)，在進行貨位優(yōu)化時，由于出入庫的不同目標，分別建立入庫貨位優(yōu)化和出庫貨位優(yōu)化模型。

（1） 入庫貨位優(yōu)化模型

在對貨物進行入庫貨位分配時，要考慮的重要原則是“提高物品相關(guān)性，將關(guān)聯(lián)性大的貨物放至相鄰貨架”、“保證貨架穩(wěn)定性，上輕下重”和“提高入庫作業(yè)效率，減少倉儲作業(yè)堵塞”，即在保證貨架穩(wěn)定性的前提下，將出入庫關(guān)聯(lián)性較大的貨物放在一起，提高貨物上架效率，減少作業(yè)停頓與堵塞。

目標一：提高貨物相關(guān)性

為了便于倉庫出入庫作業(yè)，在對倉儲貨物出入庫情況進行分析的基礎(chǔ)上，應該將同時出入庫的產(chǎn)品放在一起，以提高出入庫效率，也方便后續(xù)盤點工作。

i 類貨物中第j 個產(chǎn)品到m 的距離為：

產(chǎn)品的類聚散度d 定義為全部n 類產(chǎn)品到mi的距離之和：

全部產(chǎn)品到n 類產(chǎn)品中心坐標M 的離散度之和的值定義為每一類產(chǎn)品的中心mi到M 的距離之和：

因此，為了使相關(guān)性高的產(chǎn)品盡可能均勻存放在一起，應該使關(guān)聯(lián)度高的貨物類內(nèi)離散度最小，提高相鄰貨架的產(chǎn)品相關(guān)度，目標函數(shù)如下：

目標二：提高貨架穩(wěn)定性

在立體倉庫中，為了提高貨架穩(wěn)定性，通常按照“上輕下重”的原則進行貨物存儲，將重量大的貨物放在貨架底層，重量小的貨物放在貨架上層，以降低貨架的重心，因此，應使產(chǎn)品重量與所處層數(shù)乘積之和最小，目標函數(shù)為：

立體倉庫中，一組貨架通常包含兩排貨架，如果兩排貨架之間的重量相差較大，會導致貨架發(fā)生傾斜，因此，為了提高貨架的穩(wěn)定性，要使同一組兩排貨架（x=2k 和x=2k+1 ）的總重量基本保持一致，目標函數(shù)如下：

目標三：入庫效率最大化

倉儲作業(yè)人員操作叉車的速度是既定的，為了提高出入庫效率，可以將出入庫頻率較高的貨物放在離出入庫平臺較近的位置，目標函數(shù)為：

立體倉庫入庫的總目標可表示為：

約束條件為：

（2） 出庫貨位優(yōu)化模型

貨物出庫需要考慮的因素為訂單響應速度最快，即出庫效率最高。出庫時貨物的貨位初始狀態(tài)是入庫后的貨位狀態(tài)。立體倉庫貨物出庫的總目標為：

約束條件為：

2 基于多目標粒子群算法的貨位優(yōu)化仿真

粒子群算法將尋優(yōu)過程等價于信息共享條件下鳥群的覓食過程，鳥群中每只鳥可看作一個粒子，在貨位優(yōu)化的粒子群算法中，將每個貨位看作倉儲系統(tǒng)中的一個個體，即群體中的成員。本文采用多目標粒子群算法，通過不斷更新自身位置與速度來搜尋最優(yōu)解。其進化表達式為：

其中：i 表示第i 個粒子，t 表示迭代次數(shù)，ω 為慣性權(quán)重，c1和c2為加速常數(shù)，γ1和γ2為［0,1 ］范圍內(nèi)的隨機數(shù)，用來增加粒子飛行的隨機性，vi（t ）表示第i 個粒子在第t 次迭代時的速度，xi（t ）表示第i 個粒子在第t 次迭代時的位置，pbest和gbest為粒子自身經(jīng)歷的最佳位置以及整個種群的歷史最佳位置。對于多目標問題，通過判斷當前狀態(tài)是否支配該粒子的歷史最優(yōu)pbest，若是，則將pbest更改為粒子的當前狀態(tài)，若pbest支配粒子的當前狀態(tài)，則不做任何操作，若不是這兩種情況，則說明這兩個解均為非劣解，即無法判斷哪個狀態(tài)更好，所以定義［0,1 ］之間的隨機數(shù)rand，若小于0.5，則將pbest改為當前狀態(tài)，否則不做任何操作。gbest通過隨機選取非劣解集中的個體來決定。根據(jù)每次迭代過程產(chǎn)生的非劣解集的上下限，將解空間分為等大的網(wǎng)格，以各網(wǎng)格中解的密度大小來刪除冗余解，達到控制種群分布的目的。

多目標粒子群算法的流程如圖1 所示：

本文中出庫作業(yè)為單目標優(yōu)化問題，與入庫作業(yè)基本條件有差異，且出庫作業(yè)的優(yōu)化目標在入庫多目標優(yōu)化模型中有體現(xiàn)，故在本文中暫不考慮出庫作業(yè)優(yōu)化，只對入庫優(yōu)化模型進行求解。假設(shè)立體倉庫有20 排、16 列、6 層，倉儲作業(yè)人員作業(yè)操作叉車時在x方向上的速度為1m/s，y 方向上的速度為1.2m/s，z 方向上的速度為0.6m/s，倉庫內(nèi)存儲的貨物可分為A、B、C 三類，A 類貨物的周轉(zhuǎn)率為0.2～0.4，重量為30 個單位，B 類貨物的周轉(zhuǎn)率為0.4～0.6，重量為40 個單位，C 類貨物的周轉(zhuǎn)率為0.6～0.8，重量為50 個單位，在多目標優(yōu)化函數(shù)中，幾個目標的重要性同等重要，即ω= （0.25,0.25,0.25,0.25 ），貨物的初始狀態(tài)如表2 所示。

根據(jù)圖1 中的算法基本流程，選取粒子數(shù)M=50，最大迭代次數(shù)N=150，速度更新時，學習因子c1=c2=1.4945，慣性因子ωmax=0.8,ωmin=0.2，在第n 次迭代中，慣性因子根據(jù)以上參數(shù)，運用多目標粒子群算法對立體倉庫出入庫模型進行求解，優(yōu)化前后的貨位分布及最優(yōu)個體適應度如圖2 至圖4 所示。

圖1 多目標粒子群算法基本流程

根據(jù)優(yōu)化前后的貨物分布對比可以看出，優(yōu)化前的貨物分布較為分散，沒有明顯的布局規(guī)則，優(yōu)化后的貨物更集中分布于立體倉庫出入口附近，相關(guān)性較大的貨物擺放位置較近，且大部分貨物位于貨架低層，貨架的穩(wěn)定性得以提高。在此模型中，F(xiàn)3=7.1859，取值相對較大，說明在立體倉庫貨位優(yōu)化過程中，貨物的移動距離較小，本方案運用較小的倉儲作業(yè)成本實現(xiàn)了倉庫作業(yè)效率的提升；適應度函數(shù)取值為87.964，數(shù)值較大，說明本優(yōu)化方案取得了一個較為理想的結(jié)果。

圖2 優(yōu)化前貨物分布圖

圖3 最優(yōu)個體適應度

3 結(jié) 論

本文在考慮貨架穩(wěn)定性、貨物相關(guān)性、出入庫效率這三個因素的基礎(chǔ)上構(gòu)建了立體倉庫入庫優(yōu)化模型，通過多目標粒子群算法的優(yōu)化求解，對立體倉庫貨位進行了重新分配。在獲取立體倉庫最新貨位分配數(shù)據(jù)的基礎(chǔ)上，結(jié)合多個目標來調(diào)整其貨位分配，提高企業(yè)倉儲作業(yè)效率，減少出入庫作業(yè)中的資源浪費。

表2 立體倉庫貨位初始方案

圖4 優(yōu)化后貨物分布圖