黃敏芳,張源凱,王顏新,胡祥培
(1.華北電力大學經(jīng)濟與管理學院, 北京 102206;2.大連理工大學管理與經(jīng)濟學部,遼寧 大連 116024;3.北京聯(lián)合大學商務(wù)學院,北京 100025;4.新能源電力與低碳發(fā)展研究北京市重點實驗室(華北電力大學),北京 102206)
近年來,網(wǎng)上超市逐漸成為主流的商品零售方式之一。然而,高額的物流成本和低效的物流作業(yè)成為制約網(wǎng)上超市經(jīng)營與生存的首要因素。從成本角度分析,訂單分揀成本占配送中心運營成本的55%以上[1]。訂單分揀環(huán)節(jié)的優(yōu)化對訂單履行成本的節(jié)約至關(guān)重要。如何在上百萬種商品中將訂單要求的商品高效、準確地分揀出來,是網(wǎng)上超市亟待解決的難題。
在分揀環(huán)節(jié),網(wǎng)上超市每個訂單都需經(jīng)過分組、分割、揀貨、集貨復核、包裝這一作業(yè)流程,大量個性化訂單導致這一流程的組織和調(diào)度變得十分復雜。一般B2C電商采用的按單分揀或者基于整個倉庫的批量分揀方法已遠遠滿足不了大型網(wǎng)上超市在海量商品中揀選大批量個性化訂單的需求。網(wǎng)上超市所銷售的商品的種類和形態(tài)多樣、成本高昂、需求的不穩(wěn)定,企業(yè)在短期內(nèi)無法實現(xiàn)全自動倉儲管理,還需依靠人工手動完成揀貨、集貨理貨、包裝等作業(yè)。由于還缺乏科學規(guī)范的方法體系來指導人工作業(yè),網(wǎng)上超市各個作業(yè)的效率和時間在這一復雜的多環(huán)節(jié)作業(yè)流程中都無法保障。網(wǎng)上超市訂單分揀、包裝作業(yè)與產(chǎn)品裝配流水線具有相似性,即一個訂單包裹為一個產(chǎn)品,訂單揀選、集貨理貨、包裝對應(yīng)于產(chǎn)品加工的工序,因此本文借鑒大規(guī)模生產(chǎn)企業(yè)的成組裝配流水作業(yè)模式以及針對多品種、小批量生產(chǎn)條件下的JIT裝配模式的思想,建立在倉庫內(nèi)各獨立的揀選區(qū)域進行并行揀貨的大批量訂單成組分揀方法,組織和協(xié)調(diào)訂單的揀選、集貨復核和包裝三個關(guān)鍵作業(yè)環(huán)節(jié),以指導作業(yè)人員的實際操作,確保網(wǎng)上超市訂單分揀及包裝作業(yè)流程能高效、準確、平衡、流暢運轉(zhuǎn)。
基于JIT裝配流水線的訂單分揀作業(yè)的優(yōu)化涉及兩個方面:訂單分批與批次訂單的排序。已有的訂單分批方法的優(yōu)化策略主要集中在按訂單到達的時間窗分批[2]、按訂單中商品存儲位置的鄰近性分批[3]和以最小化總完成時間和最小化訂單延遲時間為目標來實現(xiàn)訂單分批[4-5]。學者們也提出了用于求解按不同策略建立的訂單分批模型的精確求解方法[6]和啟發(fā)式算法,如自組織神經(jīng)網(wǎng)絡(luò)分類方法[7]等。其中,Scholz等[8]和Hong和Kim[9]提出的啟發(fā)式算法均能求解數(shù)量級為103的大規(guī)模訂單的分批問題,但僅適用于訂單包含一種商品的情況。近年來,有學者提出將客戶訂單的分批與排序[10-11]、訂單的分批與揀選路徑進行集成優(yōu)化[12],以及將訂單分批、訂單批次的分派、揀選路徑的選擇三個問題進行聯(lián)合優(yōu)化[13]。上述成果僅針對單個倉庫內(nèi)的訂單揀選作業(yè)進行優(yōu)化。近期也有學者研究了并行分區(qū)揀選下考慮工作量均衡的訂單分批問題[14]。批次訂單排序方面較有借鑒意義的成果主要集中在裝配線中加工產(chǎn)品的排序問題上,其研究工作多是針對JIT生產(chǎn)系統(tǒng)。目前裝配線排序問題一般都按多目標問題來研究。Sun Hui和Fan Shujin[15]針對一家門鎖公司的混合裝配線產(chǎn)品排序問題構(gòu)建了整數(shù)規(guī)劃優(yōu)化模型。魯建夏等[16]以最小化總調(diào)整時間、最小化超載和空閑時間為目標建立了混合裝配線排序的多目標模型,運用混合人工蜂群算法求解模型得到目標函數(shù)的最優(yōu)解。也有學者提出對平衡和排序問題進行聯(lián)合優(yōu)化,如,Kucukkoc和Zhang[17]針對混合裝配線的雙邊裝配線問題,運用蟻群優(yōu)化方法為排序問題以及線路平衡問題提供了較優(yōu)的解決方案。Manavizadeh 等[18]針對任務(wù)平衡和排序問題,提出以最小化周期時間、最小化工作站浪費和減少工作負荷為優(yōu)化目標。
已有的關(guān)于訂單分揀中訂單分批問題與排序問題的優(yōu)化工作都圍繞最小化揀貨行走距離或揀貨時間這一目標,雖然提升了作業(yè)效率,有助于縮短訂單分揀作業(yè)期,但都未從整個訂單分揀流程角度出發(fā),而僅僅是單個揀貨環(huán)節(jié)的優(yōu)化,效果較好但無法保證后續(xù)工作的效率,并且也未考慮網(wǎng)上超市訂單由于包含多品項商品而被拆分在各個揀選區(qū)域需要合并打包的問題?;贘IT裝配流水線中對加工產(chǎn)品在各道工序上排序的優(yōu)化思想對本文有一定的借鑒作用,但對于同時加工多品種產(chǎn)品,單道工序中存在多臺機器平行加工且需在下一工序中合并,這依然是該領(lǐng)域的一個難題。在網(wǎng)上超市每天需處理巨大訂單量的情況下,如何保證每批商品總品項數(shù)和各個揀貨區(qū)域工作量的均衡,如何將分布在各個揀選區(qū)域的同屬于一個訂單的商品能在恰當?shù)臅r間送到包裝車間進行合并打包,科學的訂單分批與排序是解決上述問題提高訂單分揀作業(yè)效率的關(guān)鍵,也是本文致力于研究的問題。
本文首先針對訂單分揀三道工序提出作業(yè)時間計算模型,然后基于倉庫內(nèi)各存儲區(qū)域并行揀貨策略,建立訂單分批與排序的聯(lián)合優(yōu)化模型,并設(shè)計兩階段啟發(fā)式方法求解該模型。第一階段提出基于工作量均衡的訂單成組分批模型,設(shè)計訂單分批方案生成策略,第二階段將批次訂單排序問題轉(zhuǎn)化為置換流水生產(chǎn)調(diào)度問題,并采用經(jīng)典的NEH算法求解。
由于龐大的商品種類數(shù),網(wǎng)上超市的商品需按照商品關(guān)聯(lián)度進行分類存儲,形成多個獨立的商品存儲區(qū)域,由固定的揀貨人員負責固定區(qū)域的商品,這一策略可使揀貨員揀選商品的分布面積減小,減少通道擁擠,提高效率。網(wǎng)上超市單個訂單中包含的商品往往分布在多個存儲區(qū)域,因此需將各存儲區(qū)域的商品揀選完畢都送至包裝車間,才能進行該訂單的包裝工作。
按照流水線作業(yè)的原理和思想,將訂單揀選、集貨復核、包裝作業(yè)作為順次開展的三道工序來優(yōu)化作業(yè)流程,合理規(guī)劃三道工序的作業(yè)時間,可大大提高人員設(shè)施的利用率。在多個存儲區(qū)域間進行并行揀貨的訂單批量分揀作業(yè)流程可抽象為如圖1所示的包括多道工序的流水線作業(yè)圖。

