基于關聯規則與聚類分析的儲位分配問題研究

朱鋮程，吳兆東，張建東

（1.中國人民解放軍92678部隊，天津 300042；2.陸軍軍事交通學院 學員五大隊研究生隊，天津 300161）

1 引言

為了提高倉庫的作業效率，研究人員從倉庫設施布局、儲位分配、訂單分批、執行單元自動化等多個方面入手，分析研究策略并進行優化升級。其中，儲位分配問題（Storage Location Assignment Problem,SLAP）主要服務于戰略運營層面，在布局、設備確定的條件下，儲位分配策略直接影響倉庫作業效率。

儲位分配問題是將貨架的每個儲位分配給對應的貨物，以達到某種效果最佳，例如方便揀選、方便盤點、出庫速度快等。隨著物流行業的發展，儲位分配問題的研究逐漸成為熱點。在上世紀60-80年代，研究人員提出了眾多儲位分配策略，例如隨機存儲策略[1]、定位存儲策略[2]、分類存儲策略[3]等。Heskett[4]在上世紀60年代率先提出了基于貨物周轉率COI系數的儲位分配策略，并證明了在物資完全不相關的前提下，該策略最接近最優解。Hausman[5]等針對自動倉儲系統，分別對隨機存儲策略、基于物資分類的存儲策略以及基于周轉率的存儲策略進行了對比分析，并且發現基于周轉率的存儲策略可以有效地減少作業中的行走距離。Rosenblatt[6]基于物資品類出庫量提出了分類定位存儲策略，并發現在品類增加時，可有效縮短物資出庫時的行走距離。

儲位分配問題被證明是NP難題，早期的研究考慮的條件都較為單一。近年來，隨著物流技術和管理作業模式以及計算機技術的發展，儲位分配越來越考慮多方面的因素，例如物資之間的關聯性、物資自身屬性、倉庫貨架特點等。Rosenwein[7]考慮不同物資之間的需求相關度，建立P-中值二進制優化模型對物料進行聚類，在此基礎上進行儲位分配。Jewkerse[8]在分區揀選策略基于人工揀選條件時，運用動態規劃算法對貨位分配與均衡作業量進行了研究，并通過實驗驗證該方法的有效性。Quintanilla[9]等應用啟發式算法，以最大化空間利用率為目標，研究了隨機存儲策略下半自動倉庫的儲位分配問題。Yang[10]等在基于COI系數的儲位分配理論基礎上，結合主成分分析，將待分配的物資進行分類分級，通過計算比較各級物資的COI 系數來確定儲位。Xie[11-12]等從商品的尺寸角度出發，建立了具有分組約束的雙層規劃數學模型，求解得到分組約束條件下的儲位分配。趙士博[13]在設計儲位優化模型時，應用聚類分析與關聯規則，挖掘物資之間的相關性，并將此與物資和倉庫其他信息結合起來考慮。

與以往儲位分配問題研究側重于物資本身的屬性不同，本文提出的模型側重于優化倉庫對訂單的反應敏捷程度，即縮短每一筆訂單的出庫時間，同時，針對以往研究中的數量關聯分析不足，本文在物資關聯分析的基礎上，考慮了數量上的關聯分析。重點針對傳統窄巷道立體庫的儲位分配問題，結合倉儲作業的實際情況和儲位分配原則，給出窄巷道立體庫儲位分配問題的規范化描述，建立了基于關聯規則分析和聚類分析的儲位分配模型，通過求解模型給出了儲位分配策略。

2 模型建立

2.1 儲位分配問題描述

儲位分配是根據倉庫的性質、物資的屬性等要素，確定各類物資的擺放位置，這是進行倉庫一系列作業的前提。就窄巷道立體庫而言，對儲位分配的研究是指通過合理的儲位分配，直接減少工作人員在進行存、取、盤點等作業的行走距離，從而提高作業效率。當前，基于物資COI的儲位分配策略[4]可以有效地提高倉庫整體的作業效率，而這種儲位分配策略僅僅針對一種物資而言，其缺陷在于對于某一個訂單而言，如果需要多種物資，這些物資可能相互關聯但是被放置在距離較遠的位置，會使倉庫處理該訂單的速度降低。

不管物資如何放置，從儲位的角度來看，儲位的價值是永遠不變的，若以到I/O 口的距離為衡量指標，對于窄巷道立體庫而言，其儲位的價值可近似看成是沿著半徑R的方向下降，即越靠近I/O位置的儲位價值越高，如圖1所示。通過借鑒現有的儲位分配策略，分析倉庫出庫訂單的特點，側重從物資之間的相關性、物資的需求量、物資的需求頻率，結合倉庫作業的基本原則，以最大化儲位價值為目標，建立儲位分配的數學模型。

