辛禹辰，李潤超，楊華龍

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

0 引言

隨著互聯(lián)網的飛速發(fā)展，電商環(huán)境下客戶的商品交付和退貨需求不斷增長。物流企業(yè)安排配送車輛進行同時送取貨服務，既可以節(jié)省運營成本，又能減少車輛對環(huán)境的不良影響，制訂同時送取貨車輛路徑問題(Vehicle Routing Problem with Simultaneous Delivery and Pickup,VRPSDP)方案已成為物流企業(yè)日常運營中的一個核心決策問題[1]。然而，在VRPSDP 方案的實際執(zhí)行過程中，會發(fā)生客戶請求頻繁變動的情形，如客戶取消送/取貨請求，客戶送/取貨量或時間窗發(fā)生改變，這種隨時出現的每次變動都可能對VRPSDP方案造成干擾，導致車輛配送無法按原方案執(zhí)行。因此，在無法準確預判客戶請求變動發(fā)生時間及頻率的情況下，如何對VRPSDP 方案加以有效調整是物流企業(yè)面臨的一個十分急迫的復雜問題。

VRPSDP 是典型NP 難問題VRP 的擴展，學者們早期研究大多關注VRPSDP 算法。如?ztas 等[2]使用迭代局部搜索、可變鄰域下降和元啟發(fā)式相結合的混合算法來解決VRPSDP，降低了算法的設計難度；Gupta 等[3]結合模擬退火、粒子群優(yōu)化和遺傳算法的優(yōu)點提出一種混合算法來解決具有時間窗口和有限車輛的同時提取和交付問題。上述研究均是在客戶請求給定情形下開展的，若在車輛配送過程中出現客戶請求變動的情形，許多文獻會采取全局重調度方法進行方案調整，即以整個車輛配送系統(tǒng)總費用最低為目標，制訂出全局優(yōu)化的新調整方案[4]。這種方法犧牲了原任務配送時間的及時性和準確性，容易增加配送車輛司機工作壓力和降低客戶滿意度。為此，已有部分學者開始將干擾管理思想引入到客戶請求變動下的VRPSDP 研究中。如Clauden等[5]針對客戶需求變動，以車輛配送路徑(成本)擾動最小為目標，建立VRPSDP 干擾管理模型；胡祥培等[6]依據客戶時間窗和退貨量的變化，建立干擾管理恢復模型，并設計遺傳算法求解；王旭坪等[7]將同一顧客的收貨和退貨需求視為兩次服務構建干擾模型，并設計兩種策略下的啟發(fā)式算法；Yang等[8]設計客戶時間窗變動的干擾管理模型，實現車輛配送路徑和時間廣義擾動成本最小化的目標。

上述VRPSDP實時干擾管理方法，均較好地解決了存在少量客戶請求變動下的VRPSDP。但當客戶請求頻繁變動時，這種方法就需要頻繁地對VRPSDP進行實時處理，這樣不僅會產生管理者無法及時進行決策的困境，也會造成車輛路徑調整方案面臨無法執(zhí)行的難題。有鑒于此，本文提出基于等待策略的干擾管理方法，將車輛配送過程進行等份時段劃分，并設置干擾事件數量累積閾值和客戶等待時段數極限值，在各時段末干擾事件數量達到累積閾值或客戶等待時段數達到極限值時進行干擾管理決策，以避免系統(tǒng)響應不及時或配送延誤等問題。

1 問題描述

在由一個配送中心和多個客戶組成的同時送取貨物流配送系統(tǒng)中，配送中心通常事先依據客戶的送取貨請求，制訂車輛配送路徑方案。在方案執(zhí)行過程中，若出現客戶請求變動，配送中心需要辨識客戶請求變動是否形成干擾事件，即判斷該變動是否對原方案造成干擾。其中，干擾可分為兩類：一是未進行服務客戶在其請求的送貨量或取貨量出現變化時，由于原方案中配送車輛的裝載量無法實現其配送要求產生的；二是未進行服務客戶在其配送請求時間窗出現變化時，原方案中配送車輛不能在未服務客戶規(guī)定的時間窗內到達產生的。若未造成干擾，則車輛繼續(xù)執(zhí)行原配送方案；若造成干擾，則配送中心調整原配送方案，生成新的車輛路徑方案。

