動態(tài)并行分區(qū)揀選系統(tǒng)下訂單分批問題研究

胡小林，徐菱,2

（1.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031；2.西南交通大學(xué) 綜合交通運(yùn)輸智能化國家地方聯(lián)合工程實(shí)驗(yàn)室，四川 成都 610031）

1 引言

B2C電子商務(wù)環(huán)境下訂單多采用分區(qū)存儲策略，并具有種類多、數(shù)量少、需求不確定、時效性強(qiáng)等特征，分區(qū)存儲可以有效提高動態(tài)環(huán)境下的訂單揀選效率，因此有必要研究動態(tài)并行分區(qū)揀選系統(tǒng)下的訂單揀選問題，如何在資源有限的情況下快速制定訂單分區(qū)揀選策略是本文解決的主要問題，本文將協(xié)同運(yùn)用訂單分批與分區(qū)揀選方式。

國內(nèi)外學(xué)者多采用啟發(fā)式算法求解訂單分批問題，最常用的三種啟發(fā)式算法包括種子算法[1]、節(jié)約算法[2]和優(yōu)先規(guī)則算法，還有一部分學(xué)者采用遺傳算法[3-5]、鄰域搜索算法[6-7]、聚類分析算法[8-9]等進(jìn)行訂單分批研究；當(dāng)前對于多揀選人員的訂單分批揀選主要集中在如何解決揀選通道的堵塞問題[6，10-12]；對于在線訂單分批問題，王旭坪等[13]研究了基于緊急程度的在線訂單分批算法，Chen[14]提出Green Area實(shí)時規(guī)劃調(diào)整揀選人員的揀選路徑，同時解決了訂單分批、批次分配和路徑規(guī)劃問題，相較于其他算法，Green Area更適合實(shí)時訂單環(huán)境下的訂單分批問題。

本文研究動態(tài)并行分區(qū)揀選系統(tǒng)下的訂單分批揀選問題（Order Batching Problem under Dynamic Synchronized Zone Picking System,OBPDSZPS），目前針對分區(qū)揀選的研究主要考慮分區(qū)批次商品數(shù)量、分區(qū)形狀等因素對揀選系統(tǒng)的影響[15-16]，還有的學(xué)者將訂單分批與分區(qū)揀選結(jié)合考慮[17-18]，也有學(xué)者考慮按分區(qū)工作量均衡原則進(jìn)行優(yōu)化，張珺[19]和王旭坪等[20]則研究了考慮分區(qū)工作量均衡和總揀選時間最短的雙目標(biāo)優(yōu)化問題，并設(shè)計(jì)了改進(jìn)的遺傳算法求解。

綜上所述，分區(qū)揀選的研究成果尚未考慮對分揀的優(yōu)化，并且缺乏動態(tài)并行分區(qū)揀選的研究，本文考慮到離線訂單環(huán)境訂單在各個分區(qū)的不均衡分布，綜合考慮訂單分批、批次分配、路徑優(yōu)化和批次分揀，研究動態(tài)并行分區(qū)揀選系統(tǒng)下的訂單分批揀選問題。此外本文考慮根據(jù)訂單揀選截止時間和揀選通道相似度構(gòu)建一個綜合相似度指標(biāo)進(jìn)行訂單分批，目前研究成果主要是根據(jù)通道相似度構(gòu)建訂單分批指標(biāo)。總的來說，本文借鑒訂單分批、分區(qū)揀選研究成果，進(jìn)一步研究訂單分批揀選問題，并提出相應(yīng)的算法求解，數(shù)值實(shí)驗(yàn)驗(yàn)證了算法的有效性。

2 研究問題與模型構(gòu)建

本文研究動態(tài)并行分區(qū)揀選系統(tǒng)下離線訂單分批揀選問題，研究對象為企業(yè)前一天晚上00:00到第二天白天06：00累計(jì)生成的n個需求點(diǎn)的訂單，每個需求點(diǎn)有r個訂單，衡量該問題效益的指標(biāo)為由揀選時間、等待時間組成的訂單總服務(wù)時間。問題的關(guān)鍵決策包括：（1）如何確定訂單所屬的揀選批次；（2）如何將一個批次分配到不同的揀選分區(qū)；（3）分區(qū)批次訂單的分揀順序根據(jù)什么規(guī)則確定。

