多出/入口倉(cāng)庫(kù)的貨位優(yōu)化研究

劉旺盛, 馬國(guó)旺, 江雨瑤, 曾艷

(集美大學(xué)航海學(xué)院， 廈門(mén) 361021)

隨著電子商務(wù)產(chǎn)業(yè)的興起與企業(yè)發(fā)展的需要，現(xiàn)代倉(cāng)庫(kù)由傳統(tǒng)的少品種小批次的揀選向大批次多品種揀選發(fā)展，這種變化使企業(yè)對(duì)貨物周轉(zhuǎn)的需求愈來(lái)愈高，因此，傳統(tǒng)少出/入口倉(cāng)庫(kù)布局很難滿(mǎn)足企業(yè)實(shí)際生產(chǎn)活動(dòng)的需要，而多出/入口倉(cāng)庫(kù)能夠有效地提高作業(yè)揀選速度、減少單一出/入口工作量等優(yōu)點(diǎn)，成為更多企業(yè)的選擇。

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

貨位優(yōu)化問(wèn)題被證明是 NP(nondeterministic polynomially)難題，早期相關(guān)問(wèn)題研究考慮條件大多較為單一。近年來(lái)，隨著大數(shù)據(jù)技術(shù)的提出以及數(shù)據(jù)挖掘的應(yīng)用[1-2]，貨位優(yōu)化問(wèn)題的研究從基于貨品頻率、貨品類(lèi)別與貨位關(guān)系的研究轉(zhuǎn)向從歷史訂單中發(fā)掘貨品之間關(guān)聯(lián)度、貨品屬性與倉(cāng)庫(kù)實(shí)際相結(jié)合的研究。Lee[3]最早于1992年提出貨品之間的關(guān)聯(lián)性的概念，他認(rèn)為貨品關(guān)聯(lián)度可表示為貨品同時(shí)出現(xiàn)在一張訂單上的頻率。而后,許多學(xué)者在考慮關(guān)聯(lián)度的基礎(chǔ)上,不斷地拓展與延伸，采用不同方法對(duì)貨位優(yōu)化問(wèn)題開(kāi)展研究。

部分學(xué)者嘗試將貨品相關(guān)性與其他因素考慮起來(lái)構(gòu)建貨品優(yōu)化模型，如Qiu 等[4]基于貨品關(guān)聯(lián)度，根據(jù)實(shí)際優(yōu)化情況設(shè)計(jì)了一種基于耗時(shí)規(guī)則的貨位編號(hào)規(guī)則。Ning等[5]同樣在考慮貨品相關(guān)性的基礎(chǔ)上，將貨架穩(wěn)定性、交貨時(shí)間等因素納入模型構(gòu)建。Yang 等[6]針對(duì)醫(yī)藥物流中心布局不合理導(dǎo)致效率低下的問(wèn)題，提出了品類(lèi)間和品類(lèi)內(nèi)兩階段優(yōu)化方法。Wu 等[7]結(jié)合預(yù)測(cè)訂單請(qǐng)求，采用貨品相關(guān)度構(gòu)建了一個(gè)多目標(biāo)優(yōu)化模型來(lái)解決倉(cāng)庫(kù)空間分配問(wèn)題。Yang等[8]考慮了貨架穩(wěn)定性、貨品相關(guān)性構(gòu)建模型。除此之外，在模型求解方面， Wang等[9]針對(duì)貨架穩(wěn)定性、貨品相關(guān)性等因素構(gòu)建模型，并采用改進(jìn)遺傳算法進(jìn)行求解。周亞云等[10]采用譜聚類(lèi)算法對(duì)貨品關(guān)聯(lián)規(guī)則聚類(lèi)問(wèn)題進(jìn)行求解。

