一種求解交通網(wǎng)絡(luò)中最短路徑問題的人工蜂群算法

王 玉, 申鉉京, 周昱洲， 林鴻斌

(1. 吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長春 130012； 2. 吉林大學(xué) 軟件學(xué)院， 長春 130012)

隨著智能交通系統(tǒng)的應(yīng)用越來越廣泛, 車輛路徑規(guī)劃作為智能交通系統(tǒng)的一項(xiàng)基本功能, 因而得到越來越多的關(guān)注. 目前, 對于靜態(tài)交通網(wǎng)絡(luò)的車輛路徑規(guī)劃研究已有很多結(jié)果： 張波良等[1]對靜態(tài)路網(wǎng)中的各算法進(jìn)行了比較; TNR算法[2]用表查找完全替代了Dijkstra搜索, 使其加速比達(dá)100多萬; 文獻(xiàn)[3]進(jìn)一步將TNR算法與邊標(biāo)記法相結(jié)合, 加速比提升至300多萬. 但實(shí)際交通網(wǎng)絡(luò)總在不斷變化, 而忽視路網(wǎng)環(huán)境的變化很可能使車輛陷入交通擁擠的狀態(tài)中, 因此, 在靜態(tài)交通網(wǎng)絡(luò)中獲取的最短路徑通常不能很好地滿足人們出行的需求, 動(dòng)態(tài)網(wǎng)絡(luò)下的路徑規(guī)劃更具有實(shí)際意義. 交通路網(wǎng)中各條道路的通行時(shí)間是不斷變化的, 即滿足網(wǎng)絡(luò)中弧的行走時(shí)間是時(shí)間的函數(shù)這一特性. 故交通網(wǎng)絡(luò)是一個(gè)時(shí)間依賴網(wǎng)絡(luò)(簡稱TDN網(wǎng)絡(luò)). 譚國真等[4]將TDN網(wǎng)絡(luò)分為先進(jìn)先出(FIFO)型與非FIFO型, 并證明在FIFO型網(wǎng)絡(luò)中可采用Dijkstra算法求解, 而非FIFO網(wǎng)絡(luò)則不可行; 王海梅[5]通過對路網(wǎng)進(jìn)行分析認(rèn)為, 當(dāng)路徑尋優(yōu)的對象為機(jī)動(dòng)車輛時(shí), 道路交通網(wǎng)絡(luò)具有FIFO網(wǎng)絡(luò)的特性.

本文針對在TDN網(wǎng)絡(luò)中求解最短路徑問題, 提出一種基于人工蜂群算法的解決方案, 相比于遺傳算法[6], 該算法具有控制參數(shù)少、 易實(shí)現(xiàn)的特點(diǎn). 同時(shí), 根據(jù)FIFO網(wǎng)絡(luò)的特性對算法中的路徑選擇策略進(jìn)行改進(jìn), 進(jìn)一步提升算法的執(zhí)行效率.

1 問題描述

定義1[7]圖G={V,E,F(t)}稱為時(shí)間依賴網(wǎng)絡(luò)TDN, 其中V={1,2,…,n}為頂點(diǎn)集合,E={(i,j)|i≠j,i,j∈V}為邊集合,F(t)={fi,j|(i,j)∈E}為邊權(quán)函數(shù)的集合,fi,j(t)為時(shí)間t的函數(shù),t∈[a,b],b>a≥0.

定義1中的TDN網(wǎng)絡(luò)是連續(xù)的, 而在研究交通網(wǎng)絡(luò)時(shí), 由于交通網(wǎng)絡(luò)在連續(xù)的一段時(shí)間內(nèi)變化較小, 因此為簡化計(jì)算, 通常將交通網(wǎng)絡(luò)離散化處理. 離散時(shí)間情形下的TDN網(wǎng)絡(luò)模型為

G={V×T,E,F},

