時變需求環境下同時取送貨的車輛路徑問題優化研究

郭富蓉 鞏建忠 崔袁丁

摘 ?要：針對客戶需求隨時間實時變化且存在同時取送貨的車輛路徑優化問題，構建最小化配送總成本的優化模型。考慮動態路徑優化問題的處理策略，提出滾動周期型動態調度優化方法，將問題劃分為一系列靜態車輛路徑問題進行求解。通過在蟻群算法中引入遺傳算法的交叉、變異操作設計混合蟻群遺傳算法對問題進行優化。算例表明：本文所構建的模型及動態調度優化方法能夠利用在途配送車輛對時變客戶需求做出快速響應，有效降低了配送成本的同時極大地提高了配送中心的服務質量。

關鍵詞：時變需求;同時取送貨;滾動周期型動態調度優化方法;車輛路徑問題; 混合蟻群遺傳算法

中圖分類號：U116.2??????????????????????文獻標識碼：

0引言

在現有的關于車輛路徑問題（Vehicle Routing Problem，VRP）的研究中，一般假定客戶的服務地址、需求量及服務時間窗等信息在路徑規劃前均為靜態且已知的。這種條件下，車輛的行駛路徑一經確定，在后續配送過程中是相對固定的，因此這類VRP被稱為靜態車輛路徑問題（Static vehicle routing problem，SVRP）。但隨著移動互聯網及電子商務的飛速發展，人們對更快捷的物流服務需求不斷增加，客戶的需求是隨時發生變化的，這就使得配送中心需要重新規劃調整車輛的配送路徑以快速響應客戶需求的更新，這類信息隨時間動態變化的動態車輛路徑問題（Dynamic vehicle routing problem，DVRP）更加符合實際生活^[1-2]。與此同時，客戶的日常服務需求不僅包括接收來自車輛配送的貨物，還要求車輛將郵寄出的貨物帶回配送中心^[3-4]。因此，本文結合實際考慮時變需求環境下同時取送貨的VRP問題。

目前，國內外學者對于時變需求環境下同時取送貨的VRP問題已經進行了大量的研究。A. Fabri等^[5]采用動態事件更新策略對該問題進行調度優化;李兵等^[6]考慮新增客戶需求和更改已知客戶服務地址兩種情形，提出虛擬客戶的概念將問題轉化成SVRP進行求解;Hu等^[7]基于同時取送貨VRP問題，建立了動態路徑優化模型;Abdallah^[8]研究了帶容量約束的動態需求VRP問題;劉虹^[9]針對動態需求下同時取送貨的VRP問題設計了“實時柔性點”的調度策略，構建了多行程VRP優化模型，提出了嵌套隨機模擬的變鄰域禁忌搜索算法的混合算法進行求解;Chen等^[10]針對動態客戶需求及帶客戶時間窗環境下的VRP問題，運用兩階段優化策略對問題進行求解。

綜上，既有研究雖然對時變需求VRP問題已經進行了大量深入的研究，但其研究僅考慮了單一的影響因素，對于貼合實際下的多影響因素的VRP研究比較少，而多影響因素下的VRP問題在實際生活中是最普遍發生的，其求解過程也是十分復雜的。因此，本文針對配送中心在調度服務時域內會接收到客戶實時動態變化的取送貨需求的情況，以配送中心總成本（包括派車成本、行駛成本和時間懲罰成本）最小為優化目標，研究時變需求環境下同時取送貨的VRP問題。

1問題描述及模型建立

1.1問題描述

時變需求環境下同時取送貨的VRP問題可描述如下：某配送中心擁有一定數量且狀態良好的配送車輛，通過為車輛安排合適的服務順序及配送路徑對所屬區域內的客戶需求節點進行取送貨服務;車輛容量有限且已知，且車輛從配送中心出發，結束配送任務后返回配送中心^[11];客戶以服務時間窗的形式只接受單車單次服務^[12]，且在配送過程中會隨時隨機的出現新增客戶取貨需求或更改原有的客戶需求（包括已知客戶的需求取消、需求地址變更及時間窗發生變化）。優化目標是最大限度地利用在途配送車輛完成時變出現的客戶需求任務，在最小化配送中心總成本的前提下，求出盡可能滿足客戶服務時間窗和快速響應時變客戶需求的車輛路徑規劃方案。

1.2模型參數及變量

