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

周 麗，張 雪，楊江龍

（1.北京物資學(xué)院信息學(xué)院，北京 101149；2.首都經(jīng)濟(jì)貿(mào)易大學(xué)管理工程學(xué)院，北京 100070）

1 引言

揀選成本在倉儲成本中占據(jù)較大比例，而應(yīng)用分批策略又可進(jìn)一步減少揀選作業(yè)的總時間。國內(nèi)外關(guān)于訂單分批的研究從未停止，研究的內(nèi)容也隨著解決問題方法的改變更契合實(shí)際變的更加深入。文獻(xiàn)[1]以最小化平均有效訂單服務(wù)時間為目標(biāo)，構(gòu)建了一個考慮訂單完成期限的在線訂單分批混合整數(shù)規(guī)劃模型；文獻(xiàn)[2]提出了一種能夠有效求解波次分批揀選以及提高揀選效率的啟發(fā)式聚類算法；文獻(xiàn)[3]針對訂單分批處理問題，運(yùn)用可變鄰域搜索的方式，實(shí)現(xiàn)最大化訂單關(guān)聯(lián)或最小化訂單差異，以最少揀選次數(shù)實(shí)現(xiàn)訂單的分批處理；文獻(xiàn)[4]提出了一種訂單分批處理的優(yōu)化模型，將其拓展到具有多個倉庫分區(qū)的情況，并提出了一種元啟發(fā)式方法；文獻(xiàn)[5]研究了揀選器路由的訂單批量問題，提出了消除對稱性以及顯著提高線性規(guī)劃松弛值的約束條件，設(shè)計(jì)了一種基于部分整數(shù)優(yōu)化的啟發(fā)式算法，適用于網(wǎng)格型布局的倉庫或存儲區(qū)域。

然而，關(guān)于隨機(jī)性訂單分析尚處在起步，雖然有的學(xué)者考慮到了隨機(jī)性的影響，但大多局限在參數(shù)的引入上[6]，而把整體在線訂單處理看作排隊(duì)系統(tǒng)并與分區(qū)策略相結(jié)合的研究不多。因此，需要進(jìn)一步分析分區(qū)揀選系統(tǒng)中隨機(jī)到達(dá)的訂單特性，研究考慮訂單到達(dá)隨機(jī)性的訂單分批策略，為物流企業(yè)的基本運(yùn)作提供新的思路和方法。

在隨機(jī)存儲策略、S型揀選路徑下，將電商倉庫的在線訂單揀選整個過程看作一個隨機(jī)服務(wù)系統(tǒng)，通過構(gòu)建串行分區(qū)下訂單分批與不分批的隨機(jī)服務(wù)系統(tǒng)模型，將單個訂單揀選系統(tǒng)的平均服務(wù)時間等效率指標(biāo)，同批訂單的相應(yīng)效率指標(biāo)做對比，尋找最優(yōu)的分批方式，期望可以為倉儲分區(qū)揀選系統(tǒng)的效率管理和優(yōu)化控制提供決策依據(jù)，進(jìn)一步豐富訂單揀選隨機(jī)服務(wù)系統(tǒng)的理論研究。

2 串行分區(qū)訂單揀選隨機(jī)服務(wù)系統(tǒng)模型

2.1 模型假設(shè)與符號說明

2.1.1 模型假設(shè)條件

在建立模型前，對這里的倉庫揀選作業(yè)選取的各種策略進(jìn)行描述并做相應(yīng)假設(shè)：（1）倉儲布局、存儲與揀選路徑策略：在串行分區(qū)揀選系統(tǒng)、隨機(jī)存儲策略、S型揀選路徑下研究倉庫到達(dá)訂單分批。（2）訂單情況：這里研究單個訂單輸入過程符合泊松分布，訂單中包含的物品件數(shù)Si假設(shè)服從泊松分布。（3）服務(wù)方式：這里的訂單服務(wù)規(guī)則采用先到先服務(wù)對訂單進(jìn)行揀選服務(wù)；分區(qū)揀選系統(tǒng)的每個區(qū)有一位揀選者，而若每x個訂單成一批則揀選者的揀選能力一次可以完成揀選x個訂單的任務(wù)。（4）分批方式：分區(qū)揀選系統(tǒng)按照固定時間窗分批方式進(jìn)行分批。批訂單的到達(dá)服從參數(shù)為λtf泊松分布，假設(shè)最初系統(tǒng)中無訂單，隨著第一個訂單到達(dá)才開始服務(wù)訂單，揀選者完成當(dāng)前批次任務(wù)后方可揀選下批次訂單。

