B2C電子商務(wù)環(huán)境下訂單揀選與配送聯(lián)合調(diào)度優(yōu)化

王旭坪，張 珺，易彩玉

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

B2C電子商務(wù)環(huán)境下訂單揀選與配送聯(lián)合調(diào)度優(yōu)化

王旭坪1,2，張 珺1，易彩玉1

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

如何在顧客下單后協(xié)調(diào)好揀選和配送環(huán)節(jié)，在最短的時間、以較低的成本將商品從貨架上揀出、打包后配送到顧客手中，已成為B2C電子商務(wù)物流管理中亟待解決的問題。本文嘗試以最小化訂單履行時間為目標(biāo)，構(gòu)建非線性揀選與配送聯(lián)合調(diào)度模型，以解決訂單揀選順序、揀選作業(yè)方式、車輛行駛線路等聯(lián)合決策。為求解此NP難問題，設(shè)計了三階段啟發(fā)式算法：首先采用“聚類-路徑優(yōu)化”思想，依據(jù)顧客位置進(jìn)行配送方案確認(rèn)；然后采用基于相似度聚類的訂單分批規(guī)則對每條配送線路的訂單進(jìn)行分批合并；最后調(diào)整揀選任務(wù)與配送線路順序。通過數(shù)據(jù)實驗對模型進(jìn)行驗證，并與傳統(tǒng)揀選與配送分開優(yōu)化的結(jié)果進(jìn)行對比。結(jié)果表明，三階段算法能夠有效縮短訂單完成時間、降低配送車輛等待時間、改善配送資源利用率。

聯(lián)合調(diào)度；訂單揀選；路徑優(yōu)化；三階段算法；遺傳算法

1 引言

當(dāng)前移動互聯(lián)網(wǎng)、手機(jī)APP等技術(shù)手段使得電子商務(wù)購買方式越來越便捷，同時消費者對商品到達(dá)的時效性要求越來越高。然而客戶眾多、位置分散，且每單需求量小、品類差異性大等新特征，使得B2C電子商務(wù)的訂單揀選和配送難度增大。對于商家來說，能否在顧客下單后協(xié)調(diào)好揀選和配送環(huán)節(jié)，在最短的時間內(nèi)，以較低的成本將商品從貨架上揀出、打包后配送到顧客手中，已成為電子商務(wù)物流管理中亟待解決的問題。當(dāng)前B2C電子商務(wù)企業(yè)(如天貓、京東、亞馬遜等)開始通過自建物流提高揀選和配送效率，但訂單從進(jìn)入商家平臺到送達(dá)顧客手中被分割成訂單處理和配送兩個階段：訂單處理部門依據(jù)訂單到達(dá)的時間、包含的商品及其倉儲信息等制定合理的揀選任務(wù)，其優(yōu)化目標(biāo)通常是訂單完成時間最小化[1]；配送部門依據(jù)訂單數(shù)量、顧客分布、期望最遲收貨時間等優(yōu)化配送線路，以最小化行駛距離或顧客等待時間[2-3]。由于配送過程的優(yōu)化受到訂單揀選順序、揀選完成時間等揀選階段因素的影響，很難實現(xiàn)整體效率最優(yōu)。本文綜合考慮揀選和配送系統(tǒng)優(yōu)化調(diào)度的特點，嘗試構(gòu)建揀選與配送聯(lián)合調(diào)度模型，并制定快速求解方案，以實現(xiàn)在最短的時間內(nèi)揀選配送完所有顧客訂單。關(guān)鍵決策問題包括：1)如何進(jìn)行合理的訂單分批優(yōu)化，確定訂單所屬揀選批次；2)如何安排顧客所屬配送車輛以及每輛車的行駛線路；3)如何安排不同揀選批次作業(yè)順序及不同車輛開始配送時間。