不同倉(cāng)庫(kù)布局適合的貨位優(yōu)化方法也不一樣。從以往研究來(lái)看，大多數(shù)學(xué)者均以單一出入口倉(cāng)庫(kù)為研究對(duì)象，而目前倉(cāng)庫(kù)的流動(dòng)性高，大多數(shù)倉(cāng)庫(kù)為了方便貨物的進(jìn)出，設(shè)計(jì)為多出入口、一邊進(jìn)一邊出模式，現(xiàn)有的貨位優(yōu)化方法顯然不適用。因此，現(xiàn)針對(duì)這種倉(cāng)庫(kù)布局提出了以相關(guān)性進(jìn)行聚類(lèi)的貨位優(yōu)化策略。該策略基于峰值聚類(lèi)算法以貨品關(guān)聯(lián)度最大為優(yōu)化目標(biāo)對(duì)貨品進(jìn)行關(guān)聯(lián)聚類(lèi)，并根據(jù)多出/入口倉(cāng)庫(kù)的實(shí)際情況對(duì)貨位布局進(jìn)行優(yōu)化與調(diào)整。最后，通過(guò)實(shí)例數(shù)據(jù)與企業(yè)現(xiàn)行隨機(jī)存儲(chǔ)策略進(jìn)行對(duì)比，驗(yàn)證本文方法的有效性與穩(wěn)健性。

1 多出/入口倉(cāng)庫(kù)簡(jiǎn)介

多出/入口倉(cāng)庫(kù)布局如圖1所示，有X排貨架，每個(gè)貨架上有多個(gè)儲(chǔ)位可供存儲(chǔ)。每個(gè)入口對(duì)應(yīng)一個(gè)出口，兩者是一一對(duì)應(yīng)的，稱(chēng)為一個(gè)組對(duì)，一共有多少這樣的組對(duì)，稱(chēng)為出/入口組對(duì)數(shù)。每當(dāng)訂單下達(dá)時(shí)，揀選員需要按照訂單所列貨品進(jìn)行判斷，根據(jù)訂單上首位貨品所在巷道對(duì)應(yīng)的入口進(jìn)入，然后按照訂單貨品順序依次揀選貨品，當(dāng)訂單中所有貨品均揀選完畢后，從巷道所屬最近出口離開(kāi)。

圖1 多出/入口倉(cāng)庫(kù)平面布局例圖Fig.1 Multi-exit/entrance warehouse layout

2 貨品優(yōu)化模型及求解

2.1 模型假設(shè)

為了結(jié)合實(shí)際，突出研究主要問(wèn)題，現(xiàn)有如下假設(shè)。

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

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

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

(4)貨位數(shù)量可以滿(mǎn)足所有待優(yōu)化貨品存儲(chǔ)需求。

2.2 貨位優(yōu)化模型構(gòu)建

2.2.1 相似度

本文研究中貨品之間關(guān)聯(lián)性是根據(jù)不同貨品是否同時(shí)出現(xiàn)在同一訂單中[11]，出現(xiàn)在相同訂單內(nèi)次數(shù)越多，其貨品之間關(guān)聯(lián)程度越高。兩兩貨品相關(guān)程度計(jì)算公式為

(1)

式(1)中：i、j為貨品編號(hào)，i、j∈{1,2,…,m}；Cij為貨品i、j之間的關(guān)聯(lián)性指數(shù)；Pi為包含貨品i的訂單數(shù)目；Pj為包含貨品j的訂單數(shù)目；Pij為同時(shí)包含貨品i、j的訂單數(shù)目。

當(dāng)Cij=0，表示貨品i、j不存在關(guān)聯(lián)性，即訂單集中沒(méi)有訂單同時(shí)包含貨品i、j；當(dāng)Cij=1，表示兩者存在完全關(guān)聯(lián)關(guān)系，即訂單集中貨品i、j總是能夠同時(shí)被分配到同一個(gè)訂單中。同時(shí)Cij=Cji總存在對(duì)稱(chēng)性。且Cij取值范圍為[0,1],其值越接近于1，貨品i、j被分配到同一個(gè)貨品聚合類(lèi)可能性越大。

2.2.2 貨品聚類(lèi)優(yōu)化模型

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