其中:T為感興趣的時(shí)間閉區(qū)間[t0,tm],T={t0,t0+Δ,t0+2Δ,…,t0+(M-1)Δ,…,tm},Δ表示一段較短的連續(xù)時(shí)間, 本文設(shè)Δ=5 min;V×T={(i,tj)|i∈V,tj∈T}表示節(jié)點(diǎn)的狀態(tài)空間, 有序?qū)?i,tj)表示節(jié)點(diǎn)的一個(gè)狀態(tài), 節(jié)點(diǎn)i在不同時(shí)間段內(nèi)可能有不同的狀態(tài).

2 人工蜂群算法

人工蜂群(artificial bee colony, ABC)算法[8]是一種基于群智能的全局優(yōu)化算法, 其通過模仿蜂群尋找食物的過程解決問題. 該算法包括3類核心元素： 食物源、 雇傭蜂和非雇傭蜂; 以及兩種基本操作： 招募蜜蜂和放棄食物源. 其中: 食物源表示待解決問題的可能解； 雇傭蜂在食物源附近進(jìn)行領(lǐng)域搜索, 并通過“8”字舞的方式分享食物源信息; 非雇傭蜂可分為觀察蜂和搜索蜂, 觀察蜂在獲取雇傭蜂的信息后根據(jù)食物源的質(zhì)量選擇是否前往, 搜索蜂尋找新的有價(jià)值的食物源.

人工蜂群算法是為解決函數(shù)優(yōu)化問題而提出的, 目前在多領(lǐng)域廣泛應(yīng)用, 本文對該算法的編碼方式以及種群生成方式進(jìn)行離散化處理, 以適應(yīng)最短路徑問題.

2.1 編碼策略

因?yàn)檐囕v路徑規(guī)劃屬于離散問題, 所以本文采用自然數(shù)編碼的方式, 即采用自然數(shù)對路網(wǎng)中的每條邊進(jìn)行編號(hào), 而一條路徑是由這些編號(hào)組成的隊(duì)列, 隊(duì)列中的編號(hào)允許重復(fù). 由于實(shí)際應(yīng)用中因?yàn)榻煌ㄒ?guī)則的限制, 因此最優(yōu)路徑中可能會(huì)出現(xiàn)環(huán)路.

2.2 路徑選擇策略

人工蜂群算法的收斂依賴于一個(gè)具有多樣性的種群, 本文用每條從起始節(jié)點(diǎn)至目的節(jié)點(diǎn)的可行路徑表示種群中的每個(gè)個(gè)體. 其中路徑的搜索過程為： 從起始節(jié)點(diǎn)開始, 按照路徑選擇策略選取一個(gè)鄰接節(jié)點(diǎn)作為下一個(gè)節(jié)點(diǎn), 持續(xù)此操作, 直至目的節(jié)點(diǎn). 因此, 路徑選擇策略直接影響路徑選擇的優(yōu)劣, 進(jìn)而影響種群的收斂速度與效果.

文獻(xiàn)[9]在蟻群選擇路徑時(shí)加入了方向引導(dǎo), 該方法可有效縮小搜索空間. 在真實(shí)路網(wǎng)中由于地形和交通規(guī)則等限制, 并非所有的邊都可以到達(dá)終點(diǎn), 所以在有些邊上可能會(huì)出現(xiàn)無下一條路可選的情形. 為防止下次路徑搜索時(shí)再進(jìn)入該邊, 本文加入一個(gè)禁忌表用于記錄該類邊. 路徑搜索策略(為敘述方便， 記為路徑選擇策略1)如下：

為方便描述, 設(shè)當(dāng)前路徑的終點(diǎn)為j.

步驟1) 搜索所有與當(dāng)前路徑終點(diǎn)相連接的邊, 加入邊隊(duì)列;

步驟2) 從候選隊(duì)列選取一條邊ei, 并將其出隊(duì);

步驟3) 判斷邊ei是否可以駛離當(dāng)前路徑終點(diǎn), 如果可以則轉(zhuǎn)步驟4); 否則轉(zhuǎn)步驟7);

步驟4) 檢查邊ei是否存在于禁忌表T中, 如果不存在則轉(zhuǎn)步驟5)； 否則轉(zhuǎn)步驟7)；

