隨機存儲機制下基于引力模型的訂單波次劃分方法的研究

□ 盧燁彬 劉少軒

(上海交通大學(xué) 安泰經(jīng)濟與管理學(xué)院,上海 200030)

隨機存儲機制下基于引力模型的訂單波次劃分方法的研究

□ 盧燁彬 劉少軒

(上海交通大學(xué) 安泰經(jīng)濟與管理學(xué)院,上海 200030)

研究倉儲中心隨機存儲機制下訂單波次劃分問題時,創(chuàng)新性地將引力模型應(yīng)用到波次劃分模型中,以波次內(nèi)不同儲位商品之間的引力大小衡量訂單之間的相似度,從而進(jìn)行訂單的波次劃分,然后運用遺傳算法對該模型進(jìn)行求解。并從實證的角度出發(fā),將求解得出的方案與傳統(tǒng)的基于訂單聚類劃分的方案進(jìn)行對比,發(fā)現(xiàn)在都采用S型揀選策略的情形下,所提出的基于引力模型構(gòu)建的波次劃分方案的揀貨路徑更短,揀貨效率更高。

隨機存儲;波次劃分;訂單相似度;引力模型;遺傳算法

一、引 言

在2015年的”雙十一”活動中,天貓一天的交易額達(dá)到912.17億元,相比于2014年呈現(xiàn)爆發(fā)式增長,增速達(dá)59.7%,并且京東、蘇寧等電商也實現(xiàn)巨量成交額。由此看出,網(wǎng)絡(luò)購物在未來必定發(fā)展成為一種主流的購物形式,市場巨大。而在整個物流配送過程中,揀貨是比較重要的一步,在整個訂單配送過程中,訂單分揀的勞動量占總勞動量的60%[1]。由此可見,提高倉儲中心的揀貨效率對整個供應(yīng)鏈效率的提升至關(guān)重要。而各類電商在貨物存儲方式上各不同,1號店、京東等大部分電商采取的是分類存儲方式,即按照A～Z拼音分類或者銷量分類依次存儲貨物。而像美國亞馬遜這樣的大電商,它的許多倉儲方法在世界均處于領(lǐng)先地位,其采取的則是隨機存儲方式,相比于分類存儲,其在庫存空間利用率上具有絕對的優(yōu)勢。隨機存儲是指對于每個商品而言,沒有固定的存儲位置,商品可以放到任何庫存中空的貨位,即“見縫插針”式存放。隨機存儲相比于分類存儲,其空間節(jié)省約為30%。

本文以倉儲中心的隨機存儲運作方式為背景,研究在隨機存儲機制下訂單波次劃分的問題。波次劃分時需要考慮訂單相似度,而同一個商品的不同位置的選擇,直接關(guān)系到這個訂單與波次內(nèi)其他訂單之間的相似度。在已有的學(xué)者研究文章中,一般通過訂單之間的關(guān)聯(lián)來構(gòu)建訂單之間的相似度,比如根據(jù)訂單含有相同商品的個數(shù)作為劃分依據(jù),相同商品個數(shù)越多,應(yīng)劃分到同一個波次中[2]。然而這種劃分方法并不適合于隨機存儲,因為隨機存儲機制下,即便是相同的商品,也有可能被存儲在相距較遠(yuǎn)的儲位上。因此,為了解決隨機存儲下波次劃分問題,只能從存放商品的本身地理位置特征考慮相似度。

本文創(chuàng)新性地將引力模型應(yīng)用到波次劃分模型中,以波次內(nèi)不同儲位的商品之間的引力大小來衡量訂單之間的相似度,從而進(jìn)行訂單的波次劃分。

引力模型是根據(jù)牛頓的萬有引力定律延伸而來,近幾年不斷地被運用到不同的領(lǐng)域,如城市群理論[3,4]。該模型能夠很好的衡量不同位置對象之間的關(guān)聯(lián)程度,而國內(nèi)外學(xué)者曾經(jīng)將該模型運用到衡量電子商務(wù)配送站點之間的關(guān)聯(lián)強度[5]。

