求解帶容量和時(shí)間窗約束車輛路徑問題的改進(jìn)蝙蝠算法*

張 瑾,洪 莉,戴二壯

(河南大學(xué)計(jì)算機(jī)與信息工程學(xué)院，河南 開封 475004)

1 引言

車輛路徑問題VRP(Vehicle Routing Problem)是物流理論體系中一類經(jīng)典的組合優(yōu)化問題，隨著物流業(yè)的不斷發(fā)展，越來越多的VRP問題模型得以產(chǎn)生和發(fā)展，如帶容量約束的VRP CVRP(Capacitated VRP)、帶時(shí)間窗約束的VRP VRPTW(VRP with Time Windows)以及帶容量和時(shí)間窗約束的VRP CVRPTW(Capacitated VRP with Time Windows)[1]等。

由于上述問題都屬于NP難題，對于較大規(guī)模問題，精確算法難以在有限時(shí)間內(nèi)給出最優(yōu)解，因此普遍采用智能算法進(jìn)行求解?，F(xiàn)有關(guān)于CVRPTW問題的算法大致有遺傳算法GA(Genetic Algorithm)、蟻群算法、禁忌搜索算法、粒子群優(yōu)化PSO(Particle Swarm Optimization)算法、蝙蝠算法和狼群算法等，問題的優(yōu)化目標(biāo)大多為運(yùn)輸距離最短或時(shí)間最短，部分文獻(xiàn)考慮了違反時(shí)間窗約束的懲罰成本。采用遺傳算法GA求解的文獻(xiàn)中，Jiang等[2]通過合理構(gòu)造染色體，利用遺傳算法使最優(yōu)解的搜索在可行空間內(nèi)進(jìn)行;趙振華等[3]提出一種先考慮客戶服務(wù)的先后次序，然后在此基礎(chǔ)上構(gòu)建初始種群的方法，二者都以運(yùn)距最短為優(yōu)化目標(biāo)；李加玲等[4]在遺傳算法中引入輪盤賭策略尋找可行的配送路徑；黃務(wù)蘭等[5]引入精英保留策略，采用客戶點(diǎn)交叉和路段交叉算子相結(jié)合的方式以保證算法中種群的多樣性，二者都以配送時(shí)間最短作為優(yōu)化目標(biāo)。采用蟻群算法求解的文獻(xiàn)中，李琳等[6]在算法的不同階段采用不同的信息素?fù)]發(fā)策略防止算法陷入局部最優(yōu)；辜勇等[7]以改進(jìn)蟻群算法為主體，插入遺傳操作算子作為局部優(yōu)化方法，二者都以運(yùn)距最短為優(yōu)化目標(biāo)；黃震等[8]在節(jié)點(diǎn)選擇概率公式中引入時(shí)間窗因素來初始化種群，然后引入遺傳操作的交叉和變異算子對路徑進(jìn)行優(yōu)化；李奕穎等[9]采用改進(jìn)的狀態(tài)轉(zhuǎn)移規(guī)則和輪盤賭選擇機(jī)制構(gòu)建初始解，并結(jié)合k元素優(yōu)化k-opt(k-optimization)鄰域搜索進(jìn)行優(yōu)化，二者都以配送車輛最少和運(yùn)距最短為優(yōu)化目標(biāo)。采用禁忌搜索算法求解的文獻(xiàn)中，鐘石泉等[10]引入多初始解和全局禁忌表等措施，旨在擴(kuò)大搜索范圍并減少解的不穩(wěn)定性，以運(yùn)距和違反時(shí)間窗約束的懲罰成本之和最小為優(yōu)化目標(biāo)；Chen等[11]在禁忌搜索算法中引入遺傳操作算子進(jìn)行初始化，并采用2-opt操作進(jìn)行局部優(yōu)化；李明燏等[12]引入一條虛擬的路徑作為保留表，已選擇路徑上的用戶點(diǎn)可以與保留表中的用戶點(diǎn)進(jìn)行交換和移動(dòng)，以便擴(kuò)大搜索空間，二者都以運(yùn)距最短為優(yōu)化目標(biāo)。采用粒子群優(yōu)化算法PSO求解的文獻(xiàn)中，李寧等[13]在初始化時(shí)將粒子群劃分為若干個(gè)兩兩重疊的相鄰子群，使算法跳出局部最優(yōu)；馬炫等[14]提出一種基于粒子交換原理的整數(shù)粒子更新方法；羅耀[15]引入微生物行為機(jī)制中的趨化、繁殖和遷移算子對算法進(jìn)行優(yōu)化，三者都以總運(yùn)距和違反時(shí)間窗約束的懲罰成本之和最小為優(yōu)化目標(biāo)；王飛[16]在慣性權(quán)重遞減的基礎(chǔ)上通過群體極值進(jìn)行t分布變異，使算法跳出局部最優(yōu)；Marinakis等[17]提出一種多自適應(yīng)粒子群優(yōu)化算法，二者都以最短運(yùn)距為優(yōu)化目標(biāo)。采用蝙蝠算法求解的文獻(xiàn)中，馬祥麗等[18]針對帶時(shí)間窗車輛路徑問題的具體特征對蝙蝠算法的操作算子進(jìn)行重新設(shè)計(jì)，以運(yùn)距最短為優(yōu)化目標(biāo)；戚遠(yuǎn)航等[19]以硬時(shí)間窗為約束條件(即車輛在客戶時(shí)間窗之外到達(dá)不進(jìn)行配送，反之則為軟時(shí)間窗約束)，引入隨機(jī)插入搜索、最少客戶車輛插入搜索、普通插入搜索和交換搜索等策略來擴(kuò)大搜索空間，以配送車輛最少和運(yùn)距最短為優(yōu)化目標(biāo)；孫奇等[20]加入貪婪隨機(jī)自適應(yīng)啟發(fā)式策略提高求解精度，引入病毒進(jìn)化機(jī)制使蝙蝠算法跳出局部最優(yōu)，以客戶滿意度最大和運(yùn)距最短為優(yōu)化目標(biāo)。采用狼群算法求解的文獻(xiàn)中，葉勇等[21]利用近鄰初始化方式構(gòu)建初始解，結(jié)合狼群算法覓食行為中的游走、召喚和圍攻3種行為重新定義其智能行為，以運(yùn)距最短為優(yōu)化目標(biāo)。