為了進(jìn)一步簡化研究問題，假設(shè)建立模型的其他條件為：（1）倉庫中儲存貨物的空間在此只考慮貨架的長度，其高度不被考慮；（2）揀選作業(yè)時間除考慮揀選者行走時間外，還分析到貨架上揀取物品花費(fèi)的時間，揀取一件物品時間包括抓取與尋找時間，揀取貨物時間設(shè)為常數(shù)；（3）每個訂單間物品件數(shù)相互無關(guān)系且隨機(jī)的；（4）每種貨物按隨機(jī)存儲策略等可能的被存儲在各個通道；（5）每種貨物具體存儲貨位是均勻隨機(jī)的分布于整個貨架；（6）每種貨物在貨位的存儲數(shù)量足夠滿足隨機(jī)到達(dá)訂單包含的物品數(shù)量需求，不會有缺貨現(xiàn)象；（7）假設(shè)揀選者的行走速度設(shè)為常數(shù)。

2.1.2 模型符號說明

為了統(tǒng)一計(jì)算，對模型中所要用到的符號進(jìn)行的定義，如表1所示。

表1 模型符號匯總表Tab.1 Summary of Model Symbols

2.2 訂單不分批揀選隨機(jī)服務(wù)系統(tǒng)模型

每個區(qū)到達(dá)的訂單按其所包含的物品種類選擇依次經(jīng)過Z1、Zi、Zn所有n個區(qū)中的某幾個區(qū)，如果訂單中沒有Z1區(qū)的物品，則可以直接進(jìn)入Zi區(qū)進(jìn)行揀選，不會涉及訂單的分割。訂單進(jìn)入第i個區(qū)的概率為pi，訂單的輸入流符合λ泊松分布，則進(jìn)入每個區(qū)的相當(dāng)于泊松過程的分流，進(jìn)入Z1、Zi、Zn區(qū)的訂單輸入流符合λZ1=λp1，=λpi，=λpn。

2.2.1 訂單輸入過程

就外部訂單輸入符合泊松過程進(jìn)行研究，串行分區(qū)揀選系統(tǒng)整體的訂單到達(dá)個數(shù)N(x)的概率計(jì)算方式為：

其中，λ＞0為符合泊松過程外部訂單到達(dá)率的均值。

2.2.2 平均服務(wù)時間

串行分區(qū)揀選系統(tǒng)的訂單揀選時間的計(jì)算需要考慮i個區(qū)的各自的揀選時間，整個訂單的完成時間是n個區(qū)揀選時間的加和［7］。揀選行走距離記為D(S)，揀選時間由揀選距離、行走速度以及揀取每件貨物時間決定，即：

基于式（2），可求出每個區(qū)的揀選時間(S)，進(jìn)而可得到一個訂單的期望揀選時間：

設(shè)期望揀選時間相對應(yīng)揀選時間的分布為G(t)，計(jì)算得到所有訂單的揀選時間υ1，υ2，…這些取值獨(dú)立同分布為一組離散時間序列，記為tk(k=1，2，…kmax)。

由揀選時間的分布計(jì)算串行分區(qū)所有單個平均服務(wù)時間，記為1μ，μ為單位時間內(nèi)服務(wù)的訂單個數(shù)，表示單個訂單依次進(jìn)入串行分區(qū)系統(tǒng)揀選時的n個訂單的總平均服務(wù)時間。

2.2.3 平均隊(duì)長

把第n個訂單被揀選服務(wù)完成離開串行分區(qū)系統(tǒng)時所留下的隊(duì)長記為qn，平均隊(duì)長為：

其中，串行分區(qū)揀選系統(tǒng)的服務(wù)強(qiáng)度ρ=λμ，σ2是服務(wù)時間分布G(x)的方差。

2.2.4 平均等待時間

串行分區(qū)揀選系統(tǒng)中在訂單揀選時間υn內(nèi)到達(dá)的訂單數(shù)加上等待時間wn內(nèi)到達(dá)的訂單數(shù)即為隊(duì)長qn。wn與υn獨(dú)立，令Wq(x)是wn的分布，則：

再結(jié)合式（6），得到平均等待時間：

2.3 訂單分批揀選隨機(jī)服務(wù)系統(tǒng)模型

在串行分區(qū)揀選系統(tǒng)中按照固定時間窗方式進(jìn)行訂單分批。假設(shè)訂單符合λ的泊松分布，只要時間長度夠tf（tf為常數(shù)）則該時間段內(nèi)到達(dá)的訂單成為一批。此時進(jìn)入Z1、Zi、Zn區(qū)的訂單輸入流符合

