改進(jìn)多目標(biāo)蟻群算法在動(dòng)態(tài)路徑優(yōu)化中的應(yīng)用

吳耕銳 郭三學(xué) 吳虎勝 薄 鳥(niǎo)

1(武警工程大學(xué)裝備管理與保障學(xué)院 陜西 西安 710086)2(武警警官學(xué)院基礎(chǔ)部 四川 成都 610213)3(武警警官學(xué)院信息通信系 四川 成都 610213)

0 引 言

隨著科技發(fā)展，城市交通向集成化、智能化、網(wǎng)絡(luò)化不斷發(fā)展，車(chē)輛、設(shè)備、網(wǎng)絡(luò)形成了一個(gè)共同體，為研究車(chē)輛運(yùn)輸路徑提供海量動(dòng)態(tài)信息已然成為可能，動(dòng)態(tài)路徑優(yōu)化問(wèn)題成為了研究熱點(diǎn)。決策者應(yīng)當(dāng)將動(dòng)態(tài)路徑問(wèn)題看成一個(gè)系統(tǒng)問(wèn)題，包括數(shù)據(jù)信息采集、數(shù)據(jù)傳輸和路徑優(yōu)化計(jì)算等。

目前動(dòng)態(tài)路徑優(yōu)化的研究較多。如劉波等[1]結(jié)合冷鏈物流特點(diǎn)，建立了以配送總成本最小為優(yōu)化目標(biāo)的帶時(shí)間窗冷鏈配送動(dòng)態(tài)車(chē)輛路徑優(yōu)化模型，提出了一種自適應(yīng)改進(jìn)人工魚(yú)群算法，利于節(jié)約企業(yè)資源和提高客戶滿意度。李治等[2]提出了小波神經(jīng)網(wǎng)絡(luò)的速度預(yù)測(cè)模型，針對(duì)動(dòng)態(tài)最優(yōu)路徑選擇問(wèn)題，確定了基于短時(shí)交通預(yù)測(cè)的動(dòng)態(tài)路徑求解算法。趙宏偉等[3]針對(duì)實(shí)時(shí)環(huán)境下交通特性，提出了實(shí)時(shí)環(huán)境下基于混合的動(dòng)態(tài)路徑優(yōu)化算法，將剪枝算法和自適應(yīng)A算法結(jié)合，并引入粒子群優(yōu)化，更好適應(yīng)了實(shí)時(shí)環(huán)境求解。

蟻群算法求解路徑優(yōu)化的研究也較多。如陳希瓊等[4]建立了同時(shí)考慮車(chē)輛容量和距離約束的雙目標(biāo)模型，用蟻群算法求解多個(gè)目標(biāo)，實(shí)現(xiàn)了運(yùn)輸成本和路徑間最大長(zhǎng)度差最小化的目的。徐少甫等[5]綜合考慮運(yùn)輸風(fēng)險(xiǎn)和運(yùn)輸時(shí)間目標(biāo)，通過(guò)ACO算法尋優(yōu)，實(shí)現(xiàn)了對(duì)危險(xiǎn)化學(xué)品的運(yùn)輸路徑優(yōu)化求解。孫沁等[6]采用2-opt算法擴(kuò)大搜索范圍，克服了蟻群算法缺陷，將其應(yīng)用于電子商務(wù)配送路徑優(yōu)化中，達(dá)到了配送成本最低目標(biāo)。開(kāi)吉等[7]為解決配送效率低的問(wèn)題，以淮海經(jīng)濟(jì)區(qū)為實(shí)例，建立了蟻群算法模型，降低了物流配送成本，提高了服務(wù)質(zhì)量。