上述文獻(xiàn)在求解CVRPTW問題時(shí)均取得了一定的成果，但其多考慮硬時(shí)間窗約束，目標(biāo)函數(shù)大多以運(yùn)輸距離或時(shí)間最短為優(yōu)化目標(biāo)，且采用的測試案例基本都是小規(guī)模的，未涉及較大規(guī)模問題的求解。由于在實(shí)際物流運(yùn)輸中軟時(shí)間窗約束更符合客戶需求，本文將綜合考慮包含車輛使用成本、運(yùn)輸成本和違反時(shí)間窗約束的懲罰成本在內(nèi)的帶軟時(shí)間窗和容量約束的車輛路徑問題。蝙蝠算法是一種較為新穎的智能優(yōu)化算法，在離散優(yōu)化領(lǐng)域應(yīng)用較少，為了提高CVRPTW問題的求解精度，本文設(shè)計(jì)了一種改進(jìn)的離散蝙蝠算法DBA(Discrete Bat Algorithm)，并考慮了較大規(guī)模問題的有效求解。

2 求解問題描述

本文研究的問題為：在同時(shí)滿足客戶軟時(shí)間窗約束和車載容量約束的前提下，通過合理安排車輛配送路線，使得包含車輛使用成本、運(yùn)輸成本和違反時(shí)間窗約束的懲罰成本最小。問題研究的前提條件如下所示：

(1)配送起點(diǎn)和終點(diǎn)唯一；

(2)所有車輛容量相同，每個(gè)客戶點(diǎn)僅由1輛車提供服務(wù)；

(3)每個(gè)客戶點(diǎn)的需求量已知，時(shí)間窗約束唯一，無優(yōu)先服務(wù)約束。

模型中相關(guān)重要參數(shù)定義如下所示：

Z：總成本；

