鄢棟　陳家琪

摘要：

針對(duì)動(dòng)態(tài)車輛路徑中出現(xiàn)新的客戶請(qǐng)求時(shí)，輸入信息（可能包括客戶請(qǐng)求出現(xiàn)時(shí)的車輛位置、客戶時(shí)間窗、服務(wù)時(shí)間、需求量等）也隨著時(shí)間推移而動(dòng)態(tài)改變，在服務(wù)客戶時(shí)由于動(dòng)態(tài)客戶需要不停插入，導(dǎo)致不停地進(jìn)行優(yōu)化計(jì)算，致使車輛路徑更新頻繁的問(wèn)題，提出了緊急動(dòng)態(tài)客戶和數(shù)據(jù)包的概念（簡(jiǎn)稱ICP）。通過(guò)該策略并使用遺傳方法（Genetic Algorithm，GA）與局部搜索方法（Local Search，LS）的混合算法（簡(jiǎn)稱GALS），可提高車輛路徑更新質(zhì)量，降低車輛運(yùn)輸成本并控制配送中心管理成本，從而提高服務(wù)質(zhì)量。通過(guò)實(shí)驗(yàn)證明了該策略的有效性。

關(guān)鍵詞：車輛路徑優(yōu)化；DVRPSTW；遺傳算法；LS；數(shù)據(jù)包

DOIDOI：10.11907/rjdk.172443

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2018）003017204

英文摘要Abstract：For the new customer requests that appear in the dynamic vehicle path， the input information （which may include the location of the vehicle when the customer request appears， the customer's time window， service time， demand， etc.） changes dynamically over time. In the service of customers， due to frequently inserting of dynamic customers demand and the vehicle path updating ，which leads to the nonestop optimal calculation.In this paper， the concept of emergency dynamic customer and data packet （ICP） is proposed. Through using this strategy and GALS method ， the transportation cost of vehicle is reduced and the management cost of distribution center is controlled， then the quality of service is optimized.The validity of the ICP method is proved by experiments.

英文關(guān)鍵詞Key Words：vehicle routing optimization； DVRPSTW； genetic algorithm； LS；data package

0引言

動(dòng)態(tài)車輛路徑問(wèn)題是指對(duì)一系列發(fā)貨點(diǎn)（或收貨點(diǎn)），組織適當(dāng)?shù)男熊嚶窂?，使車輛有序通過(guò)，在滿足一定約束條件（如貨物需求量、客戶需求、交發(fā)貨時(shí)間、車輛容量限制、行駛里程限制、時(shí)間限制等）的情況下，達(dá)到一定目標(biāo)（如路程最短、費(fèi)用最少、消耗能源最少等）[1]。由于在現(xiàn)代社會(huì)中時(shí)間約束的重要性，出現(xiàn)了VRPTW（Vehicle Routing Problem with Time Window，有時(shí)間窗車輛路徑問(wèn)題）。在具有硬時(shí)間窗口（VRPHTW）的車輛路徑和調(diào)度問(wèn)題中，根本不允許在時(shí)間約束窗口之外進(jìn)行交付，這對(duì)于現(xiàn)實(shí)生活中的物流運(yùn)輸是不太合理的。因此，帶有軟時(shí)間窗（VRPSTW）的車輛路徑和調(diào)度問(wèn)題引起了人們關(guān)注，即其在約束時(shí)間窗口外仍然可以通過(guò)增加一些懲罰成本進(jìn)行交付。但由于靜態(tài)VRPSTW的有些約束條件是規(guī)定好的，并不能反映現(xiàn)實(shí)世界的真實(shí)情況。

因此，更具有實(shí)際研究意義的DVRPSTW問(wèn)題受到越來(lái)越多研究者的青睞。黃務(wù)蘭、張濤[2]提出了基于事件觸發(fā)（包括不需要調(diào)整路線車輛位置變化、完成節(jié)點(diǎn)服務(wù)，以及需要調(diào)整路線的，比如新的請(qǐng)求到達(dá)、因阻塞等原因路網(wǎng)發(fā)生了變化）的分解策略，根據(jù)系統(tǒng)的當(dāng)前狀態(tài)，構(gòu)造一個(gè)系統(tǒng)的延遲快照，每個(gè)快照被視為一個(gè)VRPTW，從而把DVRPTW分解成一系列的VRPTW問(wèn)題。然后在LNS算法基礎(chǔ)上，提出一個(gè)雙緩沖區(qū)來(lái)改進(jìn)LNS算法，求解靜態(tài)VRPTW問(wèn)題。