也有將智能優(yōu)化算法用于動(dòng)態(tài)路徑優(yōu)化的相關(guān)研究。如趙峰等[8]提出了一種新型自適應(yīng)搜索半徑的蟻群路徑優(yōu)化算法，能根據(jù)障礙分布自動(dòng)選擇搜索半徑，完成路徑動(dòng)態(tài)規(guī)劃，其環(huán)境適應(yīng)能力和路徑優(yōu)化性能優(yōu)。文獻(xiàn)[9]應(yīng)用蟻群算法來(lái)優(yōu)化車(chē)輛路徑，將蟻群算法與基于聚類(lèi)算法相結(jié)合，進(jìn)一步提高優(yōu)化結(jié)果。文獻(xiàn)[10]通過(guò)多處修改遺傳算法后，將算法用于求解動(dòng)態(tài)路徑問(wèn)題，求解優(yōu)于之前很多同類(lèi)求解動(dòng)態(tài)路徑優(yōu)化算法。文獻(xiàn)[11]設(shè)計(jì)一種基于蟻群優(yōu)化和動(dòng)態(tài)平臺(tái)點(diǎn)播的優(yōu)化算法，該算法在路徑構(gòu)建時(shí)能有效反應(yīng)車(chē)輛行駛環(huán)境的變化。文獻(xiàn)[12]求解與車(chē)輛隱私位置相關(guān)的動(dòng)態(tài)路徑問(wèn)題，對(duì)車(chē)輛增加情況進(jìn)行集約計(jì)算，可以有效避免任何類(lèi)型的交通擁堵。

以上研究動(dòng)態(tài)路徑優(yōu)化的過(guò)程中尚沒(méi)有考慮實(shí)時(shí)動(dòng)態(tài)路徑道路因素對(duì)路徑優(yōu)化的影響問(wèn)題，使得路徑優(yōu)化結(jié)果的客觀性、針對(duì)性沒(méi)有與實(shí)際路徑情況緊密結(jié)合，優(yōu)化得到路徑的準(zhǔn)確性、實(shí)用性仍需改進(jìn)。且在動(dòng)態(tài)路徑優(yōu)化后，對(duì)于車(chē)輛旅行時(shí)間窗硬要求方面，只是給出優(yōu)化路徑，沒(méi)能給出最短抵達(dá)目的地時(shí)間路徑，一方面影響了服務(wù)質(zhì)量的時(shí)效，另一方面也增大了燃料油耗，沒(méi)能很好地解決運(yùn)輸時(shí)間硬要求和資源節(jié)約問(wèn)題。

本文用多目標(biāo)蟻群算法求解動(dòng)態(tài)車(chē)輛路徑問(wèn)題。在考慮車(chē)輛行程約束條件下，以動(dòng)態(tài)路徑優(yōu)化為對(duì)象，設(shè)計(jì)了改進(jìn)的多目標(biāo)蟻群算法，在螞蟻尋徑過(guò)程中添加了貪婪搜索規(guī)則和禁忌表，加快了搜索速度，進(jìn)行多目標(biāo)局部搜索，改進(jìn)螞蟻生成的解集，防止陷入局部最優(yōu)或遺漏一些帕累托解。與傳統(tǒng)蟻群算法和多目標(biāo)粒子群算法求解相同動(dòng)態(tài)路徑問(wèn)題的解進(jìn)行比較，與三種最新優(yōu)化算法(改進(jìn)灰狼優(yōu)化算法、改進(jìn)細(xì)菌菌落優(yōu)化算法和鼠疫傳染病優(yōu)化算法)在不同條件下求解動(dòng)態(tài)路徑問(wèn)題的旅行時(shí)間上進(jìn)行對(duì)比，更全面分析改進(jìn)多目標(biāo)蟻群算法的求解性能，更細(xì)致掌握改進(jìn)多目標(biāo)蟻群算法的優(yōu)劣。將動(dòng)態(tài)路徑道路因素適應(yīng)度函數(shù)引入目標(biāo)函數(shù)當(dāng)中，較好地解決了動(dòng)態(tài)路徑優(yōu)化求解中優(yōu)化路徑與實(shí)際道路情況結(jié)合不緊密的問(wèn)題，使優(yōu)化路徑實(shí)用性增強(qiáng)，同時(shí)解決了優(yōu)化路徑旅行時(shí)間縮短的進(jìn)一步要求，一方面提高了運(yùn)輸服務(wù)的時(shí)間質(zhì)量，另一方面也節(jié)約了油料資源，較好地實(shí)現(xiàn)了運(yùn)輸時(shí)間硬要求和資源節(jié)約目標(biāo)。