N：客戶點(diǎn)總量；

Q：車輛的最大載重量；

c：單位車輛的固定費(fèi)用；

b：單位距離油耗成本；

dij：客戶點(diǎn)i到客戶點(diǎn)j之間的距離；

Ai：車輛到達(dá)客戶點(diǎn)i的時(shí)間點(diǎn)；

ti：為客戶點(diǎn)i進(jìn)行服務(wù)所需時(shí)間；

qi：客戶點(diǎn)i的貨物重量；

Sj：客戶點(diǎn)j的時(shí)間窗開始點(diǎn)；

Ej：客戶點(diǎn)j的時(shí)間窗結(jié)束點(diǎn)；

e：早于客戶最早時(shí)間窗到達(dá)的懲罰系數(shù)；

l：晚于客戶最晚時(shí)間窗到達(dá)的懲罰系數(shù)；

tij：車輛從客戶點(diǎn)i到客戶點(diǎn)j的運(yùn)行時(shí)間；

S：客戶點(diǎn)的編號(hào)集合，S?{1,2,…,N}；

x0jk：表示車輛k從配送中心駛向客戶點(diǎn)j；

xi0k：表示車輛k從客戶點(diǎn)i返回配送中心。

決策變量為：

K：所需車輛總數(shù)；

xijk：0-1變量，當(dāng)車輛k由客戶點(diǎn)i到達(dá)客戶點(diǎn)j時(shí)為1，否則為0；

yik：0-1變量，當(dāng)車輛k為客戶點(diǎn)i提供服務(wù)時(shí)為1，否則為0。

構(gòu)建模型如式(1)～式(11)所示，其中式(1)為目標(biāo)函數(shù)，表示包含車輛租賃成本、違反時(shí)間窗約束的懲罰成本以及與行駛距離相關(guān)的油耗成本在內(nèi)的總配送成本最??；式(2)表示每輛車裝載的貨物總量不超過車輛的最大容量；式(3)表示每個(gè)客戶點(diǎn)由且僅由1輛車提供服務(wù)；式(4)保證客戶點(diǎn)j之前的臨近節(jié)點(diǎn)只有1個(gè)；式(5)保證客戶點(diǎn)i之后的臨近節(jié)點(diǎn)只有1個(gè)；式(6)表示從配送中心出發(fā)的車輛在完成配送任務(wù)后要返回配送中心；式(7)表示消除子回路即消除車輛不是從車場出發(fā)的現(xiàn)象，式(4)～式(7)共同保證了可行回路；式(8)和式(9)表示客戶時(shí)間窗約束；式(10)和式(11)表示決策變量的取值范圍。

(1)

(2)

(3)

?k∈{1,2,…,K}

(4)

(5)

(6)

2≤|S|≤N-1

(7)

Sj

(8)

Aj=Ai+ti+tij,i,j∈{0,1,2,…,N},i≠j

(9)

xijk∈{0,1},i,j∈{1,2,…,N},?k∈{1,2,…,K}

(10)

yki∈{0,1},i∈{1,2,…,N},?k∈{1,2,…,K}

(11)

3 模型求解的改進(jìn)蝙蝠算法

蝙蝠算法BA是由Yang[22]提出的一種新型啟發(fā)式算法，算法利用蝙蝠通過回聲定位行為進(jìn)行捕食的原理進(jìn)行問題求解，具有參數(shù)少、穩(wěn)定性高、求解速度快、尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn)，已在工程優(yōu)化、特征選擇、故障診斷和數(shù)據(jù)挖掘等多個(gè)領(lǐng)域展現(xiàn)出較好的應(yīng)用效果[23 - 27]。蝙蝠回聲定位原理為：蝙蝠以脈沖的形式發(fā)射一定頻率和響度的超聲波，當(dāng)超聲波在傳播的過程中遇到物體時(shí)會(huì)返回回聲，通過對接收到的回聲進(jìn)行處理，蝙蝠可以檢測到物體相對于自身的距離和方向，以及物體的大小和運(yùn)動(dòng)速度，從而捕食或者避開障礙物。為便于模擬蝙蝠的回聲定位行為，Yang給出2個(gè)理想化規(guī)則：

