開放式帶時間窗車輛路徑問題及變鄰域搜索算法

陳久梅,李英娟,胡 婷,但 斌,李 俊

(1.重慶工商大學 長江上游經(jīng)濟研究中心,重慶 400067；2.重慶工商大學 管理科學與工程學院，重慶 400067；3.重慶工商大學 工商管理學院，重慶 400067；4.重慶大學 經(jīng)濟與工商管理學院，重慶 400044)

0 引言

近年來，隨著O2O平臺的快速發(fā)展，物流配送需求大幅度增長，人們的消費模式從線下向線上轉變。相比線下而言，線上平臺面臨更多挑戰(zhàn)，如配送時效性與準確性、配送成本等。以美團外賣為例，在消費者下單、商家接單和騎手配送的幾大環(huán)節(jié)中，騎手配送是關鍵，面臨最大的挑戰(zhàn)便是車輛調度問題。與傳統(tǒng)車輛路徑問題(Vehicle Routing Problem, VRP)不同，騎手配送環(huán)節(jié)往往由第三方平臺負責，配送結束后車輛不必返回商家，這屬于開放式車輛路徑問題。此外，顧客往往對接受配送有最早和最晚時間的要求。該車輛路徑具有受時間窗約束的特征，這類問題屬于學術界研究的開放式帶時間窗車輛路徑問題(Open Vehicle Routing Problem with Time Windows, OVRPTW)。

OVRPTW在現(xiàn)實中應用廣泛，如報紙配送、牛奶配送、快遞服務、校園班車、大型生產(chǎn)制造業(yè)原材料的運輸?shù)取Ｒ孕@班車為例，校車下午從學校出發(fā)，沿著預定路線，依次按照預定時間到達學生下車點，直到最后一位學生下車，早上接學生的情況正好相反。又如，當某些公司不擁有車隊，或其車隊不合適或不足以滿足顧客需求時，這家公司需要將全部或部分貨物交付第三方或借助外部載體進行運輸，這種情況下車輛不必返回倉庫，費用主要取決于行駛距離，即開放路線的長度。類似地，對于危險品、易耗品、易腐食品、建筑材料、原材料的運輸?shù)龋约拌F路部門或者航空公司在運送貨物時，車輛在完成一批貨物運輸后，為節(jié)省物流成本無需返回原出發(fā)點。上述物流配送過程中，貨物的到達時間是影響消費者服務滿意度的關鍵因素之一，因此車輛路徑通常是執(zhí)行具有時間窗約束的開放路線。

雖然OVRPTW的應用廣泛，但目前的研究還相對較少。REPOUSSIS等[1]針對OVRPTW設計了一種貪婪的前瞻性路徑構造啟發(fā)式求解算法，該算法通過組合顧客選擇和路徑插入來利用時間窗相關信息;FAIZ等[2]針對OVRPTW分別建立了兩個整數(shù)線性規(guī)劃模型：基于弧的混合整數(shù)線性規(guī)劃模型并采用通用求解器求解和基于路徑公式設計一個列生成框架，最后經(jīng)過數(shù)值實驗比較了兩種模型的性能;RUSSELL[3]提出一種利用建模語言和CP優(yōu)化器約束編程的方法，解決多產(chǎn)品報紙生產(chǎn)和投遞的協(xié)調問題;CHEN等[4]基于緊急程度采用插入啟發(fā)式算法構造初始解，運用帶強化學習的變鄰域搜索算法求解具有時間窗和開放路徑的周期車輛路徑問題;REPOUSSIS等[5]結合新達爾文主義進化模型的基本原理和短時記憶的禁忌搜索算法，提出一種進化算法求解OVRPTW;BRANDO[6]針對OVRPTW設計了迭代局部搜索算法，并采用Solomon、Homberger和Gehring等算例進行求解;李三彬等[7]提出一種多開始禁忌搜索算法求解OVRPTW，同樣使用Solomon算例進行驗證;RUSSELL等[8]在構建初始路徑的基礎上，使用禁忌搜索對路徑改進;孫國華[9]設計了改進的自適應遺傳算法求解開放車輛路徑。