成本和服務時間的偏離是客戶請求變動產生的主要擾動指標。成本偏離包括：由于新配送方案中新增車輛而產生的成本偏離；由于路徑距離變化產生的運輸成本偏離。例如，車輛k從客戶i到客戶j的原行駛路徑為rijk，若在某個時段結束時，車輛k獲知需要改變原行駛路線，車輛k從客戶i出發(fā)需要抵達客戶h，然后再抵達客戶j，如圖1(a)所示，此時路徑的偏離情況為路徑rijk的減少，以及路徑rihk和rhjk的增加；若在某個時段結束時，車輛k已從客戶i出發(fā)，此時車輛位置為pk，如圖1(b)所示，即在車輛接收到新服務客戶目標點時，車輛已經在原方案路線上行駛一段距離后進行路線調整，新方案與原方案有重合部分，此時路徑的偏離情況為的減少，以及和rhjk的增加。

圖1 車輛路徑偏離Fig.1 Deviation of vehicle route

在客戶要求的時間范圍內，配送車輛無法完成配送時，客戶會給予一定的懲罰。因此，本文將時間偏離懲罰成本轉換成廣義時間成本。

當辨識出的干擾事件頻繁隨機出現時，配送中心每次都進行干擾管理決策變得不切實際。為此，配送中心可基于等待策略，在將決策期劃分為若干個相等時段的基礎上，設置一個決策閾值，在每個時段末檢查干擾事件累積數量是否達到閾值。若是，則配送中心需要進行干擾管理決策；否則，則將干擾事件累積數量計入下一時段，并在下一時段末繼續(xù)檢查是否達到閾值，直至決策期結束。同時，考慮到等待策略下可能會產生干擾事件累積數量雖經多個時段仍未達到閾值，導致由于等待時段數過長而產生的客戶滿意度下降問題。因此，配送中心需要設定一個客戶等待時段數極限值，如果在某時段末，即使干擾事件累積數量未達到閾值，但客戶等待時段數達到該極限值，則此時配送中心也要進行干擾管理決策。

在每次進行干擾管理決策時，配送中心都需要制定新的車輛配送路徑方案，這會導致新舊方案在配送成本和時間方面產生偏離，這些偏離可以轉換成廣義配送總成本。包括新增配送車輛產生的成本、路徑距離變化產生的運輸成本，以及超出客戶時間窗要求產生的時間懲罰成本。由此可見，VRPSDP干擾管理決策的目標是：在滿足客戶服務要求的前提下，使客戶請求變動所產生的廣義配送總成本最小。

綜上所述，基于等待策略的VRPSDP干擾管理決策的核心步驟包括：首先，將決策期劃分為若干個等份時段；其次，設定干擾事件累積量閾值和客戶等待時段數極限值，在每個時段末，對每個客戶請求變動進行干擾辨識，判斷干擾事件累積量是否達到閾值或客戶等待時段數是否達到極限值；最后，針對每次干擾事件累積量達到閾值或客戶等待時段數達到極限值的情形，建立以廣義配送總成本最小為目標的干擾管理模型，獲得本次干擾管理決策下的VRPSDP優(yōu)化方案。

為了便于建模，本文結合實際做以下假設：

(1)車輛從配送中心出發(fā)，并最終返回配送中心；

(2)車輛只訪問客戶一次，每個客戶只能由一輛車服務；

(3)車輛是同質的。

2 干擾管理決策模型

2.1 模型參數和變量

(1)集合

Ω——干擾管理決策時節(jié)點集合，Ω={0,1,…,M}，其中，0 為配送中心，M為待服務客戶總數；

Ψ——干擾管理決策時在途車輛集合，Ψ={1,2,…,N}，其中，N為在途車輛總數；

Φ——干擾管理決策時可用車輛集合，

Φ={1,2,…,K}，其中，K為可用車輛總數。

(2)參數