(2)

(3)

(4)

(5)

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

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

2.3 模型求解

聚類(lèi)分析是通過(guò)將數(shù)據(jù)對(duì)象集合劃分成為不同聚合簇的過(guò)程，每個(gè)聚合簇內(nèi)數(shù)據(jù)間彼此具有相關(guān)性[12]。本文將根據(jù)目標(biāo)函數(shù)，設(shè)計(jì)有效地智能聚類(lèi)算法進(jìn)行問(wèn)題求解。首先，從客戶(hù)歷史訂單數(shù)據(jù)入手，挖掘貨品之間相關(guān)度并求出N維貨品相關(guān)度矩陣，然后，基于貨品相關(guān)度矩陣?yán)枚嗑S標(biāo)度分析算法對(duì)矩陣進(jìn)行數(shù)據(jù)處理。以出/入口數(shù)量作為貨品聚類(lèi)簇?cái)?shù)目，并采用密度峰值聚類(lèi)算法進(jìn)行聚類(lèi)并輸出聚類(lèi)結(jié)果集，最后基于聚類(lèi)后結(jié)果集求解模型并進(jìn)行貨位分配。

2.3.1 多維標(biāo)度分析算法

多維標(biāo)度分析算法是以數(shù)據(jù)點(diǎn)之間距離為標(biāo)準(zhǔn)，將高緯度坐標(biāo)投影到低緯度坐標(biāo)的一種數(shù)據(jù)處理方法[13]。它與其他數(shù)據(jù)處理算法最大不同在于，在處理過(guò)程中，MDS算法要求數(shù)據(jù)點(diǎn)之間相對(duì)距離(在本文中為貨品之間相關(guān)度)變化最小。本文中要處理數(shù)據(jù)是貨品相關(guān)度矩陣，它與多維空間中距離矩陣在矩陣形式上表現(xiàn)一致，因此，以貨品之間的相關(guān)度代替?zhèn)鹘y(tǒng)數(shù)據(jù)點(diǎn)之間的距離,采用MDS算法對(duì)相關(guān)度矩陣進(jìn)行數(shù)據(jù)處理。該算法基本流程如下。

輸出：低維矩陣Z。

(1)對(duì)輸入訂單數(shù)據(jù)集預(yù)處理得到兩兩貨品同時(shí)訂購(gòu)矩陣P并生成相關(guān)度矩陣W,W∈Rm×m。

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

(3)令B=ZTZ，B∈Rm×m,其中B為降維后樣本內(nèi)積矩陣，求解實(shí)對(duì)稱(chēng)矩陣B,B=UΛUT。

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

2.3.2 基于峰值聚類(lèi)下貨品關(guān)聯(lián)挖掘算法

在實(shí)際中，多出/入口倉(cāng)庫(kù)往往具有規(guī)模大、存儲(chǔ)貨品數(shù)量多、種類(lèi)豐富等特點(diǎn)。所以在進(jìn)行數(shù)據(jù)處理和分析時(shí)需要面對(duì)大量數(shù)據(jù)，而傳統(tǒng)聚類(lèi)算法在求解時(shí)往往需要多次循環(huán)往復(fù)的迭代。本文選取DPC算法進(jìn)行求解能有效地解決上述問(wèn)題，同時(shí)該算法具有直觀發(fā)現(xiàn)聚類(lèi)中心、處理不同形狀數(shù)據(jù)集等優(yōu)點(diǎn)[14]。

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

數(shù)據(jù)對(duì)象xi的局部相關(guān)度ρi計(jì)算公式為

(6)

lc=dis(MP)

(7)

式中：lij為MDS處理后貨品之間相關(guān)度大?。籰c為截?cái)嘞嚓P(guān)度；dis為貨品集中所有貨品間相關(guān)度按照升序排列后相關(guān)度序列；M為貨品間相關(guān)度值的總數(shù)目；P為百分比，通常取2%[16]。

相對(duì)最小相關(guān)度δi，定義為