1 影響動(dòng)態(tài)路徑的道路因素

車(chē)輛在行駛中能采集不同道路信息，其中不同道路因素對(duì)動(dòng)態(tài)路徑優(yōu)化問(wèn)題會(huì)產(chǎn)生不同影響，從道路通行能力影響因素角度考慮，選擇了下面三種道路影響因素。

道路質(zhì)量A：道路質(zhì)量取決于不同因素，如坑洞、車(chē)道數(shù)等，將此作為一個(gè)重要矩陣，用于計(jì)算路徑優(yōu)化問(wèn)題。

道路長(zhǎng)度B：多重長(zhǎng)度在兩個(gè)道路連接點(diǎn)間是同時(shí)存在的。選擇道路時(shí)不僅要考慮道路質(zhì)量最高，還要考慮路徑最短。

道路擁堵C：有些道路比其他道路要擁堵。因?yàn)樽顑?yōu)路徑的形式可能多樣化，有時(shí)長(zhǎng)但不擁堵的路徑會(huì)比短而擁堵的路徑更好，因此道路擁堵情況也需要重點(diǎn)考慮。

這里定義一個(gè)數(shù)組,用來(lái)代表網(wǎng)絡(luò)中的道路長(zhǎng)短、擁堵情況和質(zhì)量因素。用適應(yīng)度函數(shù)計(jì)算在特殊出發(fā)點(diǎn)和終點(diǎn)間的最優(yōu)路徑，適應(yīng)度函數(shù)表示如下：

(1)

式中：n是度量數(shù)，Cixy定義為從節(jié)點(diǎn)x到節(jié)點(diǎn)y的道路要素的第i個(gè)矩陣值。當(dāng)函數(shù)D值越小，則道路通行能力越大，路徑越優(yōu)；相反，函數(shù)D值越大，則道路通行能力越弱，路徑越差。

2 改進(jìn)的多目標(biāo)蟻群優(yōu)化算法

2.1 改進(jìn)算法步驟

構(gòu)造一種具有貪婪轉(zhuǎn)移準(zhǔn)則的多目標(biāo)蟻群算法MT-ACO，對(duì)產(chǎn)生的解進(jìn)行多目標(biāo)迭代搜索，進(jìn)一步優(yōu)化替換帕累托解集和目標(biāo)函數(shù)值。具體步驟如算法1所示。

算法1MT-ACO

初始化信息素矩陣T；

令全局帕累托解集Q為空集φ；

令目標(biāo)函數(shù)值矩陣F1=[-∞,+∞];

當(dāng)?shù)螖?shù)IT≠max_IT進(jìn)行循環(huán)1：

令QIT為空集φ；

令FIT=[∞,∞]；

令x=1 ton，進(jìn)行循環(huán)2：每只螞蟻依次尋覓其路徑，n為螞蟻數(shù)；

采用貪婪搜索辦法尋覓路徑Aij(詳見(jiàn)2.2節(jié))；

對(duì)路徑Aij進(jìn)一步進(jìn)行多目標(biāo)迭代搜索優(yōu)化，生成新解Qo；(詳見(jiàn)第2.3節(jié))

更新局部信息素(I,Qo)；

如果FQo>FIT，則FIT=FQo，QIT=Qo；

如果FQo

令FIT=(FIT,FQo)，擴(kuò)充函數(shù)值矩陣；

令QIT=QIT∪Qo；

循環(huán)2結(jié)束；

更新全局信息素(I,Q,QIT)；(詳見(jiàn)第2.4節(jié))

循環(huán)1結(jié)束；

返回Q、F1兩個(gè)值。