(1)搜索規(guī)則：蝙蝠隨機(jī)飛行，同時(shí)以固定的頻率、可變的波長和音量的超聲波來搜索獵物。

(2)參數(shù)變化規(guī)則：蝙蝠根據(jù)自身與獵物的距離來自動(dòng)調(diào)整脈沖波長和脈沖發(fā)射率，并限定聲音響度在指定范圍內(nèi)依照給定方式由大到小變化。

算法求解過程由若干獨(dú)立搜索的蝙蝠完成，算法首先將每只蝙蝠視為當(dāng)前可行域內(nèi)的一個(gè)解，每個(gè)解對應(yīng)一個(gè)由所優(yōu)化問題確定的適應(yīng)值，每只蝙蝠通過調(diào)整其脈沖頻率、聲音響度、脈沖發(fā)射率3項(xiàng)參數(shù)來追隨當(dāng)前最優(yōu)蝙蝠，使得整個(gè)種群在問題求解空間中產(chǎn)生從無序到有序的衍化，進(jìn)而獲取最優(yōu)解。脈沖頻率、速度和位置的更新方式如式 (12)～式(14)所示：

fa=fmin+(fmax-fmin)β

(12)

(13)

(14)

Begin

初始化算法相關(guān)參數(shù)及蝙蝠的位置、速度和脈沖頻率；

根據(jù)蝙蝠的初始位置計(jì)算適應(yīng)度值，得出初始解，找出最優(yōu)蝙蝠位置；

While(t<最大迭代數(shù))

根據(jù)式(12)～式(14)分別調(diào)整蝙蝠的脈沖頻率、速度和位置；

If(當(dāng)前隨機(jī)數(shù)>當(dāng)前脈沖發(fā)射率)

在當(dāng)前最優(yōu)解附近根據(jù)式(15)進(jìn)行局部搜索；

xnew=x*+ε*μ

(15)

其中，xnew表示隨機(jī)擾動(dòng)得到的新解；ε表示服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)向量，且ε～N(0,1)；μ表示常量，且0<μ<1；x*表示當(dāng)前最優(yōu)解。

Endif

If(當(dāng)前隨機(jī)數(shù)<當(dāng)前聲音響度,且xnew的適應(yīng)度值優(yōu)于x*)

接受新解，分別根據(jù)式(16)和式(17)更新脈沖發(fā)射率和聲音響度；

(16)

(17)

Endif

輸出全局最優(yōu)解；

Endwhile

End

3.1 編碼策略

車輛路徑問題屬于離散的組合優(yōu)化問題，首先對所求問題中的各個(gè)變量設(shè)計(jì)編碼策略，然后將其轉(zhuǎn)變?yōu)轵鹚惴梢詢?yōu)化的變量。假設(shè)求解問題的規(guī)模為N，將客戶點(diǎn)編碼為從1到N的不同整數(shù)。

(1)解編碼策略。

針對CVRPTW問題的特性，解的編碼以待訪問客戶點(diǎn)編號(hào)序列表示，解中每個(gè)分量對應(yīng)一個(gè)客戶點(diǎn)編號(hào)，因而得到解X的編碼形式為：X=(m1,m2,…,mN)。其中，N表示編碼長度，mi表示第i個(gè)要訪問的客戶點(diǎn)編號(hào)(mi∈[1,N]，且任意mi≠mj)。

(2)速度編碼策略。

vi表示蝙蝠訪問到第i個(gè)客戶點(diǎn)時(shí)的速度值，則速度的編碼形式為：V=(v1,v2,…,vN)。其中，V表示速度，編碼中每一個(gè)速度的值可以為正值或負(fù)值，vi∈[-(N-1),N-1]。

3.2 局部搜索策略

由于標(biāo)準(zhǔn)蝙蝠算法缺少擾動(dòng)機(jī)制，存在算法后期收斂速度慢、易陷入局部最優(yōu)等缺陷[28]，為此引入變步長搜索策略和2元素優(yōu)化2-opt操作以增加解的多樣性，跳出局部最優(yōu)。

