徐 菱，胡小林，胡小亮

時間窗約束下需求可拆分的揀選與配送聯(lián)合優(yōu)化問題研究

徐 菱1, 2，胡小林1，胡小亮1

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

針對企業(yè)急需解決的訂單履行效率低問題, 基于需求可拆分的思想, 綜合考慮時間窗和組合揀選策略特征, 建立時間窗約束下需求可拆分的揀選與配送聯(lián)合優(yōu)化模型。通過揀選成本、拆分需求成本、配送成本、時間懲罰成本反映訂單履行效率, 指出拆分需求、組合策略以及算法對于模型的優(yōu)化。利用兩階段算法對模型求解, 通過算例驗證了模型和算法的有效性。最后以不拆分需求、S-Shape策略和順序決策算法為對比方案, 發(fā)現(xiàn)總成本分別下降了33.43%、12.3%和28.17%, 證明本文建立的模型和算法可以有效提高訂單響應速度, 降低訂單履行成本。

聯(lián)合優(yōu)化; 組合策略; 需求可拆分; 時間窗; 兩階段算法

0 引 言

隨著電子商務的發(fā)展，我國快遞量高速增長，2017年國內快遞量突破400億件，其中電子商務驅動的快件量超過130億件。高速增長的快遞量使企業(yè)面臨成本居高不下、快遞爆倉、暴力分揀、配送延誤等問題，同時消費者對商品送達時效性要求更高，提高訂單履行效率、縮短訂單響應時間是電子商務企業(yè)亟待解決的問題。

訂單履行包括揀選和配送兩個環(huán)節(jié)，配送路徑優(yōu)化決定車輛訂單及其揀選截止時間（PickingDue Date，簡稱PDD），訂單PDD影響揀選批次劃分和批次揀選順序，批次揀選順序影響批次揀選完成時間，從而影響車輛開始配送時間。而將揀選與配送聯(lián)合優(yōu)化可以從整體上降低5%~20%的成本[1-3]。此外，電子商務環(huán)境下需求呈現(xiàn)數量少、種類多的特點，若1個需求點由1個人員揀選并由1輛車配送效率太低，拆分需求可以提高車輛滿載率、縮短配送距離、提高配送準點率[4-6]。

因此，本文借鑒生產與配送聯(lián)合優(yōu)化（Integrated Production and Delivery Problem，簡稱IPDP）成果，將揀選視為生產環(huán)節(jié)，研究時間窗約束下需求可拆分的揀選與配送聯(lián)合優(yōu)化問題（Integrated Optimization of Picking and Spilt Delivery Problem under Time Windows，簡稱IOPSDPTW）。2005年Chen等[1-3]提出了IPDP問題，并于2010年構建了該問題的通用模型[1-3]，接著越來越多的學者進行了深入的研究，目前國內外對IPDP的研究有以下特點：從確定性環(huán)境[7]轉向不確定環(huán)境的研究[8]；從一般行業(yè)的聯(lián)合優(yōu)化轉向研究新興行業(yè)的聯(lián)合優(yōu)化[9]；配送階段從簡單的VRP問題轉向CVRP[10]、VRPTW[11]等復雜VRP問題的研究；生產階段從單機轉向并行機的聯(lián)合優(yōu)化[12]。

目前對于IPDP的研究較為豐富，但對于揀選與配送聯(lián)合優(yōu)化問題（Integrated Order Picking and Delivery Scheduling，IOPDS）的研究較少。Su等[10]首次研究了帶車輛容量約束的單車輛IOPDS問題及其分階段算法，根據任意兩個配送批次之間有無等待時間調整，但并未研究揀選分批問題；而王旭坪等[13]第一次詳細研究了單車輛IOPDS及其三階段算法，論述了IOPDS問題的不同，根據配送時間調整揀選順序，但僅僅基于揀選通道相似度進行分批；Zhang等[14,15]研究了基于通道相似度與時間緊急度的混合分批規(guī)則。還有一部分學者主要從配送階段進行深入探討，Schubert等[16]證明了與非聯(lián)合優(yōu)化相比，帶截止時間、時間窗等復雜VRP的IOPDS問題及其分階段禁忌搜索算法平均減少了37.8%的配送延遲時間。