模型中，式（1）為配送中心總成本（包括派車成本、行駛成本和時間懲罰成本）最小化的目標函數;式（2-3）保證每個節點都僅被一輛車服務且只能被服務一次;式（4）表示消除子回路，其中S為需求節點的任意子集;式（5-6）保證車輛從配送中心或當前車輛所在位置出發，直到完成任務后，最終返回配送中心;式（7）流平衡約束，即確保車輛訪問了一個節點就必須從該節點離開;式（8）指車輛離開配送中心時的初始載重量不得超過其最大載重量;式（9）任意車輛在取送貨過程中的載重量不得大于車輛最大載重量;式（10-11）容量約束，車輛完成客戶節點j取送件任務后的載重量與完成上一節點任務后的載重量之間的關系;式（12-13）時間窗約束，滿足所有客戶節點及配送中心的時間窗約束;式（14）時刻的發車數不超過此時配送中心的車輛總數;式（15）為決策變量的取值約束。

2?滾動周期型動態調度方法及求解算法設計

針對時變需求環境下同時取送貨VRP問題的特點，本文在分析研究現有文獻^[13-15]提出的動態調度策略的基礎上，采用滾動周期型動態調度方法對問題進行求解。考慮時變客戶需求的服務屬性及累計情況，將配送中心的調度服務時域劃分為一系列不等的路徑重新調度周期，將在該周期內更新接收到的時變客戶需求插入到正在進行配送任務的車輛路徑中，并利用混合蟻群遺傳算法對插入客戶需求后的配送路徑進行優化，從而將時變需求環境下同時取送貨VRP問題轉化為若干個SVRP問題進行求解。滾動周期型動態調度方法如圖1所示：

2.1路徑重新調度時刻

配送中心路徑重新調度時刻的劃分決定路徑重新調度周期的時間長短，也將決定配送路徑及調度方案的優劣。因此依據實時更新的客戶需求及配送車輛信息，若有以下幾種情況時，則判定當前時刻為路徑重新調度時刻。

（1）已知客戶更改原有的客戶需求（包括已知客戶的需求取消、需求地址變更及時間窗發生變化）;

（2）新增客戶取貨需求的累計數量達到最大累計數量Q;

（3）距上一調度的時間達到最大間隔時間T，且該時間段內存在新增客戶取貨需求;

（4）某一時刻，配送中心派出車輛到達新增客戶節點時刻將大于等于該客戶最晚接收服務的時間窗時，該時刻即為路徑重新調度時刻。

2.2 需求插入算法

通過插入法將時變客戶需求盡可能插入到在途配送車輛的服務路徑中，從而利用在途配送車輛對其進行服務以降低配送中心總成本，不能插入的則由配送中心派車完成。為此本文根據Solomon^[16]及Zheng^[17]等提出的PFIH插入法設計需求插入算法，具體步驟如下：

2.3路徑重新優化算法

本文以蟻群算法為基礎，引入遺傳算法的交叉、變異操作，設計混合蟻群遺傳算法對插入時變客戶需求的車輛配送路徑進行優化，以求解時變需求環境下同時取送貨的VRP優化問題。

（1）蟻群算法

（2）遺傳算法

遺傳算法（Genetic Algorithm，GA）通過對個體適應度進行交叉、變異等操作搜索最優解，是模擬達爾文的遺傳選擇和自然淘汰生物進化過程的搜索最優解的方法。GA算法中的交叉、變異操作能夠產生新的個體，保持群體的多樣性，以防出現未成熟收斂^[20]。

（3）混合蟻群遺傳算法的算法流程圖如圖2所示。

圖2混合蟻群遺傳算法流程圖

3算例分析

3.1實驗設置

時變客戶需求信息包括新增客戶取貨需求、已知客戶的需求取消、需求地址變更及時間窗發生變化，具體信息見表2。

3.2 模型計算結果及分析

配送中心調度服務時域開始后，依據實時更新的車輛狀態及陸續接收到的時變客戶需求信息判斷路徑重新調度時刻，并對路徑重新調度周期的時變客戶需求進行調度優化，結果如圖3及表4所示。

4結語

時變需求環境下同時取送貨的VRP問題是時變需求VRP、同時取送貨VRP和帶時間窗VRP問題的綜合，屬于經典VRP問題的衍生，更符合實際情況。針對基于動變需求下同時取送貨的車輛路徑問題，本文構建時變需求下同時取送貨VRP問題的調度優化模型，提出一種滾動周期型動態調度優化方法，將配送中心調度服務時域分為若干路徑重新調度周期，利用正在進行配送任務的車輛對每個路徑重新調度周期內累計的時變客戶需求進行快速響應;在求解算法中，考慮到蟻群算法在迭代過程中存在信息素停滯問題，將遺傳算法的交叉與變異操作引入蟻群算法，從而擴大搜索解空間，避免陷入局部最優。