(1)變步長搜索。

在搜索過程中，蝙蝠的移動(dòng)步長應(yīng)伴隨搜索過程的進(jìn)行發(fā)生改變，在算法運(yùn)行初期，步長應(yīng)保持一個(gè)較大值，以避免算法過早陷入局部最優(yōu)；隨著迭代次數(shù)的增加，步長應(yīng)自適應(yīng)地減小，最后保持一個(gè)較小值，使得算法后期加快收斂，得到更精確的值。標(biāo)準(zhǔn)蝙蝠算法中，蝙蝠位置的更新受ε和μ2個(gè)因子的影響，二者不能保證步長值遵循上述規(guī)則發(fā)生改變。若常量u取值較大，易使算法收斂速度變慢，若μ取值較小，則算法易陷入局部最優(yōu)。

本文引入變步長搜索策略，以增加擾動(dòng)機(jī)制和解的多樣性。定義步長擾動(dòng)因子，其計(jì)算方法如式(18)所示：

τj=(Nitermax-j)/Nitermax

(18)

其中，τj表示在第j次迭代時(shí)的步長擾動(dòng)因子，Nitermax表示最大迭代次數(shù)，j≤Nitermax。

改進(jìn)的蝙蝠算法中，蝙蝠以變步長的方式進(jìn)行局部搜索，搜索方式如式(19)所示:

xnew=x*+ε*μ*τj

(19)

(2) 2-opt優(yōu)化操作。

2-opt操作即選定路徑上的任意2個(gè)節(jié)點(diǎn)并將節(jié)點(diǎn)間的路徑進(jìn)行翻轉(zhuǎn)，得到新的路徑，以增加路徑搜索的多樣性，提高算法局部搜索能力。以7個(gè)客戶點(diǎn)的配送為例，假設(shè)客戶點(diǎn)為A、B、C、D、E、F、G，s為當(dāng)前最優(yōu)解，s={A,B,C,D,E,F,G}。以一定的概率進(jìn)行2-opt操作，首先在s中隨機(jī)選擇不相鄰的2個(gè)節(jié)點(diǎn)B和E，然后將2個(gè)節(jié)點(diǎn)之間的路徑翻轉(zhuǎn)獲得新路徑，節(jié)點(diǎn)B之前的路徑保持不變添加到新路徑中，將節(jié)點(diǎn)B到節(jié)點(diǎn)E之間的路徑逆序排號(hào)后添加到新路徑中，節(jié)點(diǎn)E之后的路徑不變添加到新路徑中，則得到的新路徑s′={A,E,D,C,B,F,G}。

3.3 算法實(shí)現(xiàn)

為降低算法在搜索過程中的隨機(jī)性，縮小搜索范圍，加快搜索速度，本文首先引入聚類操作，對所有客戶點(diǎn)按其所在位置采用K-means算法進(jìn)行聚類，使得每個(gè)客戶點(diǎn)最終歸屬于若干個(gè)不同分區(qū)。本文DBA算法的適應(yīng)度值根據(jù)式(1)計(jì)算，具體求解方法如下：

Step1根據(jù)每個(gè)待配送客戶點(diǎn)所需配送的貨物重量，并結(jié)合車輛的載重限制把滿足要求的客戶點(diǎn)放入車輛運(yùn)行路線中。

Step2如果該客戶點(diǎn)的貨物重量超出了車輛的限載量Q，則再申請1輛車，并將當(dāng)前所需車輛總數(shù)加1；當(dāng)遍歷完所有客戶點(diǎn)時(shí)，即可確定所需車輛總數(shù)K。

Step3每個(gè)客戶點(diǎn)都對應(yīng)唯一的時(shí)間窗，若車輛不在客戶點(diǎn)相應(yīng)的時(shí)間窗內(nèi)到達(dá)，則給予一定的懲罰。

Step4計(jì)算油耗成本、違反時(shí)間窗的懲罰成本和車輛的租賃費(fèi)用之和。

DBA算法實(shí)現(xiàn)步驟如下所示：