2.2 螞蟻尋徑原則

迭代過(guò)程中，螞蟻在走過(guò)的路徑上會(huì)留下信息素。假設(shè)信息素初始濃度為T(mén)ij0=1/Dij，令Tijk代表第k次迭代中弧(i,j)的信息素濃度，螞蟻x在運(yùn)動(dòng)中根據(jù)路徑信息素濃度和效用函數(shù)(φij)α(φij)β選擇下一步前往的節(jié)點(diǎn)，當(dāng)螞蟻x在節(jié)點(diǎn)i時(shí)，通過(guò)式(6)式(7)的尋徑原則轉(zhuǎn)移到節(jié)點(diǎn)j，Pxij表示螞蟻x由節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率。其中B1為均勻分布在[0,1]上的隨機(jī)數(shù)，B1值可預(yù)先設(shè)定。當(dāng)B≤B1時(shí)，螞蟻轉(zhuǎn)移到使效用函數(shù)Tijk(φij)α(φij)β值最大的節(jié)點(diǎn)j，否則按式(8)進(jìn)行選擇轉(zhuǎn)移到節(jié)點(diǎn)j，B1越大說(shuō)明螞蟻貪婪概率越大，Cxik表示螞蟻x在第k次迭代中達(dá)到節(jié)點(diǎn)i時(shí)未訪問(wèn)節(jié)點(diǎn)的集合。

(2)

(3)

(4)

(5)

式中：φij為節(jié)點(diǎn)i和節(jié)點(diǎn)j在同一條路徑與不同路徑距離的差值與節(jié)點(diǎn)i和節(jié)點(diǎn)j間距離的比值，φij為節(jié)點(diǎn)i和節(jié)點(diǎn)j在同一路徑上額外需要的載重容量的倒數(shù)。φij、φij和尋徑規(guī)則體現(xiàn)了螞蟻服務(wù)需求差最小客戶時(shí)，偏好距離最短的貪婪性。參數(shù)α和β代表φij和φij對(duì)轉(zhuǎn)移概率的影響因子。每只螞蟻從中心節(jié)點(diǎn)出發(fā)，根據(jù)式(2)-式(3)選擇下一個(gè)節(jié)點(diǎn)，生成路徑，當(dāng)Cxik=φ時(shí)，螞蟻返回中心節(jié)點(diǎn)，并再次從中心節(jié)點(diǎn)出發(fā)，開(kāi)始新的尋徑，直到所有節(jié)點(diǎn)都被訪問(wèn)過(guò)。

螞蟻尋徑過(guò)程中，按尋徑規(guī)則轉(zhuǎn)移到下一個(gè)節(jié)點(diǎn)，到達(dá)該節(jié)點(diǎn)后，對(duì)其載重容量和距離約束進(jìn)行判斷，如果達(dá)到最大行駛距離，則螞蟻回到中心節(jié)點(diǎn);如果超出載重容量，則將該節(jié)點(diǎn)從未訪問(wèn)的節(jié)點(diǎn)中刪除，在未訪問(wèn)節(jié)點(diǎn)集合中重新搜索下一個(gè)節(jié)點(diǎn)，直到找到能訪問(wèn)的節(jié)點(diǎn)，或者所有未訪問(wèn)點(diǎn)均被禁忌則回到中心節(jié)點(diǎn)。

螞蟻尋徑過(guò)程如算法2所示。

算法2 螞蟻尋徑過(guò)程

初始化：中心節(jié)點(diǎn)A0=1，路徑R=[Ai]，Ai為當(dāng)前節(jié)點(diǎn)，未訪問(wèn)節(jié)點(diǎn)U，每條路徑長(zhǎng)度RD，禁忌表tabu=?；

當(dāng)U=?時(shí)，進(jìn)行循環(huán)：

按尋徑準(zhǔn)則選擇下一個(gè)節(jié)點(diǎn)N；

令當(dāng)前巡回長(zhǎng)度tD=0，Ra=[R,N]；

