基于改進(jìn)型蜻蜓算法的車輛路徑問題研究

陶文瀚，趙晨聰，孫翌博，劉晨磊，孫知信，孫 哲

(1．南京郵電大學(xué) 現(xiàn)代郵政學(xué)院&現(xiàn)代郵政研究院，江蘇 南京 210003；2.常州工學(xué)院 計(jì)算機(jī)信息工程學(xué)院，江蘇 常州 213032；3.南京郵電大學(xué) 寬帶無線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003)

0 引 言

車輛路徑問題(vehicle routing problem，VRP)[1]是物流配送優(yōu)化環(huán)節(jié)中至關(guān)重要的一環(huán)。在物流配送過程中，通過為配送車輛選擇最優(yōu)的運(yùn)輸路徑，合理安排車輛的調(diào)度順序，可以有效減少車輛的空車行駛率和行駛距離。該問題最早由國外學(xué)者Dantzig和Ramser在1959年提出，屬于NP-Hard問題[2]。目前，國內(nèi)外學(xué)者對VRP問題已經(jīng)進(jìn)行了廣泛而深入的研究，VRP已經(jīng)應(yīng)用到垃圾車的線路優(yōu)化、連鎖商店的送貨線路優(yōu)化等[3]眾多社會領(lǐng)域。

但是，傳統(tǒng)的VRP問題往往只考慮到配送距離而忽視了客戶對配送時(shí)間的要求,進(jìn)而影響客戶對物流配送服務(wù)的滿意度。帶時(shí)間窗約束的車輛路徑問題是原車輛路徑問題的一種拓展，在經(jīng)典組合優(yōu)化車輛路徑問題上，引進(jìn)了客戶對貨物到達(dá)時(shí)間的時(shí)間窗約束。其中，時(shí)窗約束可以分為兩種，一種是硬時(shí)間窗，要求車輛必須要在時(shí)窗內(nèi)到達(dá)，早到必須等待，而遲到則拒收;另一種是軟時(shí)窗，不一定要在時(shí)窗內(nèi)到達(dá)，但是超出時(shí)間窗到達(dá)則需要處罰。

該文總結(jié)眾多新型智能算法應(yīng)用到車輛路徑問題上的優(yōu)缺點(diǎn)，分析當(dāng)前路徑規(guī)劃上存在的問題和需求，提出了一種改進(jìn)型蜻蜓算法，并將該算法應(yīng)用到帶軟時(shí)間窗約束的車輛路徑問題中，發(fā)現(xiàn)該算法在求解VRP問題上具有較高的可行性。

1 相關(guān)研究

目前，已有許多新型智能算法用于求解帶時(shí)間窗約束的車輛路徑問題[4]。文獻(xiàn)[5]通過使用禁忌搜索算法和自適應(yīng)大鄰域搜索算法來解決具有時(shí)間依賴性的軟時(shí)間窗和隨機(jī)行駛時(shí)間的車輛路徑問題，并說明該方法可用于解決其他一些大規(guī)模問題。文獻(xiàn)[6]利用人工蜂群激發(fā)蜜蜂的覓食行為，運(yùn)用混合超啟發(fā)式算法求解帶軟時(shí)間窗的多目標(biāo)車輛路徑問題。文獻(xiàn)[7]提出了一種使用分布估計(jì)算法的方法，通過使用廣義的Mallows分布作為概率模型來描述解空間的分布，以解決帶時(shí)間窗的車輛路徑問題。文獻(xiàn)[8]探索了時(shí)變多行車輛路徑問題(TDMTVRP)，使用了具有改進(jìn)行進(jìn)速度的模型，與容量較大的VRPTW[9]相比，減少了行車時(shí)間和行進(jìn)距離，并通過使用最近鄰啟發(fā)式算法獲得初始解和禁忌搜索啟發(fā)式算法搜索最優(yōu)解。文獻(xiàn)[10]提出了一種基于改進(jìn)的頭腦風(fēng)暴優(yōu)化算法(IBSO-ACO)的新型蟻群優(yōu)化算法，以解決帶有軟時(shí)間窗的車輛路徑問題。文獻(xiàn)[11]開發(fā)了一種混合遺傳算法的求解方法，對遺傳算法和變量鄰域搜索方法(VNS)進(jìn)行了雜交，以解決帶有軟時(shí)間窗的靜態(tài)和動態(tài)車輛路徑問題。這些學(xué)者對帶有時(shí)間窗的車輛路徑問題進(jìn)行了系統(tǒng)而深入的研究，但他們的研究大多使用改進(jìn)型的傳統(tǒng)啟發(fā)式算法，例如遺傳算法、蟻群算法和禁忌搜索算法等。這些算法在帶時(shí)間窗約束VRP的求解上取得了可喜的成果，但也存在不少問題，如禁忌搜索算法對初始解的依賴性較高，遺傳算法存在局部搜索能力不強(qiáng)、易陷入早熟、總體上可行解的質(zhì)量不是很高等缺點(diǎn)。