洪聯(lián)系[3]用混合節(jié)約算法與禁忌搜索算法優(yōu)化動(dòng)態(tài)車輛路徑問(wèn)題，目標(biāo)為最小化車輛旅行距離與車輛數(shù)量。根據(jù)動(dòng)態(tài)需求的特點(diǎn)，按照一定規(guī)則和策略，將整個(gè)配送過(guò)程分為若干個(gè)相等或不等的時(shí)間段進(jìn)行處理。在每個(gè)時(shí)間段的結(jié)束時(shí)刻，實(shí)行動(dòng)態(tài)需求的插入，并根據(jù)車輛當(dāng)前位置和更新后的信息制定出新的路線方案。通過(guò)比較相同數(shù)據(jù)下單個(gè)節(jié)約算法、單個(gè)禁忌搜索算法、混合算法輸出的總目標(biāo)值，得出結(jié)論。

劉霞等[4]研究的是帶軟時(shí)間窗的動(dòng)態(tài)車輛路徑問(wèn)題，首先將計(jì)劃周期劃分為固定時(shí)間間隔的時(shí)間片段并設(shè)置一個(gè)中斷時(shí)間作為算法終止條件之一，從而將問(wèn)題靜態(tài)化；然后利用插入法求解DVRPTW的初始線路（初始解），采用線路間局部搜索和線路內(nèi)局部搜索對(duì)初始解進(jìn)行優(yōu)化。對(duì)于違反時(shí)間窗的車輛，增加一個(gè)延遲時(shí)間懲罰參數(shù)；最終通過(guò)Solomon的算例，進(jìn)行實(shí)驗(yàn)并分析結(jié)果，求得最優(yōu)路線。

對(duì)于DVRPSTW問(wèn)題的求解，大多是將時(shí)間窗進(jìn)行劃分，把DVRPSTW問(wèn)題轉(zhuǎn)換為一系列的靜態(tài)子問(wèn)題，從而求解VRPSTW問(wèn)題。對(duì)于動(dòng)態(tài)需求，大多數(shù)是在當(dāng)前時(shí)間段（一般是結(jié)尾處）插入一個(gè)動(dòng)態(tài)客戶，并計(jì)算插入的必要條件，插入后進(jìn)行路徑實(shí)時(shí)優(yōu)化，最后得出最優(yōu)路徑，接著再插入下一個(gè)動(dòng)態(tài)客戶。這樣由于不斷地進(jìn)行插入和優(yōu)化計(jì)算，從而導(dǎo)致不停地更新車輛路徑，進(jìn)而增加了車輛運(yùn)輸成本與配送中心管理成本。因此，為了減少動(dòng)態(tài)過(guò)程中的插入和優(yōu)化計(jì)算負(fù)載，提高車輛路徑更新質(zhì)量，減少車輛運(yùn)輸成本（車輛數(shù)量）并控制配送中心管理成本（車輛行駛總距離），本文基于插入（緊急需求插入）和數(shù)據(jù)包（用來(lái)存放非緊急客戶的動(dòng)態(tài)客戶暫存區(qū)）的概念，提出一種緊急需求插入和數(shù)據(jù)包的求解新方法。

1DVRPSTW問(wèn)題描述與數(shù)學(xué)建模

帶軟時(shí)間窗的動(dòng)態(tài)車輛路徑問(wèn)題（DVRPSTW）可以描述如下：G=（I，E）是有向圖，其中I = （1，2，…，N）是頂點(diǎn)集，表示客戶。E={（i，j）：i≠j∧i，j∈I}是弧集。頂點(diǎn)0（Distribute Center）表示有M個(gè)容量為Q的相同車輛的配送中心，且是路線的起點(diǎn)和終點(diǎn)。頂點(diǎn)集I = （1，2，…，N）指定一組N個(gè)客戶的位置。I中的每個(gè)頂點(diǎn)具有相關(guān)聯(lián)的需求qi≥0，服務(wù)時(shí)間si≥0，以及服務(wù)時(shí)間窗口[ei，li]。每個(gè)?。╥，j）具有相關(guān)聯(lián)的恒定距離dij≥0和行駛時(shí)間tij（tij=dijv），v是車輛速度。車輛到達(dá)客戶i的時(shí)間表示為Ri（Reach），車輛m訪問(wèn)客戶i時(shí)的剩余容量表示為gim，且gim≤Q。T是車輛工作時(shí)長(zhǎng)。在對(duì)車輛進(jìn)行路徑規(guī)劃時(shí)，將工作日T劃分為Nt個(gè)不同長(zhǎng)度的時(shí)間片段。那么當(dāng)在某一時(shí)刻Tl：

（1）設(shè)G=（ITl，ETl）。