令Ra中最后一次到達(dá)中心節(jié)點(diǎn)后訪問(wèn)的節(jié)點(diǎn)為當(dāng)前巡回Y；

計(jì)算Y連接弧上的車(chē)輛載重量Zc和當(dāng)前巡回長(zhǎng)度tD；

如果(1)max(L)≤Z，即容量未超出；

如果(2)tD+D(N,1)≤L，即從下一點(diǎn)回中心節(jié)點(diǎn)的距離沒(méi)有超出距離約束；

則R=Ra；Ai=N；U=(U,N)∪tabu；

tabu=[]；即釋放禁忌表；

否則，距離超出，則在訪問(wèn)節(jié)點(diǎn)N前返回中心節(jié)點(diǎn)；

螞蟻回到中心節(jié)點(diǎn)，生成巡回路徑(R,tD,RD)=[RD,tD]；

開(kāi)始新的巡回，令新巡回長(zhǎng)度tD=0，Ai=1；

如果(2)結(jié)束；

否則，容量超出時(shí)，將下一個(gè)節(jié)點(diǎn)N添加到當(dāng)前節(jié)點(diǎn)Ai不能訪問(wèn)的禁忌表中；

tabu=[tabu,N]；

U=U/N；

如果(3)U=?且tabu=?，當(dāng)前節(jié)點(diǎn)到未訪問(wèn)節(jié)點(diǎn)間均超出容量；

螞蟻回到中心節(jié)點(diǎn)，記錄生成的路徑信息(R,tD,RD)=[RD,tD]；

開(kāi)始新的巡回，令新巡回長(zhǎng)度tD=0，Ai=1；

U=tabu，tabu=[]，釋放被禁忌的節(jié)點(diǎn)；

如果(3)結(jié)束；

如果(1)結(jié)束；

大循環(huán)結(jié)束；

記錄完成路徑Rw，并根據(jù)RD計(jì)算目標(biāo)函數(shù)。

2.3 多目標(biāo)局部搜索

螞蟻找到一條路徑后，采用局部搜索法來(lái)進(jìn)一步優(yōu)化路徑。這里采用兩種Swap交換法：交換一條路徑上任意兩個(gè)節(jié)點(diǎn)，交換兩條不同路徑上任意兩個(gè)節(jié)點(diǎn)。因?yàn)楣?jié)點(diǎn)需求不同，交換節(jié)點(diǎn)后就可能出現(xiàn)不可行解或者原解更優(yōu)的情況，因此進(jìn)行交換后，需要對(duì)新生成路徑進(jìn)行驗(yàn)證，如果該解更優(yōu)，則擇優(yōu)保留，如果生成新的帕累托解，則生成新的解集K。

2.4 信息素濃度更新準(zhǔn)則

螞蟻在找到一個(gè)解后，按下式更新路徑上的信息素濃度:

(6)

式中:ρ為信息素?fù)]發(fā)程度，Q為信息素強(qiáng)度，Lgb為當(dāng)前最優(yōu)解，取Q為100。

每次迭代完成，從所有螞蟻找到的解中，將所有帕累托解作為迭代最優(yōu)帕累托解集，將迭代最優(yōu)帕累托解集與全局最優(yōu)帕累托解集進(jìn)行對(duì)比，保留并更新最優(yōu)帕累托解集。

2.5 目標(biāo)函數(shù)

目標(biāo)函數(shù)設(shè)定為：

S=S1+S2

3 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)配置是由兩個(gè)開(kāi)源軟件NS2和SUMO共同組成。應(yīng)用兩個(gè)時(shí)間窗，長(zhǎng)時(shí)間窗tl和短時(shí)間窗ts，分別為120 s和60 s。在每個(gè)短時(shí)間間隔后對(duì)數(shù)據(jù)進(jìn)行初始化，在每個(gè)長(zhǎng)時(shí)間間隔后進(jìn)行路徑優(yōu)化計(jì)算。所以，任何路徑重構(gòu)都是在長(zhǎng)時(shí)間間隔后才完成的。實(shí)驗(yàn)初始化流程如圖1所示，相關(guān)實(shí)驗(yàn)參數(shù)如表1所示。

