基于關聯性分析的智能倉庫貨位優化研究

曾敏剛 張俊杰 陳偉賢

摘? 要：訂單分揀是倉儲作業中很重要的一個環節，而智能倉庫揀選中貨架的位置處于動態變化中，因此進行合理的貨位布局尤為重要。為有效解決智能倉庫貨位分配問題，提出了在倉庫中設置關聯貨物儲存區的策略，進而給出了基于關聯性分析的貨位優化方案，即先根據歷史出庫訂單數據進行關聯性分析以進行儲位布局，以實現機器人搬運貨架次數最少的目標;同時考慮COI指數等因素進行建模確定貨架布局，以實現機器人搬運路徑最短的目標。最后，通過算例分析，驗證了基于關聯分析的貨位優化方案的有效性。

關鍵詞：貨位優化;關聯規則;Apriori算法;智能倉庫

中圖分類號：F253? ? 文獻標識碼：A

Abstract： Orders sorting is an important part of warehousing operations， the position of shelves is in dynamic change in intelligent warehouse， so it is particularly important to carry out reasonable location layout. The strategy of setting up associated cargo storage area in warehouse is proposed so as to realize the optimization of storage location in intelligent warehouse. Then， a new optimization solution of storage location is put forward： first， the correlation analysis is carried out according to the historical outgoing order data to carry out the layout of storage space， so as to achieve the goal of minimizing the number of cargo sorties carried by robots. At the same time， the factors included COI index are taken into the model to realize the shelf layout in order to achieve the goal of the shortest moving path of the robot. Finally， the effectiveness of the location optimization scheme based on correlation analysis is verified by an example.

Key words： storage allocation; association rules; apriori algorithm; intelligent warehouse

0? 引? 言

電商倉儲，正在經歷半人工、半自動化向以機器人智能物流系統為主的倉庫自動化轉變，實現無人智慧化布局、數字化運營和自動化作業。智能倉庫主要包括四大系統：（1）存儲系統，主要由不同類型的貨架組成，限高2.5米;（2）輸送系統，主要由AGV機器人組成;（3）分揀系統，主要由揀貨臺、輸送裝置和自動識別系統等組成;（4）控制系統，主要由自動控制系統和中央計算機管理系統組成。揀貨作業時間一般約占全部作業時間的40%以上，揀選成本一般占全部運營成本的65%以上[1]，所以貨位布局的優化對提高分揀效率尤為重要。

目前國內外學者對貨位優化的研究主要集中在3個方面：（1）貨位優化模型：①以貨架穩定性、揀貨時間或揀貨距離為優化目標：文獻[2-5]以貨架穩定性最高和堆垛機運行時間最短建立多目標模型，張貴軍等[6]提出了精英多策略的貨位分配方法;楊瑋等[7]基于多色集合理論對貨位分區建立多目標模型;肖建等[8-9]根據物料的確定相關性和統計相關性這兩個概念，建立了以揀貨人員距離最短的多目標優化數學模型，但所研究的相關性，僅限于物料需求的相關性，例如加強螺栓與防松螺母這樣的物料組合;文獻[10-11]以傳統倉庫為例，提出了SKUs相關性的概念，設計了“SKUs對”位置交換策略以提高效率。②以倉庫利用率、成本和能耗為優化目標：Simon Brezovnik等[12]考慮提高倉庫空間利用率和降低庫存成本兩個目標建立優化模型;Muppant等[13]建立了整數規劃數學模型;Quintanilla等[14]基于隨機存儲策略，提出了最大化倉庫空間利用率的貨位調整方法;張思建等[15]以出入庫總能耗及存取效率為目標建立模型;ELSAYED E A[16]提出基于迭代搜索的定位儲存模型，以租用存儲空間的方式最優化倉儲容量;András Kovác[17]針對貨物循環進出的情況，建立了循環周期最短和工作強度最低的貨位分配模型。③RGV行駛時間為優化目標：劉萬強等[18]建立了RGV小車行程時間的通用計算模型，通過更改不同的參數來對應計算不同工況下RGV車的行程時間。④貨架搬運次數為優化目標：Nils Boysen等以亞馬遜倉庫Kiva系統為例，建立了以貨架搬運次數最小化為目標的混合整數規劃模型，用于求解最佳揀選訂單的批次和順序以及貨架分配方案[19]。（2）貨位仿真和編程實現：趙金萍等[20]對自動化立體倉庫的叉車、堆垛機和貨架均進行了優化，Flexsim軟件仿真結果表明操作臺的利用率提高了10%～15%;張仰森等[21]以某集團公司立體倉庫管理系統為例，提出了一個多角度計算的級聯式的貨位優化分配算法及其編程實現。（3）貨位布局方式和存儲策略：文獻[22-23]研究了不同的倉儲設施布局方式對貨位分配的影響，文獻[24-26]研究了Fishbone布局方式對AGV小車的行駛路徑的影響;文獻[27-28]基于聚類方法，提出了現貨物分類優化管理的策略;QUINTANILLA S等[29]將貨位分配問題類比于著色問題，采用定位存儲策略最小化存儲空間。

