客戶配送要求變動下的VRPSDP干擾管理優(yōu)化

趙 亮，梁曉萍，楊華龍，王 征

(大連海事大學交通運輸管理學院，遼寧大連116026)

0 引言

在許多實際物流配送問題中，客戶同時具有送貨和取貨兩種需求，這樣便產(chǎn)生了同時送取貨車輛路徑問題(Vehicle Routing Problem with Simultaneous Delivery and Pickup VRPSDP)[1]，它是經(jīng)典VRP的一個變種，其車輛負載并不像其在VRP中那樣單調(diào)變化[2].隨著近年來電子商務(wù)等快速發(fā)展，客戶需求變得觸手可及，經(jīng)常會出現(xiàn)來自客戶需求或時間窗變動等配送要求不確定性因素，對原配送計劃造成干擾，導致原配送方案無法順利實施[3].因此，考慮客戶配送要求變動的VRPSDP已被業(yè)界高度關(guān)注.

國內(nèi)外學者針對配送過程中出現(xiàn)不確定性問題的研究大體可分為3種方法：第1種方法是運用隨機動態(tài)知識，通過預(yù)測未來可能發(fā)生的干擾事件，采取相應(yīng)的措施減小干擾對整個配送系統(tǒng)帶來的影響[4]，但是，該方法的局限性主要是預(yù)測的準確性無法保證；第2種方法是對車輛路徑問題進行重新優(yōu)化[5]，此方法沒有綜合考慮原配送方案，很容易造成原計劃配送時間的偏離和客戶不滿意度的增加；于是許多學者提出了第3種方法，即基于干擾管理思想，在原方案基礎(chǔ)上進行實時調(diào)整以滿足要求[6]，但現(xiàn)有研究主要針對的是VRP問題[7].王旭坪等[8]對帶回程取貨的車輛調(diào)度(VRPB)干擾恢復問題進行了研究，但該研究考慮的是送貨和取貨無交叉的VRPB問題，若客戶有同時送貨和取貨的需求，則將其看成2個客戶進行2次服務(wù)，這樣不僅會出現(xiàn)車輛行駛路線重復的現(xiàn)象，而且還容易增加客戶的不滿意度.

鑒于此，本文針對客戶需求和時間窗等配送要求變動的VRPSDP問題，同時考慮同1位客戶的送貨和取貨需求，并將其看作1次服務(wù)，綜合分析干擾事件對配送車輛成本和服務(wù)時間偏離的影響，構(gòu)建以廣義費用偏離最小化為目標的VRPSDP干擾管理模型，并設(shè)計求解算法，以期解決客戶配送要求變動下的VRPSDP優(yōu)化問題.

1 問題描述

物流企業(yè)在配送時，通常會以成本最低為目標，通過建立VRPSDP模型，制定一個優(yōu)化同時送取貨的車輛路徑方案.顯然，當干擾發(fā)生時，新的車輛路徑方案不包括已經(jīng)服務(wù)完成的客戶.因此，本文研究的客戶需求和時間窗等配送要求變動的VRPSDP干擾管理模型，是在文獻[9]模型的基礎(chǔ)上，通過干擾辨識和擾動度量，建立擾動恢復模型，用以制定干擾發(fā)生后余下客戶的優(yōu)化配送方案.

干擾辨識是指判斷干擾事件是否對原配送方案造成了干擾.主要包括以下4種情況：

(1)當配送車輛所裝載的貨物量無法滿足未服務(wù)客戶點的需求量時，產(chǎn)生干擾；

(2)當配送車輛剩余的載重量無法滿足未服務(wù)客戶點要求的取貨量時，產(chǎn)生干擾；

(3)當客戶時間窗提前時，原方案中客戶的開始服務(wù)時間晚于新時間窗，產(chǎn)生干擾；

(4)當客戶時間窗延后時，按初始方案不能對車輛未服務(wù)的所有后續(xù)客戶按要求配送或取貨，產(chǎn)生干擾.

