考慮完成期限的電子商務在線訂單分批模型及算法

王旭坪，張 珺，馬 駿

1 大連理工大學 系統工程研究所，遼寧 大連 116023 2 大連理工大學 商學院，遼寧 盤錦 124221

考慮完成期限的電子商務在線訂單分批模型及算法

王旭坪1,2，張 珺1，馬 駿1

1 大連理工大學 系統工程研究所，遼寧 大連 116023 2 大連理工大學 商學院，遼寧 盤錦 124221

在電子商務在線訂單揀選系統中，訂單到達時間和訂購商品等信息未知。針對揀選設備容量、員工人數等資源有限約束情況，研究在何時、對多少訂單進行分批優化，以保證在訂單完成期限前以最短的時間揀出最多的訂單。構建考慮訂單完成期限的在線訂單分批混合整數規劃模型，以最小化平均有效訂單服務時間，采用改進的固定時間窗訂單分批啟發式規則求解模型，定義剩余操作時間在[前置時間，配送準備時間]內的訂單為緊急訂單，構建綜合考慮緊急程度和相似度因素的在線訂單分批算法。采用某配送中心14：00～18：00時間段內以泊松分布(λ=17)隨機生成的訂單進行數據實驗，將實驗結果與傳統固定時間窗在線訂單分批算法進行比較。研究結果表明，考慮完成期限時，系統揀選配送的訂單數量更多，總服務時間和平均有效訂單服務時間更短，且出現延遲訂單的數量更少，延遲時間更短。揀選員工人數的增多在不同程度上提高配送率，且考慮完成期限時，配送率提高幅度要大于傳統算法；但隨著人數的增加，配送率的提高幅度呈降低趨勢。

電子商務；在線訂單揀選；訂單分批；完成期限

1 引言

在人到貨訂單揀選系統中，訂單分批是將1組訂單集合分批為幾個小的訂單子集合，且每個批次由1名揀選員工進行揀選[1]。當訂單中包含的商品足夠多時，可由1名揀選員工完成1個訂單，即按單揀選。但在電子商務環境下，訂單具有小批量、高頻次等特征，有必要采用訂單分批策略減少總服務時間，提高揀選效率。且電子商務訂單到達時間和訂購商品等信息提前未知，管理人員不能等到訂單全部到達后再揀選，而應進行實時的訂單分批決策。同時顧客對商品到達時間更為敏感，為保證訂單出庫時間和顧客最終收貨時間，配送中心會針對目的地的不同設置不同的配送車輛離開時間，即訂單的完成期限。因此，有必要研究考慮完成期限的在線訂單分批優化方法，將總服務時間和訂單實際配送數量同時作為衡量系統運作效率的因素。本研究探討電子商務環境下考慮完成期限的在線訂單分批優化策略，擬解決的關鍵問題是，在配送時間確定的情況下，在何時、對多少訂單、采用怎樣的分批策略，以保證在配送車輛離開前以最短的服務時間配送出最多的訂單，從出庫環節優化電子商務物流配送系統。

2 相關研究評述

訂單揀選是電子商務物流倉儲作業的重要環節之一，是依據顧客訂單信息準確迅速地將貨物從存儲位中揀出的過程[1]。傳統的倉儲操作中，訂單揀選是最耗費時間和勞力的一項工作，成本約占總倉儲費用的55%[2]。國內外學者對訂單揀選效率優化方法的研究集中在貨位設計[3-5]、揀選路徑[6-9]、訂單分批[10-11]和分區揀選[12-13]4種，但Petersen等[14]認為訂單分批策略對揀選效率的提升更快。

訂單分批優化最常見的優化目標是，在設備容量資源約束下最大化其揀選系統服務水平，服務水平的衡量指標包含訂單服務時間、完成時間、延遲時間等。訂單信息已知情況下進行的訂單分批優化稱為離線訂單分批問題，由于訂單分批問題為NP-hard問題，無法用精確算法求解[15]，當前優化算法可大概分為5類。①優先規則算法[16]，首先給顧客訂單分配優先級，再根據優先級別對訂單進行合并操作，并確保合并的批次不超過最大容量限制；②種子算法[13,17]，包括種子訂單選擇階段和訂單合并階段；③節約算法[18]，計算兩訂單合并后行走距離比單獨揀選的節約值，對節約從大到小進行排序，選取節約值最大的一對訂單生成揀選批次；④啟發式算法，如遺傳算法[19]、蟻群算法[20]、貪婪算法[21]等；⑤數據挖掘方法，Chen等[22]介紹了一種新的訂單合并方法，基于關聯規則分析構建訂單合并的整數規模模型，以最大化訂單間的支持度；Hsieh等[23]基于數據挖掘中的K-均值聚類和自組織神經網絡分類方法，構建了K-均值訂單合并(KMB)和自組織神經網絡訂單合并(SOMB)兩種新的訂單合并規則。