Step1對蝙蝠位置、脈沖頻率和速度進(jìn)行初始化操作。

Step2將Step 1中所有初始蝙蝠個(gè)體的位置(即所有客戶點(diǎn))按其所處位置利用K-means算法進(jìn)行分區(qū)處理。

Step3蝙蝠位置更新，即對于任意蝙蝠a，根據(jù)式(12)～式(14)分別調(diào)整其脈沖頻率、速度和位置，從而產(chǎn)生后代蝙蝠。

Step4若當(dāng)前隨機(jī)數(shù)小于當(dāng)前脈沖頻率，則按Step 3進(jìn)行全局搜索，并計(jì)算新的適應(yīng)度值；否則在當(dāng)前解附近根據(jù)式(19)以變步長搜索方式進(jìn)行局部搜索，并以一定的概率進(jìn)行2-opt操作，計(jì)算新的適應(yīng)度值。

Step5若Step 4得到的適應(yīng)度值小于當(dāng)前最小適應(yīng)度值，并且當(dāng)前聲音響度大于當(dāng)前隨機(jī)數(shù)，則利用Step 4得到的適應(yīng)度值更新最小適應(yīng)度值，并記錄各個(gè)蝙蝠的位置，得到全局最優(yōu)解，否則不更新。

Step6根據(jù)式(16)和式(17)分別更新脈沖發(fā)射率及聲音響度。

Step7重復(fù)Step 4～Step 6，直到滿足結(jié)束條件，輸出全局最優(yōu)解。

4 仿真實(shí)驗(yàn)

由于遺傳算法、蟻群算法和粒子群優(yōu)化算法是當(dāng)前在CVRPTW問題求解領(lǐng)域應(yīng)用較為廣泛的群智能優(yōu)化算法，而蟻群算法在求解較大規(guī)模問題時(shí)速度相對較慢，因此，本文選取GA和PSO算法進(jìn)行對比實(shí)驗(yàn)。實(shí)驗(yàn)測試環(huán)境為Windows 10 64位操作系統(tǒng)，CPU為3.4 GHz，內(nèi)存為4.0 GB；仿真實(shí)驗(yàn)平臺(tái)為Matlab R2017b。

Solomon數(shù)據(jù)集是目前帶時(shí)間窗車輛路徑問題最常用的標(biāo)準(zhǔn)測試庫，按照節(jié)點(diǎn)間的位置關(guān)系可以將Solomon數(shù)據(jù)集中的測試數(shù)據(jù)分為C、R和RC 3大類，每類問題又劃分為1和2 2個(gè)子類。3大類問題客戶點(diǎn)坐標(biāo)及時(shí)間窗設(shè)置方式不同，其中C類數(shù)據(jù)中節(jié)點(diǎn)呈集簇式分布，節(jié)點(diǎn)分布于若干中心位置附近；R類數(shù)據(jù)中節(jié)點(diǎn)呈隨機(jī)分布，節(jié)點(diǎn)位置間無明顯集簇關(guān)系；RC類數(shù)據(jù)介于兩者之間，部分節(jié)點(diǎn)呈隨機(jī)分布，部分節(jié)點(diǎn)呈集簇式分布。子類1中問題的時(shí)間窗設(shè)置相對集中，子類2中問題的時(shí)間窗設(shè)置相對分散，且時(shí)間跨度較大。為了更全面地驗(yàn)證本文算法求解效果，本文分別選取C1、C2、R1、R2、RC1、RC2問題中12個(gè)經(jīng)典測試實(shí)例(見表1，其中，測試實(shí)例C101、C102、C104都屬于C1類問題。C101、C102、C104是Solomon測試集中的測試實(shí)例名稱，其問題規(guī)模均為101，不同測試實(shí)例之間的客戶點(diǎn)分布不同)，分別使用DBA、PSO和GA算法對每個(gè)實(shí)例進(jìn)行10次計(jì)算，所有測試均采用全浮點(diǎn)數(shù)運(yùn)算，算法所得最優(yōu)解為10次計(jì)算所得最小值。