蜻蜓算法(dragonfly algorithm，DA)自從2015年被Mirjalili[12]提出就得到了廣泛的研究與應(yīng)用。該新型算法已被成功用于醫(yī)療疾病預(yù)測診斷[13]、太陽能熱系統(tǒng)優(yōu)化[14]、小麥碰撞聲信號檢測與識別[15]等諸多領(lǐng)域。其中，Abdelaziz I. Hammouri等[16]將蜻蜓算法運(yùn)用到旅行商問題(TSP)的求解之中，驗(yàn)證了蜻蜓算法在求解類路徑規(guī)劃問題的可行性。文獻(xiàn)[17]使用DA來估計(jì)隨機(jī)部署在指定區(qū)域中的節(jié)點(diǎn)的位置，通過仿真實(shí)驗(yàn)來表明DA可以為基于范圍的定位產(chǎn)生低誤差。文獻(xiàn)[18]提出了一種用于預(yù)測問題的帶有極限學(xué)習(xí)機(jī)(ELM)系統(tǒng)的混合蜻蜓算法，通過利用DA在隱藏層中選擇較少數(shù)量的節(jié)點(diǎn)，以加快ELM的性能。

然而，在軟時(shí)間窗的約束下，針對原蜻蜓算法解決大規(guī)模問題時(shí)存在收斂速度慢、運(yùn)算時(shí)間長、容易陷入局部最優(yōu)解等缺陷[19]，該文提出一種改進(jìn)型的蜻蜓算法應(yīng)用于車輛路徑問題，從而更好地提高物流運(yùn)輸車輛的配送效率。

2 問題描述及數(shù)學(xué)模型

帶時(shí)間窗約束的車輛路徑問題可以描述為：一個(gè)配送中心，擁有一定數(shù)量的同種車輛，車輛容量有限且已知，車輛滿載貨物由配送中心出發(fā)，向區(qū)域內(nèi)若干客戶配送同種商品，要求在完成配送任務(wù)的總路程最短的基礎(chǔ)上派出的車輛數(shù)最少，并考慮在客戶點(diǎn)的駐留成本、未在規(guī)定時(shí)間內(nèi)送達(dá)的懲罰成本。

該文從實(shí)際物流車輛運(yùn)輸特點(diǎn)和自身實(shí)驗(yàn)條件出發(fā)，對構(gòu)建的帶時(shí)間窗約束的車輛路徑問題數(shù)學(xué)模型進(jìn)行如下假設(shè)：

(1)車輛必須從固定的配送站點(diǎn)出發(fā)，運(yùn)輸途中不經(jīng)停該站點(diǎn)，在完成一趟運(yùn)輸過程之后才能回到配送站點(diǎn)；

(2)規(guī)定車輛以一種恒定的行駛速度在各站點(diǎn)之間行駛；

(3)各服務(wù)點(diǎn)的需求量、服務(wù)時(shí)間窗、服務(wù)時(shí)間不會臨時(shí)變動；

(4)各服務(wù)點(diǎn)之間的路徑都可達(dá)，并且不會產(chǎn)生任何突發(fā)事件影響車輛的行駛；

(5)一輛車只可以同時(shí)服務(wù)一個(gè)服務(wù)點(diǎn)、配送一條路線。

根據(jù)以上數(shù)學(xué)模型假設(shè)，對構(gòu)建的帶時(shí)間窗的車輛路徑問題數(shù)學(xué)模型中的參數(shù)和相關(guān)的變量進(jìn)行如下定義：

V={1,2,…,n}表示站點(diǎn)編號集合，n為站點(diǎn)總個(gè)數(shù)，編號1為起始站點(diǎn)。

Pos表示配送站點(diǎn)和客戶服務(wù)站點(diǎn)的位置集合，其中(Posix,Posiy)表示站點(diǎn)i的橫、縱坐標(biāo)位置。