（2）車輛m最終確定服務(wù)的客戶集記為Csd，即包括已知的靜態(tài)客戶和即將服務(wù)的動(dòng)態(tài)客戶，如圖1所示。

（3）用NTl表示工作日之前和工作日內(nèi)接收的動(dòng)態(tài)客戶。

（4）則ITl=NTl∪{o，Csd}，NTl∩{o，Csd}=，其中o是Tl時(shí)刻的配送起點(diǎn)，不同于配送中心0。

（5）定義決策變量xijm={0，1}，表示如果存在車輛m從客戶i到客戶j的路線時(shí)，xijm=1，其他情況xijm=0。

本文目標(biāo)是最小化車輛數(shù)量（在路徑圖中體現(xiàn)為路徑數(shù)）和最小化配送中心的運(yùn)輸成本（在路徑圖中體現(xiàn)為路徑總距離）。采用線性加權(quán)權(quán)重法[5]衡量目標(biāo)子函數(shù)，則本文的目標(biāo)函數(shù)可以定義為：

minf=α∑i∈NTl∑m∈Mxi0m+β∑i∈{o，Csd}∑j∈{0}∪{o，Csd}∑m∈Mdijxijm（1）

滿足如下約束條件：

（1）車輛從配送中心出發(fā)，服務(wù)客戶后必須返回配送中心。用公式表示為：

∑i∈{0}∪{o，Csd}∑j∈NTlxijm=1，m∈M（2）

∑i∈NTlxi0m=1，m∈M（3）

（2）每個(gè)客戶有且只能由一輛車為其服務(wù)，用公式表示為：

∑j∈NTl∑m∈Mxijm=1，i∈ITl∧i≠j（4）

∑i∈ITlxikm=∑j∈NTlxkjm，k∈NTl，m∈M（5）

（3）每輛車運(yùn)輸量不能超過(guò)車輛本身的裝載能力，即：

∑i∈NTl∑j∈{0}∪NTl∧j≠iqixijm≤gim，m∈M（6）

（4）時(shí)間參數(shù)計(jì)算。

等待時(shí)間：

Wi=ei-Ri，若ei≥Ri0，否則 ，i∈NTl（7）

客戶j的到達(dá)時(shí)間：

Rj=∑i∈ITl∑m∈M[xijm*（Ri+Wi+Si+tij）]，

j∈{0}∪NTl∧j≠i（8）

車輛必須在客戶i的時(shí)間窗口關(guān)閉前到達(dá)，否則增加一個(gè)懲罰參數(shù)Pi，并重新分配路徑，即：

Ri≤li，i∈ITl（9）

Pi=Ri-li，Ri>li（10）

2緊急需求插入與數(shù)據(jù)包求解方法描述

在時(shí)刻Tl，假設(shè)某輛車的配送路徑為（v0，v1，…，vk，…，vK），vk∈ITl（該路徑作為初始路徑，用遺傳算法求解），如果一個(gè)顧客v*插入到該路徑中，而路徑仍是有效的，且滿足需求公式：

qv*+∑Kv=1qvk≤gvkm，vk∈ITl（11）

并且滿足：

（1）當(dāng)v*插在上述配送路徑的最后一個(gè)，則：

Wvk+Rvk+Svk+tvk，v*≤Lv*（12）

（2）當(dāng)v*插在上述配送路徑中間，假設(shè)在vk和vk+1之間（k∈[0，k-1]），則：

Wvk+Rvk+Svk+tvk，v*≤Lv*（13）

max{Wvk+Rvk+Svk+tvk，v*，Ev*}+Sv*+tv*，vk+1≤Rvk+1+Wvk+1+Dvk+1（14）

其中Dvk+1表示顧客vk+1的最大延遲時(shí)間，為：

Dvk=Lvk-（Rvk+Wvk），k=Kmin{Lvk-（Rvk+Wvk），Dvk+1+Wvk+1}，k∈[1，k-1]（15）

如果動(dòng)態(tài)客戶發(fā)送動(dòng)態(tài)需求的時(shí)刻記為t0，t1，…（t0

“緊急動(dòng)態(tài)客戶”采用實(shí)時(shí)插入的方法，“非緊急動(dòng)態(tài)客戶”采用數(shù)據(jù)包策略，即把“非緊急顧客”都放到數(shù)據(jù)包里，待達(dá)到優(yōu)化條件時(shí)，再一起發(fā)送給優(yōu)化模塊。整體方法流程如圖2所示。

3DVRPSTW算法描述

