多出/入口倉庫的貨位優化研究

劉旺盛, 馬國旺, 江雨瑤, 曾艷

(集美大學航海學院， 廈門 361021)

隨著電子商務產業的興起與企業發展的需要，現代倉庫由傳統的少品種小批次的揀選向大批次多品種揀選發展，這種變化使企業對貨物周轉的需求愈來愈高，因此，傳統少出/入口倉庫布局很難滿足企業實際生產活動的需要，而多出/入口倉庫能夠有效地提高作業揀選速度、減少單一出/入口工作量等優點，成為更多企業的選擇。

在倉儲作業中，揀選作業成本占倉儲總運營成本的65%以上。合理的貨位指派規則在降低揀選距離的同時，更能顯著地提高人力效率從而降低企業成本。因此，探究多出/入口倉庫的環境下貨位指派策略具有重要的實踐意義。

貨位優化問題被證明是 NP(nondeterministic polynomially)難題，早期相關問題研究考慮條件大多較為單一。近年來，隨著大數據技術的提出以及數據挖掘的應用[1-2]，貨位優化問題的研究從基于貨品頻率、貨品類別與貨位關系的研究轉向從歷史訂單中發掘貨品之間關聯度、貨品屬性與倉庫實際相結合的研究。Lee[3]最早于1992年提出貨品之間的關聯性的概念，他認為貨品關聯度可表示為貨品同時出現在一張訂單上的頻率。而后,許多學者在考慮關聯度的基礎上,不斷地拓展與延伸，采用不同方法對貨位優化問題開展研究。

部分學者嘗試將貨品相關性與其他因素考慮起來構建貨品優化模型，如Qiu 等[4]基于貨品關聯度，根據實際優化情況設計了一種基于耗時規則的貨位編號規則。Ning等[5]同樣在考慮貨品相關性的基礎上，將貨架穩定性、交貨時間等因素納入模型構建。Yang 等[6]針對醫藥物流中心布局不合理導致效率低下的問題，提出了品類間和品類內兩階段優化方法。Wu 等[7]結合預測訂單請求，采用貨品相關度構建了一個多目標優化模型來解決倉庫空間分配問題。Yang等[8]考慮了貨架穩定性、貨品相關性構建模型。除此之外，在模型求解方面， Wang等[9]針對貨架穩定性、貨品相關性等因素構建模型，并采用改進遺傳算法進行求解。周亞云等[10]采用譜聚類算法對貨品關聯規則聚類問題進行求解。

不同倉庫布局適合的貨位優化方法也不一樣。從以往研究來看，大多數學者均以單一出入口倉庫為研究對象，而目前倉庫的流動性高，大多數倉庫為了方便貨物的進出，設計為多出入口、一邊進一邊出模式，現有的貨位優化方法顯然不適用。因此，現針對這種倉庫布局提出了以相關性進行聚類的貨位優化策略。該策略基于峰值聚類算法以貨品關聯度最大為優化目標對貨品進行關聯聚類，并根據多出/入口倉庫的實際情況對貨位布局進行優化與調整。最后，通過實例數據與企業現行隨機存儲策略進行對比，驗證本文方法的有效性與穩健性。

1 多出/入口倉庫簡介

多出/入口倉庫布局如圖1所示，有X排貨架，每個貨架上有多個儲位可供存儲。每個入口對應一個出口，兩者是一一對應的，稱為一個組對，一共有多少這樣的組對，稱為出/入口組對數。每當訂單下達時，揀選員需要按照訂單所列貨品進行判斷，根據訂單上首位貨品所在巷道對應的入口進入，然后按照訂單貨品順序依次揀選貨品，當訂單中所有貨品均揀選完畢后，從巷道所屬最近出口離開。

圖1 多出/入口倉庫平面布局例圖Fig.1 Multi-exit/entrance warehouse layout

2 貨品優化模型及求解

2.1 模型假設

為了結合實際，突出研究主要問題，現有如下假設。