但電子商務環境下，訂單信息提前未知，企業需對到達的訂單進行實時處理。此類訂單分批問題又稱為在線訂單分批問題，所采用的分批策略可分為固定時間窗分批規則和可變時間窗分批規則。固定時間窗是將在某一固定時間范圍內到達的訂單進行合并生成揀選批次。Henn[20]和Bukchin等[24]分別從最小化總完成時間和最小化訂單延遲時間的角度決定訂單分批的開始時間。可變時間窗則是等待訂單到達一定量后，將這些訂單合并生成揀選批次。Chew等[25]、Le-Duc等[26]和Xu等[27]采用排隊論等方法優化每一個批次需揀選訂單數量。也有學者在訂單分批優化時考慮完成期限約束。Tsai等[19]構建以行走距離成本和提前、延遲完成懲罰成本之和最小為目標的訂單分批優化模型，并采用多階段遺傳算法求解；Henn等[28]將訂單分批和分配排序問題進行聯合優化，以最小化訂單的總延遲時間，并構建局部迭代搜索和基于屬性的爬山算法兩種啟發式方法求解模型；Azadnia等[29]考慮訂單的完成期限，構建帶權重的關聯規則算法計算訂單間的關聯度，構建訂單間關聯度最大化的訂單分批優化模型，采用求解旅行商問題的遺傳算法求解合并批次的最優揀選路徑，最后采用遺傳算法對生成批次揀選順序進行排序以最小化延遲時間；馬士華等[30]將延遲制造思想引入到配送中心揀貨作業中，提出基于時間延遲的動態時窗分批策略。總的來說，上述訂單分批優化研究為后續的工作者提供了豐富的可借鑒策略，但多集中在訂單信息已知下的離線訂單分批策略[10-19]，而少數在線分批優化僅假設揀選人員數量為1名[20,24-27]，且未綜合考慮揀選效率和配送效率對系統的影響[28-30]。因此，本研究在人員數量為多名的情況下，以總服務時間和訂單實際配送數量作為優化目標，構建考慮完成期限的在線訂單分批優化模型。面臨如下決策問題，①合并揀選已經到達的訂單還是繼續等待更多的訂單到達；②對已到達訂單采用何種分批策略；③合并批次如何分配給有限的揀選員工。

本研究構建考慮訂單完成期限的在線訂單揀選分批優化模型，最小化平均有效訂單服務時間；采用改進的固定時間窗訂單分批啟發式規則求解模型，即依據不同訂單完成期限的緊急程度，構建緊急和非緊急情況下的兩種不同分批算法；最后通過數據實驗，從服務時間、完成訂單數量、有效訂單數量、延遲時間等多方面，將本研究算法與傳統算法分批結果進行對比分析，以證明模型和算法的有效性，為倉儲管理部門提高訂單處理服務質量提供決策支持。

3 考慮完成期限的在線訂單分批優化模型

3.1 問題描述和假設

圖1為在線訂單揀選系統示意圖，分為訂單分批系統和批次操作系統。

訂單隨機到達，進入訂單分批系統，采用考慮完成期限的在線訂單分批策略生成合并批次。批次進入操作系統，并按照先來先服務規則分配給空閑員工揀選；若無空閑員工，則排隊等待。最后按單進行復核打包后，準備裝車配送。系統中涉及到的時間如下。

到達時間，即訂單進入訂單分批系統時間；

進入時間，即訂單合并生成揀選批次后進入操作系統的時間；

分批時間，即生成的揀選批次中最早訂單到達時間與進入時間之差；

開始時間，即合并批次分配給空閑員工揀選的時間點；

等待時間，即合并批次進入操作系統等待服務的時間；

服務時間，即員工完成合并批次所需時間，包含揀貨時的行走時間、揀取時間和準備時間等；

結束時間，即服務完成后的時間點；

剩余時間，若結束時間早于離開時間(完成期限)，則兩者差值為剩余時間；

延遲時間，若結束時間晚于離開時間(完成期限)，則兩者差值為延遲時間。