圖1 基于分區(qū)并行揀貨的訂單分揀各工序作業(yè)示意圖
以訂單批次A和批次B的順次分揀作業(yè)為例。訂單批次A包含的商品分布在存儲區(qū)域1和存儲區(qū)域2,分別形成A11和A12兩個揀選單,這兩個區(qū)域的揀選人員各自將相應(yīng)商品揀選完畢并在指定時間段內(nèi)送至包裝車間的緩存區(qū)域,集貨后由復核人員按訂單批次A中單個訂單內(nèi)容審核商品,包裝人員按照訂單進行打包并將包裹放置在相應(yīng)的裝貨點上。訂單批次B包含的商品分布在存儲區(qū)域1、存儲區(qū)域2和存儲區(qū)域3,分別形成B11、B12和B13三個揀選單,揀貨工序完成A11和A12工作后,即可進行B11、B12和B13的揀貨工作。以此類推,完成訂單批次A和批次B的訂單分揀作業(yè)。圖2示例了三個訂單批次A、B、C在揀貨、集貨復核、包裝三道工序上的流程作業(yè)的時間甘特圖。

圖2 三個訂單批次ABC流水作業(yè)的時間甘特圖
圖3示例了訂單批次B在經(jīng)過訂單揀選、集貨復核、包裝作業(yè)三道工序時的作業(yè)時間關(guān)系。