綜上可知，（1）國內外學者研究對象集中于自動化立體倉庫，對智能倉庫的貨位優化問題研究甚少，而“貨到人”揀選方式中貨架位置是動態變化的，傳統優化方法并不適用于智能倉庫分揀的工作場景;（2）研究方法主要集中于建立數學模型，目標多為揀貨時間、貨架穩定性和空間利用率等，考慮因素集中于周轉率，而對貨物相關性研究甚少;（3）部分學者雖從相關方面進行了研究，但相關性分析算法的有效性較弱，并未從數據挖掘方面進行拓展。因此本文針對智能機器人“貨到人”揀選工作特點，綜合考慮了貨物相關性和貨物COI指數等因素，結合數據挖掘的Apriori算法，提出了基于關聯性分析的貨位優化方案。

1? ?問題描述

1.1? 問題提出與基本假設

智能倉庫自動化應用的主要一個方面便是“貨到人”揀選，工作模式為：當訂單開始處理后，系統發出指令，AGV智能機器人從儲存區將整個貨架搬運至揀貨工作臺，揀選人員只需根據顯示屏和播種墻電子標簽的提示，從指定貨位揀取相應數量的商品放入訂單箱即可?！柏浀饺恕边@一揀選方式，給貨物存儲與貨物揀選之間的動靜結合帶來了新的問題：（1）如何在一個貨架上擺放多張訂單的貨物？（2）電商倉庫中存儲的貨物批量大、種類多，如何挖掘出貨物之間的關聯性？（3）如何布局貨位，使得AGV機器人搬運貨架路徑最短？

根據如上描述，將本文進行貨位優化所作假設總結如下：

（1）存放的貨物種類已知;

（2）每種貨物的周轉率和體積已知，即COI指數已知;

（3）貨架上每個儲位只擺放同一種貨物，儲位單元格長寬高為定值;

（4）智能倉庫采用單端出入庫方式;

（5）存取貨物耗費的時間忽略不計，僅考慮貨物揀選時間。

1.2? 模型建立

1.2.1? 符號說明

模型所需符號及說明見表1所示。

1.2.2? 建立模型

（1）AGV搬運貨架次數最少

AGV每次從存儲區搬出的貨架上要盡可能包含多張訂單的貨物，即關聯性高的貨品的位置盡可能緊鄰。為此通過關聯性分析將貨物分成不同的類別，使得同類貨物盡可能集中放置，而不同類貨物則盡可能分散。

①同類貨物內部的分散度

定義各類貨品的中心位置為該類貨品內所有貨物向量坐標的均值：

a=∑x，y，z，w? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）

每類貨品的類內分散度定義為此類貨品中每種貨物到中心位置的距離之和：

d=∑? ? ? ? ? ? ? ? ? ? ? （2）

則所有貨物的類內分散度為：

d=∑d? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （3）

②不同類貨物之間的分散度

定義所有貨品的中心位置為各類貨品中心位置的向量坐標的均值：

A=∑a? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）

定義不同貨品間的類間分散度為各類貨品中心位置到所有貨物中心位置的距離之和：

D=∑a-A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（5）

考慮到讓關聯度高的貨物盡可能放在一起，故類內分散度要最小，而關聯性很低的貨物則要均勻地分散到倉庫中且離倉庫入口距離最小，故類間分散度最大，且A=最小。

故目標函數為：

maxF=? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （6）

（2）AGV搬運貨架行走路徑最短

在考慮貨架的布局時，引進貨物COI指數[30-31]，綜合考慮貨物周轉率和體積兩個因素，使得COI指數小的貨物盡可能靠近出庫口，減少AGV搬運距離。

該目標函數為：

minF=∑∑∑∑C·L? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （7）

約束條件為：

①貨位界限約束

x≤x≤x? ? y≤y≤y? ? z≤z≤z? ? w≤w≤w? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（8）

②容量約束

∑∑∑∑Q≤∑∑∑∑V? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （9）

2? 模型求解

2.1? 算法思路