本節(jié)訂單分批揀選隨機(jī)服務(wù)系統(tǒng)模型中平均服務(wù)時間的研究思路與計(jì)算方法與上節(jié)訂單不分批揀選隨機(jī)服務(wù)模型中相對應(yīng)的部分基本一致，本節(jié)不再贅述。

2.3.1 批訂單輸入過程

對于串行分區(qū)揀選系統(tǒng)，固定時間窗的批訂單的整體輸入流是符合λtf的泊松分布，批訂單到達(dá)個數(shù)Nf(x)的概率計(jì)算方式為：

其中，λtf＞0為符合泊松過程外部訂單到達(dá)率的均值。

2.3.2 平均隊(duì)長

把第n個訂單被揀選服務(wù)完成離開串行分區(qū)系統(tǒng)時所留下的隊(duì)長記為，則平均隊(duì)長為：

2.3.3 平均等待時間

根據(jù)平均隊(duì)長與平均等待時間的關(guān)系以及先到先被揀選服務(wù)規(guī)則，可以求出串行分區(qū)揀選系統(tǒng)的平均等待時間，此部分計(jì)算流程與上節(jié)訂單不分批揀選隨機(jī)服務(wù)模型中相對應(yīng)的部分基本一致，不再贅述，直接寫出求解公式。

再結(jié)合式（10），得到平均等待時間：

綜上可以得出串行分區(qū)揀選系統(tǒng)的批訂單平均服務(wù)時間、平均隊(duì)長與平均等待時間，根據(jù)這些指標(biāo)可以與上節(jié)不分批揀選的方式進(jìn)行對比。

3 串行分區(qū)揀選系統(tǒng)訂單分批揀選仿真研究

3.1 仿真系統(tǒng)參數(shù)設(shè)計(jì)

研究人工揀選隨機(jī)服務(wù)系統(tǒng)的訂單分批問題，涉及過程較多，需對參數(shù)進(jìn)行合理設(shè)計(jì)。經(jīng)過實(shí)地調(diào)研某連鎖超市，將倉庫通道總數(shù)、貨架長度、貨架寬度、兩排貨架間的通道寬度、兩個存儲區(qū)域間的過道寬度以及貨架的后部過道寬度分別設(shè)置為72條、6m、0.8m、1.5m、3m以及1.5m。

假定在人工揀選情況下，倉庫一位揀選者行走速度V=50m/min，而揀取單件貨物所花費(fèi)的時間tp，經(jīng)過多次參數(shù)調(diào)試的仿真驗(yàn)證，并根據(jù)實(shí)際情況判斷選出參數(shù)數(shù)值在0.3min/件比較合適。此外，需進(jìn)一步確定訂單到達(dá)率以及訂單中包含的貨品件數(shù)。根據(jù)調(diào)研結(jié)果，發(fā)現(xiàn)訂單到達(dá)率按泊松分布均值最大取2個/min，顧客買商品的件數(shù)一般在5件左右，因此，訂單包含物品件數(shù)的均值λs按泊松分布設(shè)計(jì)為5。

3.2 仿真結(jié)果分析

分析對于串行分區(qū)的倉庫布局是三個分區(qū)是水平左中右并排放置，訂單依次通過三個區(qū)被揀選服務(wù)。三個分區(qū)的面積與所包含貨物周轉(zhuǎn)率都相同，此時每個訂單的揀選時間為三個區(qū)各自揀選時間的總和。

根據(jù)仿真系統(tǒng)參數(shù)設(shè)計(jì)及以上信息，在MATLABR2019a軟件環(huán)境下，以訂單到達(dá)率為0.2個/min為例，對固定時間窗訂單分批串行分區(qū)揀選隨機(jī)服務(wù)系統(tǒng)進(jìn)行仿真，從下文圖表中可以看到固定時間窗訂單分批操作下，服務(wù)系統(tǒng)各種指標(biāo)的變化情況。

3.2.1 服務(wù)時間分析

當(dāng)固定時間窗值＜50min時，訂單的平均服務(wù)時間隨著時間窗的增大而快速下降，如圖1所示。當(dāng)固定時間窗值＞50min之后，串行分區(qū)服務(wù)時間隨著時間窗取值的變大而緩慢減小，但整體還是下降趨勢。這是因?yàn)樵诜?wù)時間內(nèi)只有部分行走時間受分批時間窗取值的影響，而揀貨時間不受影響。隨著固定時間窗的逐漸增加，該時間窗內(nèi)包含的訂單個數(shù)也不斷增多，分批后所有訂單的總行走揀選距離隨著時間窗的增大而逐漸減少，行走時間縮短。因此，串行分區(qū)平均服務(wù)時間呈現(xiàn)下降的趨勢。

