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

王旭坪，張 珺，馬 駿

1 大連理工大學(xué) 系統(tǒng)工程研究所，遼寧 大連 116023 2 大連理工大學(xué) 商學(xué)院，遼寧 盤錦 124221

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

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

1 大連理工大學(xué) 系統(tǒng)工程研究所，遼寧 大連 116023 2 大連理工大學(xué) 商學(xué)院，遼寧 盤錦 124221

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

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

1 引言

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

2 相關(guān)研究評述

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

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

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

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

3 考慮完成期限的在線訂單分批優(yōu)化模型

3.1 問題描述和假設(shè)

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

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

到達(dá)時間，即訂單進(jìn)入訂單分批系統(tǒng)時間；

進(jìn)入時間，即訂單合并生成揀選批次后進(jìn)入操作系統(tǒng)的時間；

分批時間，即生成的揀選批次中最早訂單到達(dá)時間與進(jìn)入時間之差；

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

等待時間，即合并批次進(jìn)入操作系統(tǒng)等待服務(wù)的時間；

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

結(jié)束時間，即服務(wù)完成后的時間點；

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

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

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

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

圖2 揀選區(qū)域布局Figure 2 Layout of Picking Area

3.2 參數(shù)定義

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

常量：

N為訂單集合；

M為訂單合并批次集合；

L為揀選人員集合；

O為配送目的地集合；

tpack為配送準(zhǔn)備時間(復(fù)核、打包等所需時間)；

qi為訂單i中包含的商品數(shù)量；

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

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

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

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

變量：

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

Tservice為完成訂單的總服務(wù)時間；

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

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 構(gòu)建模型

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

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

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

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

4.1 整體算法設(shè)計思路

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

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

(16)

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

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

(17)

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

算法整體思路見圖3。

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

4.2 基于通道相似度的訂單分批優(yōu)化算法

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

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

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

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

①若Qi+Qj

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

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

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

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

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

步驟7 結(jié)束。

4.3 基于緊急程度的訂單分批優(yōu)化算法

若時間窗內(nèi)到達(dá)的訂單包含緊急訂單，采用基于緊急程度的訂單分批優(yōu)化算法。設(shè)在時間窗內(nèi)到達(dá)的訂單集合為OO，具體分批步驟如下。

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

步驟2 訂單合并。計算種子訂單Oseed與其他訂單間的相似度，選取相似度最大的訂單Oi，容量為Qi。設(shè)Oseed與Oi合并后的服務(wù)時間為service_time(Oseed,Oi)，進(jìn)入時間為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，則不滿足容量約束，繼續(xù)運行。

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

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

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

步驟6 結(jié)束。

5 傳統(tǒng)在線訂單分批算法

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

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

步驟5 更新時間窗。更新tstart=tend，返回步驟1；如到達(dá)系統(tǒng)結(jié)束時間，運行步驟6。

步驟6 結(jié)束。

6 數(shù)據(jù)實驗和結(jié)果分析

6.1 實驗參數(shù)設(shè)置

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

表1 揀選區(qū)域參數(shù)Table 1 Parameters of the Picking Area

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

圖4 各時段訂單到達(dá)數(shù)量統(tǒng)計Figure 4 Summary of the Number of Arrival Orders in Each Time Interval

6.2 結(jié)果分析

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

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

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

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

延遲時間一般作為評價訂單揀選系統(tǒng)效率的一個常用指標(biāo)[25-30]，本部分對揀選員工人數(shù)為6人時存在延遲訂單的合并批次進(jìn)行分析。員工為6人時的延遲訂單信息見表4，17：00、17：30和18：00三列分別表示此配送期限的訂單數(shù)量；延遲時間為該批次結(jié)束時間與最早離開時間之差，黑體數(shù)字為存在延遲的訂單數(shù)量。在不考慮配送期限的情況下，有17組合并批次存在延遲，總延遲訂單數(shù)量為275個，總延遲時間為2 255分鐘。考慮配送期限的情況下，有7組合并批次存在延遲情況，延遲訂單總量為10個，降低96.364%；總延遲時間為35分鐘，降低98.448%?？梢钥闯霰狙芯繕?gòu)建的模型和算法能有效地減少延遲訂單數(shù)量和延遲時間。

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

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

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

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

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

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

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

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

7 結(jié)論

針對電子商務(wù)環(huán)境下訂單實時到達(dá)的情況，平衡訂單開始揀選時間和揀選量的關(guān)系，同時綜合考慮訂單離開時間，從配送中心運作環(huán)節(jié)提高電子商務(wù)物流配送效率。通過構(gòu)建考慮完成期限的在線訂單分批優(yōu)化模型，并采用基于訂單緊急程度的固定時間窗訂單分批啟發(fā)式算法，實現(xiàn)對固定時間窗內(nèi)到達(dá)訂單的分批優(yōu)化。

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

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

表4 揀選員工人數(shù)為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ī)服務(wù)系統(tǒng)效率研究[J].管理科學(xué)學(xué)報,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]鄧愛民,蔡佳,毛浪.基于時間的自動化立體倉庫貨位優(yōu)化模型研究[J].中國管理科學(xué),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]陳方宇,王紅衛(wèi),祁超,謝勇.考慮多揀貨員堵塞的倉庫揀選路徑算法[J].系統(tǒng)工程學(xué)報,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]朱杰,郭鍵,周麗.隨機(jī)存儲下返回型與S型揀選路徑隨機(jī)模型的比較研究[J].系統(tǒng)仿真學(xué)報,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]陳璐,陸志強(qiáng).自動化立體倉庫中的儲位分配及存取路徑優(yōu)化[J].管理工程學(xué)報,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]胡少龍,胡志華,曹楊.基于多候選儲位的存取路徑優(yōu)化問題研究[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] 李詩珍,杜文宏.基于聚類分析的訂單分批揀貨模型及啟發(fā)式算法[J].統(tǒng)計與決策,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] 吳穎穎,吳耀華.基于并行揀選的自動揀選系統(tǒng)訂單拆分優(yōu)化[J].計算機(jī)集成制造系統(tǒng),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] 李詩珍.基于工作量均衡的分區(qū)同步揀貨系統(tǒng)儲位分配與評價[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].工業(yè)工程與管理,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

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

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

□