客戶需求和時間窗變動產(chǎn)生的干擾事件對物流配送車輛路徑方案的擾動影響，主要體現(xiàn)在成本和服務(wù)時間的偏離上.在成本偏離上：一是，增派車輛而產(chǎn)生的派車成本；二是，由于路徑偏離產(chǎn)生的與路徑長度有關(guān)的運輸成本的增減.例如，車輛k原路徑為rijk(表示從客戶i到客戶j的路徑)，若車輛從客戶i出發(fā)前就已知要改變原路線，先去服務(wù)客戶h再去服務(wù)客戶j，如圖1(a)所示，這時路徑的偏離可表示為rijk的減少和rihk、rhjk的增加；若車輛k在從客戶i出發(fā)后，臨時得知需要變更下一個客戶點，即車輛已經(jīng)在需要改變的路線上，此時車輛位置為pk，如圖1(b)所示，這時原路線并沒有完全減少，而是與新路線有重合部分ripkk，路徑的偏離可表示為rpkjk的減少和rpkhk、rhjk的增加.

圖1 路徑偏離示意圖Fig.1 The diagram of route deviation

在客戶服務(wù)時間偏離上，本文引入時間偏離懲罰系數(shù)將時間偏離轉(zhuǎn)換成廣義時間費用.即在車輛路徑方案調(diào)整后，若車輛到達客戶點時，該客戶的時間窗尚未打開，則車輛需要在原地等待，此時，單位時間偏離系數(shù)記為α；若車輛到達客戶j的時間在客戶滿意的截止時間(即按原方案到達客戶的時間)和硬時間窗之間，此時車輛的到達時間雖然仍在時間窗內(nèi)，但卻晚于原方案到達客戶的時間，這樣可能也會對客戶的滿意度造成一定的影響，為此，引入單位時間懲罰系數(shù)記為β(β≥0)，其中，β=0表示對客戶滿意度未產(chǎn)生影響；若車輛到達客戶點時，該客戶的時間窗已經(jīng)關(guān)閉，該車輛不能再對其服務(wù)，則可將懲罰系數(shù)定義為一個無窮大的正數(shù)M.

2 模型的建立

2.1 模型假設(shè)和符號定義

本文做以下假設(shè)：

(1)針對1個車場的物流配送系統(tǒng)，且車輛數(shù)有限；

(2)車輛所載貨物是同質(zhì)的，所有車輛的載重能力相同；

(3)客戶有硬時間窗約束；

(4)每個客戶只能由1輛車進行配送服務(wù).

模型中的變量及參數(shù)符號定義如下：

N——擾動發(fā)生后未服務(wù)的客戶數(shù)量；

Qmax——配送車輛的最大載重量；

v——配送車輛的行駛速度；

S——配送車輛在客戶的服務(wù)時間；

T——擾動發(fā)生的時刻；

——擾動發(fā)生后車輛k正在服務(wù)的客戶；

pk——擾動發(fā)生后車輛k在行駛途中(未在客戶點)的位置；

Qk——擾動發(fā)生后車輛k的剩余送貨量；

qj——擾動發(fā)生后未服務(wù)客戶j處的送貨量；

Gk——擾動發(fā)生后車輛k已裝載的取貨量；

gj——擾動發(fā)生后未服務(wù)客戶j處的取貨量；

L——擾動發(fā)生時在途車輛的數(shù)量；

K——擾動發(fā)生時車場中的剩余車輛的數(shù)量；

C1——從車場派出1輛車的固定成本；

C2——單位路徑長度的車輛行駛成本；

dij——客戶i到客戶j的距離；

dpkj——擾動發(fā)生后原車輛k從所在位置到客戶j的行駛距離；

dk——車輛k按原方案服務(wù)擾動發(fā)生后剩余客戶的總行駛距離；

Sj——原方案中開始服務(wù)客戶j的時間；