2.1 問題描述與符號說明

考慮有N個揀選截止時間已知的需求點(diǎn)，每個需求點(diǎn)可拆分為vi1,vi2,...,vir共R個訂單，其具體流程如圖1所示，系統(tǒng)涉及的時間如下：批次開始揀選時間，批次路徑時間，批次分揀時間，批次揀選完成時間，訂單開始包裝時間，訂單等待時間，其中表示需求點(diǎn)第一個與最后一個訂單到達(dá)分揀臺包裝的時間差。

圖1 OBPDSZPS問題訂單履行流程圖

模型假設(shè)如下：

（1）商品均有足夠庫存，不考慮補(bǔ)貨時間；

（2）倉庫為單區(qū)型，存儲區(qū)域由平行排列的貨架組成；

（3）已知所需揀選貨品存儲貨位；

（4）揀選路徑忽略垂直方向上的位移；

（5）需求點(diǎn)位置和時間窗已知。

相關(guān)符號說明如下：

V：需求點(diǎn)集合，V={v1,v2,...,vn}；

oH：揀選分區(qū)集合，oH={o1,o2,...,oh}，其中H={1,2,...,h}表示揀選人員集合；

B：批次集合，B={b1,b2,...,bm}，bm=bmo1,bmo2,...,bmoh，bmoh表示批次bm屬于分區(qū)oh的部分；

volvir,weivir：需求點(diǎn)vi第r個訂單的體積和重量；

Qvmax,Qwmax：揀選批次的體積和重量限制；

決策變量：

2.2 約束條件

（1）訂單拆分約束。一個需求點(diǎn)的需求只屬于一個揀選批次，同時訂單不可拆分，即：

（2）容量約束

（3）揀選約束

①批次分配約束。每一個訂單必須分配一個揀選批次，每一個揀選批次必須分配到相應(yīng)的揀選分區(qū)，即：

②批次揀選順序與時間約束，即：

③變量取值約束

2.3 目標(biāo)函數(shù)

該模型的目標(biāo)是訂單總服務(wù)時間最小化，訂單總服務(wù)時間主要由兩部分組成，即揀選時間和等待時間。

（1）揀選時間t pick。揀選時間包括路徑時間trouting和分揀時間tsorting兩部分。

①路徑時間為批次路徑時間之和，則揀選路徑時間為：

設(shè)揀選人員h的批次訂單bm在通道i距離前端和后端通道的最遠(yuǎn)存儲位置為，員工進(jìn)入通道gi的位置=0或1，=0表示揀選人員從前端通道進(jìn)入，=1則表示后端通道進(jìn)入，其中Sg1bmoh=0；通道寬度和貨架寬度相等為Lc，通道長度為La，每一揀選批次通道數(shù)為Gbmoh，最大通道序號為，則人員h揀選批次m時在通道gi的揀選距離計(jì)算如圖2所示。

通道揀選距離計(jì)算如下：

圖2 揀選距離計(jì)算示意圖

則bmoh的揀選距離為：

vh是揀選人員的行走速度；t0是一個訂單的揀選時間，是批次bm的揀選路徑時間，則：

②分揀時間tsorting。訂單的開始包裝時間為，批次分揀時間是批次中所有商品進(jìn)入分揀臺到分揀臺處理完所有訂單的時間差，即：

（2）等待時間twait。在揀選階段采用并行揀選分區(qū)系統(tǒng)會導(dǎo)致需求拆分揀選，同一個需求點(diǎn)的訂單分屬于不同的揀選分區(qū)，并分配給不同的人員揀選，因此在揀選分揀階段會產(chǎn)生屬于同一輛車需求點(diǎn)的等待時間。

則訂單的揀選等待時間為：

3 算法設(shè)計(jì)

3.1 訂單分批算法HB

根據(jù)Elsayed研究成果[1]，結(jié)合本文建立的綜合相似度指標(biāo)，采用表示訂單vir和vjr揀選通道的相似度，|Aislevir?Aislevjr|表示兩個訂單之間相同揀選通道的數(shù)量，|Aislevir?Aislevjr|表示兩個訂單的總通道數(shù)量，則根據(jù)兩個訂單vir和vjr之間揀選截止時間的差值計(jì)算兩個訂單揀選截止時間的相似度，越小，表明兩個訂單的揀選截止時間越接近、相似度越大，則揀選截止時間相似度，則，其中α+β=1。