帶軟時(shí)間窗的動(dòng)態(tài)車輛路徑問(wèn)題（DVRPSTW）算法采用了結(jié)合遺傳算法和局部搜索算法的混合算法。其思想是第一步采用遺傳算法產(chǎn)生路徑初始解，然后使用該解作為局部搜索搜索算法的初始值，然后用重定位法和2-opt法進(jìn)行優(yōu)化運(yùn)算。在該混合算法中，時(shí)間窗被劃分為不同長(zhǎng)度的時(shí)間片段，在每個(gè)時(shí)間片段的結(jié)尾處收集靜態(tài)和動(dòng)態(tài)客戶集，如果是緊急動(dòng)態(tài)客戶，則立即插入線路中并優(yōu)化，如果是非緊急動(dòng)態(tài)客戶，則先加入到數(shù)據(jù)包中，待達(dá)到優(yōu)化條件再進(jìn)行優(yōu)化，直到優(yōu)化模塊更新信息，輸出最優(yōu)路徑。在每個(gè)時(shí)間片中，該問(wèn)題類似于靜態(tài)VRPTW。因此，通過(guò)已經(jīng)描述的混合算法，對(duì)于具有不同起始位置的車輛，該問(wèn)題在每個(gè)時(shí)間片結(jié)束時(shí)作為部分靜態(tài)問(wèn)題來(lái)解決。算法步驟如下：①首先獲取車輛m的實(shí)時(shí)數(shù)據(jù)，設(shè)其初始數(shù)據(jù)在配送中心，開始時(shí)間為0；②確定車輛m最終服務(wù)的客戶集Csd；③判斷當(dāng)前時(shí)間是否超過(guò)了時(shí)間片與懲罰參數(shù)Pi（即最大延遲時(shí)間）之和，如果超過(guò)，則結(jié)束，轉(zhuǎn)步驟⑨；否則，還有動(dòng)態(tài)客戶的需求沒(méi)有到達(dá)或未到時(shí)間片的結(jié)尾，執(zhí)行步驟④；④在每個(gè)時(shí)間片的結(jié)尾處構(gòu)成了靜態(tài)子問(wèn)題。在時(shí)間片開始之前，靜態(tài)子問(wèn)題中的客戶集是由當(dāng)前時(shí)間片還未提交的客戶以及上一個(gè)時(shí)間片內(nèi)出現(xiàn)的即時(shí)新客戶組成（這里不考慮上一個(gè)工作日）；⑤采用遺傳算法的精英策略產(chǎn)生線路初始值；⑥采用重定位法和2-opt法對(duì)步驟⑤中產(chǎn)生的初始值進(jìn)行優(yōu)化。如果時(shí)間片結(jié)束，終止優(yōu)化計(jì)算，到下一步驟⑦，否則，循環(huán)執(zhí)行⑥；⑦提交已優(yōu)化的線路給下一個(gè)時(shí)間片內(nèi)的車輛，并移除已優(yōu)化線路中的客戶節(jié)點(diǎn)；⑧更新信息；⑨配送任務(wù)完成，車輛返回配送中心，并輸出最優(yōu)路徑解。

其中⑥、⑦、⑧構(gòu)成優(yōu)化模塊。算法流程如圖3所示。

4實(shí)驗(yàn)結(jié)果分析

本文測(cè)試采用Lackner的benchmark數(shù)據(jù)c101、r101、rc101、c201、r201、rc201 這6類數(shù)據(jù)集，取α=1 000，β=1，T=1/20[5]，優(yōu)化計(jì)算5次，選擇5次運(yùn)行中的最優(yōu)解進(jìn)行分析，成本距離與車輛數(shù)分別如圖4、圖5所示。

從圖4的成本距離數(shù)據(jù)看，本文采用的基于ICP策略得出的結(jié)果比其它插入后進(jìn)行實(shí)時(shí)優(yōu)化的策略更優(yōu)，而且整體數(shù)據(jù)較為穩(wěn)定。本文平均使用的車輛數(shù)大約為10輛，平均成本距離為1 057.68（車速為1）。設(shè)想在大規(guī)模車輛調(diào)度的實(shí)際問(wèn)題中，優(yōu)化效果會(huì)更明顯。

另外可以看到，201數(shù)據(jù)集的數(shù)據(jù)中，車輛數(shù)明顯少于101數(shù)據(jù)集的數(shù)據(jù)，這是由于其數(shù)據(jù)集的特點(diǎn)所造成的。201的數(shù)據(jù)集時(shí)間窗寬，但客戶坐標(biāo)是隨機(jī)的；101數(shù)據(jù)集時(shí)間窗窄，客戶坐標(biāo)也是隨機(jī)的。這說(shuō)明車輛使用數(shù)量與時(shí)間窗大小有關(guān)，時(shí)間窗越寬，使用的車輛數(shù)越少；反之，車輛使用越多。