圖1 串行分區(qū)平均服務(wù)時間變化圖Fig.1 Change Chart of Average Service Time of Serial Partition

3.2.2 平均隊(duì)長分析

當(dāng)固定時間窗為50min時，單個訂單的平均隊(duì)長大約為10個，當(dāng)固定時間窗為360min時，訂單的平均隊(duì)長大約為55個，串行分區(qū)平均隊(duì)長整體隨著固定時間窗的增大而增大，呈現(xiàn)上升趨勢，如圖2所示。這是因?yàn)榇蟹謪^(qū)單個訂單到達(dá)必須等夠規(guī)定時長后，該時間段內(nèi)的訂單才能成一批進(jìn)入系統(tǒng)并依次通過三個區(qū)被揀選。隨著固定時間窗的取值增加，每個訂單需要等待時間也越久，相應(yīng)的該時間段內(nèi)等待的訂單數(shù)量會越多，整體隊(duì)長會變大，因此串行分區(qū)平均隊(duì)長后呈現(xiàn)逐漸上升的趨勢。

圖2 串行分區(qū)平均隊(duì)長變化圖Fig.2 Change Chart of Average Queue Length of Serial Partition

3.2.3 平均等待時間分析

當(dāng)固定時間窗為50min時，串行分區(qū)單個訂單的平均等待時間大約為20.90min，當(dāng)固定時間窗為360min時，串行分區(qū)訂單的平均等待時間大約為174.65min，串行分區(qū)訂單平均等待時間隨著固定時間窗的增大而逐漸增大，如圖3所示。等待時間由等待批訂單形成時間和批訂單形成后等待的服務(wù)時間兩部分組成，隨著固定時間窗的增大，每個訂單需要等待的機(jī)率越大，等待一批訂單形成的時間增加，總的等待時間變長，因此串行分區(qū)的平均等待時間逐漸上升。

圖3 串行分區(qū)平均等待時間變化圖Fig.3 Change Chart of Average Waiting Time of Serial Partition

3.2.4 綜合指標(biāo)分析

當(dāng)固定時間窗值小于50min時，串行分區(qū)訂單的綜合指標(biāo)隨著批量的增大而快速下降，如圖4、圖5所示。當(dāng)固定時間窗值為210min時，綜合指標(biāo)下降到最低點(diǎn)；當(dāng)固定時間窗值大于210min，隨著固定時間窗值的增加，綜合指標(biāo)逐漸上升，此時串行分區(qū)系統(tǒng)訂單分批的最優(yōu)固定時間窗為210min。不同的時間窗分批操作，實(shí)際變換的是訂單成批的數(shù)量大小，以單個訂單維度看，其總的訂單個數(shù)是不變的，因此，單個訂單平均服務(wù)時間的變化趨勢與總服務(wù)時間是一致的。

圖4 串行分區(qū)單個指標(biāo)變化圖Fig.4 Change Chart of Single Index of Serial Partition

圖5 串行分區(qū)綜合指標(biāo)變化圖Fig.5 Change Chart of Comprehensive Index of Serial Partition

繼續(xù)分析訂單到達(dá)率為0.08、0.1、0.2、0.5、0.8、1、1.5、2時，對應(yīng)的串行分區(qū)揀選系統(tǒng)訂單不分批和按固定時間窗分批的服務(wù)系統(tǒng)的指標(biāo)變化情況，分別匯總，如表2、表3所示。

表2 串行分區(qū)訂單不分批揀選結(jié)果匯總表Tab.2 Summary of Batch Picking Results of Serial Partition Orders

表3 串行分區(qū)固定時間窗訂單分批揀選結(jié)果匯總表Tab.3 Summary of Batch Picking Results of Serial Partition Fixed Time Window Orders

其中，串行分區(qū)固定時間窗的最高限制為360min。

其中，串行分區(qū)固定時間窗的最高限制為360min。