V——配送車輛的行駛速度(km·h-1)；

T——干擾管理時刻；

Pk——干擾管理時刻車輛k在行駛途中(未在客戶點)的位置；

Uk——干擾管理時刻車輛k的剩余送貨量(kg)；

Rj——干擾管理時刻待服務客戶j送貨量(kg)；

Gk——干擾管理時刻車輛k已裝載的取貨量(kg)；

Qj——干擾管理時刻待服務客戶j處的取貨量(kg)；

W——配送車輛的最大載貨量(kg)；

C1——車輛固定成本(元)；

C2——車輛單位行駛成本(元·km-1)；

Dij——節(jié)點i到節(jié)點j距離(km)；

Dk——車輛k在干擾管理時刻后按原方案總行駛距離(km)；

S——車輛在配送客戶處的停留時間(h)；

Ej——客戶j最早服務時刻；

Fj——客戶j最遲服務時刻；

Sj——原方案中開始服務客戶j的時刻；

Aj——原方案中車輛到達客戶j的時刻；

α——車輛在客戶服務時間窗之前到達的單位懲罰成本(元·h-1)；

β——車輛在客戶服務時間窗之后到達的單位懲罰成本(元·h-1)。

(3)變量

xijk——0-1 變量，若車輛k由節(jié)點i至節(jié)點j，則等于1，否則等于0；

sj——干擾管理后開始服務客戶j的時刻；

tj——干擾管理后車輛到達客戶j的時刻。

2.2 優(yōu)化模型

根據問題描述，配送中心需要事先設定干擾事件累積量閾值和客戶等待時段數極限值，在某個時段末，當干擾事件累積量達到閾值或客戶等待時段數達到極限值而觸發(fā)干擾管理決策時，將生成新的車輛配送路徑方案，若在新方案中，車輛到達客戶j的時刻tj超出其要求的配送時間窗范圍，則會產生時間偏離懲罰成本，即客戶時間偏離懲罰成本函數δj(tj)為

于是，可建立每次干擾管理決策優(yōu)化模型。

目標函數為

約束條件為

目標函數式(2)表示廣義總成本最小化，其中，第1 項為新派車的固定成本，第2 項為時間偏離成本，第3項為路徑偏離成本；式(3)～式(5)表示每個客戶只能由一輛車服務；式(6)和式(7)表示車輛送貨量約束；式(8)和式(9)表示車輛取貨量約束；式(10)表示客戶服務時間約束；式(11)表示車輛到達客戶時間約束；式(12)表示時間偏離懲罰函數取值；式(13)和式(14)表示車輛從配送中心出發(fā)，并返回到配送中心；式(15)為變量取值約束。

3 算法設計

VRP屬于NP難問題，VRPSDP是VRP的擴展，需要設計啟發(fā)式算法求解[9]。遺傳算法和禁忌搜索算法是元啟發(fā)式方法，能夠在合理的時間內找到NP難問題的解。本文設計基于改進遺傳算法和改進禁忌搜索算法的兩階段啟發(fā)式算法對模型進行求解：在第1 階段，將傳統(tǒng)遺傳算法解碼后與進化逆轉操作結合得到改進遺傳算法，以提高算法的局部搜索能力，迅速找出初始車輛配送路徑；在第2階段，利用2-opt操作改進禁忌搜索算法，對原方案進行全局逐步尋優(yōu)調整，以計算出最小擾動新方案。

3.1 改進遺傳算法

Step 1 初始化種群

設置種群30個，最大迭代次數為50，適應度值函數為目標函數值。

Step 2 適應度值評價

隨機挑選染色體的兩個點，將兩點間的基因序列進行進化逆轉(顛倒)操作處理，生成新的染色體。若優(yōu)于原方案，則保留；否則，保留原最優(yōu)方案。

Step 3 選擇

通過隨機抽取兩條染色體，適應度小的進入下一代，直到新一代的種群數量與親代相同。對親代染色體的適應度值升序排列，將適應度值小的染色體進行優(yōu)先保留，依次代替新代染色體的最大值。

Step 4 交叉變異