圖1 儲位價值示意圖

儲位分配問題的分析流程如圖2所示。

圖2 儲位分配問題分析流程

2.2 儲位分配的基本原則

就儲位分配問題而言，核心是提高運行效率和可靠性，需要遵循以下幾點原則：

（1）周轉率原則。周轉率高意味著貨物出入庫的數量較多，通常需要將其安排在距離倉庫I/O口較近的區域。

（2）集中存放原則。對于同一品類的物資而言，要求儲位區域盡量集中。窄巷道立體庫的出入庫作業、盤點作業、維護保養作業等通常由人工完成，因此，為了便于員工執行作業，對于同一品類的物資，要求集中存放。

（3）區域均衡原則[14]。物資集中存放方便人工識別和作業，但是過程中可能會在某一時間段內，某一類物資或幾種物資因存取頻繁導致庫內交通擁堵。因此，在考慮集中存放的同時，需要考慮作業區域分布均衡。

（4）均勻承載原則。通常，貨物之間重量、規格區別較大，在進行貨位分配時，需要考慮貨架整體承載力和受力均勻，意味著儲位上的物資需要滿足上輕下重的要求。

（5）物資關聯原則。儲位分配要求能夠對出庫訂單作出迅速的反應，這就要求工作人員能夠在最短的時間內執行完作業。一個訂單中可能含有多種物資，若將相關程度較大的物資就近存儲能夠減少中間輾轉的距離。

2.3 儲位分配模型的基本假設

根據儲位分配的部分規則、倉庫運營情況與實際作業情況，本文模型基于的假設如下：

（1）不同種類物資的包裝規格尺寸標準統一；

（2）一個貨位只存放一種貨物；

（3）采用分類分區存儲策略，即同類物資在貨位分布上集中存放；

（4）物資到I/O的距離為這些集中存放物資的質心；

（5）叉車與其貨叉在窄巷道立體庫中勻速運動，忽略加速減速過程；

（6）忽略叉車轉向的影響；

（7）叉車一次能夠叉取的某種貨物的數量，稱為該類貨物的一個單位數量；

（8）倉庫在一定時間區間內的訂單具有規律性，且在該階段內與時間無關。

2.4 符號說明

符號說明見表1。

表1 符號說明

2.5 模型構建

基于上述儲位分配問題描述、原則與假設，優化的目標為最大化儲位價值，構建儲位分配問題的目標函數如下：

式（1）主要包含兩個部分，第一部分表示貨物x自身的儲位價值，第二部分表示關聯物資的儲位價值。其中，F(x)表示訂單中貨物x 出現頻率的特征函數，C(x)表示訂單中貨物x出現數量的特征函數，D(x)表示貨物x儲位價值的特征函數，具體表示為儲位到出口的距離，R(x)表示貨物x 的關聯物資的儲位價值。就訂單而言，最大化儲位的價值，即要求該訂單中涉及的物資的揀貨距離總和最短。

F(x)是對訂單中貨物x 出現的頻率進行統計，其計算公式如下：

C(x)是對訂單中貨物x 的數量統計特征，由于是一維數據，數據量龐大，數據中噪音的影響可以忽略，這里采用基礎的數學統計分析方法。

F(x)表示訂單含有貨物x 的概率，C(x)表示訂單中含有貨物x 的數量，則F(x)·C(x)可以理解為一個訂單中含有貨物x的期望值。

D(x)不僅與貨位的位置(X,Y,Z)有關，也與叉車的水平運行速度vhor和貨叉的升降速度vver有關，通過權值變換，其計算公式如下：

R(x)是指與貨物x關聯程度較高的物資的儲位價值。同樣，它涉及到關聯物資的數量期望值與關聯物資的儲位位置，因此表達式如下：

其中，CR(x)是反映關聯貨物之間數量關系的系數，其計算可以分為2 個步驟，首先是根據關聯規則得到與其關聯程度較高的貨物為關聯程度的置信度；第二步是將訂單數據簡化為ai={x=c1,rx=c2} ，將其看為二維的坐標數據，再通過二維數據的K-means 聚類分析貨物之間數量上的關聯特征。D(rx)的計算方式同式（4）。

3 模型求解

該模型求解涉及3 個步驟，第一個步驟是利用Apriori 關聯規則算法得到物資種類關聯關系，第二步是通過DBSCAN 密度聚類，得到不同物資之間的數量關系，第三步是通過回溯法，搜索解空間得到相對最優解。

3.1 Apriori關聯規則算法[15]