與串行分區(qū)訂單不分批的系統(tǒng)指標(biāo)相比，雖然訂單分批后的平均等待時間與平均隊(duì)長都是呈現(xiàn)增加趨勢，但單個訂單的平均服務(wù)時間是呈下降的趨勢，說明在串行分區(qū)揀選系統(tǒng)中，固定時間窗訂單分批方式優(yōu)于單個訂單依次揀選處理方式。另外，訂單到達(dá)率為0.2個/min時，串行分區(qū)單個訂單處理的系統(tǒng)服務(wù)強(qiáng)度大約為94%，采用固定時間窗分批后，系統(tǒng)服務(wù)強(qiáng)度減少至39%，相當(dāng)于串行分區(qū)3個區(qū)的3位揀選者在有大量休息時間的情況下即可完成這么多訂單揀選任務(wù)量。

此外，只有極少數(shù)論文將整體在線訂單處理視作排隊(duì)系統(tǒng)并采用時間窗分批方式進(jìn)行訂單揀選。文獻(xiàn)[8]對訂單分批研究是近年來該領(lǐng)域中較為全面的研究，他假設(shè)訂單到達(dá)是泊松輸入、訂單分批是先到先服務(wù)的隨機(jī)服務(wù)系統(tǒng)（M/Gk/1），采用2-階矩近似計(jì)算公式，依據(jù)文獻(xiàn)[9]所設(shè)計(jì)的揀選系統(tǒng)的參數(shù)對模型進(jìn)行了仿真計(jì)算。文獻(xiàn)[10]又在前面的基礎(chǔ)上進(jìn)一步設(shè)計(jì)出一個基于2個分區(qū)的倉庫系統(tǒng)模型，并計(jì)算出每個訂單的平均揀選時間，估算最優(yōu)批量的大小和隨機(jī)訂單的等待時間，仿真結(jié)果，如圖6所示。

圖6 不同服務(wù)時間分布的平均吞吐量時間（服務(wù)時間的近似值）Fig.6 Average Throughput Time for Different Service Time Distributions（with the Approximation Value of the Service Time）

訂單成批的等待時間、服務(wù)的等待時間和揀選時間是影響訂單平均吞吐量時間的主要因素。當(dāng)訂單批量較大時，訂單成批的等待時間和揀選時間較少，但服務(wù)的等待時間可能會較多，這種情況下可以說明存在最優(yōu)訂單分批。在模型設(shè)計(jì)中，他們分別模擬了含有2個分區(qū)的倉庫6通道、10通道、16通道的情況，雖然結(jié)果較為精確，可實(shí)際應(yīng)用，但現(xiàn)在隨著電商的日益發(fā)展，他們設(shè)計(jì)的參數(shù)和估算的最佳批量已不能滿足現(xiàn)在倉庫的需求。另外，他們并沒有對倉庫的兩個分區(qū)進(jìn)行詳細(xì)的設(shè)定，例如是串行分區(qū)還是并行分區(qū)，忽略了可能存在多個訂單揀選者同時在同一個揀貨區(qū)揀選貨物的情況，這會導(dǎo)致通道內(nèi)過度擁擠。在所模擬的串行分區(qū)揀選系統(tǒng)下，揀選者只有在一個區(qū)域內(nèi)完成揀選工作才會進(jìn)入到下一個區(qū)域，通道數(shù)多達(dá)72條，模擬了多種訂單到達(dá)率，設(shè)定的其它參數(shù)大小更加貼合現(xiàn)在一般電商倉庫的需求，所采用的固定時間窗分批方式在提高揀選效率的同時也有效避免了通道擁擠的情況。

4 總結(jié)

分析了串行分區(qū)揀選系統(tǒng)下不采用訂單分批方式與采用固定時間窗訂單分批方式服務(wù)系統(tǒng)各種指標(biāo)變化情況，并與其它方法進(jìn)行比較分析。總的來看采用的固定時間窗訂單分批操作的服務(wù)系統(tǒng)強(qiáng)度更小，大約能降低30%左右，說明固定時間窗分批方式對于串行分區(qū)是有效的，合理結(jié)果同時也說明了模型的有效性。

揀選成本在倉儲成本中占據(jù)較大比例，而應(yīng)用分批策略又可進(jìn)一步減少揀選作業(yè)的總時間。在考慮訂單到達(dá)隨機(jī)性情況下研究分區(qū)揀選系統(tǒng)的訂單分批策略，對企業(yè)而言，可以進(jìn)一步提高揀選效率，優(yōu)化揀選作業(yè)系統(tǒng)，提高客戶服務(wù)滿意度。而對于整個物流行業(yè)倉庫揀選環(huán)節(jié)的優(yōu)化，物流揀選效率的有效提升以及最大化減少物流成本而言也是很有現(xiàn)實(shí)意義的。