此揀選系統的特征可概括為，訂單的完成期限由其所屬目的地配送區域決定，即每個配送區域運輸車輛的離開時間固定；訂單陸續進入訂單分批系統，訂單到達信息提前未知；倉庫雇傭員工完成揀選操作，且員工數量有限；員工只有完成當前批次任務后，才能進行下一個批次任務。要解決的關鍵問題是，如何合理進行訂單分批和批次的分配，以最小化完成訂單的總服務時間；在各配送區域車輛離開前揀出的最多訂單數量，即有效訂單最多。基于上述分析，模型的假設條件如下。①配送中心的揀選區域布局見圖2，倉庫類型為單區型，通道的入口在倉庫的最左端，且每個通道的寬度相同；②訂單信息提前未知；③揀選人員數量有限，允許出現訂單合并批次排隊等待；④采用遍歷型的揀選路徑策略，訂單完成時間考慮行走時間、揀取時間和配送準備(復核、打包)時間；⑤由于各訂單的配送期限不同，允許出現訂單完成后配送車輛已經離開的情況；⑥配送車輛離開前某一段時間(設為準備時間)內到達的訂單，直接列入第二天的揀選任務；⑦訂單中至少包含一個商品，且在合并的過程中，需保證訂單的完整性，即不得對訂單進行分割；⑧每個商品的體積相同，每種商品只能存儲在一個貨架上，揀選員工行走在通道的中央同時從左右兩邊揀選商品；⑨生成的訂單合并批次的容量不得超過揀選推車的容量上限；⑩揀選員工已知揀選任務單中的商品存儲位置。

圖1 在線訂單揀選系統示意圖Figure 1 Diagram of On-line Order Picking System

圖2 揀選區域布局Figure 2 Layout of Picking Area

3.2 參數定義

本研究構建考慮完成期限的在線訂單分批優化模型，首先對模型中的常量和變量作如下定義。

常量：

N為訂單集合；

M為訂單合并批次集合；

L為揀選人員集合；

O為配送目的地集合；

tpack為配送準備時間(復核、打包等所需時間)；

qi為訂單i中包含的商品數量；

Qb為每個合并批次能容納的最大商品數量；

vtravel為單位時間揀選人員的行走距離；

vpick為單位時間揀選員工尋找并揀出商品數量；

zih為0-1變量，表示訂單i是否屬于目的地h，如果訂單i屬于目的地h，zih=1，否則zih=0；

變量：

disj為完成批次j揀選任務所需行走距離(揀選路徑優化策略采用遍歷策略)；

Tservice為完成訂單的總服務時間；

R為有效訂單數量，即揀選并裝車配送出的訂單數量；

xij為0-1變量，表示訂單i是否分配給批次j，如果訂單i分配給批次j，xij=1，否則xij=0；

yjk為0-1變量，表示批次j是否分配給揀選人員k，如果批次j分配給揀選人員k，yjk=1，否則yjk=0；

ri為0-1變量，表示訂單i是否在配送車輛離開前完成，如果訂單i在配送車輛離開前完成，ri=1，否則ri=0。

3.3 構建模型

基于上述分析，構建考慮完成期限的在線訂單分批優化模型，以在有限的時間里完成更多的有效訂單，提高揀選和配送效率。

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

目標函數(1)式為最小化有效訂單的平均服務時間；約束條件(2)式和(3)式分別為完成訂單總服務時間和有效訂單數量的表達式；約束條件(4)式～(7)式為對訂單分批和配送目的地的限制，即保證一個訂單只能分配給一個合并批次，一個合并批次只能分配給一個揀選人員，一個合并批次商品量不超過上限Qb，一個訂單只能配送到一個目的地；約束條件(8)式定義批次j的服務時間，為行走時間、揀選時間和配送準備時間之和；約束條件(9)式和(10)式為對揀選人員分配批次的限制，即批次j僅分配給最早完成前期工作任務的揀選人員；約束條件(11)式～(13)式為對批次j開始服務時間的限制，即批次j應在其批次內的所有訂單到達后開始，只有揀選完批次(j-1)才能開始下一個批次，批次j開始服務時間為該批次進入批次操作系統時間與等待時間之和；約束條件(14)式表明，訂單i的結束時間為其所屬批次j的開始時間與服務時間之和；約束條件(15)式表示，如果訂單i在配送時間到達前完成，則ri=1，否則ri=0。

4 基于緊急程度的在線訂單分批算法

4.1 整體算法設計思路

訂單分批問題一直被認為是NP-hard問題，無法用精確算法求解[15]。本研究基于固定時間窗訂單分批規則，綜合考慮訂單的緊急程度和相似度等因素，構建考慮訂單緊急程度的固定時間窗訂單分批啟發式算法，實現對固定時間窗內到達訂單的分批優化，以利用較短的時間在各配送目的地車輛離開前完成更多訂單。

(1)定義訂單i的緊急程度urgent為

(16)

(2)定義訂單間的相似度

本研究選取種子算法訂單分批規則中的兩兩訂單相同通道數系數simiii′作為衡量訂單間相似度的指標，具體公式為

(17)