關聯規則分析是從大量數據中挖掘出事物之間的關聯關系，其基本的表達方式是A?B，意思是某一條數據包含A，則很有可能同時會包含B。在本文的研究中，關聯規則主要用于分析貨物之間的關聯程度。

在關聯規則分析中，支持度和置信度是用來量化關聯分析的基本指標，以關聯規則A?B為例，支持度是指待挖掘的數據集合中同時包含A 與B 的樣本個數占所有樣本數量的百分比；規則A?B的置信度是指同時包含A 與B 的樣本個數占只包含A 的樣本數量的百分比。計算公式如下：

關聯規則分析主要分為2個步驟，挖掘頻繁項集和挖掘關聯規則。這里基于Apriori算法來進行關聯規則的挖掘。

算法的計算步驟如下：

集合Lk中每一個項集含有k項，項集的個數＞0：計算每個項集是否滿足式（6），若滿足，保留頻繁項集，由新保留的頻繁項集構建k+1 項組成的集合Lk+1，并重復操作。

算法第二個步驟的偽代碼描述如下：

對于頻繁項集中每一個項：

生成關聯規則列表，從右部只包含1個項開始；

計算關聯規則的置信度是否滿足式（7）；

重復上述操作。

在該模型中，計算流程如圖3所示。

圖3 模型計算流程

3.2 DBSCAN密度聚類算法

密度聚類算法是基于樣本分布的緊密程度對樣本進行分類，相比較于K-means 聚類分析方法，密度聚類可以較好地處理數據噪聲的影響[16]。其核心思想就是通過發現密度較高的點，將相鄰的高密度的點連成片，從而生成各種簇。

在密度聚類中，將點主要分為3類：核心點、邊界點和噪音點。核心點是指在該點半徑為er范圍內的點的個數大于等于Ptmin的點。邊界點是指不滿足核心點的條件，但是在核心點的半徑范圍內的點。噪音點是不滿足上述兩者的點。

DBSCAN算法的偽代碼描述如下：

定植：定植前需進行土壤消毒處理。每畝施腐熟有機肥（豬糞、雞鴨糞肥）2500kg、復合肥25kg，翻耕入土，整平后筑畦寬60～65cm、溝寬30cm、溝深20～25cm。草莓花芽分化時為最佳定植期，幼苗帶土隨起隨栽，每畦種2行，株距17～18cm，每畝栽7000株。

將所有的點按要求劃分為核心點、邊界點、噪音點；

刪除噪聲點；

距離小于等于er的核心點用邊連接；

每組連通的核心點組成一個簇；

邊界點指派到關聯的核心點的簇中。

本文中應用聚類分析，主要是為了分析訂單關聯規則中涉及兩種貨物之間的數量關系特征，屬于二維密度聚類。其計算流程如圖4所示。

圖4 密度聚類計算流程

3.3 回溯法求解

在3.1 節和3.2 節算法分析的基礎上，可以確定優化目標式（1）中除貨物儲位位置以外的參數。這樣，模型就可以看做是一個TSP 問題，這類問題也是NP完全問題。有i種貨物，每種貨物的數量為wi，按照距離I/O 口的距離，根據不同類別的物資進行排列，分配儲位，使得儲位價值最高，儲位分配方案如圖5所示。

圖5中，將距離遠近近似看成扇形區域，圖中的儲位分配方案可以描述成，I/O的第一個扇形區域儲存物資A，下一個環形區域儲存B，剩余區域儲存C。通常求解該問題的方法有回溯法[17]、分支定界法[18]以及一系列啟發式算法。本文采用回溯法對該問題進行求解。回溯法是一種以深度優先的搜索算法，以3種貨物A、B、C為例，可以建立二叉樹圖，如圖6所示。

圖5 儲位分配方案示意圖

圖6 二叉樹圖

圖6展示了儲位分配解的空間樹，通過搜索空間樹，并利用剪枝函數判斷節點是否可行來尋找最優解。

4 案例分析

4.1 模型計算

以某電商倉庫的出庫訂單記錄為例，應用本文模型進行儲位分配方案的規劃。這里獲取了該電商倉庫2017年上半年的出庫記錄4 322 條。該倉庫共有儲位 500 個，10 列，5 層，每列有 10 個貨位，主要負責6大類物資的發貨任務，即飲品類、速食類、衛生用品類、玩具類、文具類以及寵物用品類，其訂單數據見表2。

表2 訂單詳情

第一步，通過Matlab 編程實現Aprorio 算法對這些訂單數據進行關聯規則分析，設定支持度為0.2，最小置信度為0.45，可以得到關聯規則30條左右，見表3。

表3 生成關聯規則示例