HB算法包括訂單選擇和訂單合并兩個步驟，訂單選擇階段采用揀選截止時間-通道-儲位的規(guī)則（Picking Due Date-Aisle-Storage Location Rule，PDD-A-SL）選擇種子訂單。訂單合并階段在剩余訂單中選擇與vseed綜合相似度指標(biāo)最大的訂單與其合并為一個批次（Largest Comprehensive Similarity Rule，LCS），并與揀選裝置容量比較判斷該訂單是否加入該批次，直至所有的訂單分批完成，HB算法的具體步驟如下：

步驟1：初始化。待分批訂單集合Vp、QVp、、Qmax，并設(shè)置分批集合B為空。

步驟2：訂單容量Vp判斷。如果QVp＞Qmax，執(zhí)行步驟3；如果QVp≤h·Qc，則只有一個揀選批次，將Vp合并為一個揀選批次，記錄B={bm}、bm=Vp，運(yùn)行步驟9。

步驟3：種子訂單選擇。依據(jù)PDD-A-SL規(guī)則選擇種子訂單vseed。

步驟5：合并訂單選擇。依據(jù)LCS規(guī)則在集合Vp中選擇simivseedvir最大的訂單vir。

步驟6：計(jì)算訂單揀選完成時間。調(diào)用批次分配和分揀算法計(jì)算bm={vseed，vir}的批次訂單分揀完成時間t，bm={vseed，vir}的最小揀選截止時間為

步驟7：容量判斷。對vseed和vir兩個訂單的合并容量(qvseed+qvir)進(jìn)行如下判斷：

I.如果（qvseed+qvir）＜Qvmax、t＜tmin，則滿足揀選裝置容量和揀選截止時間約束，合并訂單vseed和vir為新的vseed，并記錄批次集合bm={vseed，vir}，從集合Vp刪除訂單vir，更新QVp，返回步驟5。

II.如果(qvseed+qvir)=Qvmax、t≤tmin或(qvseed+qvir)＜Qvmax、t=tmin，則滿足揀選裝置容量和揀選截止時間約束，合并訂單vseed和vir為人員h的一個揀選批次，即批次集合bm={vseed，vir}，從集合Vp刪除訂單vir，更新QVp，返回步驟8。

III.如果(qvseed+qvir)≤Qvmax、t＞tmin或(qvseed+qvir)＞Qvmax、t≤tmin，則不滿足揀選裝置容量和揀選截止時間約束，令V′=Vpvir，從V′中根據(jù)LCS規(guī)則選擇訂單vir，返回步驟6。

IV.如果(qvseed+qvir)＞Qvmax、t＞tmin，不滿足揀選裝置容量約束，運(yùn)行步驟7。

步驟8：訂單分批完成判斷。輸出批次bm，判斷是否還有未分批訂單，若Vp=φ，運(yùn)行步驟9；若Vp≠φ，返回步驟2。

步驟9：分批結(jié)束。輸出揀選批次集合Bm={b1,b2,...,bm}，則有m個揀選批次，并調(diào)用分配和分揀算法計(jì)算批次訂單分揀完成時間。

3.2 批次分配算法HBD

本文根據(jù)批次訂單存儲位置進(jìn)行動態(tài)分區(qū)，對每一個揀選批次進(jìn)行通道分配，使得每一個揀選批次的分區(qū)揀選時間均衡，縮短訂單的等待時間。

圖3 訂單分批流程圖

訂單的存儲位置已知，在訂單分批完成后，各個揀選通道的訂單及其體積已知，本文通過枚舉法對通道的分配方案進(jìn)行對比，最后選擇最優(yōu)的通道分配方案計(jì)算各個分區(qū)的批次揀選路徑時間，其分配算法HBD具體步驟如下：

步驟1：初始化。輸入批次訂單集合bm、倉庫總的通道數(shù)量n、揀選人員數(shù)量h。