訂單揀選與配送聯(lián)合調(diào)度問題(Integrated Order Picking and Delivery Scheduling，IOPDS)可抽象為生產(chǎn)與配送聯(lián)合調(diào)度問題(Integrated Production and Delivery Scheduling，IPDS)，包括生產(chǎn)調(diào)度和配送調(diào)度兩階段：生產(chǎn)調(diào)度解決每個訂單何時被處理及所需處理時間等問題；配送階段則解決每個訂單何時被配送、所需配送車輛數(shù)、車輛行駛路徑及時間等。Chen Zhilong[4]構(gòu)建了IPDS問題的通用表達(dá)形式：α|β|π|δ|γ，其中α表示生產(chǎn)配置集合，包括單一、并行、流水等生產(chǎn)形式；β表示訂單約束集合，包括訂單到達(dá)時間、處理時間、期望收貨時間等；π表示配送參數(shù)，包括配送車輛參數(shù)、配送方式等；δ表示顧客數(shù)量，包括單一顧客和多個顧客等；γ表示優(yōu)化目標(biāo)，包括顧客服務(wù)質(zhì)量、成本、收益等。當(dāng)前學(xué)者對IPDS問題的研究多是在不同的α、β、π、δ、γ參數(shù)條件下建立生產(chǎn)與配送聯(lián)合優(yōu)化模型。生產(chǎn)調(diào)度包括單機(jī)/并行機(jī)條件下的直接/批量生產(chǎn)調(diào)度優(yōu)化。Geismar等[5]構(gòu)建單一有限生命周期產(chǎn)品的單機(jī)直接生產(chǎn)模式下的IPDS模型；Low等[6-7]、李凱等[8]構(gòu)建考慮配送時間窗的單機(jī)多產(chǎn)品多車輛IPDS模型；ChenZhilong等[9]分別構(gòu)建了多產(chǎn)品在單一和平行生產(chǎn)線上的IPDS模型；裴軍等[10]、馬士華和呂飛[11]、馬士華和王青青[12]建立采取批量生產(chǎn)分批配送模式的生產(chǎn)與配送協(xié)同模型；馮鑫等[13]探討了單機(jī)批量加工的生產(chǎn)配送調(diào)度模型；配送調(diào)度優(yōu)化則包含直接配送、分批配送、配送路徑優(yōu)化及帶時間窗的配送等方面。LiKai等[14]、李昆鵬和馬士華[15]、王建華等[16]考慮了配送時間固定的直接配送模式；ChengBayi等[17]研究了考慮單一顧客的分批配送調(diào)度；GaoSu等[18]、Amstrong等[19]、Low等[6-7]、李凱等[8]研究了更為復(fù)雜的路徑優(yōu)化IPDS問題；Low等[20-21]構(gòu)建了帶配送時間窗的生產(chǎn)與配送聯(lián)合調(diào)度問題；馮鑫和鄭斐峰[22]對比分析了直接配送與批量配送對生產(chǎn)配送協(xié)同調(diào)度效果的作用。模型的優(yōu)化目標(biāo)有客戶最大收貨時間最小化[5-6]，車輛固定成本、配送成本及懲罰成本總和最小化[7]，制造商懲罰成本與配送成本總和最小化[8]，最大延遲時間與配送車輛數(shù)之間加權(quán)和的最小化[23]等。由于IPDS屬于NP難問題[7]，當(dāng)前的求解算法多為啟發(fā)式算法，如基于遺傳算法和Gilmore-Gomory算法的兩階段啟發(fā)式算法[5]、兩階段自適應(yīng)遺傳算法[6-7]、2-近似算法[24]、禁忌搜索算法[25]、模擬退火算法[8]等。

當(dāng)前IPDS的研究已較豐富，但缺少訂單揀選與配送聯(lián)合調(diào)度問題(IOPDS)的相關(guān)研究。IOPDS與IPDS存在一定的差異性，集中表現(xiàn)為：1)訂單作業(yè)方式與加工時間更復(fù)雜。電子商務(wù)環(huán)境下訂單具有小批量、高頻次等特征，有必要采用訂單分批策略提高揀選效率[26]。傳統(tǒng)IPDS批量加工時間通常為批次訂單加工時間之和、批次訂單中最大加工時間或按某一固定加工速率計算，但I(xiàn)OPDS揀選時間更為復(fù)雜，由訂單分批情況[26-27]、揀選路徑策略[28]、貨位分布[29]等多因素決定，屬于NP-hard問題。2)考慮配送路徑的批量生產(chǎn)批量配送方式。IPDS中批量生產(chǎn)批量配送問題多假設(shè)生產(chǎn)容量與配送容量相同，即批量生產(chǎn)完后立即由同一車輛配送，但I(xiàn)OPDS中揀選設(shè)備容量與車輛容量不同，即生產(chǎn)批次與配送批次并不一一對應(yīng)，且同時考慮配送線路優(yōu)化，增加模型的復(fù)雜性和求解的難度；3)最小化訂單履行時間為優(yōu)化目標(biāo)。網(wǎng)購顧客更注重配送時效性，應(yīng)結(jié)合訂單分批優(yōu)化、車輛路徑優(yōu)化等方法，合理制定揀選和配送聯(lián)合調(diào)度方案，使得顧客盡早收到訂購商品。