通過關聯規則分析可以確定式（5）中與貨物x關聯程度較高的貨物rx以及置信度矩陣，見表4。

表4 置信度矩陣

第二步，數量特征分析。通過數學統計的方法，分析每一類貨物出庫的數量特征。針對關聯貨物的數量關系，通過二維的K-mean 聚類算法進行分析。首先，每一類物資的數量特征如圖7所示。

這幾類貨物出庫量的數學統計特征見表5。

表5 物資數學統計特征

Counts 是指某類物資數量非零的訂單總數。通過加權平均，就可以得到每類物資的出庫平均值，該值可以認為是一個訂單中包含該類貨物的數量。

由關聯規則和訂單數據，可以提取兩種貨物同時出現在一個訂單上的數量關系。將兩種貨物視為兩個維度，貨物的數量視為在該維度上的取值，通過MATLAB 編寫的DBSCAN 密度聚類算法程序，以Drink 貨物為例，得到Drink 與其他貨物的數量聚類圖像，如圖8所示。

以聚類中占數量最多的一類的質心作為關聯貨物之間的數量關系，可以得到關聯貨物的數量關系系數矩陣，見表6。

第三步，利用回溯法搜索最優解。經過前兩步的計算，除位置信息以外的其他參數均已確定，剩下的就是確認各類物資在儲位分配上的位置關系，即對靠近I/O的程度做一個排序。

該電商倉庫遵循集中存放原則，同時儲位較為充足，采用了劃區域分類存儲物資策略。對D(x)的計算，可以簡化成離散變量表示。由于上述只有6種物資，這里通過{1,2,3,4,5,6} 等差數列形容各區域的儲位價值。

通過Matlab 編寫回溯算法，以式（1）為優化目標，計算求解得到最終的儲位分配距離I/O由近及遠分別是{Drink、Fast Food、Hygience、Stationery、Toy、Pet}。

圖8 物資-頻率關聯圖

表6 數量關系系數矩陣

4.2 策略對比

若單純基于物料COI進行儲位分配，則儲位分配中，距離I/O 口的物資順序應是{Drink、Hygience、 Fast Food、Stationery、Toy、 Pet}。 取2017年下半年7月份500 個訂單數據測試，以{1,2,3,4,5,6} 表示距離I/O 相對距離的絕對值，對比4.1 節最后的方案，結果見圖9與表7。

圖9 本文儲位分配策略與基于物料COI的儲位分配策略對比變化示意圖

縱軸表示增加的距離值，“+”號表示因策略變更增加貨物出庫距離的訂單，數量為152個，“o”表示距離減少的訂單，數量為213 個，總共減少的距離為489。可以發現，該策略從總體上優化了出庫的效率。

5 研究結論與展望

本文主要研究了傳統窄巷道立體庫的儲位分配問題。首先，根據窄巷道立體庫的實際背景，給出了本文所研究的儲位分配問題的規范描述。接著，從倉庫出庫訂單角度出發，以縮短訂單貨物的出庫距離為優化目標，結合儲位分配的一些原則，建立基于關聯規則與聚類分析的儲位分配模型。在模型中，一些基本參數通過統計數學方法得到，與不同物資關聯程度相關的參數通過Apriori關聯規則算法求解得到，與貨物之間數量關系相關的參數通過聚類分析得到。應用回溯法求解整個模型。

將模型應用于某一電商倉庫，將電商倉庫提供的數據集劃分為訓練集與測試集，通過訓練集得到了新的儲位分配策略，并應用測試集對比基于COI的分配策略。計算過程表明，通過關聯分析發現，在訂單中存在大量的物資關聯信息，這些關聯信息反映了同一個訂單包含不同類的物資在統計上的關系。同時，通過對這些關聯物資進行聚類分析，可以挖掘出這些不同種類的物資在同一訂單中的數量關系。研究求解模型得到相應的儲位分配策略發現，在局部上，模型對不同的訂單有的產生了正面的優化效果，縮短了出庫距離，有的產生了負面效應。但是，從優化的訂單數量與優化的幅度來看，優化效果要高于產生的負面效應，因此可以說基于本文模型提出的策略在整體上優化了訂單出庫距離。

本文的研究是建立在場景條件相對理想的條件下，例如物資包裝規格尺寸統一、倉庫布局單一、叉車速度運行穩定、訂單數據具有代表性等，與實際倉庫的作業環境有所出入，這些也為下一步的研究提供了思路。下一步將重點研究以下幾個方面：（1）物資包裝規格尺寸不統一的影響；（2）不同時間區段訂單數據的變化趨勢對儲位策略的影響；（3）不同倉庫布局的影響。