同時(shí)，實(shí)時(shí)插入策略雖然在平均車輛數(shù)的趨勢(shì)上減少，在201數(shù)據(jù)集上使用的車輛數(shù)也大大減少，但是距離成本卻很高。這說(shuō)明實(shí)時(shí)插入雖然時(shí)效性很好，企業(yè)花費(fèi)的距離成本卻大幅上升?？傮w來(lái)看，本文的ICP策略減少了企業(yè)的服務(wù)成本，提高了總體服務(wù)質(zhì)量。所以，可以根據(jù)具體的企業(yè)需求選擇策略，如果企業(yè)要求的是在可控成本內(nèi)的時(shí)效性以及盡量減少車輛使用，則選擇實(shí)施插入策略；如果企業(yè)要求總體減少服務(wù)成本輸出，則最好選擇ICP策略，這樣既保證了時(shí)效性，又能減少企業(yè)服務(wù)成本。

5結(jié)語(yǔ)

本文研究帶軟時(shí)間窗的動(dòng)態(tài)車輛路徑問(wèn)題，在動(dòng)態(tài)車輛路徑問(wèn)題的基礎(chǔ)上添加了時(shí)間窗，可更加貼近現(xiàn)實(shí)生活中車輛早到或延遲的情況，采用時(shí)間片的方法收集動(dòng)態(tài)客戶需求，將問(wèn)題靜態(tài)化，同時(shí)針對(duì)緊急動(dòng)態(tài)客戶采用即時(shí)插入方法，非緊急動(dòng)態(tài)客戶采用數(shù)據(jù)包策略，這樣既保證了運(yùn)輸系統(tǒng)的實(shí)時(shí)性，又減少了優(yōu)化模塊的優(yōu)化計(jì)算，從而減少車輛使用數(shù)量和企業(yè)管理成本。在未來(lái)研究中，可以考慮多個(gè)中心倉(cāng)庫(kù)的DVRPSTW問(wèn)題，或者考慮在車輛損壞、天氣變化以及多個(gè)工作日中的DVRPSTW問(wèn)題，以求解更復(fù)雜的現(xiàn)實(shí)情況。另外，對(duì)于共享資源以及綠色路徑的優(yōu)化也是未來(lái)的一個(gè)研究方向。

參考文獻(xiàn)參考文獻(xiàn)：

[1]潘瑩，陳家琪.基于MultiAgent仿真的動(dòng)態(tài)車輛路徑算法研究[J].信息技術(shù)，2015（5）：121124.

[2]黃務(wù)蘭，張濤.基于改進(jìn)遺傳算法的帶時(shí)間窗車輛路徑問(wèn)題研究[J].微型機(jī)與應(yīng)用，2016，35（13）：2124.

[3]洪聯(lián)系.帶時(shí)間窗口動(dòng)態(tài)車輛路徑規(guī)劃模型及其求解算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（4）：244248.

[4]劉霞，齊歡.帶時(shí)間窗的動(dòng)態(tài)車輛路徑問(wèn)題的局部搜索算法[J].交通運(yùn)輸工程學(xué)報(bào)，2008，8（5）：114120.

[5]王君，李波，盧志剛.帶時(shí)間窗動(dòng)態(tài)車輛路徑問(wèn)題的優(yōu)化調(diào)度策略[J].計(jì)算機(jī)工程，2012，38（13）：137141.

[6]XIAO J， LU B. Vehicle routing problem with soft time Windows[M]. Advances in Computer Science and Information Engineering. Springer Berlin Heidelberg，2012：317322.

[7]MAK K L， GUO Z G. A genetic algorithm for vehicle routing problems with stochastic demand and soft time windows[C].Systems and Information Engineering Design Symposium， Proceedings of the.IEEE Xplore，2004：183190.

[8]WEI L， ZHUO F. A variable neighborhood tabu search algorithm for the heterogeneous fleet vehicle routing problem with time windows[C].International Conference on Logistics Engineering and Intelligent Transportation Systems， 2010：14.

[9]ABBATECOLA L， FANTI M P， UKOVICH W. A review of new approaches for dynamic vehicle routing problem[C]. IEEE International Conference on Automation Science and Engineering，2016：361366.

[10]FAN XC， LI NL， ZHANG BY， et al. Research on vehicle routing problem with soft time windows based on tabu search algorithm[C].International Conference on Industrial Engineering and Engineering Management，2011：420423.

責(zé)任編輯（責(zé)任編輯：黃?。?