變鄰域搜索(Variable Neighbourhood Search, VNS)算法作為一種新元啟發(fā)式算法，最早由MLADENOVI等[10]提出，該算法通過改變鄰域結構使搜索方向多元化，從而增強搜索能力，優(yōu)化計算性能[11]。鑒于VNS算法的優(yōu)越性，其已經(jīng)被廣泛應用于解決VRP的各種擴展問題。XU等[11]使用VNS算法求解連續(xù)性車輛路徑問題;SEVKLI等[12]提出一種求解OVRP的變鄰域搜索算法，并在各種標準算例和大規(guī)模實際問題上進行了測試;REZGUI等[13]將VNS算法應用于解決具有異車型和時間窗等約束條件的問題;姚冠新等[14]將改進VNS算法用于研究多隔室車輛路徑優(yōu)化問題。

本文針對OVRPTW，在建立數(shù)學模型的基礎上，借鑒文獻[1]的貪婪插入法生成初始解，設計VNS算法對其進行求解。算法框架中融入GLOVER[15]的路徑重連和KINDERVATER等[16]的鄰域搜索算子，并將鄰域搜索嵌套在VNS算法的抖動過程中。通過求解兩組算例，并將求解結果與已有文獻進行比較，驗證了VNS算法的有效性。

1 問題描述與模型構建

OVRPTW是經(jīng)典VRPTW的一個擴展問題，可考慮為配送中心安排車輛將物品配送給一系列顧客，每輛車完成自己所負責配送的最后一位顧客后，服務結束，無需返回配送中心。其中，車輛有容量限制，在配送過程中不得超載；顧客在地理位置上是分散的，且各自有不同的需求量及接受配送服務的時間窗。OVRPTW的目標是構建一組滿足所有顧客點需求的總行駛成本最小的配送路徑。

OVRPTW可用有向圖D=(V,A)來表示，其中V表示點集，A表示邊集。點集V=Vc∪{0}，其中Vc表示顧客點集，0表示配送中心。邊集A=Ac∪E(0)，其中Ac={(i,j)|i,j∈Vc,i≠j}表示顧客點i到顧客點j的邊集，E(0)表示離開配送中心的邊。給定點子集G?Vc，δ(G)表示到達G的邊，E(G)表示離開G的邊。d(G)表示G中所有顧客的需求量之和，Q表示車輛容量。車輛集合為K={1,2,…,k}。

借鑒KALLEHAUGE[17]的方法，OVRPTW的解記為R={r1,r2,…,rk}，其中rk=(0,vk1,vk2,…)，vkj∈Vc。路徑rk上所有顧客的需求量之和記為d(rk)，車輛行駛成本記為c(rk)，路徑rk上顧客vkj的實際開始服務時間記為ssvkj，服務時間記為svkj，車輛從點i到點j的行駛時間記為tij，節(jié)點i的開始服務時間時間窗為[ai,bi]，其中a0=0。若路徑rk上任意顧客vkj都滿足avkj≤ssvkj≤bvkj且d(rk)≤Q，則路徑rk為可行路徑。若任意rk∈R均為可行路徑，則R為OVRPTW的一個可行解，X(?)表示“?”中邊的數(shù)量。由此，可構建OVRPTW的模型。

目標函數(shù)：

(1)

s.t.

X(δ(i))=1,?i∈Vc;

(2)

X(E(i))=1,?i∈V,i≠vk(|rk|-1),?k∈K;

(3)

X(E(i))=0,?i=vk(|rk|-1),?k∈K;

(4)

X(E(G))≤|G|-1,G?Vc,|G|≥2;

(5)

ssvkj=max{ssvk(j-1)+svk(j-1)+tvk(j-1)vkj,avkj},

?j∈Vc,?k∈K;

(6)

avkj≤ssvkj≤bvkj,?j∈Vc,?k∈K;

(7)

d(rk)≤Q,?k∈K。

(8)

目標函數(shù)(1)表示車輛總行駛成本最小。約束(2)表示有且僅有一輛車到達顧客點為其提供服務;約束(3)表示車輛到達任意路徑rk上除最后一個顧客點外，必須離開;約束(2)和約束(3)保證了路徑的連續(xù)性;約束(4)表示任意路徑rk上車輛服務完最后一個顧客即結束;約束(5)用于消除子回路徑。約束(6)和約束(7)表示任意路徑上任意顧客vkj的實際開始服務時間必須在其時間窗內(nèi);約束(8)表示車輛容量約束，即任意路徑rk上顧客需求量之和不得超過車輛容量。