步驟5) 檢查邊ei是否違反轉(zhuǎn)彎限制, 如果不違反則轉(zhuǎn)步驟6)； 否則轉(zhuǎn)步驟7)；

步驟6) 做邊ei起點(diǎn)到終點(diǎn)的向量vi, 計(jì)算vi與vj的夾角, 將邊ei加入候選列表, 轉(zhuǎn)步驟7);

步驟7) 判斷邊隊(duì)列是否為空, 如果為空則轉(zhuǎn)步驟8)； 否則轉(zhuǎn)步驟2);

步驟8) 判斷候選列表是否為空, 如果為空則將邊ei加入禁忌表； 否則轉(zhuǎn)步驟9)；

步驟9) 計(jì)算候選列表中每條邊的選擇概率；

步驟10) 采用輪盤賭策略在候選列表中選擇一條邊加入路徑, 并計(jì)算加入后的路徑成本.

2.3 領(lǐng)域搜索策略

一條路徑的領(lǐng)域搜索策略為： 在路徑的第2個(gè)節(jié)點(diǎn)至第(n-1)個(gè)節(jié)點(diǎn)中隨機(jī)選擇一個(gè)節(jié)點(diǎn), 并刪除此后全部節(jié)點(diǎn); 從該節(jié)點(diǎn)開始, 按照路徑選擇策略重新搜索一條能到達(dá)目的節(jié)點(diǎn)的路徑.

2.4 人工蜂群算法執(zhí)行步驟

1) 初始化參數(shù), 產(chǎn)生初始食物源;

2) 進(jìn)行迭代判斷, 若不滿足結(jié)束條件則轉(zhuǎn)步驟3)； 否則轉(zhuǎn)步驟7)；

3) 雇傭蜂到蜜源附近進(jìn)行領(lǐng)域搜索發(fā)現(xiàn)新的食物源, 若新食物源優(yōu)于原食物源, 則用新食物源替代原食物源, 否則保持原食物源;

4) 跟隨蜂根據(jù)雇傭蜂分享的信息按食物源的質(zhì)量進(jìn)行概率選擇食物源, 并在食物源附近進(jìn)行領(lǐng)域搜索;

5) 判斷雇傭蜂領(lǐng)域搜索次數(shù), 當(dāng)達(dá)到控制參數(shù)閾值時(shí), 如仍未找到更優(yōu)的食物源, 則放棄其對應(yīng)的食物源, 將雇傭蜂轉(zhuǎn)化為偵查蜂尋找下一個(gè)新的食物源；

6) 記錄當(dāng)前最優(yōu)解；

7) 輸出最優(yōu)解.

3 改進(jìn)人工蜂群算法

3.1 算法可行性

人工蜂群算法可適用于FIFO網(wǎng)絡(luò)和非FIFO網(wǎng)絡(luò), 圖1為采用路徑選擇策略1生成的一條路徑. 由圖1可見, 當(dāng)取路段長度作為路網(wǎng)中邊的權(quán)值時(shí)(即在靜態(tài)路網(wǎng)中), 在該靜態(tài)路網(wǎng)中存在若干條更短的路徑(圖1中紅色路段), 在替換原路徑中部分子路徑后一定可以使原路徑的距離更短.

圖1 采用路徑選擇策略1生成的一條路徑Fig.1 Path generated by path selection strategy 1

定理1[10]如果網(wǎng)絡(luò)中每個(gè)圈的長度為非負(fù), 則網(wǎng)絡(luò)中每條路徑的長度不小于相應(yīng)的最短路徑長度, 且每條最短路徑的子路徑也是最短路徑.

定理2[10]在時(shí)變FIFO網(wǎng)絡(luò)中, 如果tS時(shí)刻從節(jié)點(diǎn)nS出發(fā)到達(dá)節(jié)點(diǎn)nD的最短時(shí)間路徑為

SP(nS,nD,tS)={(nS,tS),(n1,t1),…,(ni,ti),(ni+1,ti+1),…,(nj,tj),(nD,tD)},