本文將引力模型引入,定義兩個商品的引力大小為T=φ/r2(φ為引力常數(shù),r為兩商品之間的距離)。這樣,就可以只從存放商品的本身地理位置特征構(gòu)建訂單相似度。通過對波次訂單引力模型的構(gòu)建,最大化該批訂單的相似度。最終,運用遺傳算法對該模型進(jìn)行求解,并將求解得出的方案與傳統(tǒng)的基于訂單聚類劃分的方案進(jìn)行對比,發(fā)現(xiàn)在兩種方案都采取S型揀選策略的情形下,基于引力模型構(gòu)建的波次劃分方案比傳統(tǒng)的基于訂單聚類劃分方案揀貨路徑更短,揀貨效率更高。

一般S型揀選策略指的是:對于每一個含有待揀選商品的貨架通道,從通道一端進(jìn)入另外一端出[6]。本文選取S型揀選作為揀選策略的原因,在于亞馬遜當(dāng)前在運用隨機存儲機制下,其實際倉儲管理中運用的就是這種S型揀貨策略,這樣所進(jìn)行的研究就與企業(yè)實際情況相符合。

二、文獻(xiàn)綜述

(一)倉儲貨位存儲方法的研究

對于倉儲貨位的存儲方法,國內(nèi)外有許多這方面的研究。Haus man等[7]在1976年就研究得出,在倉儲存儲時,不同的存儲方式——隨機存儲、固定存儲、分類存儲的選擇,直接決定了揀貨員揀貨時的行走距離,從而影響了揀選效率,并研究了ABC周轉(zhuǎn)率儲存方式與其他存儲方式,比如隨機存儲、固定存儲、分類存儲的組合的模式,最終發(fā)現(xiàn)了固定存儲情況下的揀貨路徑要短于隨機存儲情況下的揀貨路徑。Br ynzer和Johansson[8]依據(jù)貨物結(jié)構(gòu)將貨物分成不同類別,同一類別放在一起可以減少揀貨時需要行走的路徑。并且,提出了揀貨效率不僅與揀貨路徑有關(guān),也與揀貨錯誤率有關(guān),劃分時需要兼顧兩者。Petersen等[9]在2002年對比了分類存儲和隨機存儲器揀選效率,分析了不同的存儲策略和訂單中貨物數(shù)量對效率的影響,最終得出分類存儲相比于隨機存儲揀貨路徑更短。董溪哲等[10]在研究中提出,以貨物周轉(zhuǎn)率為基礎(chǔ),以貨架空間大小和穩(wěn)定性為約束,最小化揀選距離構(gòu)建模型。而朱子音[11]在研究中是從另外一個角度研究倉儲貨位分配問題,是以庫房利用率為目標(biāo)函數(shù),從時間和空間兩個角度考慮,將庫房存儲區(qū)域劃分成動態(tài)和靜態(tài)兩個存儲區(qū)域,不同類型,分別進(jìn)行優(yōu)化,最終得出最有的配置方案。

(二)波次揀貨分揀策略的研究

對于同一個區(qū)域內(nèi)的揀選,Acker man[12]在1990年首次提出訂單分批揀選策略,并提出這種方法在一定程度上能夠提高貨物揀選效率。Gibson和Shar p[13]研究了訂單分批揀選方法,并運用仿真將其與普通的揀選方法進(jìn)行對比,最終得出分批揀選方法效率更高,在分批揀選時,需要考慮訂單里面貨物的相關(guān)性,以及倉儲的分布等因素。Gade mann等[14]研究發(fā)現(xiàn),訂單劃分批次問題是一個NP問題,作者采用的是分支定界法對其進(jìn)行求解。