電商倉庫中存儲的貨物種類繁多且數量龐大，然而相互之間存在關聯性的貨物卻不多，故本文提出關聯貨物存儲區的策略，只將關聯性很高的少部分貨物存放至該區域，在該區域內按照上文建立模型進行貨位布局。

貨物關聯性反映的是兩種貨物或者多種貨物之間相關程度的強弱，而COI指數則是某種貨物的周轉率與體積之比，是貨物本身特有的“屬性”。二者無法統一度量，此外關聯性程度高的貨物可能COI指數很低，故本文在求解上未采用將多目標轉化為單目標的解法，而是采用兩階段優化求解，算法思路如圖1所示。

貨品關聯性分析旨在通過分析歷史已處理的訂單數據，根據貨品間的關聯性結果確定儲位布局，貨架布局方案則通過建模求解。

2.2? 貨位布局求解

2.2.1? 關聯規則簡介

關聯規則（Association Rule）是在數據庫和數據挖掘領域中廣泛研究的一種重要模型[32]，可數學化描述為：設I

=i，i，i，…是一個項目集合，D是事務型數據庫，其中的每個事務T都由一個唯一的標識符TID進行區分，即D

=T，T，T，…，每個事務Ti=1，2，3，…對應I上的一個子集。事物數據庫D如表2所示。

設項集X、Y是項目集合I中的一個集合，滿足X？哿T，Y？哿T，X？奐I，Y？奐I，且X∩Y=？覫。用X→Y表示關聯規則，相關關系的強度由支持度（Support）和置信度（Confidence）來評價。其中SupportX→Y=PX∪Y，ConfidenceX→Y=PY|X。

為了挖掘有意義的關聯規則，需要設定兩個閾值：最小支持度MinSup（Min Support）和最小置信度MinCon（Min Confidence），將同時滿足MinSup和MinCon的規則稱為強關聯規則[33]。

2.2.2? Apriori算法簡介

在眾多挖掘關聯規則的算法中，Apriori算法為布爾關聯規則挖掘頻繁項集的經典算法，并得到了廣泛應用。Apriori算法的求解步驟為逐層搜索迭代，即利用k-項集來產生k+1-項集：首先掃描數據庫找出頻繁1項集，記為L1，然后對L1做連接操作生成C2，掃描數據庫從C2中選出頻繁2-項集即L2;不斷如此循環下去直到無法發現更多的頻繁k-項集為止[34]。

Apriori算法挖掘關聯規則主要可分為4個步驟，如圖2所示。

2.2.3? 貨位布局方案

采用Apriori算法對歷史訂單進行分析，可挖掘出關聯性高的頻繁項目集，儲位布局時需將關聯性高的貨物盡可能擺放在同一個貨架上，應遵循以下規則：（1）將關聯規則根據置信度大小排序，置信度高的關聯規則所包含的貨物優先布局;（2）相互獨立的關聯規則所包含的貨物應放置在不同貨架上;（3）存在交叉關系的關聯規則里所包含的貨物，應根據儲位數量進行合理放置，例如關聯規則A→B和E→B存在交叉，則所涉及的ABE這3種貨物統一放在一個貨架上;（4）若多個關聯規則均包含某種貨物，且該貨物已經布局完成，則將關聯規則里包含的剩余所有貨物放在同一個貨架上，例如關聯規則F→A、G→A和H→A均包含貨物A，且A布局已經完成，則將剩余的貨物FGH放置在同一貨架上。

儲位布局只確定了哪些貨物組合到同一個貨架上，實現了AGV搬運貨架次數最少的目標;而AGV搬運路徑最短目標的實現，則需在儲位布局的基礎上，將COI指數低的貨物分配到離出庫口最近的位置上，可通過Lingo進行模型求解。綜合儲位、貨架布局方案得到最終的貨位優化方案。

3? ?算例分析

3.1? 數據收集與關聯性挖掘

假設倉庫當前共存儲50種貨物，已經出庫了100張訂單，訂單數據如表3所示：

設定MinSup=0.2，MinCon=0.75，根據Apriori算法求解步驟，并按照置信度大小對其進行排序，最終篩選出的二項頻繁項目集的強關聯規則如表4所示：

置信度越高表示兩者之間的關聯性越高，儲位布局時兩者的位置應盡可能的緊鄰。

3.2? 貨位布局方案

假設一個貨架共有3個儲位，每個貨位只放一種貨物，且每個貨位的容量無限大。倉庫布局如圖3所示，其中括號內數字表示該貨架到出庫口的距離。

根據這100張歷史訂單分析得到的關聯性結果，按照儲位布局規則依次考慮貨物間的位置，得到儲位初步布局圖如圖4所示。