綜上所述，本文以最小化訂單履行時間為目標(biāo)，研究考慮配送路徑的批量生產(chǎn)批量配送的訂單揀選與配送聯(lián)合調(diào)度問題；構(gòu)建IOPDS模型，并證明模型的復(fù)雜性；采用揀選與配送聯(lián)合調(diào)度三階段算法求解模型：首先采用遺傳算法確定配送線路，再針對不同配送線路制定訂單分批揀選任務(wù)，最后調(diào)整揀選任務(wù)與配送線路順序；通過數(shù)據(jù)實驗，從履行時間、平均履行時間、車輛等待時間等方面，對三階段算法與傳統(tǒng)算法完成結(jié)果進(jìn)行對比分析，結(jié)果證明模型和算法的有效性，為B2C企業(yè)提高物流服務(wù)質(zhì)量提供決策支持。

2 問題及模型

2.1 問題描述

本文研究B2C電子商務(wù)環(huán)境下訂單揀選配送聯(lián)合調(diào)度問題，由一個配送中心和多個顧客構(gòu)成，如圖1所示。研究對象為第一天晚上到第二天白天累計的n個顧客生成的n個同城訂單，每個顧客生成一個訂單，大小為qi。訂單按照某種分批規(guī)則合并后產(chǎn)生若干揀選批次，排序后分配給員工進(jìn)行揀選，員工數(shù)為1。揀選后的訂單打包后分配給對應(yīng)的車輛進(jìn)行配送，一個訂單由且只由一輛車配送。車輛離開時間等于配送批次中的最后一個訂單揀選完成時間，顧客的收貨時間以車輛到達(dá)配送點并服務(wù)完該顧客的時間為準(zhǔn)。車輛從配送中心出發(fā)，服務(wù)完該路徑上所有顧客后返回配送中心。本文要解決的主要問題為尋找最優(yōu)的分批揀選方案及配送方案，以最小化訂單最終履行時間，從整體角度提升訂單處理速度。模型假設(shè)如下：1)所有車輛類型相同，容量為Qc，車輛數(shù)不限；2)不考慮揀選準(zhǔn)備時間、打包時間、裝貨和卸貨時間；3)配送點間時間滿足三角不等式，且配送時間具有對稱性；4)揀選員工按照S-Shape型路徑策略進(jìn)行揀選[1]，揀選容量為Q；5)揀選區(qū)域布局如圖2所示，倉庫類型為單區(qū)型，通道的入口在倉庫的最左端，且每個通道的寬度相同。

圖1 訂單揀選與配送示意

圖2 揀選區(qū)域布局

基于上述分析，結(jié)合ChenZhilong[4]總結(jié)的IPDS問題表達(dá)形式α|β|π|δ|γ，本文研究IOPDS問題可抽象為：1,manual|off-line,S-shape|V(∞,Qc),routing|n|tmax其中α：揀選員工數(shù)為1的人工揀選系統(tǒng)；β：訂單信息提前已知，揀貨策略S-shape；π：配送車輛為容量Qc的同類型車輛，數(shù)量無限制，考慮路徑優(yōu)化；δ：n個顧客；γ：最小化訂單最終履行時間。

2.2 IOPDS模型構(gòu)建

首先對模型中的常量和變量作如下定義：

常量：

N：配送點(訂單)集合；

N0：包含配送中心的配送點集合；

M：訂單合并批次集合；

V：車輛集合；

qi：訂單i中包含的商品數(shù)量，i∈N；

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

vpick：單位時間揀選員工揀出商品數(shù)量；

Q：每個揀選批次能容納的最大商品數(shù)量；

Qc：最大車容量；

τij：從配送點i到j(luò)所需時間，i,j∈N0；

tservice：配送點所需服務(wù)時間，i∈N。

變量：

disk：完成批次k揀選任務(wù)所需行走距離(揀選路徑優(yōu)化策略采用S-shape策略)，k∈M；

xik：訂單i是否分配給批次k，i∈N，k∈M；

yiv：訂單i是否由車輛v負(fù)責(zé)配送，i∈N，v∈V；

zijv：車輛v是否從配送點i駛向j，i,j∈N0，v∈V；

ri：配送點i的流量，i∈N0。

基于上述分析，構(gòu)建訂單揀選與配送聯(lián)合優(yōu)化模型，以最小化揀選和配送完所有訂單的履行時間：

MinTturnover

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

r0=0

(13)

(14)

(15)

(16)

(17)

