ICP策略下帶軟時間窗的動態(tài)車輛路徑優(yōu)化問題研究

鄢棟　陳家琪

摘要：

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

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

DOIDOI：10.11907/rjdk.172443

中圖分類號：TP319

文獻標識碼：A文章編號文章編號：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引言

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

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

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

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

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

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

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

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

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

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

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

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

本文目標是最小化車輛數(shù)量（在路徑圖中體現(xiàn)為路徑數(shù)）和最小化配送中心的運輸成本（在路徑圖中體現(xiàn)為路徑總距離）。采用線性加權(quán)權(quán)重法[5]衡量目標子函數(shù)，則本文的目標函數(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）每個客戶有且只能由一輛車為其服務(wù)，用公式表示為：

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

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

（3）每輛車運輸量不能超過車輛本身的裝載能力，即：

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

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

等待時間：

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

客戶j的到達時間：

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

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

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

Ri≤li，i∈ITl（9）

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

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

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

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

并且滿足：

（1）當v*插在上述配送路徑的最后一個，則：

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

（2）當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的最大延遲時間，為：

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

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

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

3DVRPSTW算法描述

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

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

4實驗結(jié)果分析

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

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

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

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

5結(jié)語

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

參考文獻參考文獻：

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

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

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

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

[5]王君，李波，盧志剛.帶時間窗動態(tài)車輛路徑問題的優(yōu)化調(diào)度策略[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é)任編輯：黃?。?