圖1 實(shí)驗(yàn)初始化流程圖

參數(shù)參數(shù)值技術(shù)IEEE80211.P頻帶15 MHz～2.7 GHz衰變對(duì)數(shù)距離能量大小10 dBm長(zhǎng)時(shí)間窗tl120 s短時(shí)間窗ts60 sTSD、TSM大小100字節(jié)仿真周期3 600 s

地點(diǎn)選擇了西安市市中心，應(yīng)用ArcGIS10.3軟件生成道路網(wǎng)絡(luò)圖，如圖2、圖3所示。每條邊與包含道路元素的節(jié)點(diǎn)的端點(diǎn)相對(duì)應(yīng)，主要考慮以市中心鐘樓為圓點(diǎn)，半徑3～5 km范圍內(nèi)500組不同目標(biāo)點(diǎn)道路的行駛，車(chē)速為40～60 km/h，車(chē)輛載重為5 t，車(chē)型為普通卡車(chē)。

圖2 西安市道路網(wǎng)絡(luò)圖

圖3 局部道路詳圖

4 實(shí)驗(yàn)部分

4.1 算法與傳統(tǒng)優(yōu)化算法對(duì)比

仿真中可知，在求解動(dòng)態(tài)路徑優(yōu)化問(wèn)題時(shí)，多目標(biāo)粒子群算法求解結(jié)果優(yōu)于蟻群算法，改進(jìn)的多目標(biāo)蟻群算法求得的解優(yōu)于多目標(biāo)粒子群算法，其車(chē)輛平均旅行時(shí)間更短。在時(shí)間窗要求下隨機(jī)選擇路徑就可能造成交通擁堵。然而，當(dāng)?shù)缆窊矶驴梢杂靡恍┨厥獾牡缆芬蛩貋?lái)估計(jì)時(shí)，就可以用特定算法來(lái)估計(jì)動(dòng)態(tài)路徑，為決策者提供一條更優(yōu)的路徑。在優(yōu)化過(guò)的路徑上行駛，車(chē)輛能更好地避免道路擁堵，更早抵達(dá)目的地。

不同迭代次數(shù)后蟻群算法、多目標(biāo)粒子群算法和改進(jìn)的多目標(biāo)蟻群算法優(yōu)化后的旅行時(shí)間對(duì)比情況如圖4所示。由圖4可知，蟻群算法的平均旅行時(shí)間最長(zhǎng)，基本都在350 s以上，最長(zhǎng)在500 s左右，多目標(biāo)粒子群算法則相對(duì)短一些，最短在285 s，改進(jìn)的多目標(biāo)蟻群算法平均旅行時(shí)間最短，最長(zhǎng)也在400 s以內(nèi)，平均旅行時(shí)間比多目標(biāo)粒子群算法短13.2%，比蟻群算法短20%。當(dāng)城市中車(chē)輛數(shù)量增加時(shí)，平均旅行時(shí)間也將因?yàn)榈缆窊矶潞蛙?chē)速的變化而逐漸增加，三種算法在不同車(chē)輛數(shù)量時(shí)旅行時(shí)間求解情況如圖5所示。蟻群算法在車(chē)輛數(shù)量相同時(shí)，平均旅行時(shí)間要比多目標(biāo)粒子群算法長(zhǎng)9.9%，而改進(jìn)的多目標(biāo)蟻群算法在車(chē)輛數(shù)量相同時(shí)，平均旅行時(shí)間比多目標(biāo)粒子群算法短11.4%。蟻群算法在優(yōu)化車(chē)輛路徑時(shí)，收斂比多目標(biāo)粒子群算法要快，改進(jìn)的多目標(biāo)蟻群算法則比蟻群算法收斂得更快些。因此，用改進(jìn)的多目標(biāo)蟻群算法優(yōu)化車(chē)輛動(dòng)態(tài)路徑時(shí)，會(huì)更快地獲取路徑更新信息，與之前路徑信息形成對(duì)比。