OVRPTW中，車輛不需要像VRPTW那樣返回配送中心。從圖論角度看，求解VRPTW是要找到一組哈密頓回路(如圖1)，而求解OVRPTW是要找到一組哈密頓路徑(如圖2)。SYSLO等[18]認為哈密頓路徑問題是NP-hard問題，因為它可以轉換成等價的哈密頓回路問題。因此，OVRPTW也是NP-hard問題?？紤]到變鄰域搜索算法的優(yōu)越性以及該算法在車輛路徑問題方面的成功應用[18-19]，在此運用變鄰域搜索算法對OVRPTW進行求解。

2 算法設計

VNS算法的基本思想是通過系統(tǒng)改變鄰域，從一個解跳到另一個解，不斷改善現(xiàn)有解，以得到更好的解。與禁忌搜索、模擬退火等傳統(tǒng)的元啟發(fā)式算法相比，VNS算法不但結構簡單，容易實現(xiàn)，而且與求解問題無關，適用于各種優(yōu)化問題[20]。為提高求解效果，本文在基本VNS算法的框架下，在其抖動階段，采用當前解向個體歷史最優(yōu)解和種群歷史最優(yōu)解靠近的路徑重連來實現(xiàn)；在其鄰域搜索階段，采用路徑內(nèi)和路徑間的交換、插入、2-opt算子來實現(xiàn)，并將鄰域搜索嵌套在抖動過程中。

定義1抖動算子記為SNk，k=1,2，其中SN1指當前解向個體最優(yōu)解靠近的路徑重連，SN2指當前解向種群最優(yōu)解靠近的路徑重連；鄰域搜索記為LNl，l=1,2,3，其中LN1指交換算子，LN2指插入算子，LN3指2-opt算子。求解OVRPTW的VNS算法偽代碼如下：

Generate the initial solution x

Definition:a set of neighborhood structures SNkfor k=1,2 for shaking

a set of neighborhood structures LNlfor l=1,2,3 for local search

while(stopping criterion is not met)do

k=1

l=1

while k≤2 do //shaking

x′←SNk(x)

while l≤3 do // neighborhood search

x″←LNl(x′)

If Z(x″)

x′←x″

else

l=l+1

End if

End while

If Z(x′)

x←x′

Else

k=k+1

End if

End while

End while

Output x

2.1 解的表示

OVRPTW的路徑集合R={r1,r2,…,rk}，其中路徑rk表示車輛k服務的顧客點及其服務順序，rk=(0,vk1,vk2,…)。為保證每輛車從配送中心出發(fā)，服務完最后一個顧客后不再返回，每條路徑第一個元素均為0，其余元素為非0。每個非0數(shù)字對應一個顧客，數(shù)字不重復。所有路徑的集合構成一個解，如路徑r1=(0,1,3)，r2=(0,2,5,6)，r3=(0,4)表示由3輛車服務6個顧客點的一個解，如圖3所示。

圖3中，車輛1從配送中心出發(fā)，依次服務顧客1和3；車輛2從配送中心出發(fā)，依次服務顧客2、5和6;車輛3從配送中心出發(fā)，服務顧客4。這個解可表示為{0,1,3,0,2,5,6,0,4}。該種表示具有如下優(yōu)點：①每條路徑可以表示車輛提供服務的顧客點及其服務的先后順序；②每個顧客點的服務時間可以根據(jù)式(6)計算得到，然后根據(jù)式(7)判斷是否滿足時間窗約束；③可以很方便地計算整條路徑上所有顧客的需求總量，從而根據(jù)約束條件(8)判斷是否超過車輛容量。

2.2 初始解的生成

初始解的生成采用貪婪插入法，將顧客點依次插入最優(yōu)插入位置，形成一條條行駛路徑，直到完成所有顧客點的插入，即生成初始解。

定義2最優(yōu)插入位置。給定路徑rk=(0,vk1,vk2,…)，在vk1之前和vkj之后共有|rk|個插入候選位置。如果插入后新路徑增加的車輛行駛成本最小，則該位置稱為最優(yōu)插入位置。

生成初始解的步驟如下：

步驟1隨機選擇一個不在任意一條路徑上的顧客點，將其與配送中心相連接。