——新方案中開始服務(wù)客戶j的時間；

Tj——原方案中車輛到達客戶j的時間；

——新方案中車輛到達客戶j的時間；

δj——客戶j的服務(wù)時間偏離懲罰；

fijk——配送車輛k行駛在途中(客戶i到客戶j)的荷載量；

[ETj,LTj]——擾動發(fā)生后未服務(wù)客戶j的時間窗.

2.2 干擾管理模型

針對物流配送過程中客戶需求和時間窗的變動，本文建立的擾動恢復模型為

式(1)是使廣義總費用偏離最??；式(2)和式(3)表示每個客戶被且只被1輛車服務(wù)；式(4)和式(5)分別表示在途車輛和新派車輛送貨量約束；式(6)和式(7)分別表示在途車輛和新派車輛取貨量約束；式(8)和式(9)表示車輛在每個客戶送取貨前后途中荷載量約束；式(10)增派救援的車輛數(shù)不能超過車場中的剩余車輛數(shù)；式(11)表示未服務(wù)客戶的開始服務(wù)時間約束；式(12)表示車輛到達未服務(wù)客戶的時間約束；式(13)為時間偏離懲罰取值；式(14)為變量的取值約束.

3 算法設(shè)計

VRPSDP問題是NP難題[10]，啟發(fā)式算法等已成為求解VRPSDP問題的主要方法[11].對于客戶配送要求變動的干擾，物流配送企業(yè)需要快速做出調(diào)整決策.而禁忌搜索是局部鄰域搜索算法的擴展，是一種全局逐步尋優(yōu)的啟發(fā)式算法，搜索速度快，適用于大規(guī)模的優(yōu)化計算[12].因此，本文運用禁忌搜索來設(shè)計求解算法，設(shè)計的算法流程如圖2所示.

根據(jù)圖2，本文設(shè)計如下禁忌搜索算法步驟：

Step 1根據(jù)干擾產(chǎn)生的條件，判斷需求量或時間窗的變動是否對原方案造成干擾，若不造成干擾，則直接執(zhí)行原方案；若造成干擾，則執(zhí)行Step2.

Step 2選出可以嘗試救援的在途車輛，即該車輛有足夠的貨物滿足擾動客戶的新增需求量，有足夠的空間裝載擾動客戶的新增取貨量，并可以在擾動客戶的時間窗內(nèi)到達并服務(wù).若存在可以救援的在途車輛，則執(zhí)行Step3；否則，執(zhí)行Step4.

Step 3確定候選解.令干擾發(fā)生時的當前車輛配送狀態(tài)為初始解.將擾動客戶從原路線中取出，插入每輛在途車輛與下一個客戶之間，并結(jié)合2-opt局部搜索將干擾客戶與其相鄰的客戶序列互換，生成有限個候選解.

Step 4設(shè)計禁忌表.將取出的擾動客戶所插入到每條路線中的位置作為禁忌對象，當擾動點插入到某一位置后，在規(guī)定搜索次數(shù)為l次的禁忌長度內(nèi)，擾動點插入到該位置的情況被禁忌.在禁忌搜索中，可能出現(xiàn)候選解全部被禁忌現(xiàn)象，或者存在1個優(yōu)于“best so far”狀態(tài)的禁忌候選解，此時特赦準則將某些狀態(tài)解禁，其對應(yīng)的對象替換最早進入禁忌表中的對象，更新為最優(yōu)狀態(tài).

Step 5判斷從車場派車能否進行救援.若能，則派出新的車輛進行救援，處理結(jié)束；若不能，則放棄服務(wù)該客戶.

4 算例分析

本文采用Solomon標準測試算例，選取R207、R211、RC208中每組數(shù)據(jù)的前30個和前60個客戶作為測試算例.由于原算例中沒有各個客戶的取貨量數(shù)據(jù)，為方便分析，本文采用正態(tài)分布隨機賦予一定的取貨量.假設(shè)在T=50時刻客戶配送要求發(fā)生變動，隨機生成的干擾信息如表1所示.