圖4 不同迭代次數(shù)條件下三種算法求解的旅行時(shí)間對(duì)比

圖5 不同車(chē)輛數(shù)量條件下三種算法求解旅行時(shí)間對(duì)比

計(jì)算復(fù)雜度對(duì)比情況如圖6所示。由圖可知，同樣在3 600 s的仿真周期內(nèi)，蟻群算法的求解時(shí)間在2 000 s左右，多目標(biāo)粒子群算法在2 103 s左右，而改進(jìn)的多目標(biāo)蟻群算法在2 187 s左右，也就是在計(jì)算復(fù)雜度上比蟻群算法增加8.9%，比多目標(biāo)粒子群算法增加3.5%，增加幅度較小，且增加量在可接受范圍之內(nèi)。

圖6 三種算法計(jì)算復(fù)雜度對(duì)比

4.2 算法與三種最新優(yōu)化算法對(duì)比

與改進(jìn)灰狼優(yōu)化算法[14]、改進(jìn)細(xì)菌菌落優(yōu)化算法[15]和鼠疫傳染病優(yōu)化算法[16]三種最新優(yōu)化算法在不同條件下對(duì)動(dòng)態(tài)路徑問(wèn)題求解旅行時(shí)間進(jìn)行對(duì)比，分析本文改進(jìn)優(yōu)化算法優(yōu)劣。

4.2.1與改進(jìn)灰狼優(yōu)化算法(GWO)對(duì)比

在相同迭代次數(shù)條件下，改進(jìn)多目標(biāo)蟻群算法求解的路徑平均旅行時(shí)間比改進(jìn)灰狼優(yōu)化算法要短3.33%，具體如圖7所示。由圖7可知，兩者最優(yōu)解基本相似，收斂速度上多目標(biāo)蟻群算法要快一些。

圖7 不同迭代次數(shù)條件下求解旅行時(shí)間與GWO優(yōu)化算法對(duì)比

在不同車(chē)輛數(shù)量條件下，改進(jìn)多目標(biāo)蟻群算法求解的路徑平均旅行時(shí)間比改進(jìn)灰狼優(yōu)化算法要短4.82%，具體如圖8所示。由圖8可知，在車(chē)輛數(shù)量小于250輛時(shí)，改進(jìn)灰狼優(yōu)化算法總體與改進(jìn)多目標(biāo)蟻群算法求解的旅行時(shí)間很接近，尤其當(dāng)車(chē)輛數(shù)量在200～250輛之間，求解旅行時(shí)間幾乎差不多，但當(dāng)車(chē)輛數(shù)量較大時(shí)，多目標(biāo)蟻群算法的優(yōu)勢(shì)得到凸顯，比GWO算法求解旅行時(shí)間要短5%以上。

圖8 不同車(chē)輛數(shù)量條件下求解旅行時(shí)間與GWO優(yōu)化算法對(duì)比

4.2.2與改進(jìn)細(xì)菌菌落優(yōu)化算法(BCO)對(duì)比

在相同迭代次數(shù)條件下，改進(jìn)多目標(biāo)蟻群算法求解的路徑平均旅行時(shí)間比改進(jìn)細(xì)菌菌落優(yōu)化算法要短5.21%，具體如圖9所示。由圖9可知，多目標(biāo)蟻群算法最優(yōu)解要比BCO算法好一些，但BCO算法收斂速度較快些。

圖9 不同迭代次數(shù)條件下求解旅行時(shí)間與BCO優(yōu)化算法對(duì)比