(1)訂單已經完成分拆與合并，揀貨員按照訂單分揀，每次只揀選一張訂單。每個貨位只能存儲一種貨品，且不考慮貨品體積、質量、數量的影響。

(2)貨品到出/入口的距離為存放貨品的中心到出/入口的距離。

(3)揀選路徑按照訂單所列貨品依次揀選，訂單上相鄰貨品揀選路徑遵循最短原則，不考慮擁堵情況。

(4)貨位數量可以滿足所有待優化貨品存儲需求。

2.2 貨位優化模型構建

2.2.1 相似度

本文研究中貨品之間關聯性是根據不同貨品是否同時出現在同一訂單中[11]，出現在相同訂單內次數越多，其貨品之間關聯程度越高。兩兩貨品相關程度計算公式為

(1)

式(1)中：i、j為貨品編號，i、j∈{1,2,…,m}；Cij為貨品i、j之間的關聯性指數；Pi為包含貨品i的訂單數目；Pj為包含貨品j的訂單數目；Pij為同時包含貨品i、j的訂單數目。

當Cij=0，表示貨品i、j不存在關聯性，即訂單集中沒有訂單同時包含貨品i、j；當Cij=1，表示兩者存在完全關聯關系，即訂單集中貨品i、j總是能夠同時被分配到同一個訂單中。同時Cij=Cji總存在對稱性。且Cij取值范圍為[0,1],其值越接近于1，貨品i、j被分配到同一個貨品聚合類可能性越大。

2.2.2 貨品聚類優化模型

一個組對數對應一個貨品聚類，令貨品聚類數等于出/入口組對數n。為了讓分揀員行走距離盡可能短，需要將相關性高的貨品盡量聚到一個類，放置在同一個貨架群組；相關性低貨品分配到不同聚類中，分別放置在不同貨架群組，并且將相關度大的貨品盡可能靠近放置，因此目標函數為兩兩貨品之間的相關度值乘以距離。

(2)

(3)

(4)

(5)

式(2)中：e為貨位編號且e∈{1,2,…,M}；g為聚合類編號且g∈{1,2,…,G}；dij為分配貨位后貨品i,j之間距離，通常采用曼哈頓距離進行計算。

式(3)表示每種貨品只能指派到一個貨品聚合類中；式(4)表示每種貨品只能指派到一個貨位中；式(5)表示決策變量取值約束;Xig為若將貨品i指派到聚合類g，則為1，否則為0；Yie為若將貨品i指派到貨位e，則為1，否則為0。

2.3 模型求解

聚類分析是通過將數據對象集合劃分成為不同聚合簇的過程，每個聚合簇內數據間彼此具有相關性[12]。本文將根據目標函數，設計有效地智能聚類算法進行問題求解。首先，從客戶歷史訂單數據入手，挖掘貨品之間相關度并求出N維貨品相關度矩陣，然后，基于貨品相關度矩陣利用多維標度分析算法對矩陣進行數據處理。以出/入口數量作為貨品聚類簇數目，并采用密度峰值聚類算法進行聚類并輸出聚類結果集，最后基于聚類后結果集求解模型并進行貨位分配。

2.3.1 多維標度分析算法

多維標度分析算法是以數據點之間距離為標準，將高緯度坐標投影到低緯度坐標的一種數據處理方法[13]。它與其他數據處理算法最大不同在于，在處理過程中，MDS算法要求數據點之間相對距離(在本文中為貨品之間相關度)變化最小。本文中要處理數據是貨品相關度矩陣，它與多維空間中距離矩陣在矩陣形式上表現一致，因此，以貨品之間的相關度代替傳統數據點之間的距離,采用MDS算法對相關度矩陣進行數據處理。該算法基本流程如下。

輸出：低維矩陣Z。

(1)對輸入訂單數據集預處理得到兩兩貨品同時訂購矩陣P并生成相關度矩陣W,W∈Rm×m。

