曾敏剛 張俊杰 陳偉賢

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

關(guān)鍵詞：貨位優(yōu)化;關(guān)聯(lián)規(guī)則;Apriori算法;智能倉庫

中圖分類號：F253? ? 文獻標(biāo)識碼：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? 引? 言

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

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

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

1? ?問題描述

1.1? 問題提出與基本假設(shè)

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

根據(jù)如上描述，將本文進行貨位優(yōu)化所作假設(shè)總結(jié)如下：

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

（2）每種貨物的周轉(zhuǎn)率和體積已知，即COI指數(shù)已知;

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

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

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

1.2? 模型建立

1.2.1? 符號說明

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

1.2.2? 建立模型

（1）AGV搬運貨架次數(shù)最少

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

①同類貨物內(nèi)部的分散度

定義各類貨品的中心位置為該類貨品內(nèi)所有貨物向量坐標(biāo)的均值：

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

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

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

則所有貨物的類內(nèi)分散度為：

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

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

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

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

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

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

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

故目標(biāo)函數(shù)為：

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

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

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

該目標(biāo)函數(shù)為：

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

約束條件為：

①貨位界限約束

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

②容量約束

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

2? 模型求解

2.1? 算法思路

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

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

貨品關(guān)聯(lián)性分析旨在通過分析歷史已處理的訂單數(shù)據(jù)，根據(jù)貨品間的關(guān)聯(lián)性結(jié)果確定儲位布局，貨架布局方案則通過建模求解。

2.2? 貨位布局求解

2.2.1? 關(guān)聯(lián)規(guī)則簡介

關(guān)聯(lián)規(guī)則（Association Rule）是在數(shù)據(jù)庫和數(shù)據(jù)挖掘領(lǐng)域中廣泛研究的一種重要模型[32]，可數(shù)學(xué)化描述為：設(shè)I

=i，i，i，…是一個項目集合，D是事務(wù)型數(shù)據(jù)庫，其中的每個事務(wù)T都由一個唯一的標(biāo)識符TID進行區(qū)分，即D

=T，T，T，…，每個事務(wù)Ti=1，2，3，…對應(yīng)I上的一個子集。事物數(shù)據(jù)庫D如表2所示。

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

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

2.2.2? Apriori算法簡介

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

Apriori算法挖掘關(guān)聯(lián)規(guī)則主要可分為4個步驟，如圖2所示。

2.2.3? 貨位布局方案

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

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

3? ?算例分析

3.1? 數(shù)據(jù)收集與關(guān)聯(lián)性挖掘

假設(shè)倉庫當(dāng)前共存儲50種貨物，已經(jīng)出庫了100張訂單，訂單數(shù)據(jù)如表3所示：

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

置信度越高表示兩者之間的關(guān)聯(lián)性越高，儲位布局時兩者的位置應(yīng)盡可能的緊鄰。

3.2? 貨位布局方案

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

根據(jù)這100張歷史訂單分析得到的關(guān)聯(lián)性結(jié)果，按照儲位布局規(guī)則依次考慮貨物間的位置，得到儲位初步布局圖如圖4所示。

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

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

4? 結(jié)? 論

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

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

參考文獻：

[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] 鄂曉征，祖巧紅，曹萌萌. 基于遺傳算法的汽車零件自動化倉儲貨位優(yōu)化[J]. 系統(tǒng)仿真學(xué)報，2013，25（3）：430-435，444.

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

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

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

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

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

-651，655.

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

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

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

[11] 李英德，魯建廈，潘國強. 穿越策略下考慮相關(guān)性的貨位優(yōu)化方法[J]. 浙江大學(xué)學(xué)報（工學(xué)版），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多批貨箱入庫貨位優(yōu)化[J]. 武漢大學(xué)學(xué)報（工學(xué)版），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] 劉萬強，周亞勤，楊建國，等. 新型棋盤格密集倉庫的出入庫貨位分配優(yōu)化[J]. 東華大學(xué)學(xué)報（自然科學(xué)（下轉(zhuǎn)第37頁）