步驟2以該顧客點和配送中心的連線為軸，圍繞配送中心順時針進行掃描，以時間窗和車輛容量為約束條件，將滿足條件的顧客點按照貪婪插入的方法，插入到最優(yōu)插入位置，循環(huán)該步驟，直到不滿足約束為止，便形成一條車輛行駛路徑。

步驟3若系統(tǒng)中存在不在任意一條路徑上的顧客點，則轉步驟1。

步驟4若系統(tǒng)中所有顧客均在某條路徑上，則形成一系列行駛路徑，得到初始解。

步驟5算法結束。

2.3 抖動

抖動是變鄰域搜索的關鍵階段，它能夠改變解的搜索方向，實現(xiàn)搜索空間多樣化，避免陷入局部最優(yōu)。本文算法中的抖動階段采用路徑重連實現(xiàn)當前解到另一個解的轉換。

定義3可行的路徑重連。路徑重連(path relinking)是GLOVER[15]在1997年引入的元啟發(fā)式算法，該方法通過在當前解與導向解之間建立聯(lián)系來生成新解，若生成的新解可行，則該操作稱為可行的路徑重連。本文分別以個體歷史最優(yōu)解和種群歷史最優(yōu)解作為導向解進行路徑重連。

抖動的步驟如下：

步驟1選擇導向解中某條路徑rk。

步驟2將路徑rk包含的顧客點從當前解中刪除。

步驟3當前解中，將有顧客點被刪除的路徑中剩下的顧客點，在滿足式(7)和式(8)有關時間窗和車輛容量約束條件下，添加到?jīng)]有刪除顧客點的其他路徑上。

步驟4將路徑rk直接加入到當前解中，便得到了一個新解。

步驟5算法結束。

假定隨機選擇導向解中的一條路徑為(0,2,4)。當前解中含有顧客點2和顧客點4的路徑分別為r1和r2。首先分別從r1和r2中刪除顧客點2和顧客點4;r1和r2中剩余顧客點，在滿足時間窗和車輛容量約束條件下，依次添加到?jīng)]有刪除顧客點的其他路徑上；不滿足上述約束的顧客點，則保留在原路徑上。將導向解中路徑(0,2,4)加入到當前解中，由此生成新解。

2.4 鄰域搜索

鄰域搜索采用交換、插入和2-opt三種算子[16]。三種算子同時考慮選擇的顧客點或邊在同一路徑和不同路徑2種情況。

定義4可行交換?；诳尚薪庵型粭l路徑，交換2個顧客點產(chǎn)生新路徑。若交換后，新路徑上交換位之后的顧客點滿足式(7)顧客時間窗約束，則該交換為可行交換?；诳尚薪庵胁煌窂剑粨Q2個顧客點產(chǎn)生兩條新路徑。若形成的新路徑均滿足式(7)顧客時間窗約束和式(8)車輛容量約束，則該交換為可行交換。

交換步驟如下：

步驟1在路徑集中隨機選擇2個顧客點。

步驟4算法結束。

定義5可行插入。在路徑中隨機選擇一個顧客，若將該顧客點從當前位置刪除，然后插入到同一路徑或不同路徑中，形成新的路徑依然是可行路徑，則這個插入操作被稱為可行插入。

插入步驟如下：

步驟1從路徑rk=(0,vk1,…,vkl,…,vkn,…)中隨機選擇一個顧客(記為vkl)并將其從rk中刪除。

步驟4算法結束。

定義6可行2-opt。在同一路徑rk或不同路徑rk和rk′中，將兩條不相鄰的邊斷開重新連接，若形成路徑是可行路徑，則稱該2-opt操作為可行2-opt。

2-opt步驟如下：

步驟1在路徑集中隨機選擇兩條不相鄰的邊，將其斷開。

步驟3若斷開的兩條邊位于不同路徑上，分別記為rk和rk′。

步驟5算法結束。

由圖4可知，當斷開同一條路徑上不相連的兩條邊(1,3)和(4,2)后，將被斷開的路徑段(3,4)反轉，得到新的路徑(0,1,4,3,2,5)。

由圖5可知，當斷開兩條路徑上兩條邊(3,5)和(4,7)后，將被斷開的兩個路徑段進行交叉連接，得到新的路徑(0,1,3,7,8)和(0,2,4,5,6)。