(8)

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

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

γi=ρiδi

(9)

基于DPC算法總流程如下。

輸入：低維矩陣Z。

輸出：貨品聚合類(lèi)結(jié)果集A={a1,a2,…,ag}。

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

(2)確定截?cái)嘞嚓P(guān)度lc。

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

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

(5)對(duì)剩余貨品進(jìn)行聚類(lèi)操作。

(6)返回最終聚類(lèi)結(jié)果集A。

2.3.3 存儲(chǔ)區(qū)域優(yōu)化

在DPC算法聚類(lèi)結(jié)束后，根據(jù)生成的聚類(lèi)結(jié)果返回貨品聚合類(lèi)內(nèi)貨品相關(guān)性坐標(biāo)，然后根據(jù)類(lèi)內(nèi)相關(guān)性坐標(biāo)計(jì)算貨品聚合類(lèi)相關(guān)性坐標(biāo)均值Mg,最后計(jì)算不同聚合類(lèi)相關(guān)性坐標(biāo)均值距離dg，并根據(jù)距離的大小決定存儲(chǔ)區(qū)域的分配位置。具體流程如圖2所示。

圖2 存儲(chǔ)區(qū)域優(yōu)化流程圖Fig.2 Flow chart of storage area optimization

2.3.4 貨位優(yōu)化模型求解

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

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

3 算例求解及結(jié)果分析

3.1 算例說(shuō)明

通過(guò)實(shí)地調(diào)研方式，獲得H企業(yè)A倉(cāng)庫(kù)2018年4—5月訂單數(shù)據(jù)集，其中包括訂單編號(hào)、貨品種類(lèi)、貨品位置等數(shù)據(jù)。由于企業(yè)數(shù)據(jù)需要保密處理，所以訂單編號(hào)及貨品種類(lèi)均采用數(shù)字替代。A倉(cāng)庫(kù)中共有8排貨架，對(duì)原始訂單數(shù)據(jù)集進(jìn)行處理清洗后保留2 076張有效訂單，包含842種貨品。訂單數(shù)據(jù)如表 1所示。

表1 訂單數(shù)據(jù)表Table 1 Table of order data

3.2 貨品兩兩相關(guān)性分析

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

表2 貨品兩兩相關(guān)性表Table 2 Table of goods correlation

3.3 數(shù)據(jù)處理

從貨品相關(guān)性表得出貨品相關(guān)性矩陣為n維矩陣，聚類(lèi)算法無(wú)法直接進(jìn)行處理。采用MDS算法對(duì)貨品相關(guān)性矩陣進(jìn)行處理以獲得二維相關(guān)性坐標(biāo)。處理后數(shù)據(jù)如表3所示。

表3 數(shù)據(jù)處理表Table 3 Table of data processing

3.4 數(shù)據(jù)聚類(lèi)處理

通過(guò)MDS算法對(duì)貨品相關(guān)性進(jìn)行數(shù)據(jù)處理后，再利用峰值聚類(lèi)算法進(jìn)行聚類(lèi)。本文聚類(lèi)簇選擇根據(jù)出/入口數(shù)量，H公司A倉(cāng)庫(kù)中共有4個(gè)出/入口8排貨架，因此聚類(lèi)簇選擇應(yīng)為4。聚類(lèi)結(jié)果如表4所示。

表4 聚類(lèi)結(jié)果表Table 4 Table of clustering results

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

3.5.1 貨位區(qū)域優(yōu)化

H公司原有貨位分配策略為隨機(jī)策略，想要貨品盡可能均勻分配到倉(cāng)庫(kù)，達(dá)到作業(yè)均衡化目的，但在實(shí)際應(yīng)用中與理想效果相差甚遠(yuǎn)。在原始倉(cāng)庫(kù)布局的基礎(chǔ)上，不改變貨架位置。通過(guò)DPC算法依據(jù)貨品相關(guān)性將貨品劃分為4個(gè)聚合類(lèi)。使高相關(guān)性貨品聚合類(lèi)在存儲(chǔ)區(qū)域位置上盡可能的接近。優(yōu)化貨品存儲(chǔ)區(qū)域示例圖，如圖4所示。