圖3 訂單批次B的各項作業(yè)時間關(guān)系圖
本文研究的基于JIT模式的網(wǎng)上超市訂單成組分揀問題包含兩個優(yōu)化問題:基于并行分區(qū)揀選的訂單分批問題和訂單批次排序問題。這兩個問題既是順次優(yōu)化關(guān)系,又相互制約,如將兩者進行聯(lián)合優(yōu)化,將有助于實現(xiàn)現(xiàn)有訂單分揀與包裝設(shè)施能力的最大化利用。
模型的假設(shè)條件如下:
(1)顧客對所有商品需求概率一致;
(2)一個訂單不允許分割在不同的批次進行揀選;
(3)當前批次訂單分布在多個揀貨區(qū)域的商品均被揀選完畢后,再進行下一個批次訂單的揀選;
(4)訂單集合確定后,不再插入新的訂單,即不考慮緊急訂單。
參數(shù)定義:
O一定時間段內(nèi)到達的訂單集合,O={1,…,n};
J可行的訂單分批方案集合,J={1,…,m};

P揀選區(qū)域集合,P={1,…,pmax};
i顧客訂單,i∈O;
j訂單批次,j∈J;
k訂單批次被安排的序列位置,k∈K;
p揀選區(qū)域,p∈P;
jp訂單批次j在揀選區(qū)域p的揀貨單;


常量:
C單個批次最大訂單數(shù),與倉庫集貨復核等環(huán)節(jié)的規(guī)模配置相關(guān),如訂單分揀流程中某個薄弱工序在單位時間內(nèi)可能處理的訂單數(shù)量,可根據(jù)當前倉庫訂單分揀的現(xiàn)狀憑經(jīng)驗確定;
sip訂單i分布在揀選區(qū)域p的SKUs數(shù)量;
si訂單i包含的SKUs數(shù)量;
tsetup單批訂單揀貨處理的準備時間;
tpick每單位SKU的揀選時間;
tsort集貨復核時間常量;
tpack打包時間常量;
α,β系數(shù),0<α,β<1;
變量:




Tmax所有訂單批次的完工時間;
決策變量:
xij0-1變量,xij=1表示訂單i分派到訂單批次j,否則為0,i∈O,j∈J;
yjk0-1變量,yjk=1表示訂單批次j分派到順序位置k,否則為0,j∈J,k∈K。
為構(gòu)建網(wǎng)上超市訂單分批與排序的聯(lián)合優(yōu)化模型,需計算訂單分揀流程中訂單揀選、集貨復核、包裝作業(yè)三道工序的作業(yè)時間。
(1)揀貨作業(yè)時間計算
傳統(tǒng)的訂單分批一般以縮短單個存儲區(qū)域內(nèi)的揀貨路徑和揀貨時間為目的,而本文站在整個訂單分揀流程的角度來考慮某個揀貨區(qū)域所需的揀貨時間,因此為簡化問題的求解,選取與揀貨時間密切相關(guān)的單批訂單揀貨處理的啟動時間和區(qū)域所需揀選商品品項數(shù),得到批量訂單在單個存儲區(qū)域揀貨時間的函數(shù)。訂單批次j在分區(qū)p的揀貨時間的計算模型如下:
(1)
訂單批次j對應(yīng)的存儲區(qū)域所需揀貨時間的最大值(如圖3中的揀選作業(yè)B11)為訂單批次j的揀貨時間,該時間對應(yīng)的存儲區(qū)域能送貨至包裝車間的時間點可作為其它存儲區(qū)域送貨時間的參考。則訂單批次j的揀貨時間為:
(2)
(2)集貨復核作業(yè)時間計算
根據(jù)調(diào)研,訂單批次的集貨復核時間與這批訂單所包含的存儲區(qū)域個數(shù)以及這批訂單中包含的商品品項數(shù)相關(guān),計算模型如下:
(3)
(3)包裝作業(yè)時間計算
另外,訂單批次j的包裝作業(yè)時間與該批訂單數(shù)量以及每個訂單包含品項數(shù)相關(guān),計算模型如下:
(4)
該問題的數(shù)學模型描述如下:
MinTmax
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
xij,yjk∈{0,1}, ?i,j,k
(13)
其中,目標函數(shù)(5)是最小化所有訂單的總完工時間;式(6)為所有訂單最大完成時間;式(7)確保一個訂單只分配給一個批次;式(8)確保一個批次訂單只在排序的一個位置上;式(9)確保在排序的一個位置上只能放置一個批次訂單;式(10)一個訂單批次所包含訂單數(shù)不能超過最大訂單數(shù)C;式(11)表示訂單批次在第h階段k位置的完工時間;式(12)表示訂單批次在第h階段k位置的開始時間;式(13)表示決策變量均為0-1變量。
訂單分批與排序的聯(lián)合優(yōu)化模型屬于非線性混合整數(shù)規(guī)劃模型,使用精確算法僅能求解極小規(guī)模的問題。對于一般的問題,本文基于縮減求解空間的思想,提出按照“訂單成組分批→批次訂單排序”的兩階段啟發(fā)式優(yōu)化的思路來求解問題。
訂單分揀流水線上的空閑等待時間是由各批次訂單在各工序上作業(yè)時間的差異以及單個批次訂單在同一工序的不同作業(yè)區(qū)域的作業(yè)時間的差異造成的。比如,在揀貨工序,由于客戶訂單對各個分區(qū)中的商品的需求不同,導致一批訂單分布在各揀貨區(qū)域的工作量存在差異。本文提出在對訂單進行分批時,通過均衡各個訂單批次的規(guī)模和單個批次訂單分割在各揀貨區(qū)域的工作量這兩方面來減少空閑等待時間。對于前者,根據(jù)訂單分揀流程中各工序作業(yè)時間的計算模型,可知各訂單批次在各工序上的作業(yè)時間均與該訂單批次所包含的SKU數(shù)相關(guān),因此,各批次作業(yè)時間的均衡可用每個批次所包含SKU數(shù)與批次平均SKU數(shù)的差異進行表示。對于后者,先根據(jù)所有訂單包含的商品分割在各揀貨區(qū)域的SKU數(shù)量按比例分配揀貨人員,然后要求單個批次訂單在單個分區(qū)工作量與所有訂單分割在該揀貨分區(qū)的平均工作量盡量均衡?;谏鲜鏊悸?,構(gòu)建了以工作量均衡為目標的訂單成組分批模型,目標函數(shù)為:
(14)
訂單成組分批模型的約束條件為式(7),(10),(13)。目標函數(shù)(14)最小化了各個訂單批次間的SKU數(shù)的差異,以及單個批次訂單與所有訂單分割在各個揀貨分區(qū)的工作量的差異。由于訂單分批涉及的訂單規(guī)模龐大,變量較多,使得該模型很難利用已有的精確算法在短時間內(nèi)有效求解。如1000個訂單,20個訂單分批,則變量xij的數(shù)量就可以達到20000個。因此,本文提出借鑒Local Search中Relocate和Exchange的思想,根據(jù)訂單分批規(guī)模的限制條件,設(shè)計了兩種訂單分批方案生成的改進策略,并結(jié)合成本節(jié)約的思想,不斷迭代改進,輸出較優(yōu)的訂單分批方案。求解算法的具體步驟如下:

步驟2.按訂單到達時間的先后順次選取ω個訂單組成不同批次,余下不足ω個訂單組成一個批次;
步驟3.初始化參數(shù)CapCount=0,設(shè)置參數(shù)CapCost;
步驟4.隨機選取兩個訂單分批A(包含訂單數(shù)為C)和B(包含訂單數(shù)為C或者少于C),調(diào)整方法為:
i)Relocate策略:如果訂單分批B的訂單數(shù)小于C,則分別依次計算將訂單分批A中的單個訂單調(diào)整到B分批中的節(jié)約成本Δf(xij),選取最大節(jié)約成本對應(yīng)的訂單,如果該節(jié)約成本小于GapCost,則GapCount++,否則將該訂單由訂單批次A調(diào)整至訂單批次B;
ii) Exchange策略:如果訂單分批B的訂單數(shù)等于C,則順次在A、B中分別選取一個訂單進行交換,并計算節(jié)約成本,選取最大節(jié)約成本的兩個訂單,如果該節(jié)約成本小于GapCost,則GapCount++,否則將該兩訂單進行交換;
步驟5.不斷循環(huán)迭代步驟4直到達到最大的迭代次數(shù)MaxIter或者GapCount達到最大的次數(shù)限制MaxGapCount。
每個訂單批次均需要經(jīng)過分揀、集貨復核、包裝這三個工序,將每個訂單批次看作是一個工件,則批次訂單排序的子問題可以轉(zhuǎn)化為置換流水生產(chǎn)調(diào)度問題(Permutation Flow Shop Problem)[19],因此構(gòu)建批次訂單排序的置換流水生產(chǎn)調(diào)度模型,目標函數(shù)為式(5),約束條件為式(6),(8),(9),(11),(12),(13)。置換流水生產(chǎn)調(diào)度問題是典型的NP-hard問題,本文結(jié)合經(jīng)典的NEH算法求解該子模型。NEH算法是Nawaz等[20]提出的求解置換流水車間調(diào)度問題的經(jīng)典啟發(fā)式算法,經(jīng)過許多學者的比較,已經(jīng)證明了NEH啟發(fā)式算法是最具有競爭性的算法,目前有許多算法都是在此基礎(chǔ)上提出來的[21]。
本文將批次訂單對應(yīng)為工件,訂單處理的三個環(huán)節(jié)對應(yīng)為工件的三道工序,從而直接調(diào)用NEH算法進行求解。其中,每個排序的完工時間調(diào)用式(11)和(12)迭代進行計算。
NEH算法求解批次訂單排序的步驟如下:
步驟2:將訂單批次按照總流程時間tj從大到小排序組成備選列表List。選取列表List的前兩個訂單批次,并評估兩種可能的排序,選擇完工時間較短的排序組成初始排序Schedule。
步驟3:逐次選擇List中的其他訂單批次j,j=3,…,m,然后通過將該訂單批次放置在排序Schedule中j個可能的位置上找到當前最好的排序Schedule。輸出最后的排序Schedule。
根據(jù)國內(nèi)某大型網(wǎng)上超市銷售商品的倉儲布局及訂單履行流程的實際情況,構(gòu)造算例用于驗證本文所提出的模型和求解方法。基于大多數(shù)實際倉庫的分區(qū)配置,設(shè)定揀貨分區(qū)的個數(shù)pmax=3。揀貨時間的相關(guān)參數(shù)(tsetup,tpick,tsort,tpack,α,β)由該大型電商倉庫實地調(diào)研所得,并與相關(guān)倉庫調(diào)度運營人員溝通交流確定。單個批次最大訂單數(shù)C由倉庫調(diào)度人員經(jīng)驗進行確定。關(guān)于訂單方面的相關(guān)參數(shù),本文參考文獻[22]中對大規(guī)模訂單參數(shù)的設(shè)置,訂單個數(shù)N從500 到3000,訂單需求服從泊松分布λ=1.5。在此基礎(chǔ)上,增加對訂單為10000的超大規(guī)模問題的測試。
為了做對比研究,以該網(wǎng)上超市現(xiàn)有的波次分揀方法作為對比對象。目前大型網(wǎng)上超市或者其它網(wǎng)上零售商多采用訂單波次揀選方法。訂單波次揀選是指每隔一段時間(一般5~10分鐘),對“訂單池”中具有相同屬性的訂單(如訂單配送地址、商品種類)分成若干個訂單批次。在該數(shù)值分析中,訂單波次規(guī)模同本文參數(shù)C的取值。
初始實驗參數(shù)如表1所示。
本文的訂單分揀優(yōu)化方法與波次揀貨方法在求解不同規(guī)模的算例的對比結(jié)果如表2所示。由于計算效率均比較高(均小于1分鐘),因此僅對訂單總完工時間進行對比分析。可以發(fā)現(xiàn),相較于波次揀貨方法,本文方法可以節(jié)省1.13%~8.34%的訂單總完工時間,提高了網(wǎng)上超市訂單處理作業(yè)的效率。并且隨著網(wǎng)上超市訂單規(guī)模從500個增加到10000個,本文方法得到的結(jié)果由節(jié)省308.34增長到816.5,可見本文方法可以有效解決大規(guī)模網(wǎng)上超市訂單分揀的問題,并且隨著訂單規(guī)模的增大,節(jié)約的訂單分揀作業(yè)時間越多。