步驟2：位置標(biāo)注。根據(jù)bm中訂單vir的存儲位置，計(jì)算各個通道訂單的體積與重量，并標(biāo)注各個訂單位置，找出各個通道距離前端和后端通道的最遠(yuǎn)存儲位置

步驟3：通道分配。分別設(shè)置i1=1:n、i2=i1+1:n、…、ih-1=ih-2+1:n。

步驟4：揀選路徑時間計(jì)算。根據(jù)式（13）-（17）計(jì)算各個揀選人員揀選完所負(fù)責(zé)通道訂單的揀選路徑時間，并記錄每種通道分配方案下各個揀選人員的分區(qū)揀選路徑時間、時間標(biāo)準(zhǔn)差和體積，若對于i1,i2,...,ih-1存在訂單總體積超過揀選裝置體積約束，則將i1,i2,...,ih-1標(biāo)記為不可行解。

步驟5：分區(qū)結(jié)果輸出。選擇時間差最小的通道分配方案，并輸出各個揀選人員的批次揀選路徑時間。

3.3 分揀優(yōu)化算法HSO

綜上所述，分揀算法Hso主要包括揀選分揀臺分配和投放順序，分揀臺分配基于車輛離開時間規(guī)則VDT-D確定，投放順序則包括訂單選擇與順序確定兩個步驟：訂單選擇基于最小化車輛離開時間和合并包裝訂單規(guī)則（Smallest Vehicle Depart Time and Spilt Order Rule，SVDT-SO）；順序確定則基于最大化商品包裝難度（Largest Package Difficulty Rule，LPD）規(guī)則確定，即bmoh一部分訂單Vs={vir,vjr,...,vlr}，若difvir＜difvjr＜...＜difvlr，則Ovlr＜...＜Ovjr＜Ovir。Hso具體算法規(guī)則如下：

步驟1：初始化。確定批次bmoh訂單集合Vbmoh，并設(shè)置bmoh的順序集合V′為空、順序記錄Obmoh中所有訂單的順序?yàn)?。

步驟2：分揀臺分配。根據(jù)VDT-D分配分揀臺。

步驟3：指標(biāo)計(jì)算。計(jì)算Vbmoh中所有訂單的difvir。

步驟4：訂單選擇。根據(jù)SVDT規(guī)則選擇訂單集合Vs，其訂單數(shù)量為Q(Vs)。

步驟5：容量判斷。對該集合的數(shù)量Q(Vs)做如下判斷：

I.如果Q(Vs)=1，在Obmoh中更新訂單vir的分揀順序，將Vs={vir}的訂單vir加入V′，刪除Vbmoh中Vs的訂單集合，運(yùn)行步驟8。

II.如果Q(Vs)＞1，即Vs={vir,vjr,...,vlr}，刪除Vbmoh中Vs的訂單集合，運(yùn)行步驟6。

步驟6：訂單選擇。根據(jù)LPD原則選擇Vs中訂單vir。

步驟7：順序確定。從Vs中刪除訂單vir，將訂單vir加入V′，并在Obmoh中記錄訂單vir的分揀順序。如果Vs≠φ，返回步驟6；否則運(yùn)行步驟8。

步驟8：分揀順序確定完成判斷。判斷是否還有未確定分揀順序的訂單，若Vbmoh=φ，運(yùn)行步驟9；若Vbmoh≠φ，返回步驟4。

步驟9：分揀順序確定結(jié)束。輸出順序集合V′和順序記錄Obmoh，則批次bmoh的訂單分揀順序?yàn)閂′={v1,v2,...,vn}，計(jì)算批次分揀時間，并根據(jù)Obmoh中訂單vir的揀選順序和式（20）-（24）計(jì)算訂單的分揀完成時間

4 仿真實(shí)驗(yàn)及其結(jié)果分析

4.1 實(shí)驗(yàn)參數(shù)設(shè)計(jì)

為驗(yàn)證模型和算法的有效性，將優(yōu)化分揀包裝順序但分區(qū)固定的系統(tǒng)（算法A）、不優(yōu)化分揀包裝順序但考慮靜態(tài)分區(qū)揀選系統(tǒng)（算法B）、不優(yōu)化分揀包裝順序的靜態(tài)分區(qū)揀選系統(tǒng)（算法C）與本文揀選系統(tǒng)（算法H）進(jìn)行對比，其他參數(shù)設(shè)置如下：