圖4 優(yōu)化貨品存儲(chǔ)區(qū)域圖Fig.4 Optimized goods storage area map

3.5.2 存儲(chǔ)策略比較

根據(jù)貨品存儲(chǔ)區(qū)域分配結(jié)果，使用Python2.7編程軟件基于實(shí)例數(shù)據(jù)分別計(jì)算本文存儲(chǔ)優(yōu)化與隨機(jī)存儲(chǔ)這兩種儲(chǔ)位優(yōu)化策略下跨區(qū)域平均訂單揀選距離，結(jié)果如表5所示。

表5 基于不同優(yōu)化策略跨區(qū)域平均揀選距離比較表Table 5 Table of average pick distance comparison

跨區(qū)域平均揀選距離是指平均一個(gè)揀選員揀選不同存儲(chǔ)區(qū)域需行走路徑，通常用總揀選距離除以訂單數(shù)量。

3.6 靈敏度分析

為了避免實(shí)驗(yàn)結(jié)果的偶然性，本文模擬生成幾個(gè)其他規(guī)模的算例，計(jì)算并比較本文存儲(chǔ)優(yōu)化策略與隨機(jī)存儲(chǔ)優(yōu)化策略結(jié)果，優(yōu)化存儲(chǔ)策略表如表6所示。

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

表6 優(yōu)化策略比較表Table 6 Comparison of optimization strategies

由圖5可見(jiàn)貨品種類(lèi)數(shù)量與跨區(qū)域平均揀選距離存在著正相關(guān)性。但隨著貨品種類(lèi)數(shù)量增加，其跨區(qū)域平均揀選距離增長(zhǎng)趨于平緩。這與實(shí)際情況相符，當(dāng)貨品種類(lèi)數(shù)量增加時(shí)，將高相關(guān)性的貨品聚成一類(lèi)放在同一存儲(chǔ)區(qū)域進(jìn)行存取，能有效減少揀選距離，提高揀選員工作效率。

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

4 結(jié)論

基于物流倉(cāng)庫(kù)發(fā)展趨勢(shì)出發(fā)，針對(duì)多出/入口倉(cāng)庫(kù)布局下對(duì)貨位優(yōu)化問(wèn)題進(jìn)行了研究，分別設(shè)計(jì)了多維標(biāo)度分析算法與峰值聚類(lèi)算法進(jìn)行聚類(lèi)分析，然后進(jìn)行組內(nèi)和組間貨位分配。本文有如下創(chuàng)新之處。

(1)設(shè)計(jì)了多維標(biāo)度分析算法可以直接解決企業(yè)數(shù)據(jù)與聚類(lèi)模型需要數(shù)據(jù)之間不兼容問(wèn)題。

(2)采用密度峰值聚類(lèi)算法，將高相關(guān)度貨品存放在同一存儲(chǔ)區(qū)域，減少了揀選員經(jīng)歷巷道數(shù)量，提升了倉(cāng)庫(kù)作業(yè)效率。

(3)根據(jù)多出/入口倉(cāng)庫(kù)布局情況來(lái)確定貨品聚類(lèi)簇?cái)?shù)，并根據(jù)實(shí)際情況進(jìn)行調(diào)整，利用貨品相關(guān)性來(lái)達(dá)到訂單揀選距離最小目的。

通過(guò)實(shí)際案例驗(yàn)證，本文策略比隨機(jī)策略平均優(yōu)化24.56%。本文設(shè)計(jì)模型與策略為解決多出/入口倉(cāng)庫(kù)貨位優(yōu)化問(wèn)題提供了有效地決策方法，顯著提高了倉(cāng)庫(kù)運(yùn)作效率，降低了企業(yè)的倉(cāng)儲(chǔ)運(yùn)作成本。