算法中各參數(shù)取值如下：DBA中脈沖頻率的最大值fmax=1，脈沖頻率的最小值fmin=0，聲音響度的衰減系數(shù)p=0.9，搜索頻率的增強(qiáng)系數(shù)γ=0.9，聲音響度A∈(0,1)，脈沖發(fā)射率r∈(0,1)，早于和晚于時(shí)間窗到達(dá)的懲罰系數(shù)e=l=0.35，單位距離油耗成本b=0.35，單位車輛的費(fèi)用c=100，車輛的最大載重量Q=200；GA算法中交叉概率pc=0.3，變異概率pm=0.2；PSO算法中慣性權(quán)重因子w=0.2，加速系數(shù)C1=C2=2。

表1～表3給出了種群規(guī)模等于城市規(guī)模數(shù)，迭代次數(shù)分別為200,600和1 000時(shí)3種算法所得最優(yōu)值及平均耗費(fèi)時(shí)間。

Table 1 Optimal values and average time consumption of three algorithms when iteration number is 200表1 迭代次數(shù)為200時(shí)3種算法最優(yōu)值和平均耗費(fèi)時(shí)間

Table 2 Optimal values and average time consumption of three algorithms when iteration number is 600表2 迭代次數(shù)為600時(shí)3種算法最優(yōu)值和平均耗費(fèi)時(shí)間

從表1～表3可以看出，種群規(guī)模相同的情況下，迭代次數(shù)分別為200,600和1 000時(shí)，DBA算法對于12個(gè)實(shí)例所得最優(yōu)值均在很大程度上優(yōu)于GA和PSO算法的，GA算法獲得的最優(yōu)值多數(shù)優(yōu)于PSO算法的。在平均時(shí)間耗費(fèi)方面，DBA算法稍長于GA和PSO算法。

為進(jìn)一步驗(yàn)證DBA算法性能，分別針對各問題計(jì)算GA或PSO算法最優(yōu)值與DBA算法最優(yōu)值之差與 DBA算法最優(yōu)值的百分比，得到如下結(jié)果：表1中，C101問題改進(jìn)效果最好，DBA算法相對GA和PSO算法分別改進(jìn)44.71%和66.41%；對于RC201和R201問題，DBA算法相對GA和PSO算法改進(jìn)效果較差，前者分別改進(jìn)了5.73%和4.46%，后者分別改進(jìn)了6.37% 和4.37%；對于表1中12個(gè)實(shí)例，DBA算法相對GA和PSO算法平均改進(jìn)了17.28%和24.11%。表2中，C101問題改進(jìn)效果最好，DBA算法相對GA和PSO算法分別改進(jìn)了59.47%和79.38%；RC201問題改進(jìn)效果最差，DBA算法相對GA和PSO算法分別改進(jìn)了5.49%和4.12%；對于表2中12個(gè)實(shí)例，DBA算法相對GA和PSO算法平均改進(jìn)了17.64%和22.61%。表3中，C101問題改進(jìn)效果最好，DBA算法相對GA和PSO算法分別改進(jìn)了59.38%和73.69%；對于C201和RC201問題，DBA算法相對GA和PSO算法改進(jìn)效果較差，前者分別改進(jìn)了3.71%和5.54%，后者分別改進(jìn)了6.26%和3.43%；對于表3中12個(gè)實(shí)例，DBA算法相對GA和PSO算法平均改進(jìn)了18.02%和21.24%?？傮w來看，3種問題中C類問題改進(jìn)效果最好，R類問題其次，RC類問題最差；每種問題內(nèi)1類問題相對于2類問題的改進(jìn)效果更好。

Table 3 Optimal values and average time consumption of three algorithms when iteration number is 1 000表3 迭代次數(shù)為1 000時(shí)3種算法最優(yōu)值和平均耗費(fèi)時(shí)間

圖1～圖3分別給出了與表1～表3相同條件下3種算法分別對12個(gè)測試實(shí)例進(jìn)行10次運(yùn)算所得解的平均值隨問題規(guī)模變化的曲線圖。圖4給出了對于表1～表3中12個(gè)實(shí)例，DBA算法分別相對于GA和PSO算法的平均改進(jìn)百分比條形圖。