表1 初始參數(shù)設(shè)置

表2 數(shù)值計算對比分析
由于批次訂單容量C直接影響網(wǎng)上超市訂單的分批與排序效果,因此本文在1000個訂單規(guī)模的算例基礎(chǔ)上針對批次訂單容量的變化做了靈敏度分析,結(jié)果如圖6所示。隨著批次訂單容量從10增長到35,本文方法相較于傳統(tǒng)波次揀貨方法的改進呈現(xiàn)一個先增長后減少的趨勢。這說明存在一個最優(yōu)的訂單批次規(guī)模配置使得本文的方法能夠達到最好的效果。

圖6 批次訂單容量改變下本文方法的改進變化
本文結(jié)合大型網(wǎng)上超市訂單數(shù)量龐大、訂單包含品項多等特征,針對訂單揀貨、集貨復核、包裝這一作業(yè)流程,建立了訂單分批與排序的聯(lián)合優(yōu)化模型,并提出了兩階段啟發(fā)式優(yōu)化方法。將JIT裝配理論引入訂單分揀領(lǐng)域,為網(wǎng)上超市訂單分揀的優(yōu)化決策提供了一種新方法,提高了訂單分揀理論的實用性和普適性,有利于發(fā)展網(wǎng)上超市這一新型電子商務(wù)模式。在實踐上,理論成果可為指導網(wǎng)上超市或其它B2C電子商務(wù)企業(yè)的配送中心的揀貨人員的實際作業(yè)提供借鑒,有助于電子商務(wù)企業(yè)實現(xiàn)效率與客戶服務(wù)水平的綜合提升。
所取得的成果及創(chuàng)新之處可歸納為:(1)從縮減問題求解空間的角度出發(fā),提出的基于倉庫內(nèi)各存儲區(qū)域并行揀貨的大批量訂單成組分揀方法,考慮了包裝車間的有限空間,保證各揀選區(qū)域僅在恰當?shù)臅r間將正確的商品送至包裝車間,提高了包裝車間作業(yè)的有效性和高效性;(2)建立基于JIT裝配流水線思想的訂單分揀作業(yè)模式,將訂單揀選、集貨復核、包裝作業(yè)作為順次開展的三道工序來優(yōu)化作業(yè)流程,有助于合理規(guī)劃工序的作業(yè)規(guī)模和時間,實現(xiàn)訂單分揀流程中各工序的高效、均衡運轉(zhuǎn);(3)建立的訂單批次排序模型充分考慮了根據(jù)網(wǎng)上超市訂單分揀的實際情況安排訂單分揀作業(yè)投產(chǎn)計劃,可通過加入訂單權(quán)重等因素靈活調(diào)整排產(chǎn)優(yōu)先級,使排序模型更具有實際應(yīng)用價值。
未來研究方向有:訂單分揀流程中的集貨復核和包裝兩道工序有多個設(shè)施和人員同時操作下,訂單分批與排序問題的研究;現(xiàn)實訂單分揀流程會產(chǎn)生大量不確定性,進一步研究考慮流水線單個工序產(chǎn)生擾動的訂單分揀問題。