則最短路徑SP(nS,nD,tS)的子路徑{(nS,tS),(n1,t1),…,(ni,ti)}和{(ni,ti),(ni+1,ti+1),…,(nj,tj),(nD,tD)}也一定是最短時(shí)間路徑, 其中ni是最短時(shí)間路徑上的任一中間節(jié)點(diǎn).

對于TDN網(wǎng)絡(luò), 若使用更短路徑替代原路徑中部分子路徑的方法也成立, 則蜂群算法中食物源的整體質(zhì)量將會(huì)提升, 進(jìn)而可通過減少食物源的數(shù)量以及算法迭代次數(shù)提升人工蜂群算法的運(yùn)行速度. 由定理1和定理2可知, 該方法對于FIFO網(wǎng)絡(luò)成立, 即在FIFO網(wǎng)絡(luò)中, 當(dāng)原路徑中某一段被另一段通行時(shí)間更短的子路徑替代時(shí), 原路徑的通行時(shí)間也會(huì)縮短.

3.2 改進(jìn)路徑選擇策略

在路網(wǎng)中能替代原路徑的時(shí)間更短子路徑可以有多種, 但實(shí)際上在搜索一條到達(dá)目的節(jié)點(diǎn)的路徑過程中, 每向路徑中加入一條路段之前都會(huì)遍歷到與該路段相鄰的路段, 而這些相鄰路段中可能存在更短子路徑[11-13]. 圖2～圖4分別為在路徑搜索時(shí)可能遇到的3種情形. 由圖2可見, 當(dāng)邊ab加入路徑時(shí)記錄節(jié)點(diǎn)b, 當(dāng)路徑加入邊bf時(shí)檢查節(jié)點(diǎn)b是否有過記錄, 若存在路徑abf能通行, 則用其代替原子路徑abcdebf.

圖2 路徑中存在環(huán)Fig.2 Rings in path

圖3 原路徑中某子路徑可用一條邊替換Fig.3 Subpath in original path can be replaced by an edge

圖4 原路徑中的子路徑可用兩條相鄰的邊替換FIg.4 Subpath in original path can be replaced by two adjacent edges

由圖3可見, 當(dāng)邊bc加入路徑時(shí)記錄候選邊be和節(jié)點(diǎn)e, 當(dāng)路徑加入邊ef時(shí)檢查節(jié)點(diǎn)e是否有過記錄, 若有根據(jù)節(jié)點(diǎn)e找到邊be, 檢查路徑abef能否通行, 如果可以, 則可用其替換路徑abcdef.由圖4可見, 當(dāng)邊bc加入路徑時(shí), 記錄候選邊bg和節(jié)點(diǎn)g, 當(dāng)路徑加入邊ef時(shí), 遍歷駛向節(jié)點(diǎn)e的邊, 若遍歷到邊ge是, 則檢查節(jié)點(diǎn)g是否有過記錄, 若有根據(jù)節(jié)點(diǎn)g找到邊bg, 則檢查路徑abgef能否通行, 如果可以, 則可用其替換路徑abcdef.

針對上述3種情形, 對路線選擇策略1進(jìn)行如下改進(jìn).從候選列表中選一條將要加入路徑的邊e, 對當(dāng)前路徑中最后一條邊的候選節(jié)點(diǎn)j及其候選駛?cè)脒呑鲆韵屡袛啵?/p>

判斷1) 候選節(jié)點(diǎn)j在路徑中是否出現(xiàn)兩次以上, 如果是, 則表明該路徑存在重復(fù)部分, 判斷重復(fù)部分是否可以刪除, 若可以, 則記錄刪除后的路徑通行成本, 并加入候選優(yōu)化方案中.

判斷2) 候選節(jié)點(diǎn)j是否在候選邊中出現(xiàn)過, 若出現(xiàn)過, 則表明可能存在一條更短子路徑, 判斷選擇該子路徑是否違反轉(zhuǎn)彎限制, 如果不違反, 則計(jì)算從該子路徑通行的成本, 并與原路徑通行成本進(jìn)行比較, 如果優(yōu)于原路徑, 則將其加入候選優(yōu)化方案中.

