動態并行分區揀選系統下訂單分批問題研究

胡小林，徐菱,2

（1.西南交通大學 交通運輸與物流學院，四川 成都 610031；2.西南交通大學 綜合交通運輸智能化國家地方聯合工程實驗室，四川 成都 610031）

1 引言

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

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

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

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

2 研究問題與模型構建

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

2.1 問題描述與符號說明

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

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

模型假設如下：

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

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

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

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

（5）需求點位置和時間窗已知。

相關符號說明如下：

V：需求點集合，V={v1,v2,...,vn}；

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

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

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

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

決策變量：

2.2 約束條件

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

（2）容量約束

（3）揀選約束

①批次分配約束。每一個訂單必須分配一個揀選批次，每一個揀選批次必須分配到相應的揀選分區，即：

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

③變量取值約束

2.3 目標函數

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

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

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

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

通道揀選距離計算如下：

圖2 揀選距離計算示意圖

則bmoh的揀選距離為：

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

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

（2）等待時間twait。在揀選階段采用并行揀選分區系統會導致需求拆分揀選，同一個需求點的訂單分屬于不同的揀選分區，并分配給不同的人員揀選，因此在揀選分揀階段會產生屬于同一輛車需求點的等待時間。

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

3 算法設計

3.1 訂單分批算法HB

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

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

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

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

步驟3：種子訂單選擇。依據PDD-A-SL規則選擇種子訂單vseed。

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

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

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

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′中根據LCS規則選擇訂單vir，返回步驟6。

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

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

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

3.2 批次分配算法HBD

本文根據批次訂單存儲位置進行動態分區，對每一個揀選批次進行通道分配，使得每一個揀選批次的分區揀選時間均衡，縮短訂單的等待時間。

圖3 訂單分批流程圖

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

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

步驟2：位置標注。根據bm中訂單vir的存儲位置，計算各個通道訂單的體積與重量，并標注各個訂單位置，找出各個通道距離前端和后端通道的最遠存儲位置

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

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

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

3.3 分揀優化算法HSO

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

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

步驟2：分揀臺分配。根據VDT-D分配分揀臺。

步驟3：指標計算。計算Vbmoh中所有訂單的difvir。

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

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

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

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

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

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

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

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

4 仿真實驗及其結果分析

4.1 實驗參數設計

為驗證模型和算法的有效性，將優化分揀包裝順序但分區固定的系統（算法A）、不優化分揀包裝順序但考慮靜態分區揀選系統（算法B）、不優化分揀包裝順序的靜態分區揀選系統（算法C）與本文揀選系統（算法H）進行對比，其他參數設置如下：

（1）需求點數量V=60，訂單數量為200，即一個需求點有多個訂單；

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

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

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

算法運用MATLAB R2016a在操作系統為Window10 64-bit、CPU為16GB的計算機上運行。

4.2 實驗結果分析

為確保實驗結果的可靠性，隨機生成3種不同的訂單規模環境，通過設置HB算法中綜合相似度不同的α和β的取值，對比不同相似度參數環境下的批次揀選路徑時間，尋找最優的綜合相似度參數取值。

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

表1 不同參數下數據

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

圖4 不同參數下指標變化圖

本文提出考慮優化分揀包裝順序和分區揀選時間均衡的動態并行分區揀選系統，為分析該系統的效率，在α=0.6、β=0.4取值下，將算法A、B、C與算法H進行對比，分別設置n=200,n=500,n=800,n=1100四種訂單規模，對四種算法的批次平均等待時間、批次路徑時間標準差、分揀包裝時間和訂單處理時間進行對比分析，數據見表2。

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

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

表2 不同參數下指標數據

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

綜上所述，可得出如下結論：

（1）本文提出的算法可以有效解決訂單分批與批次調度問題，保證所有的訂單在揀選截止時間之前揀選完成，并且經過多次實驗發現，綜合相似度參數最優取值為α=0.6、β=0.4；

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

5 結語

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