綜上所述，IOPDS的研究大多是從訂單分批和配送路徑兩方面進行單獨的深入研究，文獻[14,15]研究了混合分批規(guī)則，但配送階段為單車輛TSP問題，文獻[16]研究揀選階段為單一員工訂單分批和批次排序問題。此外，目前的研究主要采用S-Shape揀選策略和分階段算法，尚未考慮揀選截止時間和需求可拆分。因此，本文針對以上不足，考慮增加拆分需求成本，揀選階段采用分區(qū)組合揀選策略提高揀選效率[17]，提出了IOPSDPTW，并設計兩階段算法求解，對IOPDS進行進一步拓展研究。

1 研究問題與模型

1.1 問題描述

圖1 IOPSDPTW流程圖

訂單配送階段解決時間窗約束下需求可拆分的車輛路徑問題（Spilt Delivery Vehicle Routing Problem，SDVRP），保證所有需求得到滿足，且車輛在倉庫裝貨，完成配送后返回倉庫；在訂單揀選階段，結合訂單PDD構建訂單處理規(guī)則，解決并行分區(qū)系統(tǒng)下訂單分批和批次排序問題（Order Batching and Batch Sequencing Problem under Synchronized Zone Order Picking System，OBBSPSZOPS），相關符號說明如下：

決策變量：

1.2 目標函數

該模型目標是由揀選成本、拆分需求成本、配送成本和懲罰成本四部分組成的訂單履行成本最小化，即：

圖2 揀選距離計算示意

通道揀選距離計算如下：

配送成本包括車輛路徑成本和車輛調度成本，即：

綜上，訂單履行的總成本為：

1.3 約束條件

（1）拆分需求約束

本文考慮需求拆分揀選和配送，但訂單不可拆分，即：

（2）容量約束

在實際情況中，配送車輛和揀選裝置有容量約束，即：

（3）揀選約束

②批次揀選順序與時間約束。兩個批次之間揀選順序唯一，揀選人員必須揀選完上一批次才能繼續(xù)揀選下一批次，即：

（4）配送約束

① 節(jié)點被訪問數量約束。每一條路徑均從配送中心出發(fā)再返回配送中心，所有需求都要被滿足，即：

②路徑配送流量約束。配送遵循能量守恒定律，即：

③路徑分配和所屬區(qū)域的約束。每一條配送路徑都要分配相應的車輛進行配送，即：

④配送順序約束。路徑上兩個需求點之間的配送順序唯一，即：

⑤局部子回路約束。配送路徑不能出現(xiàn)局部子回路，即：

（5）變量取值約束

2 算法設計

文獻[13]證明了揀選與配送聯(lián)合優(yōu)化問題是NP-hard問題，而本文是考慮時間窗和需求可拆分的IOPDS問題，是對IOPDS問題的進一步研究與深入，無法用精確算法求解?，F(xiàn)有研究中，文獻[11]采用了S-AGA和AGA-2OPT算法求解IPDP問題，文獻[14-15]基于遺傳算法和聚類算法求解IOPDS問題。IOPSDPTW問題的揀選和配送兩個環(huán)節(jié)相互制約，共同影響需求被服務的時刻，因此兩階段需統(tǒng)籌優(yōu)化，本文設計兩階段算法求解該問題，配送階段采用遺傳算法，揀選階段采用訂單操作算法，兩個階段通過遺傳算法的適應度函數連接成一個整體，即在適應度函數計算時調用訂單操作算法求解最優(yōu)的訂單分批和批次順序，從而使得揀選成本最低。

2.1 遺傳算法

step2 初始種群生成。初始種群要滿足可行性、隨機性和高質量性三個條件，據此，首先需要確定較好質量的解在種群中所占比例，在比例內采用最鄰近插入法生成初始種群，比例外采用隨機插入法生成初始種群。

step4 遺傳算子設計。遺傳算子包括選擇、交叉、變異和拆分可行化算子，選擇操作采用精英選擇策略，其他算子設計如下：