判斷3) 依次遍歷j的候選駛?cè)脒? 判斷候選駛?cè)脒叺钠鹗脊?jié)點(diǎn)是否在候選節(jié)點(diǎn)中出現(xiàn), 若出現(xiàn), 則表明可能存在一條更短子路路徑, 進(jìn)行與判斷2)相同的操作.

當(dāng)以上判斷完成后, 從候選優(yōu)化方案中選擇通行成本最優(yōu)的方案對路徑進(jìn)行修改, 最后將之前選擇的邊e加入路徑.

3.3 附加數(shù)據(jù)結(jié)構(gòu)

圖5 候選節(jié)點(diǎn)記錄表結(jié)構(gòu)Fig.5 Structure of candidate node record table

為完成上述功能, 本文在原路徑基礎(chǔ)上添加一張候選節(jié)點(diǎn)記錄表, 該表采用散列存儲(chǔ)結(jié)構(gòu), 以應(yīng)對大量的查找需求.為描述方便, 本文將一條邊的終點(diǎn)稱為候選節(jié)點(diǎn), 例如圖2中邊ab的候選節(jié)點(diǎn)為b, 圖3中邊be的候選節(jié)點(diǎn)為e.而將以某個(gè)候選節(jié)點(diǎn)為起點(diǎn), 但未加入路徑中的邊稱為候選邊, 例如圖3中的邊be和圖4中的邊bg.將駛?cè)肽硞€(gè)候選節(jié)點(diǎn)但又不屬于路徑上的邊稱為候選駛?cè)脒?候選節(jié)點(diǎn)記錄表結(jié)構(gòu)由記錄索引和候選節(jié)點(diǎn)記錄組成, 其中記錄表索引為候選節(jié)點(diǎn)在路網(wǎng)中的編號(hào).候選節(jié)點(diǎn)記錄表結(jié)構(gòu)如圖5所示.候選節(jié)點(diǎn)信息用于記錄候選節(jié)點(diǎn)是否位于路徑上, 由于節(jié)點(diǎn)在路徑中可能出現(xiàn)多次, 故采用鏈表結(jié)構(gòu)進(jìn)行記錄.候選邊信息用于記錄候選節(jié)點(diǎn)所在的候選邊, 同樣由于候選邊的個(gè)數(shù)不唯一, 所以該信息也采用鏈表記錄.

圖6為某條搜索到的路徑, 其中實(shí)線表示路徑, 虛線表示候選邊.圖6中候選節(jié)點(diǎn)e和g在候選節(jié)點(diǎn)記錄表中的記錄分別如圖7和圖8所示.

圖6 某條搜索到的路徑Fig.6 A found path

圖7 節(jié)點(diǎn)e在候選節(jié)點(diǎn)記錄表中的記錄Fig.7 Record of node e in candidate node record table

圖8 節(jié)點(diǎn)g在候選節(jié)點(diǎn)記錄表中的記錄Fig.8 Record of node g in candidate node record table

為方便在刪除路徑時(shí)對記錄索引表進(jìn)行維護(hù), 對路徑中的每條邊附加一個(gè)候選邊記錄表, 用于存儲(chǔ)候選邊和候選節(jié)點(diǎn), 如圖9所示.圖6中邊05在候選邊記錄表中的記錄如圖10所示.

圖9 候選邊記錄表結(jié)構(gòu)Fig.9 Structure of candidate edge record table

圖10 圖6中邊05在候選邊記錄表中的記錄Fig.10 Record of edge 05 of Fig.6 in candidate edge record table

在增加該數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上對原路徑選擇策略進(jìn)行如下修改：

步驟1) 初始化最優(yōu)路徑成本為原路徑的通行成本;

步驟2) 篩選路徑末端的可通行路徑, 將滿足通行條件的路徑加入當(dāng)前最后一條邊的候選邊記錄表中;

步驟3) 選擇一條將要加入路徑的邊, 并將其從候選邊記錄表中移除;

步驟4) 篩選路徑末端節(jié)點(diǎn)的駛?cè)脒? 并將駛?cè)脒叺钠鹗脊?jié)點(diǎn)ID作為記錄索引在候選節(jié)點(diǎn)記錄表中搜索, 若搜索到記錄則表明路徑可能存在一條更優(yōu)子路徑;