表1 各組數(shù)據(jù)客戶信息變動情況Table 1 Each data changes in customer’s information

本文首先將參數(shù)取值為：C1=140，C2=1，且車輛的行駛速度為單位速度，以配送總成本最低為目標，借鑒文獻[7]，運用遺傳算法運行10次，選取其中最優(yōu)的初始配送方案作為該算例的初始路徑方案.其次，利用禁忌搜索算法對隨機生成的干擾事件進行求解，得到干擾管理方案.將其成本偏離、時間偏離和廣義總費用偏離與增派車輛方案及全局重調(diào)度方案的各項指標進行對比，結(jié)果如表2所示.

表2 R207、R211、RC208測試偏離結(jié)果比較Table 2 Compared deviation results of R207,R211 and RC208 dataset

分析測試結(jié)果，可得出以下結(jié)論：

(1)比較6組測試數(shù)據(jù)的3種方案結(jié)果可以看出，若采納增派車輛方案，則成本偏離較高；若采納全局重調(diào)度方案，雖然成本偏離較低，但時間偏離和廣義總費用偏離遠高于干擾管理方案，易增加客戶不滿意度；采用干擾管理方案，廣義總費用偏離較其他兩個方案至少降低了12.6%.

以數(shù)據(jù)R207的前30個客戶為例，其初始配送方案如圖3所示.干擾發(fā)生時刻，車輛1已服務(wù)完客戶28，正在前往客戶23的途中；車輛2正在客戶27等待為其服務(wù)；車輛3已服務(wù)完客戶24，正在前往客戶3；車輛4已服務(wù)完客戶18，正在前往客戶8的途中；車輛5正在客戶17等待為其服務(wù).

圖3 初始配送路徑Fig.3 The original distribution routes

運用本文方法生成的方案如圖4所示：得到的廣義總費用偏離為545.3，算法的運行時間為6.3 s，符合快速響應(yīng)的干擾管理要求.若采用增派車輛方案，即保持原有最優(yōu)行車不變，則需要新增1輛車，這時的廣義總費用偏離為629.4.若采用全局重調(diào)度方案，即以成本最小化為目標，重新尋找服務(wù)剩余客戶的最優(yōu)車輛路徑，則得到的廣義總費用偏離為1 941.9.

圖4 調(diào)整路徑方案Fig.4 The adjustment routes solution

(2)將R207、R211和RC208中客戶數(shù)為30和客戶數(shù)為60時的各方案進行對比，干擾管理方案與增派車輛方案和全局重調(diào)度方案下的廣義總費用偏離差別明顯.當客戶數(shù)為60時，運用干擾管理方法節(jié)約的廣義總費用偏離均大于客戶數(shù)為30時節(jié)約的廣義總費用偏離；說明客戶越多，本文的方法相比較其他方法越占優(yōu)勢.

(3)從算例的搜索時間來看：客戶數(shù)為30時，其搜索時間大概在7 s左右；客戶數(shù)為60時，其搜索時間大概在31 s左右.這是由于需將擾動客戶插入到每條路線中進行測試，客戶越多，搜索時間就會越長.上述所有算例干擾管理方案的搜索時間都不超過35 s，可以滿足干擾恢復的及時性要求.

綜上，本文的干擾管理方案在時間偏離和廣義總費用偏離方面有著明顯的優(yōu)勢，可以減小配送成本并提高客戶滿意度，從而保證了物流公司和客戶的整體利益.

5 結(jié) 論

本文研究了有客戶需求和時間窗變動的VRPSDP干擾管理問題，以廣義總費用偏離最小為目標，建立了客戶需求和時間窗變動的干擾管理模型，從而可以全面地刻畫各擾動因素的影響，且能夠在較短時間內(nèi)生成滿意的物流配送車輛調(diào)度調(diào)整方案.