目標(biāo)函數(shù)(1)表示最小化揀選和配送完所有訂單的履行時間；約束(2)-(7)為揀選階段約束，其中(2)和(3)是對訂單分批的約束，即保證一個訂單只能分配給一個合并批次，且每個合并批次商品量不超過上限Q；約束(4)定義批次k的服務(wù)時間，為行走時間、揀選時間之和；約束(5)和(6)為揀選開始時間約束，定義第一個開始揀選的批次時間記為0，且完成后即開始第二個批次的揀選工作；約束(7)定義訂單的揀選完成時間為其所在批次開始揀選時間和揀選所需時間之后。約束(8)-(18)為配送階段約束，其中約束(8)表示所屬車輛v的所有訂單都揀選完成后，車輛離開配送中心；約束(9)-(12)是對車輛的約束，定義一個配送點只由一輛車服務(wù)；每輛車從0點出發(fā)，并最終回到0點；進(jìn)入配送點i的車輛k必須從配送點i離開；每輛車只能離開0點1次；約束(13)-(15)為配送點的流量約束；(16)對車輛v的服務(wù)結(jié)束時間進(jìn)行了定義；約束(17)為履行時間表達(dá)式，為車輛最晚結(jié)束的時間。

2.3 IOPDS模型復(fù)雜性分析

本節(jié)分析IOPDS模型的復(fù)雜性，并證明此類問題為NP-hard問題，不存在多項式時間算法。

定理1 IOPDS模型為NP-hard問題。

此類IOPDS特殊問題最優(yōu)解構(gòu)建的配送路徑應(yīng)僅由一條路徑組成。反之若最優(yōu)配送路徑由兩條配送線路構(gòu)成：

tripv1={0,i1,i2,…,it,0}

將兩條配送線路合并可得：

求解此類IOPDS特殊問題可等同于求解TSP旅行商問題，由于TSP為NP-hard問題[30]，因此IOPDS問題同為NP-hard問題。

3 揀選與配送聯(lián)合調(diào)度優(yōu)化三階段算法

由于IOPDS模型屬于NP-hard問題，無法用精確算法求得最優(yōu)解，本文構(gòu)建三階段啟發(fā)式算法求解。

3.1 算法可行性分析

Chen Zhilong等[9]證明得出，IPDS問題存在最優(yōu)解需滿足以下幾個條件：1)訂單間生產(chǎn)不能存在空閑時間；2)每輛車的離開時間等于其配送所有訂單中最后一個訂單的完成時間；3)在同一機(jī)器上生產(chǎn)且由同一輛車配送的訂單應(yīng)在該機(jī)器上連續(xù)生產(chǎn)。本文研究的IOPDS問題為IPDS的一類特殊問題，上述條件也適用于IOPDS問題。因此由同一輛車配送的訂單需由揀選員工連續(xù)揀選完后立即配送。其次對目標(biāo)函數(shù)Tturnover分析:

3.2 配送線路優(yōu)化

3.3 訂單分批優(yōu)化

步驟2：針對第v批次的配送線路σv訂單，優(yōu)化其作業(yè)方式，以最小化揀選完成時間。采用種子算法中的相同通道數(shù)系數(shù)作為衡量訂單間相似度的指標(biāo)。兩訂單所包含相同通道數(shù)越多，其相似性越大，合并的可能性也越大。分批規(guī)則思路如下，具體規(guī)則詳見王旭坪等[27]：

1)計算訂單集合O(σv)中訂單間相似度；

2)選取O(σv)中相似度最高的兩個訂單σv(p),σv(q)，兩訂單容量為qσv(p)+qσv(q)；

3)合并批次容量約束判斷：如果qσv(p)+qσv(q)Q，選擇其他相似度較大訂單進(jìn)行合并生產(chǎn)批次后，返回1)。

3.4 揀選順序調(diào)整

在得出最優(yōu)配送線路及揀選方案后，需對揀選順序進(jìn)行排序，以最小化訂單履行時間。

4 揀選與配送聯(lián)合調(diào)度優(yōu)化傳統(tǒng)算法

傳統(tǒng)的揀選與配送聯(lián)合優(yōu)化算法可歸納為一類兩階段算法：首先配送中心依據(jù)顧客訂單信息確認(rèn)訂單的合并批次和揀選順序，以最小化揀選所需時間；然后配送部門根據(jù)顧客位置來確定合理的配送方案，最小化車輛行駛路徑且顧客收貨時間。當(dāng)某一配送方案包含的所有訂單都揀選完成后，則裝車配送，如未完成則車輛需在配送中心等待。算法簡述如下：

步驟1：訂單揀選優(yōu)化。此過程不考慮配送的影響，以最小化訂單揀選時間為目標(biāo)，采用3.3中基于相似度聚類的訂單分批規(guī)則生成揀選批次。