① 交叉。隨機生成小于1的兩個數1和2作為交叉點，由于SDVRP存在過度拆分不可行解，交叉點之間的子串需要整體取出，因此取出兩條父代染色體1、2交叉點之間的完整化子串middle1和middle2后，再按順序將其他節(jié)點從左至右填充，具體如圖3所示，其中深色代表交叉點子串，淺色代表完整化子串。

圖3 改進后的遺傳算子操作示意圖

②變異。在交叉完成后，采用固定概率進行變異操作，隨機生成小于1兩個數1和2作為變異位，對位于變異點之間的完整化子串進行逆序操作，具體操作如圖3所示。

step5設置最大迭代次數1 000為進化終止條件。

2.2 訂單操作算法

訂單分批完成后，需要對各個揀選批次的先后順序進行調整，本文考慮按批次訂單的車輛離開時間和包裝難度進行批次揀選順序的調整，即車輛離開時間越早、包裝難度越大的批次揀選順序越靠前，最后將批次訂單分配給各個分區(qū)的人員揀選。

圖4 訂單分批流程圖

2.3 對比算法

本文的對比方案為組合揀選策略下需求不拆分的揀選與配送聯(lián)合優(yōu)化問題（Integrated Optimization of Picking and Delivery Problem under Time Windows and Combined Strategy, IOPDPTW- C）、S-Shape揀選策略下需求可拆分的揀選與配送聯(lián)合優(yōu)化問題（Integrated Optimization of Picking and Spilt Delivery Problem under Time Windows and S-Shape Strategy, IOPSDPTW-S）、順序決策算法（Sequential Decision Algorithm）求解IOPSDPTW（SDA-IOPSDPTW），三種方案與IOPSDPTW相比不同的是IOPDPTW-C配送階段考慮需求一次性全部配送完成，揀選階段與IOPSDPTW一致，配送階段的模型和算法參考侯玉梅等[19]提出的軟時間窗整車物流配送路徑優(yōu)化模型和算法；IOPSDPTW-S考慮揀選階段采用S-Shape策略進行揀選，S-Shape策略批次揀選距離計算參考張珺[20]提出的方法；而SDA-IOPSDPTW則是采用順序決策算法求解IOPSDPTW問題，其中順序決策算法主要流程為：

step1 訂單分批。不考慮訂單所屬車輛的離開時間，直接建立揀選通道相似度指標，采用種子算法進行訂單分批，不對批次的揀選順序進行調整；

step2 路徑優(yōu)化。不考慮揀選對車輛離開配送中心時間的調整，對SDVRP問題進行求解，以最小化配送成本為目標優(yōu)化配送路徑；

step3 整合step1和step2的解。

3 仿真實驗

3.1 參數設計

3.2 結果分析

算法迭代到598次已經收斂到最優(yōu)解，收斂較快，算法收斂情況如圖5，實例配送路徑如圖6，從路徑圖可以看出，需求點3、5、11的客戶需求拆分到兩輛車進行配送。

圖5 目標函數值隨迭代次數的變化情況

圖6 車輛的配送路徑

為了驗證拆分需求是否可以降低總成本，將IOPSDPTW與IOPDPTW-C各項成本進行對比分析，具體數據如表1所示，從表中看出，IOPSDPTW總成本為341.311 3元，低于IOPDPTW-C總成本512.688元，優(yōu)化率為33.43%。

表1 各方案成本對比

Tab.1 Cost comparison of programs

從成本組成來看，IOPSDPTW增加了拆分需求成本，同時揀選成本上升，這是由于與IOPDPTW-C相比，車輛訂單在倉庫內分布更分散。但是在IOPSDPTW問題中，拆分需求成本和揀選成本在總成本中占比僅為12.1%和12.6%，兩個成本對總成本的影響相對較小。

與IOPDPTW-C相比，拆分需求后懲罰成本下降了70.64%，這是由于一個需求點對應多個時間窗，IOPDPTW-C使得車輛到達一個需求點后會產生多個節(jié)點的時間窗懲罰成本，而IOPSDPTW使得不同的車輛可以在需求點相對應的時間窗內到達，從而降低需求點懲罰成本。