Choe和Shar p[15]在1991年研究提出,波次揀貨劃分有兩個基準(zhǔn):相似度劃分和時間窗。在相似度分揀的情況下,按照貨物的存儲位置來進(jìn)行分批次,難點在于如何衡量各訂單直接的相似度以及訂單揀選的先后次序。這也是本文重點分析的問題。而Gade mann等[14]提出在波次揀貨時,就近訂單揀選能夠?qū)⑷我庖粋€波次的揀貨提前期最小化。對于訂單之間的相似度研究,Chen和 Wu[16]從含有相同產(chǎn)品的數(shù)量考慮,構(gòu)建模型使總關(guān)聯(lián)程度最大,然后將其轉(zhuǎn)化為0-1規(guī)劃問題求解。而在時間窗分揀方面,主要是通過訂單到達(dá)時間劃分波次,同一個時間窗內(nèi)到達(dá)的訂單被劃分到同一個波次。Tang和Che w[17]研究了在固定波次里訂單量的情況下,動態(tài)調(diào)整時間窗的問題。通過測量服務(wù)時間來估算訂單劃分波次大小。李詩珍和王轉(zhuǎn)[18]在2004年研究發(fā)現(xiàn),通過建立最短揀選距離為目標(biāo)函數(shù)的模型實現(xiàn)波次揀選,運用啟發(fā)式算法聚類分析,提出了三個相關(guān)系數(shù):巷道相似系數(shù)、包絡(luò)距離、儲位相似系數(shù)的概念。構(gòu)建模型,最后用基于包絡(luò)解碼的混合遺傳算法求解。在國內(nèi),馬士華和文堅[19]在波次揀選中考慮到了訂單延遲時間,通過調(diào)整時間窗改善揀選員閑忙分配不均的問題,使得整個供應(yīng)鏈揀選效率得到有效地提高。波次揀貨是屬于NP問題,研究下來發(fā)現(xiàn),有許多學(xué)者都是將原來問題轉(zhuǎn)換為0-1分配問題,運用啟發(fā)式算法、遺傳算法求解問題。李云[20]在研究中對波次揀貨算法進(jìn)行了分類:種子啟發(fā)式算法和節(jié)約啟發(fā)式算法。種子啟發(fā)式算法需要為每個波次定義種子的順序,可以通過隨機、數(shù)量、距離等方面考慮。而節(jié)約啟發(fā)式算法是一種針對揀貨路徑上的優(yōu)化算法。鄭凌鶯[21]對于物流倉儲貨物問題上的一般優(yōu)化方法進(jìn)行研究,并比較了各算法的優(yōu)缺點,最終得出以多目標(biāo)遺傳算法為基礎(chǔ)的算法效果最好。

參考已有研究,本文選取遺傳算法對構(gòu)建的波次劃分模型和揀貨任務(wù)指派模型進(jìn)行求解。

三、模型構(gòu)建

(一)模型相關(guān)假設(shè)

為了研究需要,參考已有的研究,本文做了以下合理假設(shè):

1.每一個訂單至少包含一個商品,最多包含N個商品(N為倉儲中心內(nèi)商品總數(shù))。

2.忽略貨架的高度,垂直方向的位移大小不計入揀選路徑,顯然,無論采用何種分配方法,垂直方向的位移大小均存在,因此,可以忽略這一部分。

3.揀選人員至少1個,這也是符合亞馬遜的實際情況。

4.同一個訂單只允許被劃分的一個波次中,然后由一個揀貨員完成揀選。

5.對同一個波次中的訂單集合揀選時,揀選順序不分先后,由系統(tǒng)給定揀選路徑(按照亞馬遜實際情況做出假設(shè))。

6.由于是隨機存儲,同一個商品,在倉儲中可能會存放在不同的位置。

7.倉儲的過道、通道、貨架的寬度、深度均為已知,在波次劃分好之后,其揀貨距離可以直接計算出來。

8.假設(shè)手推車有容量限制,因此同一個波次的商品總數(shù)不能超過M。

9.已知揀選單上的商品存儲位置,揀選時按照S型路徑行走,不存在缺貨、補單等情況。

10.揀貨員每次揀選完成一個波次后,需要將商品送到輸入/輸出點,即中轉(zhuǎn)站,定義為I/O處,才可以開始下一個波次的揀選。

11.引力模型構(gòu)建時,由于隨機存儲情形下從存放商品的本身地理位置特征構(gòu)建訂單相似度是最準(zhǔn)確的,因此不同商品之間的引力大小只與商品的儲位位置有關(guān),其經(jīng)濟質(zhì)量等因素可以歸為統(tǒng)一常數(shù)φ,不會影響最終波次劃分結(jié)果。

12.倉儲中心為雙區(qū)型倉儲,這也是實際中運用最廣泛的存儲方式,平面圖如圖1。

圖1 仿真時倉儲平面圖

(二)單個波次內(nèi)引力模型構(gòu)建