步驟2：配送線路優(yōu)化。采用3.2中“聚類-路徑優(yōu)化”的思想計算訂單配送線路，以最小化總配送時間。

步驟3：開始配送服務(wù)。合并批次按照順序依次進(jìn)行揀選工作，當(dāng)某一配送方案中的所有訂單揀選完成后，則按照事先優(yōu)化的線路離開配送中心；當(dāng)訂單揀選完成，且車輛服務(wù)完所有顧客返回配送中心后，算法結(jié)束。

5 數(shù)據(jù)實驗

5.1 實驗設(shè)置

隨機(jī)產(chǎn)生訂單300個，由于訂單具有小批量等特征，令每個訂單的需求量在[1,3]上服從均勻分布。揀選區(qū)域參數(shù)如下：包含10個揀選通道和1000種商品，每列貨架存放50種商品，每個員工一次揀選的最大商品容量為10個，通道長度50米，寬度2米。假設(shè)每個商品的體積相同，且只能存儲在一個貨架上；揀選員工行走在通道的中央，以便同時從左右兩邊揀選商品員工揀取速度30個/分，行走速度125m/分；員工通常從最左邊的入口進(jìn)入，揀取完所有商品后回到入口處。

顧客的位置坐標(biāo)在[0,100km]上服從均勻分布，且配送中心坐標(biāo)為(50km,50km)，如圖3所示。采用K均值聚類將A城的300個顧客分為16個配送區(qū)域，且每個區(qū)域的訂單由一輛車負(fù)責(zé)，車輛行駛速度為60Km/h，每個顧客服務(wù)時間1分鐘。經(jīng)過多次實驗，遺傳算法參數(shù)設(shè)置如下：初始種群大小100，最大迭代次數(shù)1000；交叉概率0.8，采用轉(zhuǎn)輪法選擇交叉點進(jìn)行單點交叉；變異概率0.8，采用實值變異；染色體適應(yīng)值為配送線路的距離。

5.2 結(jié)果分析

計算可得16區(qū)域的配送路徑如圖3所示，每個區(qū)域所需總配送時間范圍在107.25～228.82分鐘，最短為A5，最長為A15。表1給出兩種不同算法的揀選與配送聯(lián)合優(yōu)化方案，可得各區(qū)域配送時間(車輛行駛時間+服務(wù)時間)、揀選開始時間、車輛離開時間、揀選時間、結(jié)束時間等信息。三階段算法履行時間為332.08分鐘，傳統(tǒng)算法履行時間為400.64分鐘。

圖3 300個顧客分布圖及線路優(yōu)化

圖4 三階段算法各區(qū)域揀選與配送時間序列圖

傳統(tǒng)算法下對訂單進(jìn)行分批優(yōu)化，300個訂單分為63個批次，平均每個批次揀選時間2.73分鐘。圖5為各區(qū)域的配送時間序列圖，車輛離開順序A8-A4-A3-A12-A2-A6-A7-A9-A10-A11-A13-A14-A1-A5-A15-A16，A8為最早開始配送區(qū)域，需等待第50個批次揀選完成；最晚開始配送區(qū)域A1、A5、A15、A16，需等待最后一個批次揀選完成。300個訂單總履行時間400.64分鐘，平均履行時間328.80分鐘，車輛平均等待時間166.10分鐘。綜上所述，我們可以分析得到如下結(jié)論：

1)三階段算法的解Tturnover要優(yōu)于傳統(tǒng)算法的解，解的改進(jìn)程度為17.11%?？梢娊y(tǒng)籌考慮揀選和配送系統(tǒng)優(yōu)化調(diào)度的特點，能夠改進(jìn)傳統(tǒng)的揀選與配送兩個階段分別優(yōu)化的結(jié)果。

圖5 傳統(tǒng)算法各區(qū)域配送時間序列圖

配送區(qū)域配送時間三階段算法傳統(tǒng)算法揀選開始時間車輛離開時間揀選時間結(jié)束時間最后揀選批次序號車輛離開時間結(jié)束時間A1206.9733.1753.3620.19260.3363171.82378.79A2141.17155.45169.4714.02310.6462169.72310.89A3180.5553.3670.4017.03250.9557159.03339.58A4146.85143.73155.4511.73295.5054150.08296.93A5107.25208.73218.8810.15326.1363171.82279.07A6180.5370.4082.4412.05262.9762169.72350.25A7223.0919.3833.1713.8256.2662169.72392.81A8154.36116.76126.589.82280.9450135.82290.18A9140.37169.47183.4613.99323.8362169.72310.09A10163.6095.20104.869.66268.4662169.72333.32A11135.19183.46196.8913.43332.0862169.72304.91A12157.14104.86116.7611.9273.9061167.59324.73A13166.8582.4495.2012.75262.0562169.72336.57A14151.79126.58143.7317.14295.5262169.72321.51A15228.820.0019.3819.38248.2063171.82400.64A16118.74196.89208.7311.84327.4763171.82290.56履行時間Tturnover=332.08Tturnover=400.64平均履行時間285.95328.80平均車輛等待時間123.67166.10