本文采用組合策略，表2為IOPSDPTW和IOPSDPTW-S的訂單揀選時間，從表1和表2中可以看出，采用組合策略和S-Shape策略四輛車的訂單揀選時間分別為0.2332、0.3536、0.4796、0.5860和0.3288、0.4766、0.6262、0.7575，采用組合策略縮短了每一配送批次的揀選時間，降低了揀選成本，優(yōu)化率為24.52%。

表2 各方案揀選時間對比

Tab.2 Picking time of programs

為更好地分析本文研究問題和算法效果，將本文提出算法與該問題采用順序決策算法的各項成本進行對比，具體數據如表1所示，從表中可以看出，與順序決策算法相比，兩階段算法優(yōu)化了28.17%的總成本。

基于兩階段算法的揀選批次數量為16，同樣基于順序決策算法將訂單劃分為16個揀選批次，兩階段算法與順序決策算法的揀選時間如表2所示。從表中可看出對于IOPSDPTW問題，兩階段算法和順序決策算法的揀選成本分別為41.31元和41.625元，優(yōu)化率為0.76%。

與順序決策算法相比，兩階段算法計算出的拆分需求成本為72.98元，優(yōu)化率為40.9%；配送成本為194.1431元，優(yōu)化率為18.12%；懲罰成本為123.433元，優(yōu)化率為49.18%。其中懲罰成本的優(yōu)化率達到了49.18%，這是因為兩階段算法按揀選截止時間分批和調整批次揀選順序以后，使得配送車輛在時間窗內到達的節(jié)點增多，數據如表3所示。

表3 各方案偏離時間窗程度表

Tab.3 Time window deviation of programs

4 結 論

本文第一次提出了時間窗約束下需求可拆分的揀選與配送聯(lián)合優(yōu)化問題，結合揀選截止時間、時間窗、車輛容量約束等建立了數學模型，并設計兩階段算法求解，以IOPDPTW-C、IOPSDPTW-S和SDA-IOPSDPTW作為對比應用場景，結果表明，拆分需求后將需求點按不同時間窗配送，增加了拆分需求成本，但懲罰成本減少了70.64%，總成本下降了33.43%；而采用分區(qū)組合策略揀選，與全區(qū)域S-Shape揀選策略下的IOPSDPTW相比，揀選成本減少了24.52%，總成本減少了12.3%；此外本文提出的算法與順序決策算法相比，總成本節(jié)約了28.17%，證明本文研究的IOPSDPTW問題和算法對物流企業(yè)運作具有重大意義。DNA本文僅研究了需求量已知的情況，現(xiàn)在隨著信息技術發(fā)展，實時訂單系統(tǒng)下的IOPSDPTW有待進一步研究。

[1] CHEN Z L, Vairaktarakis G L. Integrated scheduling of production and distribution operations[J]. Management Science, 2005, 51(4): 614-628.

[2] CHEN Zhi-Long. Integrated production and outbound distribution scheduling: review and extensions[J]. Operation Research, 2010, 58(1): 130-148.

[3] CHANG Y C, LI V C, CHIANG C J. An ant colony optimization heuristic for an integrated production and distribution scheduling problem [J]. Engineering Optimization, 2014, 46(4): 503-520.

[4] WANG X, GOLDEN B, WASIL E, et al. The min–max split delivery multi-depot vehicle routing problem with minimum service time requirement[J]. Computers & Operations Research, 2016, 71: 110-126.

[5] 符卓, 劉文, 邱萌. 帶軟時間窗的需求依訂單拆分車輛路徑問題及其禁忌搜索算法[J]. 中國管理科學, 2017, 25(5): 78-86.

[6] 郭海湘, 潘雯雯, 周欣然, 等. 基于單車場多車型車輛路徑問題的混合求解算法[J]. 系統(tǒng)管理學報, 2017(5): 824-834.

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

[8] 方伯芃, 孫林夫. 不確定環(huán)境下的產業(yè)鏈生產與配送協(xié)同調度優(yōu)化[J]. 計算機集成制造系統(tǒng), 2018, 24(1): 224-244.

[9] MARANDI F, ZEGORDI S H. Integrated production and distribution scheduling for perishable products[J]. Scientia Iranica, 2017, 24(4): 2105-2118.