本文考慮了車輛行駛速度恒定情形下的路徑優化問題，而因交通事故、車輛堵塞、天氣變化等因素影響，車輛行駛速度實時發生變化更符合現實情形，因此考慮時變車輛行駛速度下VRP優化問題是下一步的研究方向。

參考文獻

[1]?張玉州，張子為.考慮動態客戶需求的物資配送問題求解方法[J].西安交通大學學報，2020，54（08）：124-131.

[2]?李桃迎，呂曉寧，李峰，陳燕.考慮動態需求的外賣配送路徑優化模型及算法[J].控制與決策，2019，34（02）：406-413.

[3]?龍磊，陳秋雙，華彥寧，徐亞，李晨.具有同時集送貨需求的車輛路徑問題的粗粒度并行遺傳算法[J].系統仿真學報，2009，21（07）：1962-1968+1973.

[4]?祁文祥，陸志強，孫小明.帶軟時間窗的集貨與送貨多車輛路徑問題節約算法[J].交通運輸工程學報，2010，10（02）：99-103+109.

[5] A. Fabri，P. Recht.On dynamic pickup and delivery vehicle routing with several time windows and waiting times.Transportation Research Part B： Methodological，2006（4）： 335-350.

[6]?李兵，鄭四發，曹劍東，楊揚，耿華，連小珉.求解客戶需求動態變化的車輛路徑規劃方法[J].交通運輸工程學報，2007（01）：106-110.

[7] Hu Z H，Sheu J B，Zhao L，et al.A dynamic?closed-loop vehicle routing problem with uncertainty and?incompatible goods[J].Transportation Research Part C，2015，55（6）： 273-297.

[8] Abdallah A M F M，Essam D L，Sarker R A.On?solving periodic re-optimization dynamic vehicle routing?problems[J].Applied Soft Computing，2017，55（6）：1-12.

[9]?劉虹，傅曉敏.考慮同時取送隨機需求的多行程車輛路徑研究[J].西安電子科技大學學報（社會科學版），2019，29（03）：87-95.

[10] Chen S F，Chen R， Wang G G，et al.An adaptive?large neighborhood search heuristic for dynamic?vehicle routing problems[J].Computers and Electrical?Engineering， 2018，67（4）：596-607.

[11]?張文博，蘇秦，程光路.基于動態需求的帶時間窗的車輛路徑問題[J].工業工程與管理，2016，21（06）：68-74.

[12]?李國明，李軍華.帶軟時間窗的隨機需求車輛路徑問題的算法研究[J/OL].計算機集成制造系統：1-20[2021-03-23].http：//kns.cnki.net/kcms/detail/11.5946.TP.20191129.1529.028.html.

[13]?周鮮成，王莉，周開軍，黃興斌.動態車輛路徑問題的研究進展及發展趨勢[J].控制與決策，2019，34（03）：449-458.

[14] 谷振宇，劉國榮，白曉輝等.一種快遞配送過程中處理新增取件需求的動態調度方法[P].

[15]?劉國榮. 動態需求下快遞同時取送路徑優化問題研究[D].重慶大學，2018.

[18]?Solomon M M. Algorithms for the Vehicle Routing and Scheduling Problems with Time?Window Constraints[J]. Operations Research. 1987，35（2）： 254-265.

[17]?Zheng J， Liu G， Gu Z， et al. Delivery vehicle routing problem with simultaneous delivery and?pickup in E-commerce environment[C]. 2017.

[18]?李卓，李文霞，巨玉祥，陳曉明，何曉平.混合蟻群算法求解帶軟時間窗的車輛路徑問題[J].武漢理工大學學報（交通科學與工程版），2019，43（04）：761-766.

[19]?湯雅連，蔡延光，楊期江.求解帶軟時間窗多車場多車型車輛路徑問題的一種改進蟻群算法（英文）[J].Journal of Southeast University（English Edition），2015，31（01）：94-99.

[20]?范厚明，徐振林，李陽，劉文琪，耿靜.混合遺傳算法求解多中心聯合配送路徑問題[J].上海交通大學學報，2019，53（08）：1000-1009.

[21] 萬旭，林健良，楊曉偉.改進的最大一最小螞蟻算法在有時間窗車輛路徑問題中的應用[J].計算機集成制造系統，2005，11（4）：572-576.