改進傳統(tǒng)遺傳算法中設定交叉和變異概率的做法，根據適應度、進化代數和進化過程最優(yōu)解中未改變的個體數量，動態(tài)調整交叉概率。根據迭代效果，選擇自適應式變異概率，保留最優(yōu)染色體不進行變異，兩點交叉進行反轉變異。

Step 5 結束迭代

達到設定迭代次數后，選擇最優(yōu)染色體解碼，獲得初始車輛配送路徑，算法結束。

3.2 改進禁忌搜索算法

Step 1 判斷所有在途車輛，找出所有可以嘗試救援每個干擾客戶的車輛，目標車輛必須滿足干擾客戶的新時間窗要求，并且有足夠的貨物滿足客戶新需求量以及要有足夠的空余載重量滿足客戶新增退貨量。若存在滿足條件的車輛，則執(zhí)行Step 2；否則，執(zhí)行Step 4。

Step 2 確定候選解，將此時車輛狀態(tài)作為初始解，將所有干擾客戶從原路線中剔除，隨機插入到可以參與救援的每輛運行車輛和其下一客戶之間，并運用2-opt局部搜索將干擾客戶與其他未受服務的客戶序列互換，生成有限個候選解集合。

Step 3 設計禁忌表，所插入到每條路線中的位置作為禁忌對象，當干擾客戶插入到某一位置以后，設定該解一個禁忌長度，即在禁忌長度內，擾動點插入到該位置的情況被禁忌，可能出現候選解全部被禁忌現象，或者存在一個優(yōu)于“最優(yōu)”狀態(tài)的禁忌候選解，此時特赦準則將某些狀態(tài)解禁，其對應的對象替換最早進入禁忌表中的對象，替換之前的最優(yōu)解，更新狀態(tài)。

Step 4 判斷從車場派一輛新車是否能夠服務此干擾客戶。如果可以救援，則派新車來服務；若不能救援，則放棄該客戶，附加一定的懲罰成本。

4 算例分析

本文采用Solomon 標準算例庫中客戶信息進行實驗，依次選取RC206、R211、C207 類中客戶信息進行測試。每組數據中有客戶位置、時間窗信息、送貨量等信息，對于選定的3類客戶信息，每一類中選取前60 個客戶，從其中各選10 個客戶作為干擾客戶。隨機生成客戶取貨量信息。選取固定派車成本為140 元，行駛成本為1 元·km-1，車輛行駛速度為30 km·h-1，決策期為7 h，時段時長設為0.25 h。運用遺傳算法計算得到初始配送方案。干擾事件數量累積閾值為5，客戶等待時段數極限值為4，即等待1 h 后若仍未到達閾值，也要進行干擾管理決策。

將本文方法與文獻[8]方法(實時干擾管理)得到的方案進行對比，結果如表1所示。

表1 結果對比Table 1 Results of comparison

由表1 可見，在各案例中，本文方法的成本偏離、時間偏離和廣義總成本均低于文獻[8]實時處理方法，其中，時間偏離成本節(jié)約均在7.8%以上，廣義總成本節(jié)約均在14%以上，表明本文提出的基于等待策略的干擾管理方法更為有效。究其原因是等待策略的應用能將數個干擾客戶進行統(tǒng)一處理，可以更加全局統(tǒng)籌調整路徑，避免實時逐個處理導致的路徑偏離過大的問題，且能避免車輛服務客戶不及時的問題，從而可以較少地減小服務時間偏離，更好地保障客戶的滿意度水平。此外，由表1可見，本文方法的求解時間更短，這是因為在文獻[8]方法下，每次干擾事件發(fā)生系統(tǒng)都需要進行實時決策，而本文基于等待策略方法下，只有干擾事件發(fā)生次數累積量達到閾值或客戶等待時段數達到極限值，系統(tǒng)才會進行干擾管理決策，因而決策次數更少，運行時間便會更短。