首先考慮波次內(nèi)訂單已經(jīng)確定時,選擇商品儲位,以使得該波次引力最大的儲位決策問題。在隨機存儲環(huán)境下,由于同一個商品可以存儲在在倉庫中多個位置,考慮每一個訂單內(nèi)商品取不同儲位時,該波次中所有商品之間的引力值之和,使得這個引力和最大的儲位決策即為在隨機存儲情形下該商品需要選取的儲位。根據(jù)這個最大的引力和確定該波次中每一個商品的確定儲位位置。

模型構(gòu)建如下,對于任意一個波次z,其引力大小T z可以表示為:

其中:T z為第z個波次的總引力。(X zir,Y zir)為波次z中第i個商品的第r個存儲位置的坐標(biāo);R i表示波次z中商品i一共有的儲位個數(shù),R j表示波次z中商品j一共有的儲位個數(shù)。r i、r j為決策變量,表示商品i、j的第r i、r j個存儲位置(r i=1,2,…,R i、r j=1,2,…,R j)。Q z為第z個波次中含有的商品總個數(shù)。i、j為下標(biāo)(i=1,2,…,Q z、j=1,2,…,Q z),φ為引力模型參數(shù)。

上述問題可以用來在隨機存儲情形下給定波次的情況下,求解選取的對應(yīng)商品的最優(yōu)儲位位置。

因為揀選時必須經(jīng)過I/O點(i=0),因此構(gòu)建模型時將I/O點當(dāng)做一個商品,也考慮它與其他商品之間的引力。

(三)劃分方案目標(biāo)函數(shù)構(gòu)建

從上分析,可以獲得每一個波次訂單內(nèi)的總引力大小。接下來將運用0-1規(guī)劃對波次進(jìn)行劃分。以總訂單被分成不同波次后,所有波次訂單的引力之和作為目標(biāo)函數(shù),使得該目標(biāo)函數(shù)最小的分配方案即為最優(yōu)的分配方案。

本問題中的各符號定義如下:

C i為訂單i的商品個數(shù),

M為每個波次的最大商品數(shù),N為訂單數(shù),B為波次數(shù)目。因此,利用引力模型構(gòu)建的隨機存儲情形下訂單分批模型如下:

約束條件有以下:

T z由式(1)給出。

其中,第一個、第二個約束使得最終的解是0-1變量,第三個約束使得每一個訂單只能被劃分到一個波次中,第四個、第五個約束保證一共劃分B個波次,第六個約束保證每個波次中最大商品數(shù)不超過M(由推車容量和商品體積所決定)。

四、實證分析

(一)問題說明

根據(jù)企業(yè)實際情況,隨機生成算例求解模型。為了與企業(yè)實際情況對應(yīng),并保證具有一定的普遍性,構(gòu)建算例時采用雙區(qū)域型倉儲貨架,這種類型的區(qū)域貨架會比單區(qū)域貨架的情形更加復(fù)雜。整體的倉儲中心布局如下:

為使得距離的計算更貼近實際情形,本文數(shù)值設(shè)置按照企業(yè)實際情形等比例對應(yīng)。設(shè)置對應(yīng)的d1、d2、d3、…、d6值,該值可以根據(jù)企業(yè)實際情況等比例縮小,這里取的是:d1=2,d2=2,d3=1,d4=4,d5=1,d6=4,并且區(qū)域類貨架總數(shù)為40個,訂單數(shù)為20個,波次數(shù)最大不超過訂單數(shù)的一半,即10個,總商品類別數(shù)為30個,每個商品在該庫存中最多有5個儲位。

根據(jù)這些設(shè)置,通過visual st udio C++2010編寫程序,隨機生成一批訂單,該每個訂單都有相應(yīng)的商品信息,每一個商品在該庫存中都有相應(yīng)的存儲位置,依據(jù)隨機生成的訂單,最終構(gòu)建模型,對該批隨機生成訂單進(jìn)行求解,最終分析求解結(jié)果與普通波次劃分方法的區(qū)別。并且,為了與隨機存儲情形對應(yīng),每一個商品都會隨機生成多個儲位。

(二)問題求解

1.波次的劃分

