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

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

0 引言

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

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

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

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

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

1 問題描述與模型構(gòu)建

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

OVRPTW可用有向圖D=(V,A)來表示，其中V表示點(diǎn)集，A表示邊集。點(diǎn)集V=Vc∪{0}，其中Vc表示顧客點(diǎn)集，0表示配送中心。邊集A=Ac∪E(0)，其中Ac={(i,j)|i,j∈Vc,i≠j}表示顧客點(diǎn)i到顧客點(diǎn)j的邊集，E(0)表示離開配送中心的邊。給定點(diǎn)子集G?Vc，δ(G)表示到達(dá)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的實(shí)際開始服務(wù)時(shí)間記為ssvkj，服務(wù)時(shí)間記為svkj，車輛從點(diǎn)i到點(diǎn)j的行駛時(shí)間記為tij，節(jié)點(diǎn)i的開始服務(wù)時(shí)間時(shí)間窗為[ai,bi]，其中a0=0。若路徑rk上任意顧客vkj都滿足avkj≤ssvkj≤bvkj且d(rk)≤Q，則路徑rk為可行路徑。若任意rk∈R均為可行路徑，則R為OVRPTW的一個(gè)可行解，X(?)表示“?”中邊的數(shù)量。由此，可構(gòu)建OVRPTW的模型。

目標(biāo)函數(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)

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

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

2 算法設(shè)計(jì)

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

定義1抖動算子記為SNk，k=1,2，其中SN1指當(dāng)前解向個(gè)體最優(yōu)解靠近的路徑重連，SN2指當(dāng)前解向種群最優(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服務(wù)的顧客點(diǎn)及其服務(wù)順序，rk=(0,vk1,vk2,…)。為保證每輛車從配送中心出發(fā)，服務(wù)完最后一個(gè)顧客后不再返回，每條路徑第一個(gè)元素均為0，其余元素為非0。每個(gè)非0數(shù)字對應(yīng)一個(gè)顧客，數(shù)字不重復(fù)。所有路徑的集合構(gòu)成一個(gè)解，如路徑r1=(0,1,3)，r2=(0,2,5,6)，r3=(0,4)表示由3輛車服務(wù)6個(gè)顧客點(diǎn)的一個(gè)解，如圖3所示。

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

2.2 初始解的生成

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

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

生成初始解的步驟如下：

步驟1隨機(jī)選擇一個(gè)不在任意一條路徑上的顧客點(diǎn)，將其與配送中心相連接。

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

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

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

步驟5算法結(jié)束。

2.3 抖動

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

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

抖動的步驟如下：

步驟1選擇導(dǎo)向解中某條路徑rk。

步驟2將路徑rk包含的顧客點(diǎn)從當(dāng)前解中刪除。

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

步驟4將路徑rk直接加入到當(dāng)前解中，便得到了一個(gè)新解。

步驟5算法結(jié)束。

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

2.4 鄰域搜索

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

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

交換步驟如下：

步驟1在路徑集中隨機(jī)選擇2個(gè)顧客點(diǎn)。

步驟4算法結(jié)束。

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

插入步驟如下：

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

步驟4算法結(jié)束。

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

2-opt步驟如下：

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

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

步驟5算法結(jié)束。

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

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

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

2.5 算法復(fù)雜度分析

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

2.6 算法證明

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

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

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

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

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

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

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

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

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

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

下面采用兩組算例測試本文VNS算法求解OVRPTW的性能。算例1來自文獻(xiàn)[24]；算例2采用100個(gè)顧客點(diǎn)的Solomon標(biāo)準(zhǔn)測試算例(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)境下運(yùn)行。本文參數(shù)設(shè)置如下：種群規(guī)模為N=50，最大迭代次數(shù)Tmax=1 000，隨機(jī)運(yùn)行10次。

3.1 算例1結(jié)果對比分析

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

表1 11種算法結(jié)果比較

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

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

表2 11種算法Friedman檢驗(yàn)排序及秩平均值

表3 Friedman統(tǒng)計(jì)結(jié)果

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

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

3.2 算例2結(jié)果對比分析

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

(1)解比較

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

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

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

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

(2)收斂性分析

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

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

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

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

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

4 結(jié)束語

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

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