為簡化計算：（1）以貨物周轉頻率代替COI指數;（2）因為同一貨架上的放置貨物已經固定，故可取3種貨物周轉率的加權平均值作為貨架的周轉率。

根據3.3節中建立的模型進行求解，得到新的貨架布局如圖5所示。

4? 結? 論

本文針對傳統研究的不足，對智能倉庫的貨位布局進行研究，通過算例分析，得到以下結論：（1）針對智能機器人“貨到人”揀選貨架位置動態變化的工作模式，提出了設置關聯貨物儲存區的策略，進而給出了基于關聯性分析的貨位優化方案;（2）通過關聯分析確定儲位布局，實現了機器人搬運貨架次數最少的目標;考慮COI指數建立模型求解貨架布局實現了機器人搬運路徑最短的目標;（3）引入了數據挖掘中Apriori算法來分析貨物之間的相關性，提高了算法的有效性。

研究方法和貨位布局方案對企業現有的倉庫揀選工作具有重要的指導意義。本文在方案求解上采用分階段優化方法，未來可考慮全局優化，并考慮訂單組合和貨位容量的限制，以得到更優的貨位布局方案。

參考文獻：

[1]? RENDE K， THO L D， KEES J R. Design and control of warehouse order picking： A literature review[J]. European Journal of Operation Research， 2006，182（2）：481-501.

[2] 鄂曉征，祖巧紅，曹萌萌. 基于遺傳算法的汽車零件自動化倉儲貨位優化[J]. 系統仿真學報，2013，25（3）：430-435，444.

[3] 侯忠，鄭國華. 基于遺傳算法的汽車零配件倉庫貨位優化研究[J]. 鐵道科學與工程學報，2016，13（11）：2305-2312.

[4] 李鵬飛，馬航. 基于病毒協同遺傳算法的自動化立體倉庫貨位優化模型[J]. 中國管理科學，2017，25（5）：70-77.

[5] 趙雪峰，贠超，胡江. 自動化倉儲系統不規則貨位優化問題研究[J]. 計算機工程與應用，2012，48（24）：222-225，230.

[6] 張貴軍，姚俊，周曉根，等. 基于精英多策略的貨位分配優化方法[J]. 計算機科學，2018，45（1）：273-279.

[7] 楊瑋，傅衛平，王雯，等. 基于多色集合和粒子群算法的立體倉庫貨位分配優化[J]. 機械科學與技術，2012，31（4）：648

-651，655.

[8] 肖建，鄭力. 檢修備品庫的貨位優化模型[J]. 清華大學學報（自然科學版），2008（11）：1883-1886.

[9] 肖建，鄭立. 考慮需求相關性的多巷道倉庫貨位分配問題[J]. 計算機集成制造系統，2008，14（12）：2447-2451.

[10] 李英德. 波次分區揀貨時裝箱與貨位指派問題協同優化的模型與算法[J]. 系統工程理論與實踐，2013，33（5）：1269-1276.

[11] 李英德，魯建廈，潘國強. 穿越策略下考慮相關性的貨位優化方法[J]. 浙江大學學報（工學版），2012，46（8）：1424-1430.

[12]? Simon Brezovnik， Janez Gotlih， Jo？觩e Balic， et al. Optimization of an Automated Storage and Retrieval Systems by Swarm Intelligence[J]. Procedia Engineering， 2015，100：1309-1318.

[13]? Venkata Reddy Muppani （Muppant）， Gajendra Kumar Adil. Efficient formation of storage classes for warehouse storage location assignment： A simulated annealing approach[J]. Omega， 2007，36（4）：609-618.

[14]? QUINTANILLA S， ？魨NGELES P？魨， BALLEST？魨N F， et al. Heuristic Algorithms for a Storage Location Assignment Problem in a Chaotic Warehouse[J]. Engineering Optimization， 2014，47（10）：1405-1422.

[15] 張思建，方彥軍，賀瑤，等. 基于模擬退火算法的AVS/RS多批貨箱入庫貨位優化[J]. 武漢大學學報（工學版），2016，49（2）：315-320.

[16]? ELSAYED E A. Optimization of Warehouse Storage Capacity under a Dedicated Storage Policy[J]. International Journal of Production Research， 2005，43（9）：1785-1805.

[17]? Andr？觍s Kov？觍cs. Optimizing the storage assignment in a warehouse served by milkrun logistics[J]. International Journal of Production Economics， 2009，133（1）：312-318.

[18] 劉萬強，周亞勤，楊建國，等. 新型棋盤格密集倉庫的出入庫貨位分配優化[J]. 東華大學學報（自然科學（下轉第37頁）