需說明的是，本文模型是在硬時間窗約束下構(gòu)建的，由于天氣等外部不確定性因素可能會導致原方案無法實施.因此考慮外部不確定性因素的VRPSDP干擾管理問題值得進一步的研究.

[1]MIN H.The multiple vehicle routing problem with simultaneous delivery and pick-up points[J].Transportation Research Part A：General,1989,23(5)：377-386.

[2]張亞明,李娜.基于精英單親遺傳算法的冷鏈物流VRP模型優(yōu)化研究[J].數(shù)學的實踐與認識,2016,46(4)：87-96.[ZHANG Y M,LI N.Research on elite selection based partheno-genetic algorithm under optimized cold-chain logistics VRP model[J].Mathematics in Practice and Theory,2016,46(4)：87-96.]

[3]丁秋雷.客戶時間窗變化的物流配送干擾管理模型—基于行為的視角[J].中國管理科學,2015,23(5)：89-97.[DING Q L.Model of disruption management for the change of time window based on human behavior in logistic disruption[J].Computer&Operations Research,2015,23(5)：89-97.]

[4]SCHYNS M.An ant colony system for responsive dynamic vehicle routing[J].European Journal of Operational Research,2015,245(3)：704-718.

[5]ZHANG T,CHAOVALITWONGSE W A,ZHANG Y J.Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries[J].Computers&Operations Research,2012,39(10)：2277-2290.

[6]王征,胡祥培,王旭坪.行駛時間延遲下配送車輛調(diào)度的干擾管理模型與算法[J].系統(tǒng)工程理論與實踐,2013,33(2)：378-387.[WANG Z,HU X P,WANG X P.Disruption managementmodeland algorithm for distribution vehicle scheduling problems under accidental travel time delay[J].System Engineering Theory&Practice,2013,33(2)：378-387.]

[7]楊華龍,葉迪,張倩,等.時間窗變動的車輛調(diào)度干擾管理模型與算法[J].運籌與管理,2017,26(10)：56-64.[YANG H L,YE D,ZHANG Q,et al.Disruption management model and algorithm for vehicle scheduling with time window changes[J].Operations Research and Management Science,2017,26(10)：56-64.]

[8]王旭坪,阮俊虎,孫自來,等.帶回程取貨車輛路徑問題的干擾回復模型[J].系統(tǒng)工程學報,2013,28(5)：608-616.[WANG X P,RUAN J H,SUN Z L,et al.Disruption recovery modal for vehicle routing problem with backhaul[J].Journal of Systems Engineering,2013,28(5)：608-616.]

[9]王超,穆東.基于模擬退火算法求解VRPSPDTW問題 [J].系統(tǒng)仿真學報,2014,26(11)：2618-2623.[WANG C,MU D.Solving VRPSPDTW problem using simulated annealing algorithm[J].Journal of System Simulation,2014,26(11)：2618-2623.]

[10]LAI M Y,LIU C S,TONG X J.A two-stage heuristic for pickup and delivery vehicle routing problem with time windows[J].Journal of Industrial&Management,2017,6(2)：435-451.

[11]柴獲,何瑞春,馬昌喜,等.求解帶硬時間窗車輛路徑問題的改進UMDA算法[J].交通運輸系統(tǒng)工程與信息,2016,16(2)：176-182.[CHAI H,HE R C,MA C X,et al.A univariate marginal distribution algorithm hybridized with insertion heuristics for the vehicle routing problem with hard time windows[J].Journal of Transportation Systems Engineering and Information Technology,2016,16(2)：176-182.]

[12]胡祥培,孫麗君,王雅楠.物流配送系統(tǒng)干擾管理模型研究[J].管理科學學報,2011,14(1)：50-59.[HU X P,SUN L J,WANG Y N.A modal for disruption management in urban distribution systems[J].Journal of Management Sciences in China,2011,14(1)：50-59.]