其中，Aislei為完成訂單i需通過的通道數量，Aislei′為完成訂單i′需通過的通道數量，|Aislei∩Aislei′|為訂單i與訂單i′間相同揀選通道數量；|Aislei∪Aislei′|為訂單i與訂單i′合并后總揀選通道數量。

算法整體思路見圖3。

圖3 算法流程圖Figure 3 Flowchart of the Algorithm

4.2 基于通道相似度的訂單分批優化算法

若時間窗內到達的訂單不包含緊急訂單，則采用基于通道相似度的訂單分批優化算法。從全局的角度考慮訂單間的相似性，每次進行訂單合并時都選取訂單集合中相似度最高的兩個訂單，合并后生成的新訂單重新放回訂單集合中，且在合并過程中需滿足設備容量約束。設在時間窗內到達的訂單集合為OS，具體分批步驟如下。

步驟1 計算相似度。若訂單集合中包含不止1個訂單，計算訂單集合OS中各訂單間相似度；否則運行步驟6。

步驟2 選擇訂單。選擇相似度最大的訂單Oi和Oj，容量分別為Qi和Qj。

步驟3 訂單合并。判斷訂單分批的容量約束，即

①若Qi+Qj

②若Qi+Qj=Qb，則滿足容量約束，合并{Oi,Oj}后生成揀選批次，將Oi和Oj從訂單集合刪除，返回步驟1；

③若Qi+Qj>Qb，則不滿足容量約束，繼續運行。

步驟4 選擇其他訂單進行合并。選擇Oi與Oj間容量較大的訂單(如Oi)，計算Oi與其他訂單間的相似度。如果存在與Oi相似度較大的訂單Om，滿足容量約束Qi+Qm≤Qb，則合并{Oi,Om}后生成揀選批次，將Oi和Om從訂單集合刪除，返回步驟1；否則繼續運行。

步驟5 直接生成揀選批次。如不存在滿足容量約束的訂單與Oi合并，則直接將Oi生成揀選批次，將Oi從訂單集合中刪除，返回步驟1。

步驟6 訂單集合剩余1個訂單，直接將其生成揀選批次。

步驟7 結束。

4.3 基于緊急程度的訂單分批優化算法

若時間窗內到達的訂單包含緊急訂單，采用基于緊急程度的訂單分批優化算法。設在時間窗內到達的訂單集合為OO，具體分批步驟如下。

步驟1 選取種子訂單。若訂單集合存在不止1個訂單，選取緊急程度最高的訂單為種子訂單Oseed，容量為Qseed；否則運行步驟5。

步驟2 訂單合并。計算種子訂單Oseed與其他訂單間的相似度，選取相似度最大的訂單Oi，容量為Qi。設Oseed與Oi合并后的服務時間為service_time(Oseed,Oi)，進入時間為enter_time(Oseed,Oi)，若滿足配送期限要求(分批時不考慮批次操作時可能的等待時間)，則

service_time(Oseed,Oi)+enter_time(Oseed,Oi)≤

mindepart_time(Oseed,Oi)

判斷訂單分批的容量約束，即

①若Qseed+Qi

②若Qseed+Qi=Qb，則滿足容量約束，合并{Oseed,Oi}生成揀選批次，將Oseed和Oi從訂單集合中刪除，返回步驟1。

③若Qseed+Qi>Qb，則不滿足容量約束，繼續運行。

步驟3 不滿足配送期限要求，選擇其他訂單生成揀選批次。選擇訂單集合中與Oseed相似度較大的訂單Oi′。若同時滿足配送期限約束和容量約束，合并{Oseed,Oi′}生成揀選批次，將Oseed和Oi′從訂單集合中刪除，返回步驟1；否則繼續運行。

步驟4 直接生成揀選批次。若不存在滿足配送期限約束或容量約束的訂單與Oseed合并，則直接將Oseed生成揀選批次，將Oseed從訂單集合中刪除，返回步驟1。

步驟5 訂單集合OO剩余1個訂單，直接將其生成揀選批次。

步驟6 結束。

5 傳統在線訂單分批算法

將傳統基于固定時間窗的種子算法[16]與本研究提出的算法進行比較，主要區別體現在僅以訂單揀選效率作為優化目標，未考慮訂單的緊急程度。種子算法主要分為種子訂單選擇階段和合并訂單選擇階段，當前有關種子訂單的選擇規則和訂單合并的規則有很多，本研究采用(17)式相同通道系數作為訂單間相似度的度量方式，而種子訂單的選擇規則采用隨機規則。生成的揀選批次同樣采用先來先服務規則分配給空閑揀選員工，并最終打包配送到顧客手中。訂單分批具體步驟如下。

步驟1 收集到達訂單。開始時間為tstart，設在[tstart,tend](tend=tstart+tb)內到達的訂單集合為O′。