為了對生成的隨機訂單進(jìn)行波次劃分,首先需要將模型在程序中實現(xiàn),遺傳算法運行結(jié)果如圖2。

運用遺傳算法求解隨機存儲情況下波次劃分模型,遺傳1 000代時,劃分結(jié)果為:

波次1:5、8、12、17

波次2:9、15、18、20

波次3:1、2、3、6、7、10、13

波次4:4、11、14、16、19

圖2 遺傳算法求解模型目標(biāo)值結(jié)果

2.波次訂單揀貨路徑長度求解

由于在實際企業(yè)亞馬遜揀選過程中,采用的是S型揀貨規(guī)則,因此,波次劃分完成后,需要求解該劃分情形下采用S型揀貨路徑所需要行走的總揀貨距離。顯然,在求解揀貨距離是相當(dāng)于求解TSP旅行商問題,本研究直接通過構(gòu)建遺傳算法求解通過分不同的情況,能夠?qū)澐趾玫牟ù伟凑諏嶋H過程中的揀選原則(S型),最終估算出行走的路徑長度,進(jìn)而可以很好的衡量波次劃分效果。

通過遺傳算法實現(xiàn)TSP問題,最終求得各波次訂單的最優(yōu)揀貨順序,進(jìn)而總共需要行走的S型揀貨距離,整個劃分方案的最終揀貨路徑長度為:

3.方案對比

將當(dāng)前的最優(yōu)波次劃分和揀選路徑求解方法與傳統(tǒng)的只考慮商品類別、不考慮商品存儲位置的聚類方法,比如層次聚類算法加以比較。這類方法通過構(gòu)建數(shù)據(jù)之間的連接性,一層一層的聚合,不斷的反復(fù)運行,使得最終展現(xiàn)出一種層級架構(gòu)的方法。參照已有學(xué)者的研究,采用傳統(tǒng)的聚合方法進(jìn)行聚類分析。即首先每一個訂單為一個單獨的類,計算不同類之間的距離,即不同類中不重合商品的個數(shù),合并距離最小的兩個類,得到一個新類,類的個數(shù)減1,合并距離最小的兩個類,得到一個新類,類的個數(shù)減1,依次類推。

同樣,通過遺傳算法實現(xiàn)TSP問題,最終求得各波次訂單的最優(yōu)揀貨順序,進(jìn)而總共需要行走的S型揀貨距離,劃分結(jié)果為:

波次1:1、3、8、12、15、18、20

波次2:2、6、10、17、9、14、19

波次3:4、13、16

波次4:5、7、11

總共需行走的S型距離為:兩種波次劃分方法效果對比后,可以看到,隨機存儲情形下基于商品引力大小構(gòu)建的波次劃分模型,要比傳統(tǒng)的基于訂單聚類劃分的方案更優(yōu),揀貨行走距離減小12.7%。通過隨機生成不同的訂單、儲位信息,多次構(gòu)建模型求解,并與傳統(tǒng)的波次劃分方案對比,得出的結(jié)果如表1。

可以看到,本研究在隨機存儲情形下,采用的引入引力模型的方法得到的波次劃分方案比傳統(tǒng)的基于聚類的波次劃分方案更優(yōu),多算例計算得出揀貨行走距離平均減小了15.3%。

表1 多算例情形下兩種不同的波次劃分方法的對比

五、總結(jié)與討論

本文從實證的角度研究在隨機存儲機制下訂單波次劃分的問題。對于倉儲管理而言,構(gòu)建考慮隨機存儲情形下,各種訂單組合后取不同的儲位形成的S型揀貨路徑的大小這一模型,并加以求解,是十分困難的,這是一個NP問題。而本文將引力模型引入,只從商品自身儲位地理位置出發(fā),以波次內(nèi)不同儲位的商品之間的引力大小,來衡量訂單之間的相似度,從而進(jìn)行訂單的波次劃分。最終,通過隨機生成多組仿真算例,將本研究的模型和傳統(tǒng)的波次劃分模型進(jìn)行對比,發(fā)現(xiàn)揀貨行走距離有所縮短,歸納得出,基于引力模型構(gòu)建的波次劃分方案相比于傳統(tǒng)的波次劃分模型S型揀貨路徑更短,揀貨效率更高,揀貨行走距離平均減小了15.3%。