（1）需求點(diǎn)數(shù)量V=60，訂單數(shù)量為200，即一個需求點(diǎn)有多個訂單；

（2）倉庫揀選區(qū)域存放1 000種商品，同一種商品存儲位置相同，倉庫包含20個揀選通道，每列貨架有100個貨位，通道寬度為5m，通道長度為100m，橫向通道長度為100m；

（3）揀選人員有4個，揀選裝置體積為8m3，行走速度為1.2m/s，單位訂單揀選時間為5s，員工從最左邊通道開始揀選，在通道內(nèi)需要揀選左右兩邊貨架的訂單商品，揀選完成后再進(jìn)行分揀；

（4）自動分揀線的傳輸速度為2m/s，訂單投放間隔時間為3s，自動分揀線總共有4個分揀臺，分揀臺之間間隔為20m。

算法運(yùn)用MATLAB R2016a在操作系統(tǒng)為Window10 64-bit、CPU為16GB的計(jì)算機(jī)上運(yùn)行。

4.2 實(shí)驗(yàn)結(jié)果分析

為確保實(shí)驗(yàn)結(jié)果的可靠性，隨機(jī)生成3種不同的訂單規(guī)模環(huán)境，通過設(shè)置HB算法中綜合相似度不同的α和β的取值，對比不同相似度參數(shù)環(huán)境下的批次揀選路徑時間，尋找最優(yōu)的綜合相似度參數(shù)取值。

分別設(shè)置n=200,n=400,n=500三種訂單規(guī)模，采用本文提出的訂單分批和批次操作算法進(jìn)行訂單分批，三種訂單規(guī)模環(huán)境下α、β不同取值的計(jì)算結(jié)果見表1。

表1 不同參數(shù)下數(shù)據(jù)

從表1可以看出，隨著α取值的增加，批次揀選路徑時間逐漸減少，當(dāng)α=1，即按揀選通道相似度進(jìn)行分批，批次的揀選路徑時間最短，但是隨著訂單量的增加，按揀選通道相似度進(jìn)行分批已經(jīng)不適合大規(guī)模的訂單分批問題；采用本文提出的算法求解，當(dāng)α=0、β=1時，訂單相似度根據(jù)其揀選截止時間確定，雖然不會出現(xiàn)訂單延遲，但該種參數(shù)設(shè)置下批次訂單在倉庫過于分散，導(dǎo)致了批次揀選路徑的增加；當(dāng)α增加到0.7、β為0.3時，揀選通道相似度占總相似度的70%，使得批次訂單包含了多個不同揀選截止時間的訂單，開始出現(xiàn)了訂單延遲，且隨著α取值的增加，揀選路徑時間急劇下降，但同時延遲訂單數(shù)量和總延遲時間亦急劇增加，因此當(dāng)α≥0.7、β≤0.4時，無法使所有訂單在其揀選截止時間之前完成。從表1中可以看出，最優(yōu)的參數(shù)取值為α=0.6、β=0.4。

圖4 不同參數(shù)下指標(biāo)變化圖

本文提出考慮優(yōu)化分揀包裝順序和分區(qū)揀選時間均衡的動態(tài)并行分區(qū)揀選系統(tǒng)，為分析該系統(tǒng)的效率，在α=0.6、β=0.4取值下，將算法A、B、C與算法H進(jìn)行對比，分別設(shè)置n=200,n=500,n=800,n=1100四種訂單規(guī)模，對四種算法的批次平均等待時間、批次路徑時間標(biāo)準(zhǔn)差、分揀包裝時間和訂單處理時間進(jìn)行對比分析，數(shù)據(jù)見表2。