步驟5 更新時間窗。更新tstart=tend，返回步驟1；如到達系統結束時間，運行步驟6。

步驟6 結束。

6 數據實驗和結果分析

6.1 實驗參數設置

目前對電子商務在線訂單分批問題尚未有標準的驗證數據，且不同商家訂單量差異較大，難以采用統一的數據衡量。為驗證模型和算法的有效性，本研究盡量貼近實際，訂單到達情況服從泊松分布；考慮電商訂單小批量、高頻次且多數商家日交易量可達萬單等特征，假設平均每分鐘到達訂單數量為17，滿足泊松分布，即λ=17，每單包含商品數量服從[1,3]的隨機分布；由于車輛離開時間常為17：00～18：00，按照λ=17的泊松分布隨機產生14：00～18：00時間段內到達的訂單，圖4給出對隨機生成訂單在不同時段數量的統計。揀選區域參數見表1，其中包含10個揀選通道和1 000種商品，每列貨架存放50種商品，每個員工一次揀選的最大商品容量為100個。假設每個商品的體積相同，且只能存儲在一個貨架上；揀選員工行走在通道的中央，以便同時從左右兩邊揀選商品；員工通常從最左邊的入口進入，揀取完所有商品后回到入口處。

表1 揀選區域參數Table 1 Parameters of the Picking Area

算法參數設置如下。分批時間窗大小tb為10分鐘；訂單標記為緊急訂單的前置時間tadv為60分鐘；配送準備時間tpack為10分鐘；存在3個不同的配送區域，訂單所屬配送區域滿足隨機分布；各配送區域運輸車輛的離開時間分別是17：00、17：30和18：00。

圖4 各時段訂單到達數量統計Figure 4 Summary of the Number of Arrival Orders in Each Time Interval

6.2 結果分析

本部分將考慮完成期限與不考慮完成期限兩種情況下所得分批結果進行對比分析。不考慮完成期限時直接采取基于通道相似度的訂單分批算法，以最小化平均完成訂單服務時間為目標。當進入訂單分批系統生成合并批次后，可得批次數量、完成訂單量、總服務時間等。兩種情況下合并批次實驗結果見表2，合并批次數量分別為94和86，完成訂單量為3 363和3 589。考慮配送期限時，生成的批次數量大于不考慮配送期限的情況。主要原因是，為了保證緊急程度較高的訂單在運輸車輛離開前揀選完成，系統會根據配送期限約束，單獨將緊急訂單生成揀選批次或只選取少量訂單與其合并，從而造成合并批次數量較多。而考慮完成期限時，完成訂單數量略少于不考慮配送期限的情況，考慮完成期限的訂單完成率為80.822%，不考慮完成期限的完成率為86.253%。原因在于，基于緊急程度的訂單分批優化算法將剩余操作時間小于配送準備時間的訂單直接列入第2天的揀選任務，使實際進行操作的訂單量減小。揀選完這些合并批次所需總服務時間分別為614分鐘和643分鐘，說明考慮完成期限時，完成生成的合并任務所需耗費的服務時間更少，效率更高。

表2 兩種情況下合并批次實驗結果Table 2 Merged Batching Results of Two Situations

當生成的合并批次進入批次操作系統，將揀選批次分配給揀選員工完成后，即可得到有效訂單量、平均有效訂單服務時間、延遲時間等。由于揀選員工數量會影響等待時間、有效訂單數量等，本實驗設配送中心的揀選員工分別為2人～6人，分析不同雇傭情況下的實驗結果。基于不同揀選員工數量的批次操作實驗結果見表3，兩種不同的分批情況下幾個評價指標變化趨勢基本一致，隨著員工數量的增加，進入系統的合并批次所需等待時間減少，相應的平均有效訂單服務時間、延遲時間隨之減少，有效訂單量和剩余時間隨之增加。增加揀選員工人數能不同程度增加訂單揀選效率，當員工數從2人增至3人時，等待時間減少80%以上，延遲時間減少90%以上，但雇傭成本會隨之增加。另外，通過配送率可以看出，當員工數從2人增加到4人時，兩種不同情況下的配送率提高幅度分別為26.532%和26.772%；但當員工從4人增加到6人時，提高幅度只有0.269%和0，此時為提高配送率而增加雇傭成本意義不大。