(2)構建等效方程Cij=‖zi-zj‖，zi,zj∈Z,Cij∈W。

(3)令B=ZTZ，B∈Rm×m,其中B為降維后樣本內積矩陣，求解實對稱矩陣B,B=UΛUT。

(4)對矩陣B做特征值分解。

2.3.2 基于峰值聚類下貨品關聯挖掘算法

在實際中，多出/入口倉庫往往具有規模大、存儲貨品數量多、種類豐富等特點。所以在進行數據處理和分析時需要面對大量數據，而傳統聚類算法在求解時往往需要多次循環往復的迭代。本文選取DPC算法進行求解能有效地解決上述問題，同時該算法具有直觀發現聚類中心、處理不同形狀數據集等優點[14]。

DPC算法基于一種假設[15]：對于一個貨品集，聚類中心被一些低局部相關度的貨品包圍，而且這些低局部相關度貨品與其他有高局部相關度貨品間相關度值都比較小。這對聚類中心的選取提出兩大要求，首先能夠成為聚類中心貨品具有較大的局部相關度，其次與其他局部相關度較大貨品相關性較小。因此，在DPC算法中，主要需要計算局部相關度和相對最小相關度兩個變量。

數據對象xi的局部相關度ρi計算公式為

(6)

lc=dis(MP)

(7)

式中：lij為MDS處理后貨品之間相關度大??；lc為截斷相關度；dis為貨品集中所有貨品間相關度按照升序排列后相關度序列；M為貨品間相關度值的總數目；P為百分比，通常取2%[16]。

相對最小相關度δi，定義為

(8)

即為在局部相關度高于貨品i所有貨品中，與貨品i最小相關度。

計算出所有貨品的局部相關度ρi與相對最小相關度δi后，即可根據ρi與δi的關系在決策圖中觀察出聚類中心和確定聚類簇數。對于某些在決策圖中關系不明顯，不易觀察對象?？赏ㄟ^式(9)將決策值γi進行降序排列，從前往后選取需要聚類中心即可。

γi=ρiδi

(9)

基于DPC算法總流程如下。

輸入：低維矩陣Z。

輸出：貨品聚合類結果集A={a1,a2,…,ag}。

(1)計算矩陣,且令lij=lji,i

(2)確定截斷相關度lc。

(3)計算貨品集中每個貨品ρi與δi。

(4)借助式(9)確定需要聚類中心。

(5)對剩余貨品進行聚類操作。

(6)返回最終聚類結果集A。

2.3.3 存儲區域優化

在DPC算法聚類結束后，根據生成的聚類結果返回貨品聚合類內貨品相關性坐標，然后根據類內相關性坐標計算貨品聚合類相關性坐標均值Mg,最后計算不同聚合類相關性坐標均值距離dg，并根據距離的大小決定存儲區域的分配位置。具體流程如圖2所示。

圖2 存儲區域優化流程圖Fig.2 Flow chart of storage area optimization

2.3.4 貨位優化模型求解

通過對式(1)計算得出貨品相關性矩陣，并以MDS算法對矩陣進行維度處理，再通過DPC算法將相關性高的貨品聚成一類，將存儲區域與貨品聚合類一一匹配，使相關性高的貨品盡可能被分配到同一存儲區域。模型求解具體流程如圖3所示。

圖3 模型求解流程圖Fig.3 Flow chart of model solving

3 算例求解及結果分析

3.1 算例說明

通過實地調研方式，獲得H企業A倉庫2018年4—5月訂單數據集，其中包括訂單編號、貨品種類、貨品位置等數據。由于企業數據需要保密處理，所以訂單編號及貨品種類均采用數字替代。A倉庫中共有8排貨架，對原始訂單數據集進行處理清洗后保留2 076張有效訂單，包含842種貨品。訂單數據如表 1所示。

表1 訂單數據表Table 1 Table of order data

3.2 貨品兩兩相關性分析

