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

□ 盧燁彬 劉少軒

(上海交通大學 安泰經濟與管理學院,上海 200030)

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

□ 盧燁彬 劉少軒

(上海交通大學 安泰經濟與管理學院,上海 200030)

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

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

一、引 言

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

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

本文創新性地將引力模型應用到波次劃分模型中,以波次內不同儲位的商品之間的引力大小來衡量訂單之間的相似度,從而進行訂單的波次劃分。

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

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

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

二、文獻綜述

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

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

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

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

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

參考已有研究,本文選取遺傳算法對構建的波次劃分模型和揀貨任務指派模型進行求解。

三、模型構建

(一)模型相關假設

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 仿真時倉儲平面圖

(二)單個波次內引力模型構建

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

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

其中:T z為第z個波次的總引力。(X zir,Y zir)為波次z中第i個商品的第r個存儲位置的坐標;R i表示波次z中商品i一共有的儲位個數,R j表示波次z中商品j一共有的儲位個數。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個波次中含有的商品總個數。i、j為下標(i=1,2,…,Q z、j=1,2,…,Q z),φ為引力模型參數。

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

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

(三)劃分方案目標函數構建

從上分析,可以獲得每一個波次訂單內的總引力大小。接下來將運用0-1規劃對波次進行劃分。以總訂單被分成不同波次后,所有波次訂單的引力之和作為目標函數,使得該目標函數最小的分配方案即為最優的分配方案。

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

C i為訂單i的商品個數,

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

約束條件有以下:

T z由式(1)給出。

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

四、實證分析

(一)問題說明

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

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

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

(二)問題求解

1.波次的劃分

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

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

波次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 遺傳算法求解模型目標值結果

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

由于在實際企業亞馬遜揀選過程中,采用的是S型揀貨規則,因此,波次劃分完成后,需要求解該劃分情形下采用S型揀貨路徑所需要行走的總揀貨距離。顯然,在求解揀貨距離是相當于求解TSP旅行商問題,本研究直接通過構建遺傳算法求解通過分不同的情況,能夠將劃分好的波次按照實際過程中的揀選原則(S型),最終估算出行走的路徑長度,進而可以很好的衡量波次劃分效果。

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

3.方案對比

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

同樣,通過遺傳算法實現TSP問題,最終求得各波次訂單的最優揀貨順序,進而總共需要行走的S型揀貨距離,劃分結果為:

波次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型距離為:兩種波次劃分方法效果對比后,可以看到,隨機存儲情形下基于商品引力大小構建的波次劃分模型,要比傳統的基于訂單聚類劃分的方案更優,揀貨行走距離減小12.7%。通過隨機生成不同的訂單、儲位信息,多次構建模型求解,并與傳統的波次劃分方案對比,得出的結果如表1。

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

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

五、總結與討論

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

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

[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]石賢光.基于引力模型的中原城市群空間發展模式研究[D].南京:南京航空航天大學,2008.

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

[5]李冠仕.B2C電子商務物流網絡優化技術的研究與實現[D].上海:上海交通大學,2013.

[6]周麗,朱杰,郭鍵.分類存儲返回型與S型揀選路徑隨機模型的比較研究[J].系統科學與數學,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]董溪哲,李松齡,楊波.倉儲貨位選擇優化問題的研究[J].科技資訊,2006(17).

[11]朱子音.提高庫房利用率方法研究[D].長春:吉林大學,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]李詩珍,王轉.訂單揀取路徑優化研究[J].物流技術與應用,2002(5).

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

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

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

F715.1

A

1003-1154(2016)04-0101-05

10.3969/j.issn.1003-1154.2016.04.028

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