需要注意的是，鄰域搜索時，由于顧客點位置發(fā)生變化，需要判斷路徑是否可行。由于在同一路徑上執(zhí)行3種操作算子時，該路徑包含的顧客點沒有發(fā)生變化，必定滿足車輛容量的約束，只需考慮是否滿足時間窗。而在不同路徑上執(zhí)行3種操作算子時，每條路徑上包含的顧客點發(fā)生變化，此時除了考慮是否滿足時間窗的約束以外，還要考慮是否滿足車輛容量的約束。

2.5 算法復雜度分析

VNS算法時間復雜度分析如下：對于最大迭代次數(shù)為Tmax、問題規(guī)模為I的OVRPTW，生成初始解解的時間復雜度為O(1)；每個解的操作中，顧客移動、顧客交換、2-opt和路徑重連的時間復雜度均為O(I2)；是否接受新解的時間復雜度為O(1)；每一代的時間復雜度為a×O(I2)+b×O(1)，其中a,b為正整數(shù)；Tmax代的時間復雜度為Tmax×(a×O(I2)+b×O(1))。因此，整個算法的時間復雜度為O(1)+Tmax×(a×O(I2)+b×O(1))。可見，所提算法的時間復雜度與算法迭代次數(shù)和問題規(guī)模有關。

2.6 算法證明

引理1最優(yōu)解存在性。OVRPTW存在最優(yōu)解x*。

證明OVRPTW為線性規(guī)劃問題，屬于凸優(yōu)化問題[21]，因此存在最優(yōu)解x*[22]，證畢。

定理1鄰域存在性。模型存在最優(yōu)解，因此在可行解集F內(nèi)，給定一個解x(x≠x*)，則至少存在一個鄰域結構N，滿足N=|x→x*|，并稱解x*在解x的鄰域結構N內(nèi)，即解x與最優(yōu)解x*之間至少存在一個廣義距離，廣義距離可以是歐式距離、漢明距離或者k-opt算子等[23]。

證明反證法。若模型對于任意給定可行解x(x∈F)，不存在一個鄰域結構N=|x→x*|，即解x*不在可行解集F中，則解x*不是模型的最優(yōu)解，與已知矛盾。證畢。

定理2局部最優(yōu)解可窮性。模型為組合優(yōu)化問題且存在最優(yōu)解x*，任意給定一個可行解x，則在解x的鄰域結構N(x)范圍內(nèi)可以找到所有局部最優(yōu)解。

證明因為模型為組合優(yōu)化問題，則N(x)鄰域內(nèi)解空間有限，所以可以通過枚舉算法獲得所有局部最優(yōu)解，即局部最優(yōu)解是可窮的。證畢。

引理2路徑可行性。使用VNS算法得到的開放式帶時間窗的車輛路徑是可行的。

證明可行解集F中所有解x均滿足定義的等式約束(2)～約束(8)，變鄰域也是在可行解集F內(nèi)尋找不同的鄰域結構Ng，從而尋找局部最優(yōu)解xg，即xg∈F，因此局部最優(yōu)解xg滿足定義的等式約束(2)～約束(8)，局部最優(yōu)解中的路徑也滿足模型條件約束。證畢。

基于以上定理和引理，證明使用VNS算法求解OVRPTW具有可行性。

3 實驗結果與分析