在此基礎(chǔ)上,可以進(jìn)一步討論隨機存儲情形下波次任務(wù)分配問題,比如對于同一個波次,會考慮揀貨員對該波次商品所在區(qū)域的熟悉程度,會優(yōu)先將該波次分配給對這個波次更加熟悉的揀貨員分揀,這種方法一定程度上可以縮短所有訂單揀選完成所需要的時間。

[1]Dr ury J.Towar ds More Efficient Or der Picking[R].I MM Monograph No.1,The Institute of Materials Manage ments,Cranfield,U.K.,1988.

[2]Chen M C,Wu H P.An Association-based Cl ustering Appr oach to Order Batching Considering Custo mer Demand Patter ns[J].Omega,2005,33(4):333-343.

[3]石賢光.基于引力模型的中原城市群空間發(fā)展模式研究[D].南京:南京航空航天大學(xué),2008.

[4]陳彥光,劉繼生,基于引力模型的城市空間互相關(guān)和功率譜分析——引力模型的理論證明、函數(shù)推廣及應(yīng)用實例[J],地理研究,2002(6).

[5]李冠仕.B2C電子商務(wù)物流網(wǎng)絡(luò)優(yōu)化技術(shù)的研究與實現(xiàn)[D].上海:上海交通大學(xué),2013.

[6]周麗,朱杰,郭鍵.分類存儲返回型與S型揀選路徑隨機模型的比較研究[J].系統(tǒng)科學(xué)與數(shù)學(xué),2011(8).

[7]Haus man W H,Sch warz L B,Graves S C.Opti mal Storage Assign ment in Auto matic Warehousing Systems[J].Manage ment Science,1976,22(6):629-638.

[8]Brynzér H,Johansson M I.Storage Location Assign ment:Using t he Product Str ucture to Reduce Or der Picking Ti mes[J].Inter national Jour nal of Production Econo mics,1996,40(46-47):595-603.

[9]Petersen C G,Aase G R,Heiser D R.I mproving Or der-picking Perfor mance Thr ough the Implementation of Class-based Storage[J].Inter national Jour nal of Physical Distribution&Logistics Manage ment,2004,34(7):534-544.

[10]董溪哲,李松齡,楊波.倉儲貨位選擇優(yōu)化問題的研究[J].科技資訊,2006(17).

[11]朱子音.提高庫房利用率方法研究[D].長春:吉林大學(xué),2008.

[12]Acker man K B.Practical Handbook of Warehousing[M].Springer Science&Business Media,2012.

[13]Gibson D R,Sharp G P.Order Batching Procedures[J].Eur opean Jour nal of Operational Research,1992,58(1):57-67.

[14]Gade mann A,Van Den Berg J P,Van Der Hoff H H.An Or der Batching Al gorit h m f or Wave Picking in A Parallel-aisle Warehouse[J].IIE Transactions,2001,33(5):385-398.

[15]Choe K,Shar p G.Small Parts Or der Picking:Design and Operation[R].Geor gia Tech Research Corporation,Atlanta,Georgia,1991.

[16]Chen M C,Wu H P.An Association-based Cl ustering Approach to Order Batching Considering Custo mer De mand Patter ns[J].Omega,2005,33(4):333-343.

[17]Tang L C,Chew E P.Or der Picking Syste ms:Batching and Storage Assign ment Strategies[J].Co mputers&Industrial Engineering,1997,33(3):817-820.

[18]李詩珍,王轉(zhuǎn).訂單揀取路徑優(yōu)化研究[J].物流技術(shù)與應(yīng)用,2002(5).

[19]馬士華,文堅.基于時間延遲的訂單分批策略研究[J].工業(yè)工程管理,2004(6).

[20]李云.基于波次分揀的圖書配送中心分揀效率研究[D].武漢:華中科技大學(xué),2013。

[21]鄭凌鶯.物流中心倉庫貨位優(yōu)化算法的研究[J].商場現(xiàn)代化,2006(22).

F715.1

A

1003-1154(2016)04-0101-05

10.3969/j.issn.1003-1154.2016.04.028

國家自然科學(xué)基金青年基金(71202068);上海交通大學(xué)文理交叉基金重點項目(14JCY02)。