通過對兩種分批結果比較可以看出，當揀選員工從2人逐漸增加到6人時，考慮完成期限揀出的有效訂單數量分別是2 240、3 048、3 344、3 347、3 353，相較不考慮完成期限時分別增加40、70、30、33、39；而兩種不同分批策略下的總服務時間分別為641分鐘和643分鐘，說明考慮完成期限的訂單分批策略能在更短的服務時間里揀選并配送出更多的訂單。同時在不同的雇傭情況下，考慮完成期限情況下的剩余時間要大于不考慮完成期限，使員工有更寬裕的配送準備時間。從表3可以看出，本研究構建的模型和算法很大程度上減少了訂單延遲時間，當雇傭人數為6人時，延遲時間減少比例高達98.404%。另外，由于生成批次數量多而每個批次包含的平均訂單量少，考慮配送期限時的排隊等待時間略大。

延遲時間一般作為評價訂單揀選系統效率的一個常用指標[25-30]，本部分對揀選員工人數為6人時存在延遲訂單的合并批次進行分析。員工為6人時的延遲訂單信息見表4，17：00、17：30和18：00三列分別表示此配送期限的訂單數量；延遲時間為該批次結束時間與最早離開時間之差，黑體數字為存在延遲的訂單數量。在不考慮配送期限的情況下，有17組合并批次存在延遲，總延遲訂單數量為275個，總延遲時間為2 255分鐘。考慮配送期限的情況下，有7組合并批次存在延遲情況，延遲訂單總量為10個，降低96.364%；總延遲時間為35分鐘，降低98.448%。可以看出本研究構建的模型和算法能有效地減少延遲訂單數量和延遲時間。

表3 基于不同揀選員工數量的兩種情況下批次操作實驗結果Table 3 Batching Operation Results of Two Situations under Different Number of Pickers

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

(1)考慮配送期限時，完成的訂單數量小于不考慮配送期限的情況，且總服務時間小于不考慮配送期限的情況；

(2)考慮配送期限時，揀選出的有效訂單數量更多，平均有效訂單服務時間更短；

(3)考慮配送期限時，出現延遲訂單的數量更少，延遲時間更短；

(4)隨著雇傭揀選人員數量的增多，批次操作系統揀出的有效訂單量增大，合并批次排隊等待揀選的時間減少，完成訂單延遲時間減少，但雇傭成本增加；

(5)當揀選人員為4人時，考慮完成期限情況下訂單配送率為80.365%，為該數據實驗的最優員工數量。

實驗結果驗證了模型和算法的有效性，考慮完成期限的訂單分批優化策略有利于在運輸車輛離開前以更短的時間揀出更多的訂單，從出庫環節提升了電子商務物流配送速度。

7 結論

針對電子商務環境下訂單實時到達的情況，平衡訂單開始揀選時間和揀選量的關系，同時綜合考慮訂單離開時間，從配送中心運作環節提高電子商務物流配送效率。通過構建考慮完成期限的在線訂單分批優化模型，并采用基于訂單緊急程度的固定時間窗訂單分批啟發式算法，實現對固定時間窗內到達訂單的分批優化。

研究結果表明，在制定分批規則時考慮訂單完成期限，有利于縮短完成時間和延遲時間，增加有效訂單量，在運輸車輛離開前以更短的時間揀出更多的訂單；同時雇傭人數的增多在不同程度上提高了配送率，但隨著人數的增加配送提高率呈降低趨勢，因此在雇傭員工時需綜合考慮雇傭成本和配送率間的關系。值得一提的是，固定時間窗的訂單分批規則更適用于訂單到達數量波動較小的情況，在波動較大的情況下，需綜合考慮訂單到達數量和時間的關系，采用時間-量混合的訂單分批規則求解模型，這樣保證了在不同的訂單到達情況下可以采用本研究的模型和算法。

綜上所述，本研究從倉儲配送中心存在的實際操作問題出發，綜合考慮配送車輛離開期限和訂單分批合并效率，有助于加深對訂單揀選系統的理解，對改進訂單分批優化策略具有理論分析價值和實踐指導意義，為倉儲管理部門提高訂單處理速度提供決策支持。本研究采用固定時間窗分批規則，未考慮訂單的波動性對揀選效率的影響，更復雜的在線分批規則可能同時考慮固定時間窗和固定訂單量的混合分批規則。另外，隨著顧客對訂單到達時間要求的提升，可從在線訂單揀選和配送調度整合優化方面開展進一步的研究。

表4 揀選員工人數為6人時的延遲訂單信息Table 4 Delayed Orders′ Information with Six Pickers

注：不考慮完成期限的情況下，總延遲時間=延遲批次1的延遲時間×延遲訂單量+延遲批次2的延遲時間×延遲訂單量+…+延遲批次17的延遲時間×延遲訂單量=2 255分；考慮完成期的情況下，總延遲時間=延遲批次1的延遲時間×延遲訂單量+延遲批次2的延遲時間×延遲訂單量+…+延遲批次7的延遲時間×延遲訂單量=35分。