通過Python2.7編程軟件對訂單隸屬數據進行分析根據式(1)計算貨品兩兩相關性表，如表2所示。

表2 貨品兩兩相關性表Table 2 Table of goods correlation

3.3 數據處理

從貨品相關性表得出貨品相關性矩陣為n維矩陣，聚類算法無法直接進行處理。采用MDS算法對貨品相關性矩陣進行處理以獲得二維相關性坐標。處理后數據如表3所示。

表3 數據處理表Table 3 Table of data processing

3.4 數據聚類處理

通過MDS算法對貨品相關性進行數據處理后，再利用峰值聚類算法進行聚類。本文聚類簇選擇根據出/入口數量，H公司A倉庫中共有4個出/入口8排貨架，因此聚類簇選擇應為4。聚類結果如表4所示。

表4 聚類結果表Table 4 Table of clustering results

3.5 基于密度峰值算法下模型求解

3.5.1 貨位區域優化

H公司原有貨位分配策略為隨機策略，想要貨品盡可能均勻分配到倉庫，達到作業均衡化目的，但在實際應用中與理想效果相差甚遠。在原始倉庫布局的基礎上，不改變貨架位置。通過DPC算法依據貨品相關性將貨品劃分為4個聚合類。使高相關性貨品聚合類在存儲區域位置上盡可能的接近。優化貨品存儲區域示例圖，如圖4所示。

圖4 優化貨品存儲區域圖Fig.4 Optimized goods storage area map

3.5.2 存儲策略比較

根據貨品存儲區域分配結果，使用Python2.7編程軟件基于實例數據分別計算本文存儲優化與隨機存儲這兩種儲位優化策略下跨區域平均訂單揀選距離，結果如表5所示。

表5 基于不同優化策略跨區域平均揀選距離比較表Table 5 Table of average pick distance comparison

跨區域平均揀選距離是指平均一個揀選員揀選不同存儲區域需行走路徑，通常用總揀選距離除以訂單數量。

3.6 靈敏度分析

為了避免實驗結果的偶然性，本文模擬生成幾個其他規模的算例，計算并比較本文存儲優化策略與隨機存儲優化策略結果，優化存儲策略表如表6所示。

由表6可知，跨區域平均揀選距離大小與貨品種類數量存在一定關系，因此本文基于密度峰值聚類算法下探究不同貨品種類數量與跨區域平均揀選距離關系。并對其進行靈敏度分析，靈敏度分析圖如圖5所示。

表6 優化策略比較表Table 6 Comparison of optimization strategies

由圖5可見貨品種類數量與跨區域平均揀選距離存在著正相關性。但隨著貨品種類數量增加，其跨區域平均揀選距離增長趨于平緩。這與實際情況相符，當貨品種類數量增加時，將高相關性的貨品聚成一類放在同一存儲區域進行存取，能有效減少揀選距離，提高揀選員工作效率。

圖5 靈敏度分析圖Fig.5 Sensitivity analysis diagram

4 結論

基于物流倉庫發展趨勢出發，針對多出/入口倉庫布局下對貨位優化問題進行了研究，分別設計了多維標度分析算法與峰值聚類算法進行聚類分析，然后進行組內和組間貨位分配。本文有如下創新之處。

(1)設計了多維標度分析算法可以直接解決企業數據與聚類模型需要數據之間不兼容問題。

(2)采用密度峰值聚類算法，將高相關度貨品存放在同一存儲區域，減少了揀選員經歷巷道數量，提升了倉庫作業效率。

(3)根據多出/入口倉庫布局情況來確定貨品聚類簇數，并根據實際情況進行調整，利用貨品相關性來達到訂單揀選距離最小目的。

通過實際案例驗證，本文策略比隨機策略平均優化24.56%。本文設計模型與策略為解決多出/入口倉庫貨位優化問題提供了有效地決策方法，顯著提高了倉庫運作效率，降低了企業的倉儲運作成本。