在不同車(chē)輛數(shù)量條件下，改進(jìn)多目標(biāo)蟻群算法求解的路徑平均旅行時(shí)間比改進(jìn)細(xì)菌菌落優(yōu)化算法要短5.36%，具體如圖10所示。由圖10可知，當(dāng)車(chē)輛數(shù)量小于150輛時(shí)，BCO算法與改進(jìn)多目標(biāo)蟻群算法在求解旅行時(shí)間上幾乎一致，在車(chē)輛數(shù)量達(dá)到中等規(guī)模(150～250輛之間)時(shí)，多目標(biāo)蟻群算法的求解旅行時(shí)間相對(duì)短的優(yōu)勢(shì)就逐漸凸顯，當(dāng)車(chē)輛數(shù)量較大時(shí)，BCO算法與多目標(biāo)蟻群算法的時(shí)間差距進(jìn)一步增大，旅行時(shí)間要長(zhǎng)6%左右。

圖10 不同車(chē)輛數(shù)量條件下求解旅行時(shí)間與BCO優(yōu)化算法對(duì)比

4.2.3與鼠疫傳染病優(yōu)化算法(PIDO)對(duì)比

在相同迭代次數(shù)條件下，改進(jìn)多目標(biāo)蟻群算法求解的路徑平均旅行時(shí)間比鼠疫傳染病優(yōu)化算法要短5.63%，具體如圖11所示。由圖11可知，多目標(biāo)蟻群算法求解旅行時(shí)間比PIDO算法要總體短得多，且收斂速度較快。

圖11 不同迭代次數(shù)條件下求解旅行時(shí)間與PIDO優(yōu)化算法對(duì)比

在不同車(chē)輛數(shù)量條件下，改進(jìn)多目標(biāo)蟻群算法求解的路徑平均旅行時(shí)間比鼠疫傳染病優(yōu)化算法要短6.21%，具體如圖12所示。由圖12可知，總體來(lái)說(shuō)PIDO算法與多目標(biāo)蟻群算法在求解旅行時(shí)間上保持著6%左右的時(shí)間差距，但當(dāng)車(chē)輛數(shù)量達(dá)到250輛左右，其求解旅行時(shí)間非常接近。

圖12 不同車(chē)輛數(shù)量條件下求解旅行時(shí)間與PIDO優(yōu)化算法對(duì)比

5 結(jié) 語(yǔ)

改進(jìn)的多目標(biāo)蟻群優(yōu)化算法考慮了行車(chē)距離約束，引入了貪婪搜索與禁忌表，應(yīng)用多目標(biāo)搜索改進(jìn)求解收斂。算法與傳統(tǒng)優(yōu)化算法相比，雖然在計(jì)算復(fù)雜度上有小幅度增加，但其求解動(dòng)態(tài)路徑優(yōu)化時(shí)，路徑的旅行時(shí)間在同等迭代次數(shù)時(shí)更短，平均有13%的浮動(dòng)差，在同樣車(chē)輛數(shù)量條件下旅行時(shí)間也更短，平均短10%。與三種最新優(yōu)化算法(GWO、BCO、PIDO)對(duì)比，在不同迭代條件下求解旅行時(shí)間時(shí)，雖然收斂速度存在差異，但平均分別縮短了3.33%、5.21%和5.63%。在不同車(chē)輛數(shù)量條件下求解旅行時(shí)間時(shí)，多目標(biāo)蟻群算法求解的平均旅行時(shí)間要比三種最新優(yōu)化算法分別短4.82%、5.36%和6.21%。說(shuō)明其生成的路徑更優(yōu)，能更好地避免道路擁堵、滿足運(yùn)輸時(shí)間硬要求，實(shí)現(xiàn)燃料節(jié)約，路徑實(shí)用性更強(qiáng)。另外，改進(jìn)的多目標(biāo)蟻群算法的可變性和應(yīng)用性也非常強(qiáng)，在其他組合優(yōu)化問(wèn)題中也可進(jìn)一步探索，是非常值得深入研究的優(yōu)化領(lǐng)域，為未來(lái)復(fù)雜環(huán)境下動(dòng)態(tài)路徑問(wèn)題的研究提供參考。