B2C電子商務環境下訂單揀選與配送聯合調度優化

王旭坪，張 珺，易彩玉

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

B2C電子商務環境下訂單揀選與配送聯合調度優化

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

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

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

聯合調度；訂單揀選；路徑優化；三階段算法；遺傳算法

1 引言

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

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

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

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

2 問題及模型

2.1 問題描述

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

圖1 訂單揀選與配送示意

圖2 揀選區域布局

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

2.2 IOPDS模型構建

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

常量：

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

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

M：訂單合并批次集合；

V：車輛集合；

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

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

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

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

Qc：最大車容量；

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

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

變量：

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

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

yiv：訂單i是否由車輛v負責配送，i∈N，v∈V；

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

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

基于上述分析，構建訂單揀選與配送聯合優化模型，以最小化揀選和配送完所有訂單的履行時間：

MinTturnover

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

r0=0

(13)

(14)

(15)

(16)

(17)

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

2.3 IOPDS模型復雜性分析

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

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

此類IOPDS特殊問題最優解構建的配送路徑應僅由一條路徑組成。反之若最優配送路徑由兩條配送線路構成：

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

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

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

3 揀選與配送聯合調度優化三階段算法

由于IOPDS模型屬于NP-hard問題，無法用精確算法求得最優解，本文構建三階段啟發式算法求解。

3.1 算法可行性分析

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

3.2 配送線路優化

3.3 訂單分批優化

步驟2：針對第v批次的配送線路σv訂單，優化其作業方式，以最小化揀選完成時間。采用種子算法中的相同通道數系數作為衡量訂單間相似度的指標。兩訂單所包含相同通道數越多，其相似性越大，合并的可能性也越大。分批規則思路如下，具體規則詳見王旭坪等[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，選擇其他相似度較大訂單進行合并生產批次后，返回1)。

3.4 揀選順序調整

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

4 揀選與配送聯合調度優化傳統算法

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

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

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

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

5 數據實驗

5.1 實驗設置

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

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

5.2 結果分析

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

圖3 300個顧客分布圖及線路優化

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

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

1)三階段算法的解Tturnover要優于傳統算法的解，解的改進程度為17.11%。可見統籌考慮揀選和配送系統優化調度的特點，能夠改進傳統的揀選與配送兩個階段分別優化的結果。

圖5 傳統算法各區域配送時間序列圖

配送區域配送時間三階段算法傳統算法揀選開始時間車輛離開時間揀選時間結束時間最后揀選批次序號車輛離開時間結束時間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)三階段算法平均履行時間的改進程度為13.03%。可見整體考慮揀選和配送過程有利于提高系統配送效率，提升顧客滿意程度。

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

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

6 總語

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

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

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

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

[3] 黃敏芳, 張源凱, 胡祥培. 有機蔬菜B2C直銷的配送方案智能生成方法[J]. 系統工程學報, 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]. 計算機集成制造系統, 2014, 20(12): 3011-3019.

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

[10] 裴軍, 劉心報, 范雯娟, 等. 基于生產與運輸的供應鏈調度優化問題[J]. 中國管理科學, 2012, 20(S1): 586-593.

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

[12] 馬士華, 王青青. 同步物流系統下準時化生產與配送調度問題研究[J]. 中國管理科學, 2012, 20(6): 125-132.

[13] 馮鑫, 鄭斐峰, 徐寅峰. 批加工生產配送二級供應鏈協同調度[J]. 系統管理學報, 2015, 24(2): 275-279.

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

[15] 李昆鵬, 馬士華.ATO供應鏈中航空運輸及并行機生產協調調度問題[J]. 系統工程理論與實踐, 2007, 27(12): 8-15.

[16] 王建華, 李南, 郭慧. 基于時間槽的敏捷供應鏈集成調度模型及優化[J]. 系統工程理論與實踐, 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] 馮鑫, 鄭斐峰. 面對單客戶的生產與配送二級供應鏈協同調度探討[J]. 運籌與管理, 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] 王旭坪, 張珺, 馬駿. 考慮完成期限的電子商務在線訂單分批模型及算法[J]. 管理科學,2014, 27(6):103-113.

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

[29] 陳方宇, 王紅衛, 祁超, 等. 考慮多揀貨員堵塞的倉庫揀選路徑算法[J]. 系統工程學報, 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

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

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

F274

A