Figure 1 Change curves of average values of three algorithms when population size equals to the number of cities and iteration number is 200圖1 種群規(guī)模等于城市數(shù)時(shí)迭代 200次3種算法平均值變化曲線

Figure 2 Change curves of average values of three algorithms when population size equals to the number of cities and iteration number is 600圖2 種群規(guī)模等于城市規(guī)模時(shí)迭代 600次3種算法平均值變化曲線

Figure 3 Change curves of average values of three algorithms when population size equals to the number of cities and iteration number is 1 000圖3 種群規(guī)模等于城市規(guī)模時(shí)迭代 1 000次3種算法平均值變化曲線

Figure 4 Average improvement percentage of DBA relative to GA and PSO for the 12 problems圖4 對于12個(gè)問題DBA分別相對于 GA和PSO的平均改進(jìn)百分比

從圖1～圖3及前述數(shù)據(jù)分析結(jié)果可以發(fā)現(xiàn)，DBA算法求解所得最優(yōu)值及平均值均優(yōu)于GA和PSO算法的，GA算法相對于PSO算法獲得較好最優(yōu)解的比例更高，且在迭代1 000次時(shí)的DBA算法相對于GA算法改進(jìn)效果最好。

從圖4可以看出，DBA算法相對于GA算法的平均改進(jìn)百分比最大為18.02%，最小為17.28%；DBA算法相對于PSO算法的平均改進(jìn)百分比最大為24.11%，最小為21.24%。上述圖形及數(shù)據(jù)表明，本文所設(shè)計(jì)的DBA算法相對GA和PSO算法具有較好的求解效果。

表4給出了迭代次數(shù)為1 000時(shí)，種群規(guī)模為30的DBA算法、種群規(guī)模等于城市規(guī)模數(shù)的GA和PSO算法所得平均值、最優(yōu)值和平均耗費(fèi)時(shí)間。

從表4可以看出，迭代次數(shù)相同的情況下，種群規(guī)模為30的DBA算法所得最優(yōu)值、平均值和平均時(shí)間耗費(fèi)均優(yōu)于采用較大規(guī)模種群的GA和PSO算法。在上述12個(gè)測試實(shí)例中，種群規(guī)模為30的DBA算法的平均求解時(shí)間相對于同等規(guī)模的GA和PSO算法分別加快了158.16%和168.98%；GA和PSO算法的最優(yōu)值相對于DBA算法的平均值的平均改進(jìn)百分比分別為6.73%和9.27%，最好改進(jìn)百分比分別為19.06%和33.97%。數(shù)據(jù)分析結(jié)果表明，DBA算法在問題求解精度和求解效率方面均有較為明顯的優(yōu)勢。

5 結(jié)束語

帶時(shí)間窗和容量約束的車輛路徑問題在現(xiàn)實(shí)中有著廣泛的應(yīng)用，對該問題進(jìn)行優(yōu)化的研究從未停歇。本文研究了求解該問題的離散蝙蝠算法，利用K-means算法對客戶點(diǎn)按其所在位置進(jìn)行聚類，在DBA算法中引入了變步長搜索策略和2-opt操作進(jìn)行局部搜索。

實(shí)驗(yàn)結(jié)果表明：所設(shè)計(jì)的離散蝙蝠算法具有較快的收斂速度和較強(qiáng)的尋優(yōu)能力，能夠有效降低配送成本。本文設(shè)計(jì)的算法只是對標(biāo)準(zhǔn)蝙蝠算法的初步改進(jìn)，對測試庫內(nèi)子類2中問題改進(jìn)效果相對較差，后續(xù)研究中將考慮對子類2問題的時(shí)間窗進(jìn)行聚類處理，并將蝙蝠算法與其它智能算法思想相結(jié)合，以進(jìn)一步提高算法的求解性能。

Table 4 Optimal values and average time consumption of three algorithms with different population sizes when iteration number is 1 000表4 迭代次數(shù)為1 000時(shí)3種算法在不同種群規(guī)模下的最優(yōu)值和平均耗費(fèi)時(shí)間