朱鋮程，吳兆東，張建東

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

1 引言

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

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

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

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

2 模型建立

2.1 儲位分配問題描述

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

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

圖1 儲位價值示意圖

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

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

2.2 儲位分配的基本原則

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

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

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

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

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

（5）物資關聯(lián)原則。儲位分配要求能夠?qū)Τ鰩煊唵巫鞒鲅杆俚姆磻?，這就要求工作人員能夠在最短的時間內(nèi)執(zhí)行完作業(yè)。一個訂單中可能含有多種物資，若將相關程度較大的物資就近存儲能夠減少中間輾轉的距離。

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

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

（1）不同種類物資的包裝規(guī)格尺寸標準統(tǒng)一；

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

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

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

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

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

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

（8）倉庫在一定時間區(qū)間內(nèi)的訂單具有規(guī)律性，且在該階段內(nèi)與時間無關。

2.4 符號說明

符號說明見表1。

表1 符號說明

2.5 模型構建

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

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

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

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

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

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

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

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

3 模型求解

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

3.1 Apriori關聯(lián)規(guī)則算法[15]

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

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

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

算法的計算步驟如下：

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

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

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

生成關聯(lián)規(guī)則列表，從右部只包含1個項開始；

計算關聯(lián)規(guī)則的置信度是否滿足式（7）；

重復上述操作。

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

圖3 模型計算流程

3.2 DBSCAN密度聚類算法

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

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

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

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

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

刪除噪聲點；

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

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

邊界點指派到關聯(lián)的核心點的簇中。

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

圖4 密度聚類計算流程

3.3 回溯法求解

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

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

圖5 儲位分配方案示意圖

圖6 二叉樹圖

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

4 案例分析

4.1 模型計算

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

表2 訂單詳情

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

表3 生成關聯(lián)規(guī)則示例

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

表4 置信度矩陣

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

這幾類貨物出庫量的數(shù)學統(tǒng)計特征見表5。

表5 物資數(shù)學統(tǒng)計特征

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

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

以聚類中占數(shù)量最多的一類的質(zhì)心作為關聯(lián)貨物之間的數(shù)量關系，可以得到關聯(lián)貨物的數(shù)量關系系數(shù)矩陣，見表6。

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

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

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

圖8 物資-頻率關聯(lián)圖

表6 數(shù)量關系系數(shù)矩陣

4.2 策略對比

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

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

縱軸表示增加的距離值，“+”號表示因策略變更增加貨物出庫距離的訂單，數(shù)量為152個，“o”表示距離減少的訂單，數(shù)量為213 個，總共減少的距離為489?？梢园l(fā)現(xiàn)，該策略從總體上優(yōu)化了出庫的效率。

5 研究結論與展望

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

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

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