2)三階段算法平均履行時間的改進(jìn)程度為13.03%。可見整體考慮揀選和配送過程有利于提高系統(tǒng)配送效率，提升顧客滿意程度。

3)車輛等待時間一定程度上說明了配送資源的利用情況，三階段算法平均車輛等待時間的改進(jìn)程度為25.54%，其幅度要高于總服務(wù)時間及平均服務(wù)時間，對配送資源利用率改善明顯。

實驗結(jié)果驗證了模型和算法的有效性，三階段算法有利于在從整體上提高訂單處理速度，改善配送資源利用率，從訂單揀選和配送兩個環(huán)節(jié)協(xié)同優(yōu)化提升了電子商務(wù)物流配送速度。

6 總語

為解決B2C電子商務(wù)環(huán)境下訂單揀選環(huán)節(jié)和物流配送環(huán)節(jié)分開優(yōu)化造成效率較低的問題，本文嘗試研究訂單揀選與配送聯(lián)合調(diào)度優(yōu)化，并將其抽象為α|β|π|δ|γ的表達(dá)形式，以最小化訂單履行時間為目標(biāo)，構(gòu)建單揀選員工和多配送車輛情形下的訂單揀選與配送聯(lián)合調(diào)度模型。為求解此NP難問題，構(gòu)造了三階段啟發(fā)式算法，首先構(gòu)建最優(yōu)配送方案，再進(jìn)一步對配送方案中訂單進(jìn)行揀選優(yōu)化，最終確定最優(yōu)的揀選方案和批次揀選方案的排列順序。通過數(shù)據(jù)實驗與傳統(tǒng)揀選與配送分開優(yōu)化算法進(jìn)行比較，結(jié)果表明：綜合考慮揀選和配送優(yōu)化調(diào)度系統(tǒng)的特點，能夠縮短訂單履行時間，降低配送車輛等待時間，改善配送資源利用率。本文構(gòu)建模型和算法有利于從提升效率、節(jié)約資源和提高顧客滿意度等多方面優(yōu)化電子商務(wù)物流管理問題。

本文只考慮單揀選員工下的訂單揀選情況，且顧客對配送時間無要求，進(jìn)一步的研究可考慮顧客時間窗的多揀選員工揀選與配送聯(lián)合調(diào)度問題；另外，本文研究背景為同城配送，可進(jìn)一步研究采用干線和最后一公里聯(lián)合配送的城際訂單揀選與配送聯(lián)合優(yōu)化；對于實時訂單到達(dá)情況下的揀選與配送聯(lián)合優(yōu)化也有待進(jìn)一步的研究。

[1]KosterR,ThoLD，RoodbergenKJ.Designandcontrolofwarehouseorderpicking:Aliteraturereview[J].EuropeanJournalofOperationalResearch, 2007, 182(1): 481-501.

[2] 王旭坪, 阮俊虎, 張凱, 等. 有模糊時間窗的車輛調(diào)度組合干擾管理研究[J]. 管理科學(xué)學(xué)報, 2011, 14(6): 2-15.

[3] 黃敏芳, 張源凱, 胡祥培. 有機(jī)蔬菜B2C直銷的配送方案智能生成方法[J]. 系統(tǒng)工程學(xué)報, 2013, 28(5): 600-607.

[4]ChenZhilong.Integratedproductionandoutbounddistributionscheduling:Reviewandextensions[J].OperationsResearch, 2010, 58(1): 130-148.

[5]GeismarHN,LaporteG,LeiLei,SriskandarajahC.Theintegratedproductionandtransportationschedulingproblemforaproductwithashortlifespanandnon-instantaneoustransportationtime[J].INFORMSJournalonComputing, 2008, 20(1): 21-33.

[6]LowCY,LiRK,ChangCM.Integratedschedulingofproductionanddeliverywithtimewindows[J].InternationalJournalofProductionResearch, 2013, 51(3): 897-909.

[7]LowCY,ChangCM,LiRK,etal.Coordinationofproductionschedulinganddeliveryproblemswithheterogeneousfleet[J].InternationalJournalofProductionEconomics, 2014, 153(4): 139-148.