Dis表示各個(gè)站點(diǎn)之間的距離，站點(diǎn)i與站點(diǎn)j之間的距離Disij由式(1)給出。

(1)

Ser_Time為站點(diǎn)的服務(wù)時(shí)間集合，其中Ser_Timei表示站點(diǎn)i的服務(wù)時(shí)間。

Demand為站點(diǎn)的服務(wù)需求量集合，其中Demandi表示站點(diǎn)i的貨物需求量。

TW表示各站點(diǎn)規(guī)定的服務(wù)時(shí)間窗，其中TWilast表

示站點(diǎn)i服務(wù)時(shí)間窗的最大非處罰服務(wù)時(shí)間。

duty記錄車輛已經(jīng)服務(wù)過的站點(diǎn)序列。

v_vel表示車輛行駛的速度。

v_cap表示車輛的最大載重量。

αij判斷車輛是否經(jīng)過站點(diǎn)i和站點(diǎn)j之間的路線。當(dāng)αij=1時(shí)，表示車輛經(jīng)過；當(dāng)αij=0時(shí)，表示車輛沒有經(jīng)過。

βi判斷站點(diǎn)i是否已經(jīng)服務(wù)過。當(dāng)βi=1時(shí)，表示站點(diǎn)i已經(jīng)服務(wù)過；當(dāng)βi=0時(shí)，表示沒有服務(wù)過。

γi判斷車輛在到達(dá)站點(diǎn)i時(shí)時(shí)間是否超出該站點(diǎn)的時(shí)間窗上限。當(dāng)γi=1時(shí)，表示超過；當(dāng)γi=0時(shí)，表示沒有。

time記錄車輛剛到達(dá)某一站點(diǎn)時(shí)的當(dāng)前時(shí)間，其計(jì)算公式由式(2)給出。

(2)

ctrans、cser和cpun分別表示車輛單位行駛路程、單位服務(wù)時(shí)間和單位懲罰時(shí)間成本。

綜上所述，該文構(gòu)建的數(shù)學(xué)模型目標(biāo)函數(shù)由式(3)給出。

Ser_Timei-TWilast)*cpun

(3)

約束條件如下所示。

(4)

(5)

(6)

0≤d_n≤n

(7)

(8)

(9)

3 模型實(shí)現(xiàn)

3.1 蜻蜓算法概述

蜻蜓算法是受蜻蜓行為啟發(fā)而提出的一種新型群智能算法。與其他的群智能優(yōu)化算法類似的是，蜻蜓算法也有著較好的局部最優(yōu)解避免能力和精確近似全局最優(yōu)解的能力。

蜻蜓算法像大多數(shù)群智能算法一樣皆是遵循“求生”的原則，蜻蜓個(gè)體有兩個(gè)行為：尋找食物和躲避天敵，蜻蜓群體的位置移動由以下五種行為組成：

(1)分離，即蜻蜓與相鄰個(gè)體之間避免碰撞。

式中，X是當(dāng)前個(gè)體的位置；Xj是第j個(gè)附近個(gè)體的位置；N是附近個(gè)體的個(gè)數(shù)。

(2)結(jié)隊(duì)，即相鄰個(gè)體之間傾向于保持相同的速度。

式中，Vj是第j個(gè)附近個(gè)體的速度。

(3)聚集，即蜻蜓傾向于向相鄰個(gè)體中心聚集。

(4)覓食，即蜻蜓對食物的傾向度。

Fi=X+-X

式中，X+是蜻蜓食物的位置。

(5)躲避天敵，即蜻蜓避免被天敵捕食，對其產(chǎn)生排斥。

Ei=X-+X

式中，X-是蜻蜓天敵的位置。

除以上五種行為之外，為了較為準(zhǔn)確地模擬出蜻蜓的移動過程，Mirjalili又引入了兩個(gè)量：步長向量(dX)和位置向量X。步長向量計(jì)算公式如下(這是逐維定義的步長)：

ΔXt+1=(sSi+aAi+cCi+fFi+eEi)+wΔXt

式中，s表示分離權(quán)重，a表示結(jié)隊(duì)權(quán)重，c表示聚集權(quán)重，f表示食物因子，e表示天敵因子；Si表示第i個(gè)體分離之后的位置，Ai表示第i個(gè)體結(jié)隊(duì)之后的位置，Ci表示第i個(gè)體聚集之后的位置，F(xiàn)i表示第i個(gè)體蜻蜓食物的位置，Ei表示第i個(gè)體蜻蜓天敵的位置；w表示慣性權(quán)重；t表示當(dāng)前迭代次數(shù)。