下面采用兩組算例測試本文VNS算法求解OVRPTW的性能。算例1來自文獻[24]；算例2采用100個顧客點的Solomon標準測試算例(http://web.cba.neu.edu/～msolomon/problems.htm)。

算法采用Microsoft Visual Studio 2017編程，在Intel(R)Core(TM)i7-8750H CPU@2.20 GHz 2.21 GHz環(huán)境下運行。本文參數(shù)設置如下：種群規(guī)模為N=50，最大迭代次數(shù)Tmax=1 000，隨機運行10次。

3.1 算例1結果對比分析

算例1中顧客坐標是在[1,150]×[1,150]的區(qū)域內(nèi)隨機生成，其編號為1,2,…,19,20，配送中心坐標為(70,70)，其中顧客具體信息(坐標、貨物需求量及時間窗)參見文獻[24]。本文將VNS算法與文獻[24]中的簡單遺傳算法、基于or-opt的模擬退火算法、混合遺傳算法，文獻[25]中的基本蟻群算法、單點單親遺傳混合蟻群算法、多點單親遺傳混合蟻群算法，文獻[26]中的基本蝙蝠、精英遺傳混合蝙蝠、多點重組精英混合蝙蝠、單點重組精英混合蝙蝠共11種算法的求解結果進行比較，具體結果如表1所示。

表1 11種算法結果比較

由表1可知，使用同一組算例求解VRPTW問題時，本文VNS算法的平均路徑長度以及最優(yōu)路徑長度均最短，而使用的車輛數(shù)比簡單遺傳算法、基本蟻群算法、單點單親遺傳混合蟻群算法、多點單親遺傳混合蟻群算法、基本蝙蝠以及精英遺傳混合蝙蝠都要少。這表明，在求解VRPTW時，本文VNS算法求解質量相比其他算法更優(yōu)。

盡管表1所呈現(xiàn)的結果能初步驗證本文的VNS算法在求解質量上具有優(yōu)越性，但還需進一步通過統(tǒng)計學上的顯著性檢驗，比較排序以上11種算法在同一個數(shù)據(jù)集上的性能優(yōu)劣。Friedman檢驗[27]作為非參數(shù)檢驗的方法，能對多種算法在每個數(shù)據(jù)集上的計算結果進行比較排序，并檢驗算法在置信區(qū)間內(nèi)是否存在顯著性差異。詳細比較結果和統(tǒng)計結果分別如表2和表3所示。

表2 11種算法Friedman檢驗排序及秩平均值

表3 Friedman統(tǒng)計結果

Friedman檢驗秩平均值越低，算法性能越優(yōu)。因此，由表2的結果可知，11種算法性能排序為：VNS算法(1.67)>單點(多點)重組精英混合蝙蝠(3.00)>混合遺傳算法(3.67)>精英遺傳混合蝙蝠(5.50)>單點單親遺傳混合蟻群算法(6.17)>基于or-opt的模擬退火算法(6.33)>多點單親遺傳混合蟻群算法(7.17)>基本蟻群算法(9.50)>簡單遺傳算法(9.83)>基本蝙蝠(10.17)。

表3顯示了在自由度為10、置信區(qū)間為99%的卡方分布下，F(xiàn)riedman統(tǒng)計量為25.262，p值為0.005<0.01，由此可得出11種算法之間存在1%水平下顯著差異的結論。綜上所述，根據(jù)表1的求解結果，如表2和表3的統(tǒng)計結果可知，本文VNS算法在各方面均較優(yōu)，11種算法之間存在顯著性差異。因此，初步驗證了本文VNS算法在求解VRPTW時具有可行性和有效性。

3.2 算例2結果對比分析

算例2采用經(jīng)典的Solomon Benchmark算例集，共包括R1,C1,RC1,R2,C2,RC2六類。每類算例均是在100×100的單位區(qū)域內(nèi)生成了1個配送中心和100個顧客點，其中R類、C類和RC類客戶的地理位置分別由隨機分布、聚類分布以及混合隨機聚類分布生成；R1、C1、RC1類算例的時間窗緊，而R2、C2、RC2類算例的時間窗寬，因此在每條路徑上能服務更多的客戶。Solomon Benchmark的算例，原本是VRPTW的算例。在此，借鑒文獻[5-6]的作法，即采用該算例的基本數(shù)據(jù)，車輛服務完最后一個顧客即結束，不用返回配送中心。本文將VNS算法與文獻[5]的改進的禁忌搜索啟發(fā)式算法(Improved Tabu Search Heuristic，TS)、貪婪的前瞻性路線構造啟發(fā)式算法(Greedy Look-Ahead Route Construction heuristic Algorithm，GLARCA)、進化算法(Evolutionary Algorithm, EA)和貪婪的隨機多啟動軌跡局部搜索算法(Greedy Randomized Multi-Start Trajectory local Search algorithm, GRMSTS)以及文獻[6]的統(tǒng)一的變鄰域搜索算法(Unified Variable Neighborhood Search，UVNS)、統(tǒng)一的混合遺傳搜索算法(Unified Hybrid Genetic Search，UHGS)、彈射鏈迭代局部搜索算法(Iterated Local Search Algorithm，ILSA)和求解OVRPTW的當前已知最好解(Best Known Solutions，BKS)的求解結果進行比較。

(1)解比較

通過與已有文獻最好解，以及其他算法得到的解進行比較，分析本文VNS算法的求解性能，如表4和表5所示。表中：TD表示總行駛成本;GAP表示VNS算法的解比當前已知最好解之間的差距，GAP=(已有文獻最好解-已知最好解)/已知最好解×100%。

表4 Solomon中R1、C1和RC1數(shù)據(jù)集的詳細結果

表5 Solomon中R2、C2和RC2數(shù)據(jù)集的詳細結果

由表4可知，本文VNS算法在求解R1、C1和RC1類算例中，有16個算例的VNS解比當前已知最好解更優(yōu)，5個算例的VNS解與當前已知最好解相同，其行駛成本平均節(jié)約了0.60%。由表5可知，在求解R2、C2、RC2類算例中，有19個算例的VNS解比當前已知最好解更優(yōu)，3個算例的VNS解與當前已知最好解相同，其行程成本平均節(jié)約了7.80%。因此，由表4和表5的詳細結果及比較可知，VNS算法能表現(xiàn)出良好的求解質量和性能，由此進一步驗證了本文VNS在求解OVRPTW上的可行性和有效性。

(2)收斂性分析

為分析VNS算法的收斂性，本文以算例2中R101～R104、RC101～RC104、R201～R204、和RC201～RC204為例，根據(jù)VNS算法求解OVRPTW隨機運行10次，迭代1 000次的過程數(shù)據(jù)，繪制兩組VNS算法收斂圖，如圖6和圖7所示。

由圖6可知，算法在300代之前收斂速度快，300～900代中收斂速度較慢，在900代左右向各自的最好解收斂。由圖7可知，算法在200代之前收斂速度較快，在200～900代中收斂速度緩慢，在900代后收斂于各自的最好解。因此，根據(jù)兩組收斂圖可知，VNS算法不管是在求解時間窗寬的算例還是時間窗窄的算例，最終都能收斂于各自的最好解。由此可知，本文VNS算法具有較好的收斂性。

(3)穩(wěn)定性分析

為了分析本文VNS算法的穩(wěn)定性，采用箱形圖來觀測VNS算法求解R101～R104、RC101～RC104、R201～R204、和RC201～RC204每組算例10次后得到解的分布情況，如圖8和圖9所示。其中，黑色粗線表示中位數(shù)，該箱形圖分別由上四分位數(shù)和下四分位數(shù)組成，豎線表示該組結果的平均偏差，豎線兩端的橫線分別為上限(最大值)和下限(最小值)，空心的圓圈表示異常值。

由圖8可知，R101～R104和RC101～RC104的箱盒長度短，上四分位數(shù)和下四分位數(shù)間距較小，且部分算例其上下四分位數(shù)接近于0。相比圖8來說，圖9中R201～R204和RC201～RC204的箱盒長度雖較長，但異常值較少，其中R201～R204的解不存在異常值。從兩組箱形圖整體來看，平均偏差均較小。由此可知，本文利用VNS算法求解OVRPTW 10次后解的離散程度較小，從而表明本文VNS算法具有穩(wěn)定性。

4 結束語

在外賣配送過程中，通常需要騎手滿足配送時效性、準確性以及開放性等要求。本文基于此背景，對開放式帶時間窗車輛路徑問題進行探討，考慮配送車輛無需返回配送中心和時間窗等影響，構建配送行駛總成本最小化為目標函數(shù)的OVRPTW模型，并設計了一種變鄰域搜索的啟發(fā)式算法進行問題求解。本文通過使用兩組算例，利用VNS算法分別對VRPTW和OVRPTW進行求解，并與已有文獻和現(xiàn)有已知最好解進行對比分析。實驗結果表明：①本文設計的VNS算法在求解VRPTW時，能獲得更短的運輸里程，且與眾多種算法相比，該算法優(yōu)勢明顯；②在求解OVRPTW時，大多數(shù)算例的VNS算法最好解都優(yōu)于已有文獻最好解，通過該算法求解，明顯降低了車輛行駛成本，由此表現(xiàn)出VNS算法良好的求解質量；③通過收斂圖和箱形圖可知，本文VNS算法在求解OVRPTW時，具有較好的收斂性和穩(wěn)定性，最終驗證了該算法良好的求解性能。

未來，將進一步考慮天氣、交通、實時路況和突發(fā)事件等對路徑優(yōu)化的影響，建立相應的數(shù)學模型并設計算法求解。