[8] 李凱, 王明星, 楊平, 等. 單機(jī)多車情形生產(chǎn)與配送協(xié)同調(diào)度算法[J]. 計算機(jī)集成制造系統(tǒng), 2014, 20(12): 3011-3019.

[9]ChenZhilong,VairaktarakisGL.Integratedschedulingofproductionanddistributionoperations[J].ManagementScience, 2005, 51(4): 614-628.

[10] 裴軍, 劉心報, 范雯娟, 等. 基于生產(chǎn)與運(yùn)輸?shù)墓?yīng)鏈調(diào)度優(yōu)化問題[J]. 中國管理科學(xué), 2012, 20(S1): 586-593.

[11] 馬士華, 呂飛. 基于Supply-Hub的生產(chǎn)與配送協(xié)同模式研究[J]. 中國管理科學(xué), 2014, 22(6): 50-60.

[12] 馬士華, 王青青. 同步物流系統(tǒng)下準(zhǔn)時化生產(chǎn)與配送調(diào)度問題研究[J]. 中國管理科學(xué), 2012, 20(6): 125-132.

[13] 馮鑫, 鄭斐峰, 徐寅峰. 批加工生產(chǎn)配送二級供應(yīng)鏈協(xié)同調(diào)度[J]. 系統(tǒng)管理學(xué)報, 2015, 24(2): 275-279.

[14]LiKai,YangShanlin,MaHuawei.Asimulatedannealingapproachtominimizethemaximumlatenessonuniformparallelmachines[J].MathematicalandComputerModelling, 2011, 53(5-6): 854-860.

[15] 李昆鵬, 馬士華.ATO供應(yīng)鏈中航空運(yùn)輸及并行機(jī)生產(chǎn)協(xié)調(diào)調(diào)度問題[J]. 系統(tǒng)工程理論與實踐, 2007, 27(12): 8-15.

[16] 王建華, 李南, 郭慧. 基于時間槽的敏捷供應(yīng)鏈集成調(diào)度模型及優(yōu)化[J]. 系統(tǒng)工程理論與實踐, 2011, 31(2): 283-290.

[17]ChengBayi,LiKai,HuXiaozuan.Approximationalgorithmsfortwo-stagesupplychainschedulingofproductionanddistribution[J].InternationalJournalofSystemsScience:Operations&Logistics, 2015，2(2): 78-89.

[18]GaoSu,QiLian,LeiLei.Integratedbatchproductionanddistributionschedulingwithlimitedvehiclecapacity[J].InternationalJournalofProductionEconomics, 2015，160: 13-25.

[19]AmstrongR,GaoSu,LeiLei.Azero-inventoryproductionanddistributionproblemwithafixedcustomersequence[J].AnnalsofOperationsResearch, 2008, 159(1): 395-414.

[20]LowCR,ChangCM,LiRK,etal.Coordinationofproductionschedulinganddeliveryproblemswithheterogeneousfleet[J].InternationalJournalofProductionEconomics, 2014，153: 139-148.

[21]LowCR,LiRK,ChangCM.Integratedschedulingofproductionanddeliverywithtimewindows[J].InternationalJournalofProductionResearch, 2013，51(3): 897-909.

[22] 馮鑫, 鄭斐峰. 面對單客戶的生產(chǎn)與配送二級供應(yīng)鏈協(xié)同調(diào)度探討[J]. 運(yùn)籌與管理, 2014, 23(4): 19-24.

[23]LeungJYT,ChenZhilong.Integratedproductionanddistributionwithfixeddeliverydeparturedates[J].OperationsResearchLetters, 2013, 41(3): 290-293.

[24]ZhongWeiya,ChenZhilong,ChenMing.Integratedproductionanddistributionschedulingwithcommitteddeliverydates[J].OperationsResearchLetters, 2010, 38(2): 133-138.

[25]ArmentanoVA,ShiguemotoAL,L?kketangenA.Tabusearchwithpathrelinkingforanintegratedproduction-distributionproblem[J].Computers&OperationsResearch, 2011, 38(8): 1199-1209.

[26]LamCHY,ChoyKL,HoGTS,etal.Anorder-pickingoperationssystemformanagingthebatchingactivitiesinawarehouse[J].InternationalJournalofSystemsScience, 2014, 45(6): 1283-1295.

[27] 王旭坪, 張珺, 馬駿. 考慮完成期限的電子商務(wù)在線訂單分批模型及算法[J]. 管理科學(xué),2014, 27(6):103-113.

[28] 朱杰, 周麗, 郭鍵. 分類存儲人工揀選隨機(jī)服務(wù)系統(tǒng)效率研究[J]. 管理科學(xué)學(xué)報,2012,15(2):59-71.