位置更新如下：

(6)附近存在蜻蜓個(gè)體，則按照如下方式更新：

Xt+1=Xt+ΔXt+1

(7)附近不存在蜻蜓個(gè)體，則執(zhí)行萊維飛行：

Xt+1=Xt+Levy(d)×Xt

式中，d是求解問題的維數(shù)。

3.2 改進(jìn)型蜻蜓算法

通過研究發(fā)現(xiàn)，采用傳統(tǒng)蜻蜓算法求解帶時(shí)間窗的車輛路徑問題時(shí)，存在收斂精度較低、最優(yōu)解容易陷入局部收斂等缺陷。因此，為了針對求解帶時(shí)間窗的車輛路徑問題，該文根據(jù)以上設(shè)計(jì)的數(shù)學(xué)模型，將隨機(jī)學(xué)習(xí)優(yōu)化[20]的思想融入到蜻蜓算法中，重新設(shè)計(jì)了一種能夠更有效應(yīng)用于帶時(shí)間窗約束的車輛路徑問題研究的改進(jìn)型蜻蜓算法。

該算法的主要改進(jìn)點(diǎn)在于將傳統(tǒng)蜻蜓算法結(jié)隊(duì)、覓食、避敵、避撞、聚集五種行為的實(shí)值計(jì)算形式，修改為隨機(jī)學(xué)習(xí)目標(biāo)位置對，即利用隨機(jī)學(xué)習(xí)優(yōu)化方法完成以上行為的實(shí)現(xiàn)：

(1)通過向同期蜻蜓種群中位置最優(yōu)的蜻蜓隨機(jī)學(xué)習(xí)一組排序，更新位置序列，優(yōu)化局部最優(yōu)解，實(shí)現(xiàn)結(jié)隊(duì)行為；

(2)向歷史蜻蜓種群中位置最優(yōu)的蜻蜓隨機(jī)學(xué)習(xí)一組排序，優(yōu)化位置序列，趨向于全局最優(yōu)解，實(shí)現(xiàn)覓食行為；

(3)通過遠(yuǎn)離同期蜻蜓種群中位置最差的蜻蜓位置，避免陷入局部最優(yōu)，實(shí)現(xiàn)避敵行為；

(4)發(fā)生碰撞時(shí)，隨機(jī)長度隨機(jī)打亂一只蜻蜓位置，保證種群多樣性，實(shí)現(xiàn)避撞行為。

該算法的具體實(shí)現(xiàn)步驟如下：

步驟1：初始化蜻蜓算法和數(shù)學(xué)模型的相關(guān)參數(shù)。其中，每一只蜻蜓的位置向量表示一種選路方式，即為除編號1外的n-1個(gè)站點(diǎn)編號的隨機(jī)排列組合；

步驟2：計(jì)算初代各解，即站點(diǎn)間的距離矩陣、每只蜻蜓位置向量所對應(yīng)的成本值、初代最優(yōu)解和最優(yōu)成本值等；

步驟3：開始迭代計(jì)數(shù)，令迭代標(biāo)識符iter=1；

步驟4：通過結(jié)隊(duì)、覓食、避敵、避撞等行為，進(jìn)行隨機(jī)學(xué)習(xí)優(yōu)化排序，優(yōu)化各蜻蜓的位置向量；

步驟5：利用目標(biāo)函數(shù)計(jì)算每只蜻蜓位置向量所對應(yīng)的運(yùn)輸成本值，并且記錄最優(yōu)值和最優(yōu)蜻蜓位置向量，即記錄最佳的成本值和對應(yīng)的車輛路徑規(guī)劃方案；

步驟6：將本代最優(yōu)值和歷史最優(yōu)值進(jìn)行比較，篩選得出最優(yōu)成本值和最優(yōu)蜻蜓位置向量；

步驟7：迭代標(biāo)識符加1；

步驟8：判斷是否達(dá)到最大的迭代次數(shù)。若是，進(jìn)入步驟9；若否，返回步驟4；

步驟9：得出實(shí)驗(yàn)結(jié)果，生成實(shí)驗(yàn)圖表，結(jié)束。

3.3 基于改進(jìn)蜻蜓算法的模型實(shí)現(xiàn)