從表2中可以看出，與算法A相比，本文提出的算法H優(yōu)化了18%的批次訂單平均等待時間和15%的訂單履行時間，批次訂單履行時間平均為0.639h，最高優(yōu)化率達(dá)到了30%，批次路徑時間有所增加，但批次路徑時間的標(biāo)準(zhǔn)差優(yōu)化率為24%；當(dāng)n=800時，批次訂單等待時間為0.2-0.6h，優(yōu)化率為36%-56%，當(dāng)n=500時，第二批次訂單等待時間為0.591h，優(yōu)化率為7%，這四個批次的批次等待時間僅為平均批次等待時間的50%-60%，同時優(yōu)化率高于其他批次20%-30%，這是由于該種訂單規(guī)模下，存在某些批次的容量遠(yuǎn)小于揀選裝置容量，按本文提出的等待時間最小目標(biāo)進(jìn)行批次訂單的分配可以使得各個揀選分區(qū)的工作量均衡，使訂單拆分揀選后以最小的揀選路徑時間差揀選，從而大大降低批次的等待時間，在揀選裝置剩余容量較小時，批次的平均等待時間在0.2h-0.6h之間。

算法B的平均批次履行時間為0.719h、批次平均等待時間為1.479h，與算法B相比，算法H的批次路徑時間相差不大，多個揀選批次的路徑時間標(biāo)準(zhǔn)差相同，但是降低了26%的批次平均等待時間和12%的訂單履行時間，同時算法H減少了對各個批次的分揀包裝時間，平均優(yōu)化率為7%，這說明本文提出的分揀包裝順序優(yōu)化規(guī)則通過優(yōu)先分揀揀選截止時間靠前和包裝難度較大的訂單可以減少訂單的等待時間，同時在批次訂單量較小的情況下，分揀包裝時間優(yōu)化率出現(xiàn)了負(fù)值，說明算法H的分揀包裝規(guī)則對訂單量較大的批次有更好的優(yōu)化。

表2 不同參數(shù)下指標(biāo)數(shù)據(jù)

算法C的平均批次履行時間為0.778h、批次平均等待時間為1.562h，與算法C相比，算法H優(yōu)化了24%批次揀選路徑時間標(biāo)準(zhǔn)差、31%的平均等待時間和18%的訂單履行時間；同時通過A、B、C算法之間的對比分析，發(fā)現(xiàn)算法A和算法C相比，平均降低了17%的等待時間、3%的訂單履行時間和分揀包裝時間，算法B和算法C相比，平均降低了3%的等待時間和5%的訂單履行時間，增加了1%的分揀包裝時間，算法A和算法B之間沒有可比性，再次驗(yàn)證了本文提出的考慮分區(qū)揀選時間均衡和優(yōu)化分揀包裝順序的方法可以大幅度的降低訂單等待時間和訂單履行時間。

綜上所述，可得出如下結(jié)論：

（1）本文提出的算法可以有效解決訂單分批與批次調(diào)度問題，保證所有的訂單在揀選截止時間之前揀選完成，并且經(jīng)過多次實(shí)驗(yàn)發(fā)現(xiàn)，綜合相似度參數(shù)最優(yōu)取值為α=0.6、β=0.4；

（2）通過算法H與算法A、B、C的對比分析發(fā)現(xiàn)，算法H通過合理分配各個揀選分區(qū)的訂單和優(yōu)化訂單分揀包裝順序，使得包裝難度較大的訂單先分揀，降低了18%-31%的平均等待時間、9%-24%的揀選路徑時間標(biāo)準(zhǔn)差、5%-7%的分揀包裝時間和12%-18%的訂單履行時間。

5 結(jié)語

本文以最小化訂單總服務(wù)時間為目標(biāo)，研究動態(tài)并行分區(qū)揀選系統(tǒng)下訂單揀選問題，構(gòu)建了動態(tài)并行分區(qū)揀選系統(tǒng)下訂單分批揀選模型，并設(shè)計(jì)算法求解。仿真實(shí)驗(yàn)表明，綜合相似度中揀選截止時間相似度和揀選通道相似度最優(yōu)的參數(shù)取值為，與算法A、B、C的對比分析則證明了本文提出的批次分配算法和分揀算法可以縮短訂單的等待時間和訂單的履行時間。本文提出的算法可以解決離線訂單系統(tǒng)下訂單揀選問題，對B2C電子商務(wù)企業(yè)處理凌晨00:00-06:00的訂單揀選與配送問題具有一定的借鑒意義。但本文僅研究了需求量已知的情況，隨著信息技術(shù)的發(fā)展，實(shí)時訂單系統(tǒng)下并行分區(qū)揀選系統(tǒng)的訂單分批揀選有待進(jìn)一步研究。