[29] 陳方宇, 王紅衛(wèi), 祁超, 等. 考慮多揀貨員堵塞的倉庫揀選路徑算法[J]. 系統(tǒng)工程學(xué)報, 2013, 28(5): 581-591.

[30]PapadimitriousCH.TheEuclideantravelingsalesmanproblemisNP-complete[J].TheoreticalComputerScience, 1977, 4(3): 237-244.

[31]RuanJunhu,WangXuping,ShiYan.Developingfastpredictorsforlarge-scaletimeseriesusingfuzzygranularsupportvectormachines[J].AppliedSoftComputing, 2012, 13(9): 3981-4000.

Integrated Scheduling of Order Picking and Delivery Under B2C E-commerce

WANG Xu-ping1,2, ZHANG Jun1, YI Cai-yu1

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

It is an important issue to integrate the order picking with delivery problem under shorter time and lower cost by picking the items from the shelves, packaging them and delivering to customers. A nonlinear mathematical model is proposed to minimize the time required to complete picking the orders, delivering to customer and returning to the distribution center, which solves the joint decision-making problem such as order picking sequence, picking process method and vehicle routing. For this NP-hard problem, a three-phase heuristic algorithm is designed. Firstly, the “clustering-vehicle routing” method is used to get delivery solutions. Secondly, the similarity-based order batching rules are used to optimize each route’s orders. Thirdly, picking sequence is sorted based on the descending order of each route’s delivery time. The experiments are proposed to test the efficiency of the model. The results are compared with the traditional optimization algorithm, which show that the three-phase algorithm can reduce the throughput time, decrease the vehicle’s wait time and improve the delivery resource utilization. integrated scheduling; order picking; vehicle route; three-phase algorithm; genetic algorithmAbstract：With the development and wide-spread use of mobile technology, customers can shop anytime and anywhere through a business-to-consumer (B2C) e-commerce shopping platform. However small lot-size and high frequency customer orders make order picking and delivery difficult to implement. In order to accelerate the whole order fulfillment process, orders should be picked and delivered to customers in a very short lead time. It is therefore critical to integrate scheduling order picking and distribution under B2C e-commerce. Research on order picking problems, however, seldom takes delivery constraints into consideration.The integrated order picking and distribution scheduling (IOPDS) problem is studied to minimize the time required to complete picking the orders, delivering to customer and returning to the distribution center to meet the demand of a given set of customers. The picking processing method is order bathing optimization and distribution characteristic is batching delivery with vehicle routing problem. The problem is NP-hard in strong sense. A three-phase heuristic algorithm is proposed, analyze upper bounds and low bounds of the algorithm are analyzed. The first phase uses the “clustering-vehicle routing” method to get delivery solutions; the second phase uses the similarity-based order batching rules to optimize each route’s orders; the third one sorts picking sequence based on the descending order of each route’s delivery time. The traditional sequential approach is also proposed, which optimizes order picking and delivery processes separately.In order to verify the effectiveness of the proposed model and algorithms for IOPDS, several examples are tested. The locations for 300 customers are randomly generated in the 100*100 square, where the warehouse is in the center of the square. The three-phase algorithm’s relative difference from the lower bounds is good. The results are also compared with the traditional algorithm, which show several enlightening findings: 1) the throughput time of the three-phase algorithm is 17.11% shorter than the one of the traditional algorithm, which means it is significant to integrate order picking and distribution; 2) the average improvement of the three-phase algorithm is 13.03%, shows that it is helpful to improve the whole efficiency of the picking and distribution system; 3) it decreases the vehicle’s wait time and improve the delivery resource utilization.Theoretically the IOPDS model and algorithm in the work expand the order picking optimization theory and improve the scheduling of production and distribution problem. Moreover, it is beneficial to the e-commerce shopping platform, which can promote the shipping efficiency, save vehicle resources and improve customer satisfaction.

integrated scheduling; order picking; vehicle route; three-phase algorithm; genetic algorithm

1003-207(2016)07-0101-09

10.16381/j.cnki.issn1003-207x.2016.07.012

2014-11-19；

2016-03-22

國家自然科學(xué)基金面上資助項目(71471025,71171029);國家自然科學(xué)基金重點資助項目(71531002)

王旭坪(1962-),男(漢族),遼寧錦州人,大連理工大學(xué)系統(tǒng)工程研究所教授,博士生導(dǎo)師,研究方向:電子商務(wù)與物流管理、應(yīng)急管理,E-mail：wxp@dlut.edu.cn.

F274

A