步驟5) 計(jì)算該更優(yōu)路徑的通行成本, 若優(yōu)于最優(yōu)路徑成本, 則將其替換為該更優(yōu)路徑成本, 同時(shí)記錄該更短路徑;

步驟6) 根據(jù)記錄的更短路徑修改原路徑, 同時(shí)修改候選節(jié)點(diǎn)記錄表.

4 實(shí)驗(yàn)對比分析

為驗(yàn)證路徑選擇策略改進(jìn)方案的有效性, 利用ArcEngine 10.0在JAVA編程環(huán)境中進(jìn)行仿真實(shí)現(xiàn). 實(shí)驗(yàn)數(shù)據(jù)采用ArcGIS提供的美國舊金山交通網(wǎng)絡(luò), 該交通網(wǎng)絡(luò)共有108 226條邊, 37 695個(gè)節(jié)點(diǎn), 并使用歷史流量信息構(gòu)建了基于行駛時(shí)間的成本模型. 實(shí)驗(yàn)隨機(jī)選取一對起始點(diǎn)和終點(diǎn), 設(shè)種群規(guī)模為30, 閾值為10, 迭代次數(shù)為60, 分別采用兩種路徑選擇策略各計(jì)算30次, 兩種路徑選擇策略下算法的收斂性對比如圖11所示. 表1列出了一對起始點(diǎn)終止點(diǎn)查找60次的路徑平均實(shí)驗(yàn)結(jié)果.

表1 一對起始點(diǎn)終止點(diǎn)查找60次路徑的平均實(shí)驗(yàn)結(jié)果

圖11 算法改進(jìn)前后的收斂性對比Fig.11 Convergence comparison of algorithms before and after improvement

由圖11和表1可見, 改進(jìn)后算法的路徑選擇策略在同等條件下初始化值和最終收斂值均優(yōu)于改進(jìn)前算法, 在計(jì)算時(shí)間上前者略高于后者. 為證明該改進(jìn)方法具有普遍的適應(yīng)性, 本文又隨機(jī)選取了5對起始點(diǎn)和終點(diǎn)進(jìn)行實(shí)驗(yàn), 結(jié)果列于表2.

由表2可見： 1) 在多組實(shí)驗(yàn)中, 改進(jìn)后的路徑選擇策略表現(xiàn)均優(yōu)于改進(jìn)前的策略, 表明該項(xiàng)改進(jìn)具有普適性； 2) 改進(jìn)后的路徑選擇策略使算法在每次迭代的時(shí)間花費(fèi)上比改進(jìn)前約多50%, 但結(jié)果卻遠(yuǎn)優(yōu)于改進(jìn)前的策略, 甚至前者初始解的質(zhì)量已優(yōu)于后者迭代數(shù)十次后得到的解, 因此該項(xiàng)改進(jìn)可極大減少算法的迭代次數(shù), 從而減少算法的總計(jì)算時(shí)間.

表2 5對起始點(diǎn)終止點(diǎn)分別查找一次路徑的實(shí)驗(yàn)結(jié)果

綜上所述, 動(dòng)態(tài)路網(wǎng)是典型的時(shí)間依賴網(wǎng)絡(luò), 該網(wǎng)絡(luò)中的最短路徑規(guī)劃問題具有應(yīng)用價(jià)值. 本文利用人工蜂群算法解決時(shí)間依賴網(wǎng)絡(luò)中的最短路徑問題, 針對動(dòng)態(tài)路網(wǎng)以出行者為尋優(yōu)對象時(shí), 可將路網(wǎng)視為FIFO網(wǎng)絡(luò)這一特性, 對原算法中的個(gè)體生成環(huán)節(jié)進(jìn)行了改進(jìn), 并采用JAVA語言在ArcGIS平臺(tái)提供的動(dòng)態(tài)路網(wǎng)上進(jìn)行了仿真實(shí)驗(yàn), 實(shí)驗(yàn)結(jié)果表明, 該改進(jìn)策略合理、 有效.