[1]de Koster R,Le-Duc T,Roodbergen K J.Design and control of warehouse order picking:A literature review[J].European Journal of Operational Research,2007,182(2):481-501.

[2]Manzini R.Warehousing in the global supply chain:Advanced models,tools and applications for storage[M].Berlin:Spinger,2012:1-30.

[3]Xiao J,Zheng L.Correlated storage assignment to minimize zone visits for BOM picking[J].The International Journal of Advanced Manufacturing Technology,2012,61(5/8):797-807.

[4]朱杰,周麗,郭鍵.分類存儲人工揀選隨機服務系統效率研究[J].管理科學學報,2012,15(2):59-71.

Zhu Jie,Zhou Li,Guo Jian.Research on random service system efficiency of sorted storage manual order picking manners[J].Journal of Management Sciences in China,2012,15(2):59-71.(in Chinese)

[5]鄧愛民,蔡佳,毛浪.基于時間的自動化立體倉庫貨位優化模型研究[J].中國管理科學,2013,21(6):107-112.

Deng Aimin,Cai Jia,Mao Lang.Research on slotting optimization in automated warehouse based on time[J].Chinese Journal of Management Science,2013,21(6):107-112.(in Chinese)

[6]陳方宇,王紅衛,祁超,謝勇.考慮多揀貨員堵塞的倉庫揀選路徑算法[J].系統工程學報,2013,28(5):581-591.

Chen Fangyu,Wang Hongwei,Qi Chao,Xie Yong.Routing method for multiple order pickers with congestion consideration[J].Journal of Systems Engineering,2013,28(5):581-591.(in Chinese)

[7]朱杰,郭鍵,周麗.隨機存儲下返回型與S型揀選路徑隨機模型的比較研究[J].系統仿真學報,2011,23(2):223-227.

Zhu Jie,Guo Jian,Zhou Li.Comparative research on stochastic model of random-storage return-type and S-type order picking route[J].Journal of System Simulation,2011,23(2):223-227.(in Chinese)

[8]陳璐,陸志強.自動化立體倉庫中的儲位分配及存取路徑優化[J].管理工程學報,2012,26(1):42-47.

Chen Lu,Lu Zhiqiang.Optimization for storage location assignments and interleaving problems in an automated storage/retrieval system[J].Journal of Industrial Engineering and Engineering Management,2012,26(1):42-47.(in Chinese)

[9]胡少龍,胡志華,曹楊.基于多候選儲位的存取路徑優化問題研究[J].運籌與管理,2013,22(5):111-116,165.

Hu Shaolong,Hu Zhihua,Cao Yang.Optimization for storage or retrieval routing problem based on mutil-candidates storages location[J].Operations Research and Management Science,2013,22(5):111-116,165.(in Chinese)

[10] Hong S,Johnson A L,Peters B A.Large-scale order batching in parallel-aisle picking systems[J].IIE Transactions,2012,44(2):88-106.

[11] 李詩珍,杜文宏.基于聚類分析的訂單分批揀貨模型及啟發式算法[J].統計與決策,2008(12):53-56.

Li Shizhen,Du Wenhong.Order batching model and algorithm based on similarity analysis[J].Statistics & Decision,2008(12):53-56.(in Chinese)

[12] 吳穎穎,吳耀華.基于并行揀選的自動揀選系統訂單拆分優化[J].計算機集成制造系統,2012,18(10):2264-2272.

Wu Yingying,Wu Yaohua.Order splitting for automated picking system based on parallel picking strategy[J].Computer Integrated Manufacturing Systems,2012,18(10):2264-2272.(in Chinese)

[13] 李詩珍.基于工作量均衡的分區同步揀貨系統儲位分配與評價[J].包裝工程,2010,31(11):114-118.

Li Shizhen.Location assignment and evaluation in a synchronized zone picking system base on workload balance[J].Packaging Engineering,2010,31(11):114-118.(in Chinese)

[14] Petersen C G,Aase G.A comparison of picking,storage,and routing policies in manual order picking[J].International Journal of Production Economics,2004,92(1):11-19.

[15] Gademann N,van de Velde S.Order batching to minimize total travel time in a parallel-aisle warehouse[J].IIE Transactions,2005,37(1):63-75.

[16] Lam C H Y,Choy K L,Ho G T S,Lee C K M.An order-picking operations system for managing the batching activities in a warehouse[J].International Journal of Systems Science,2014,45(6):1283-1295.

[17] Ho Y C,Tseng Y Y.A study on order-batching methods of order-picking in a distribution centre with two cross-aisles[J].International Journal of Production Research,2006,44(17):3391-3417.

[18] Bozer Y A,Kile J W.Order batching in walk-and-pick order picking systems[J].International Journal of Production Research,2008,46(7):1887-1909.