[10] GAO S, QI L, LEI L. Integrated batch production and distribution scheduling with limited vehicle capacity[J]. International Journal of Production Economics, 2015, 160: 13-25.

[11] LOW C, CHANG C M, GAO B Y. Integration of production scheduling and delivery in two echelon supply chain[J]. International Journal of Systems Science Operations & Logistics, 2015, 4(2): 122-134.

[12] BELO-FILHO M A F, AMORIM P, ALMADA-LOBO B. An adaptive large neighbourhood search for the operational integrated production and distribution problem of perishable products[J]. International Journal of Production Research, 2015, 53(20): 6040-6058.

[13] 王旭坪, 張珺, 易彩玉. B2C電子商務環(huán)境下訂單揀選與配送聯(lián)合調度優(yōu)化[J]. 中國管理科學, 2016, 24(7): 101-109.

[14] ZHANG J, WANG X, HUANG K. On-line scheduling of order picking and delivery with multiple zones and limited vehicle capacity[J]. Omega, 2017.

[15] ZHANG J, WANG X, HUANG K. Integrated on-line scheduling of order batching and delivery under B2C e-commerce[J]. Computers & Industrial Engineering, 2016, 94(C): 280-289.

[16] SCHUBERT D, SCHOLZ A, W?SCHER G. Integrated order picking and vehicle routing with due dates[J]. Or Spectrum, 2018: 1-31.

[17] 王旭坪, 張珺, 易彩玉. 電子商務人工并行分區(qū)揀選系統(tǒng)服務效率優(yōu)化研究[J]. 管理工程學報, 2017, 31(2): 209-215.

[18] ELSAYED E A, STERN R G. Computerized algorithms for order processing in automated warehousing systems[J]. International Journal of Production Research, 1983, 21(4): 579-586.

[19] 侯玉梅, 賈震環(huán), 田歆, 等. 帶軟時間窗整車物流配送路徑優(yōu)化研究[J]. 系統(tǒng)工程學報, 2015, 30(2): 240-250.

[20] 張珺. B2C電子商務訂單分批揀選與配送聯(lián)合調度[D]. 大連: 大連理工大學, 2017.

Integrated Optimization of Picking and Split Delivery Problem under Time Windows

XU Ling1,2，HU Xiao-lin1，HU Xiao-liang1

(1. School of Transportation and Logistic, Southwest Jiaotong University, Chengdu 611756, China; 2. National United Engineering laboratory of Intergrated and Intelligent Transportation, Chengdu 611756, China)

In view of the problem of low order fulfillment efficiency that enterprises need to solve urgently, an integrated optimization of picking and delivery model is established based on the idea of split delivery, considering the time window and the characteristics of combined picking strategies. The order fulfillment efficiency is reflected by picking cost, split delivery cost, distribution cost, and time penalty cost. We calculated the optimization using split demand, combination strategy, and an algorithm for the model. A two-phase heuristic algorithm was used to solve the model. Subsequently, the effectiveness of the model and the algorithm were verified using an example. Finally, compared with the non-split delivery, the S-shapestrategy, and the sequential decision algorithm, the total cost decreased by 33.43%, 12.3%, and 28.17% respectively. The results show that the model and algorithm established in this study can effectively improve the order response speed and reduce the order fulfillment cost.

integrated optimization; combination strategy; spilt delivery; time window; two-phase heuristic algorithm

1672-4747（2020）02-0018-12

N945.12

A

10.3969/j.issn.1672-4747.2020.02.003

2019-07-08

鐵路總公司科技研究開發(fā)計劃項目（2013X009-A-1-2）；四川省重點科技計劃項目（2014GZ0019）

徐菱（1965—），女，四川成都人，教授，博士生導師，研究方向：物流系統(tǒng)規(guī)劃與設計等，E-mail：xlhu173@163.com

徐菱，胡小林，胡小亮. 時間窗約束下需求可拆分的揀選與配送聯(lián)合優(yōu)化問題研究[J]. 交通運輸工程與信息學報, 2020, 18（2）：18-29.

（責任編輯：劉娉婷）