在VRPSDP中，客戶請求變動產生的干擾事件數量是對配送中心決策造成影響的一個重要因素，而配送中心設置的干擾事件累積量閾值以及客戶等待時段數極限值是觸發(fā)干擾管理決策的重要參數，其取值大小也會對干擾管理決策結果產生影響。為進一步探究在干擾事件數量和客戶等待時段數極限值同時變化時本文方法的優(yōu)化效果，從R211、C207 和RC206 的前90 個客戶中繼續(xù)依次選定10～24個客戶組成干擾事件，極限值由2～6變化，在其他參數保持不變的情況下進行算例實驗，得到干擾事件數量和客戶等待時段數極限值變化的二維敏感性分析，結果如圖2所示。

圖2 干擾事件數量和極限值的二維敏感性分析結果Fig.2 Results of two-dimensional sensitivity analysis with number of disturbance events and value of limitation

由圖2可見，隨著干擾事件數量的增多，R211、C207 和RC206 這3 類客戶群的廣義總成本均呈增長趨勢，但增長率均呈下降趨勢。隨著客戶等待時段數極限值的增加，3 類客戶群的廣義總成本均呈先降低后增長的趨勢，其中，當極限值取4時，不論干擾事件數量如何變化，廣義總成本均為最低。究其原因，是因為當極限值較低時，配送中心干擾管理決策較為頻繁，進而容易導致配送路徑偏離成本及廣義總成本增高，而當極限值較高時，雖然路徑偏離成本會有所降低，但時間偏離成本會增高較多，從而使得廣義總成本也增高。由此說明，本文方法在干擾事件數量較多時優(yōu)勢愈加明顯，客戶等待時段數極限值存在著合理的取值。

此外，本文依次選取R211、C207和RC206的前90個客戶，并從中選定18個客戶組成干擾事件，在其他參數保持不變的情況下，令閾值由1～9 變化，極限值由2～6 變化，構造算例進行二維敏感性分析，結果如圖3所示。

圖3 閾值和極限值二維敏感性分析結果Fig.3 Results of two-dimensional sensitivity analysis with value of threshold and value of limitation

由圖3可見，隨著閾值由1～4的變化，每組客戶的廣義總成本均呈現下降趨勢，之后趨于穩(wěn)定的狀態(tài)。其中，對于R 類客戶群，最優(yōu)閾值取值為5，C類和RC 類客戶群最優(yōu)閾值取值為6，此時廣義總成本取得最小值。而隨著客戶等待時段數極限值的變化，3 類客戶群的廣義總成本均呈先降低后增長的趨勢，其中，當極限值取4時，不論閾值如何變化，廣義總成本均為最低。原因在于，在干擾管理決策時，新方案與原方案在配送路徑和時間方面會產生偏離，這些超過原配送路徑的距離偏離和超出客戶時間窗要求的時間偏離可能會產生新增車輛成本、配送路徑成本和時間成本，本文選取的R211(客戶位置分布呈分散狀)、C207(客戶位置分布呈簇狀)和RC206(客戶位置分布兼具分散狀和簇狀)這3類客戶群算例中，由于客戶位置分布特征將直接影響配送路徑(距離)的偏離程度，因而不同類型客戶群的最優(yōu)閾值取值也存在差異，但客戶位置分布特征對配送時間的偏離影響較為有限，而客戶等待時段數極限值對時間偏離成本影響很大，因此，3類客戶群算例的最優(yōu)極限值取值均相同，與客戶位置分布特征關聯(lián)不大。由此可見，選擇合理的閾值和極限值能夠提高干擾管理決策的質量。因此，配送中心應針對不同類型及不同規(guī)模的客戶群，選取恰當的閾值和極限值進行基于等待策略的干擾管理決策，以實現廣義總成本最小化的目標。

5 結論

隨著互聯(lián)網電商的發(fā)展，客戶突發(fā)請求對原始配送計劃造成干擾的頻率隨之升高。本文探討了VRPSDP 優(yōu)化問題，研究結果表明：配送中心采用基于等待策略的干擾管理方法，既能有效降低配送成本，又能較好地滿足客戶服務要求。此外，相比于實時干擾管理方法，本文方法實施干擾管理決策的次數變得更少，故能降低對司機駕駛車輛的影響，降低物流從業(yè)人員的工作壓力。