[19] Tsai C Y,Liou J J H,Huang T M.Using a multiple-GA method to solve the batch picking problem:Considering travel distance and order due time[J].International Journal of Production Research,2008,46(22):6533-6555.

[20] Henn S.Algorithms for on-line order batching in an order picking warehouse[J].Computers & Operations Research,2012,39(11):2549-2563.

[21] Henn S,W?scher G.Tabu search heuristics for the order batching problem in manual order picking systems[J].European Journal of Operational Research,2012,222(3):484-494.

[22] Chen M C,Wu H P.An association-based clustering approach to order batching considering customer demand patterns[J].Omega:International Journal of Management Science,2005,33(4):333-343.

[23] Hsieh L F,Huang Y C.New batch construction heuristics to optimise the performance of order picking systems[J].International Journal of Production Economics,2011,131(2):618-630.

[24] Bukchin Y,Khmelnitsky E,Yakuel P.Optimizing a dynamic order-picking process[J].European Journal of Operational Research,2012,219(2):335-346.

[25] Chew E P,Tang L C.Travel time analysis for general item location assignment in a rectangular warehouse[J].European Journal of Operational Research,1999,112(3):582-597.

[26] Le-Duc T,de Koster R M B M.Travel time estimation and order batching in a 2-block warehouse[J].European Journal of Operational Research,2007,176(1):374-388.

[27] Xu X,Liu T,Li K,Dong W.Evaluating order throughput time with variable time window batching[J].International Journal of Production Research,2014,52(8):2232-2242.

[28] Henn S,Schmid V.Metaheuristics for order batching and sequencing in manual order picking systems[J].Computers & Industrial Engineering,2013,66(2):338-351.

[29] Azadnia A H,Taheri S,Ghadimi P,Saman M Z M,Wong K Y.Order batching in warehouses by minimizing total tardiness:A hybrid approach of weighted association rule mining and genetic algorithms[J].The Scientific World Journal,2013:246578.

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

Ma Shihua,Wen Jian.The order batching strategies based on time postponement[J].Industrial Engineering and Management,2004,9(6):1-4.(in Chinese)

E-CommerceOn-lineOrderBatchingModelandAlgorithm:ConsideringDueTime

Wang Xuping1,2，Zhang Jun1，Ma Jun1

1 Institute of Systems Engineering, Dalian University of Technology, Dalian 116023, China 2 School of Business, Dalian University of Technology, Panjin 124221, China

In the e-commerce on-line order picking system, customer orders′ arrival time and goods cannot be informed in advance. With the constraints of picking equipment capacity and pickers′ number, the order batching optimization approach, which focuses on the batching time and batching strategy, is proposed to pick out maximum orders in the shortest service time before the due time. The on-line order batching mixed-integer programming model considering orders′ due time is established to minimize the valid average service time of distributed orders. To solve this problem, the improved fixed time window order batching algorithm is proposed. The order is identified as the urgent one if its remained operation time is between lead time and distribution setup time. Based on orders′ different urgent level, we propose the on-line order batching rules while taking into account urgent degree and similar degree. Through a series of experiments where the orders are generated from 14:00 to 18:00 based on Poisson distribution (λ=17), we compare the results with ones of traditional on-line order rules. Several enlightening findings are discovered: If considering orders′ due time, the number of distributed orders is bigger, the batches′ total service time and the distributed batches′ valid average service time are shorter, and the number of delayed orders is smaller and delayed time is shorter. Meanwhile, if considering orders′ due time, with the increase of the number of order pickers, the delivery rate improves in different degree, and the increase of delivery rate is larger than the one of traditional rules. However, the increasing of delivery rate is a progressive decline.

e-commerce；on-line order picking；order batching；due time

Date:May 5th, 2014

DateOctober 30th, 2014

FundedProject:Supported by the National Natural Science Foundation of China(71171029,71350011)

Biography:Dr.Wang Xuping, a Liaoning Jinzhou native(1962-), graduated from Dalian University of Technology and is a Professor and Ph.D Supervisor in the Institute of Systems Engineering and School of Business at Dalian University of Technology. His research interests include e-commerce and logistics management, emergency management, etc. E-mail：wxp@dlut.edu.cn

F713.365.1

A

10.3969/j.issn.1672-0334.2014.06.009

1672-0334(2014)06-0103-11

2014-05-05修返日期2014-10-30

國家自然科學基金(71171029,71350011)

王旭坪(1962-)，男，遼寧錦州人，畢業于大連理工大學，獲管理學博士學位，現為大連理工大學系統工程研究所和商學院教授、博士生導師，研究方向：電子商務與物流管理、應急管理等。E-mail：wxp@dlut.edu.cn

□