時(shí)變需求環(huán)境下同時(shí)取送貨的車輛路徑問題優(yōu)化研究

郭富蓉 鞏建忠 崔袁丁

摘 ?要：針對(duì)客戶需求隨時(shí)間實(shí)時(shí)變化且存在同時(shí)取送貨的車輛路徑優(yōu)化問題，構(gòu)建最小化配送總成本的優(yōu)化模型?？紤]動(dòng)態(tài)路徑優(yōu)化問題的處理策略，提出滾動(dòng)周期型動(dòng)態(tài)調(diào)度優(yōu)化方法，將問題劃分為一系列靜態(tài)車輛路徑問題進(jìn)行求解。通過在蟻群算法中引入遺傳算法的交叉、變異操作設(shè)計(jì)混合蟻群遺傳算法對(duì)問題進(jìn)行優(yōu)化。算例表明：本文所構(gòu)建的模型及動(dòng)態(tài)調(diào)度優(yōu)化方法能夠利用在途配送車輛對(duì)時(shí)變客戶需求做出快速響應(yīng)，有效降低了配送成本的同時(shí)極大地提高了配送中心的服務(wù)質(zhì)量。

關(guān)鍵詞：時(shí)變需求;同時(shí)取送貨;滾動(dòng)周期型動(dòng)態(tài)調(diào)度優(yōu)化方法;車輛路徑問題; 混合蟻群遺傳算法

中圖分類號(hào)：U116.2??????????????????????文獻(xiàn)標(biāo)識(shí)碼：

0引言

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

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

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

1問題描述及模型建立

1.1問題描述

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

1.2模型參數(shù)及變量

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

2?滾動(dòng)周期型動(dòng)態(tài)調(diào)度方法及求解算法設(shè)計(jì)

針對(duì)時(shí)變需求環(huán)境下同時(shí)取送貨VRP問題的特點(diǎn)，本文在分析研究現(xiàn)有文獻(xiàn)^[13-15]提出的動(dòng)態(tài)調(diào)度策略的基礎(chǔ)上，采用滾動(dòng)周期型動(dòng)態(tài)調(diào)度方法對(duì)問題進(jìn)行求解?？紤]時(shí)變客戶需求的服務(wù)屬性及累計(jì)情況，將配送中心的調(diào)度服務(wù)時(shí)域劃分為一系列不等的路徑重新調(diào)度周期，將在該周期內(nèi)更新接收到的時(shí)變客戶需求插入到正在進(jìn)行配送任務(wù)的車輛路徑中，并利用混合蟻群遺傳算法對(duì)插入客戶需求后的配送路徑進(jìn)行優(yōu)化，從而將時(shí)變需求環(huán)境下同時(shí)取送貨VRP問題轉(zhuǎn)化為若干個(gè)SVRP問題進(jìn)行求解。滾動(dòng)周期型動(dòng)態(tài)調(diào)度方法如圖1所示：

2.1路徑重新調(diào)度時(shí)刻

配送中心路徑重新調(diào)度時(shí)刻的劃分決定路徑重新調(diào)度周期的時(shí)間長短，也將決定配送路徑及調(diào)度方案的優(yōu)劣。因此依據(jù)實(shí)時(shí)更新的客戶需求及配送車輛信息，若有以下幾種情況時(shí)，則判定當(dāng)前時(shí)刻為路徑重新調(diào)度時(shí)刻。

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

（2）新增客戶取貨需求的累計(jì)數(shù)量達(dá)到最大累計(jì)數(shù)量Q;

（3）距上一調(diào)度的時(shí)間達(dá)到最大間隔時(shí)間T，且該時(shí)間段內(nèi)存在新增客戶取貨需求;

（4）某一時(shí)刻，配送中心派出車輛到達(dá)新增客戶節(jié)點(diǎn)時(shí)刻將大于等于該客戶最晚接收服務(wù)的時(shí)間窗時(shí)，該時(shí)刻即為路徑重新調(diào)度時(shí)刻。

2.2 需求插入算法

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

2.3路徑重新優(yōu)化算法

本文以蟻群算法為基礎(chǔ)，引入遺傳算法的交叉、變異操作，設(shè)計(jì)混合蟻群遺傳算法對(duì)插入時(shí)變客戶需求的車輛配送路徑進(jìn)行優(yōu)化，以求解時(shí)變需求環(huán)境下同時(shí)取送貨的VRP優(yōu)化問題。

（1）蟻群算法

（2）遺傳算法

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

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

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

3算例分析

3.1實(shí)驗(yàn)設(shè)置

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

3.2 模型計(jì)算結(jié)果及分析

配送中心調(diào)度服務(wù)時(shí)域開始后，依據(jù)實(shí)時(shí)更新的車輛狀態(tài)及陸續(xù)接收到的時(shí)變客戶需求信息判斷路徑重新調(diào)度時(shí)刻，并對(duì)路徑重新調(diào)度周期的時(shí)變客戶需求進(jìn)行調(diào)度優(yōu)化，結(jié)果如圖3及表4所示。

4結(jié)語

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

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

參考文獻(xiàn)

[1]?張玉州，張子為.考慮動(dòng)態(tài)客戶需求的物資配送問題求解方法[J].西安交通大學(xué)學(xué)報(bào)，2020，54（08）：124-131.

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

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

[4]?祁文祥，陸志強(qiáng)，孫小明.帶軟時(shí)間窗的集貨與送貨多車輛路徑問題節(jié)約算法[J].交通運(yùn)輸工程學(xué)報(bào)，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]?李兵，鄭四發(fā)，曹劍東，楊揚(yáng)，耿華，連小珉.求解客戶需求動(dòng)態(tài)變化的車輛路徑規(guī)劃方法[J].交通運(yùn)輸工程學(xué)報(bào)，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]?劉虹，傅曉敏.考慮同時(shí)取送隨機(jī)需求的多行程車輛路徑研究[J].西安電子科技大學(xué)學(xué)報(bào)（社會(huì)科學(xué)版），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]?張文博，蘇秦，程光路.基于動(dòng)態(tài)需求的帶時(shí)間窗的車輛路徑問題[J].工業(yè)工程與管理，2016，21（06）：68-74.

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

[13]?周鮮成，王莉，周開軍，黃興斌.動(dòng)態(tài)車輛路徑問題的研究進(jìn)展及發(fā)展趨勢[J].控制與決策，2019，34（03）：449-458.

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

[15]?劉國榮. 動(dòng)態(tài)需求下快遞同時(shí)取送路徑優(yōu)化問題研究[D].重慶大學(xué)，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]?李卓，李文霞，巨玉祥，陳曉明，何曉平.混合蟻群算法求解帶軟時(shí)間窗的車輛路徑問題[J].武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版），2019，43（04）：761-766.

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

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

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