基于改進(jìn)型蜻蜓算法的帶時(shí)間窗約束的車輛路徑問題模型實(shí)現(xiàn)流程如圖1所示。

圖1 改進(jìn)型蜻蜓算法實(shí)現(xiàn)流程

4 算例實(shí)驗(yàn)

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

服務(wù)站點(diǎn)初始參數(shù)設(shè)置如表1所示。

表1 服務(wù)站點(diǎn)參數(shù)設(shè)置

車輛初始參數(shù)設(shè)置如表2所示。

表2 車輛參數(shù)設(shè)置

改進(jìn)蜻蜓算法的初始參數(shù)設(shè)置如表3所示。

表3 蜻蜓算法參數(shù)設(shè)置

實(shí)驗(yàn)設(shè)計(jì)的拓?fù)渚W(wǎng)絡(luò)環(huán)境如圖2所示。

圖2 實(shí)驗(yàn)物流網(wǎng)絡(luò)拓?fù)?/p>

根據(jù)該文設(shè)計(jì)的帶時(shí)間窗車輛路徑問題數(shù)學(xué)模型約束條件，該物流拓?fù)渚W(wǎng)絡(luò)一共擁有3 628 800種車輛路徑規(guī)劃方案。

4.2 實(shí)驗(yàn)結(jié)果

針對文中的車輛路徑問題所提出的數(shù)學(xué)模型，將遺傳算法(GA)、禁忌搜索算法(TSA)、傳統(tǒng)蜻蜓算法(DA)和改進(jìn)后的蜻蜓算法(RDA)一同進(jìn)行實(shí)驗(yàn)測試并進(jìn)行比較。為保證實(shí)驗(yàn)的公平性和客觀性，將以上四種算法的迭代次數(shù)設(shè)為1 000次，采用相同的成本函數(shù)進(jìn)行運(yùn)算，得到的算法對比結(jié)果如圖3所示。

由實(shí)驗(yàn)結(jié)果可以看出，無論是在求解精度還是收斂速度上，改進(jìn)型蜻蜓算法都展現(xiàn)出優(yōu)越的性能，充分說明改進(jìn)型蜻蜓算法在求解車輛路徑問題時(shí)具有更加穩(wěn)定的性能。

圖3 算法對比

經(jīng)過實(shí)驗(yàn)得到最優(yōu)的綜合成本為1 447.23。其對應(yīng)的車輛路徑規(guī)劃方案如圖4所示。

圖4 最優(yōu)路線規(guī)劃

路線規(guī)劃方案為1→7→6→3→5→2→9→8→4→10。其中，加圈位置為站點(diǎn)1，即始發(fā)站點(diǎn)。

5 結(jié)束語

討論了帶軟時(shí)間窗約束的車輛路徑問題，構(gòu)建了一種更符合配送中心與顧客服務(wù)目標(biāo)優(yōu)化的帶時(shí)間窗約束的車輛路徑問題數(shù)學(xué)模型。通過設(shè)將隨機(jī)學(xué)習(xí)優(yōu)化的思想融入到原先的蜻蜓算法之中，針對車輛路徑問題數(shù)學(xué)模型的求解，重新設(shè)計(jì)了一種能夠更有效應(yīng)用于該問題求解的改進(jìn)型蜻蜓算法。

該算法的主要改進(jìn)之處為：將傳統(tǒng)的蜻蜓算法結(jié)隊(duì)、覓食、避敵、避撞、聚集五種行為原則從原先的實(shí)值計(jì)算形式修改成為隨機(jī)學(xué)習(xí)目標(biāo)位置對，即利用隨機(jī)學(xué)習(xí)優(yōu)化方法完成以上行為的實(shí)現(xiàn)，使改進(jìn)型蜻蜓算法更符合解的特性，從而得到一個(gè)更優(yōu)的結(jié)果。

通過Matlab仿真實(shí)驗(yàn)證明了將蜻蜓算法應(yīng)用到帶軟時(shí)間窗約束的車輛路徑問題求解的可行性，并且驗(yàn)證了改進(jìn)型蜻蜓算法用于該數(shù)學(xué)模型實(shí)現(xiàn)的有效性。下一步將在該研究的基礎(chǔ)上，提高算法收斂速度和收斂精度，改進(jìn)蜻蜓隨機(jī)學(xué)習(xí)的優(yōu)化方式，并將該算法應(yīng)用于其他領(lǐng)域的優(yōu)化。