基于智能優化算法的動態路徑誘導方法研究進展

游　堯，林培群（華南理工大學土木與交通學院，廣東 廣州 510640）

基于智能優化算法的動態路徑誘導方法研究進展

游堯，林培群
（華南理工大學土木與交通學院，廣東 廣州 510640）

采用綜述的方法對當前動態路徑誘導方法中一些有代表性的智能優化算法進行了深刻的探討與總結,為未來進行深入而廣泛的智能交通系統研究及應用奠定基礎。主要從算法特性、改進效果、性能評價等方面詳細討論了智能優化算法在動態路徑誘導系統中的常見改進機制及其效果，給出了這些優化算法的基本思想、優缺點及其應用局限性；并對智能優化算法性能評價方法的研究現狀進行了詳細的分析與總結，為建模人員和研究人員對智能交通系統中動態路徑誘導方法的選擇和研究提供支持；最后結合算法應用分析成果，展望了智能優化算法在動態路徑誘導系統中的應用發展前景和智能交通系統中進一步研究未來動態路徑誘導算法的重要研究方向。

動態路徑誘導方法；研究進展；智能優化算法；蟻群算法；遺傳算法

第1卷 第1期|2015年2月

0　引言

面對規模越來越大的城市交通網絡，路徑尋優的效率問題使得基于純數學理論的最優路徑算法面臨新的挑戰。傳統的圖論方法（如Dijkstra算法）和數學規劃方法計算量大，以致計算時間長；而且根據幾何距離、道路質量為路阻計算最優路徑，不能客觀描述現實交通網絡的時變性。文獻[1]指出，路徑誘導是一個對實時性要求相當高的系統，過分追求模型的精確和復雜并沒有多大幫助。描述交通網絡的模型越復雜，算法的靈敏性就會減弱，最優路徑的求解復雜度也越大，計算中的省略誤差通常也越大，這些都會降低模型精確帶來的優勢。近年來，一些學者采用對模型精度要求較低的智能化方法研究動態交通誘導問題，智能優化算法[2-3]放寬了優化問題目標函數，加之本身的靈活性，在解決復雜結構優化問題方面有著傳統優化算法無法比擬的優越性。因此，智能優化算法在各個領域的優化計算中都得到廣泛的應用，依賴這類算法，理論上可以在盡可能短的時間內找到問題的最優解或近似最優解。

1　動態路徑誘導方法研究現狀

基本智能優化算法缺乏堅實的理論基礎，同時，其效率低、容易陷入局部最優等缺陷，難以滿足動態路徑誘導的實際需要。因此，在應用領域的研究也多是采用實驗的方法，針對特殊的問題，設計特殊的優化算子，通過反復實驗來確定算法參數，其設計步驟如圖1所示。通過優化設計而形成的方法在精度、精度時間比等評價指標[4]上往往能取得滿意的效果。

圖1　基于智能優化算法的動態路徑誘導方法設計步驟

數值實驗是驗證算法的重要方法，選取合適的測試樣本是數值實驗的關鍵。實驗的內容就是算法的整體性能評價、算子測試以及參數測試。數值實驗的結果一般反饋到參數選取階段，通過參數的相關性和靈敏度測試，可以大致地確定參數變化對算法運行的影響。經過實驗，發現一些能夠取得較好運行效果的參數，如若達不到預期還可以優化算子設計。

1.1基于蟻群算法的動態交通誘導方法

蟻群算法[5]是受自然界螞蟻尋路行為啟發產生的一種具有自適應特性的模擬仿生算法，不需要建立復雜的數學模型和大量數學計算，簡單易實現。蟻群算法自問世以來表現出了強大的生命力，具有并行性、正反饋性、健壯性等特點，且搜索過程不需要人工干預，在求解旅行商（TSP）問題、分配問題、job-shop調度問題上都取得了較好的效果[6-9]?；鞠伻核惴ㄔ谄溟_始時，信息素的作用不明顯；雖然過程中正反饋機制能強化得到較好解，但卻使算法出現停滯現象，即只取得了局部最優解就停止，而未達到全局最優解。因此，學者對其進行了一系列改進研究以適應動態交通網絡實時性與快速性的特點。

杜長海、黃席樾等人[10]提出帶方向的信息素更新和混沌選擇策略來改進蟻群算法，算法將路網節點間的相對位置信息引入信息素更新，以加快搜索速度；使用混沌擾動改進選擇策略，以避免出現早熟停滯現象。其優點在于通過對自然界中螞蟻尋路行為的模擬，在全局范圍內動態確定車輛最優行駛路線，提高了整個交通系統的效率。

Yang[11]結合實時的城市道路交通流信息來解決城市動態路徑誘導難題，提出了一種基于蟻群優化的算法，為司機提供實時最佳路徑。算法使用優先級高的干線道路循環和實時交通信息，減少并避免駕駛困難的道路；考慮到具體城市交通的特點，采用限制搜索區域機制來減少螞蟻的時間復雜度，提高了算法的搜索性能。

周明秀、程科等人[12]提出了動態路徑規劃中改進蟻群算法的方法，算法改進距離啟發因子以增加目標節點對下一節點的影響，從而提高全局搜索能力，避免陷于局部最優解，提高收斂速度；引入多個路徑質量約束來改進信息素更新，模擬出行者在選擇路徑時表現的多目標性及各目標屬性的特點。算法保證了在較短時間內得到全局最優解，有效地克服了傳統蟻群算法中收斂速度慢、易陷入局部最優解的缺陷。

黨希望[13]提出基于主次種群策略的蟻群算法的動態路徑優化算法，相應的加入了信息素交流機制和信息素更新方法，并根據動態路網模型和TSP模型的不同，適時改進了路徑交叉變異策略和路徑去交叉策略；將小窗口策略和PASPAS算法中狀態轉移參數的歸一化處理結合起來，減少了數據處理量，增加了狀態轉移概率的準確性。算法結合路徑交叉變異策略和路徑去交叉策略的優勢，雖然時間復雜度略有提升，但解質量和搜索能力得到了改善。

劉偉[14]給出了一種基于信息素擴散策略的雙種群蟻群算法——PDDPAS算法。算法選取了三個不同規模的TSP問題對PDDPAS算法進行實驗，分別對PDDPAS算法性能、參數的設置、信息素擴散的策略進行考察，得出了相應的設置方案。PDDPAS算法使用信息素擴散策略提高了算法的全局尋優能力，使用雙種群策略提高了算法的收斂速度。

董永峰、劉艷柳等人[15]提出了一種基于改進蟻群算法的求解K最短路徑方法，實現了動態路徑誘導系統中K最短路徑的搜索，通過引入方向函數作為新的啟發式因子，使其能在更少的繁殖代數下搜索到全局最優解，提高了算法的全局搜索能力。在求解K最短路徑時將交叉口延誤時間這一因素加入了目標函數中，使之符合出行者的出行行為。

林娜、霍志勝等人[16]提出基于免疫遺傳的多路搜索蟻群動態路徑誘導算法，利用了蟻群系統算法的動態性、正反饋性和分布式計算的優點；同時兼容了免疫遺傳算法的全局搜索能力以及容易和其他算法相結合等特點。隨著動態因素的增加，算法的復雜性也在增加，因此算法的效率在降低，同時算法又易陷入局部最優狀態。

HUANG[17]通過在實時交通信息網絡中采用蟻群算法找出最優路徑，然后利用群決策理論提出了基于蟻群算法和群體決策的動態路徑優化方法。算法考慮了相鄰交叉口距離以及部分交通流飽和度兩個參數，結合蟻群算法和最優路徑，通過不同群體決策算法的結果比較得到了最優動態路徑優化方法。

總的來說，基于蟻群算法及其改進算法的動態路徑誘導研究一直都未停止，研究者嘗試各種策略來解決基本蟻群算法的應用缺陷以及探索其能夠適合的結合算法。特別是基于蟻群算法的動態路徑誘導應用研究已經比較成熟，在適應性、加速收斂、防止早熟停滯、解的多樣性與全局性等性能上都得到了較大提高[18]，能滿足動態路徑誘導需求。

1.2基于遺傳算法的動態交通誘導方法

大家公認的遺傳算法[19]是建立在自然選擇和群眾遺傳學機理基礎上的隨機、迭代、進化、廣泛適應性的搜索方法，其最先由John Holland于1975年提出，從此以后，它逐漸發展成為一種通過模擬自然進化過程解決最優化問題的計算模型，近年來，基于遺傳算法的動態路徑誘導方法的應用研究也越來越深入。

楊兆升等人[20]基于從出行點出發，徑流量最大的通道到達目的點的路徑就是對應于交通網絡的最短路徑假設提出了一種將交通流比擬成自然流體的神經網絡誘導模式，并用遺傳算法來優化流體神經網絡的參數。計算表明，這種方法較傳統K路最短算法優越，并且成功率較高。

Hitoshi等人[21]為實現車輛實時導航，提出了基于遺傳算法的動態路徑選擇方法，研究分析了遺傳算法用于動態路徑誘導的優勢，設計了從當前遺傳算法路徑解集中產生新路徑的方法，對路口交通燈下的等待、換道等行為進行了模擬實現，通過與Dijkstra算法的對比實驗，驗證了遺傳算法的用于動態車輛導航的高效性。但是文中很少涉及遺傳算法在動態路徑誘導方面的具體算子設計，具有較大的局限性。

張水艦、李永樹等人[22]在建立時間依賴的動態交通網絡模型的基礎上，提出了基于遺傳算法GA 和GIS的動態路徑誘導算法，設計了基于改進輪盤賭方式的個體選擇方式和高效的算子交叉、變異規則，仿真實驗表明時間依賴動態交通網絡模型適用性較高、算法收斂性良好，在一定程度上消除了動態誘導中的Bracess現象。

遺傳算法中的關鍵是初始種群，初始種群的好壞將直接影響算法的收斂速度和收斂結果。鄒亮、徐建閩等人[23]提出了一種以隨機Dijkstra最短路徑算法為基礎，運用遺傳算法來求解動態路徑誘導系統中最短路徑問題的算法，不僅能夠較快地求出較優的路徑，而且對網絡沒有任何的約束條件，對離散和連續的動態網絡模型都有效。

李松江[24]通過有損算法來減少遺傳算法初始種群的規模，從而提升了遺傳算法的整體效率；還將模擬退火算法引入到遺傳算法中，解決遺傳算法過早收斂的缺點。而且考慮到用戶的出行習慣，通過對適應度函數的修改，可以使算法更人性化，更符合人機工程。通過實例驗證了算法的可行性，較一般的遺傳算法和有損算法有著更高的搜索效率和更精確的最優解。

李春元、魏武等人[25]鑒于采用序號編碼方式進行遺傳操作時會產生大量無效路徑，結合城市道路交叉口左轉、右轉、直行等轉向行為，設計了一種新的基于轉向行為的編碼方式，減少了染色體在交叉、變異時的無效路徑的生成。算例表明，這種編碼方式可以有效提高算法收斂性，更容易獲得最優解。

孫霞[26]通過引入一種新的帶染色體交叉控制策略的改進遺傳算法，保證了一對適應值有一定差異的染色體進行交叉，使產生的后代性狀分離，并配合引入單點交叉算子，可以增加種群中個體的多樣性，擴展解的搜索空間，避免了局部極值解；配合單點交叉算子，消除了傳統遺傳算法中早熟收斂的不足，并使所求最優路徑更加貼近實時的交通狀態，切實達到誘導目的，提高整體路網的運行效率。

趙丹[27]研究了適用于動態最優路徑求解的改進自適應遺傳算法，通過引入個體適應度改進算子選擇、設置不隨適應度改變的遺傳率和變異率，解決了局部極小和收斂速度慢的問題。建立城市路網模型和車輛路徑模型，把改進的自適應遺傳算法應用到動態交通條件下路徑誘導的最優求解，仿真比較結果驗證了改進自適應遺傳算法用于動態最優路徑計算、效率和實用性方面的優勢。

Mainali等人[28]在分層網絡上提出基于遺傳算法的高層網絡修剪方法，以此提高交通網絡計算效率。路網由子網和始發地、目的地與邊界路口相交的高級網絡構成，在搜索過程中減少高層網絡邊界路口的數量以提高搜索速度，但同時導致搜索路徑精度下降，因此在遺傳算法評價函數中引入了搜索時間與優化目標權重參數，以此提高搜索精度。使用道路網進行修剪搜索驗證，結果表明，該方法提高了計算效率且準確性喪失較小。

總之，遺傳算法作為一種模擬生命進化機制的隨機搜索優化方法，以其簡單通用、魯棒性強、適于并行處理以及應用范圍廣等特點得到了學者的青睞，但其易出現早熟現象以及對初始種群很敏感。為了適用于動態交通網絡，研究者在算子設計、初始解選擇等方面[29]進行了改進設計，通過仿真實驗等手段證明改進算法的合理性與高效性。

1.3基于其他智能優化算法的動態交通誘導方法

遺傳算法、蟻群算法在動態路徑誘導中的應用研究較為常見，形成了一套比較完整的動態路徑誘導應用理論體系。除此之外，神經網絡算法[30]、粒子群優化算法[31]的動態路徑誘導的應用研究相對較少；禁忌算法[32]、模擬退火算法[33]等算法應用研究目前則主要停留在靜態路徑規劃階段。

李菲、肖洪祥[34]在動態路徑優化中引入了一種神經動態規劃算法，解決傳統算法計算大規模路網的優化問題時所表現出來的計算時間長、存儲空間大等缺陷。它將傳統的動態規劃和BP神經網絡結合起來，通過逼近Q學習算法來尋求一種最優策略，最終達到路徑優化的目的。實驗表明，該方法的實時性、并行性和全局性都優于傳統動態規劃。

馬艷麗、裴玉龍[35]將混沌神經網絡應用于動態路徑誘導，在神經網絡中引入混沌動態，利用其遍歷性進行隨機搜索，再由退火策略控制混沌動態逐漸消失并轉入HNN進一步優化，從而可保證網絡收斂到一個最優或近似最優的穩定平衡點。通過仿真實驗驗證了將混沌神經網絡應用于動態路徑誘導系統總能保證網絡收斂至全局最優，有效克服了Hopfield神經網絡易陷入局部最優解的缺點，具有更高的搜索效率。

吳成東，楊麗英等人[36]提出了將神經網絡與遺傳算法結合的動態路徑誘導方法，研究了基于神經網絡的交通信息實時預測方法，構造了具有時變性的路阻矩陣，解決了傳統靜態路阻存在的時變性差等局限性問題；提出了適用于路徑優化的編碼方式、適應度函數和遺傳操作算子，解決了求解效率和求解質量的平衡問題。

CHEN[37]在分析粒子群優化算法的最基本原理和特征基礎上，從算法初始化、譯碼、健壯性計算、位置與速度更新等多個方面進行分析，針對動態交通網絡特點設計具體的改進方法，將粒子群優化算法應用在動態路徑誘導中。仿真實驗表明，當用于動態路徑道路網絡搜索時，粒子群優化算法具有速度快、準確性高的特點，因此表明了粒子群優化算法用于動態路徑誘導的可行性與高效性。

陳曦[38]在分析常規粒子群優化算法的基礎上，針對動態交通問題，采用一種帶變異因子的改進的粒子群優化算法。這種免疫粒子群優化算法結合了粒子群優化算法具有的全局尋優能力和免疫系統的免疫信息處理機制，并且實現簡單，改善了粒子群優化算法擺脫局部極值點的能力，提高了算法進化過程中的收斂速度和精度，實驗表明其提出的算法具有較好的性能。

DENG[39]提出一種基于神經網絡模型和粒子群算法相結合的優化方法，算法搜索時使用改進間接路徑編碼方案，簡單、收斂速度快，不易陷入局部最優解；針對不同拓撲交通網絡結構進行模擬實驗，均能以較高成功率找到最優解和近似最優解。混合算法大大提高了流體神經元網絡的收斂效率，同時，神經網絡模型和粒子群算法都是并行算法，很容易運行在并行計算機甚至神經計算機上，從而大大減少計算時間。

楊清波[40]采取了一種新的群智能優化算法——人工魚群算法[41]來實現GIS環境下的動態交通最優路徑的求解，針對原始人工魚群算法初始魚群覆蓋空間的不確定性和收斂速度慢等問題進行了改進研究。采用網格化魚群，使初始人工魚群在海域中均勻分布，利于人工魚更快的在全局范圍內尋優；算法中設立一個公告板，用來記錄最優人工魚的狀態和該人工魚位置的食物濃度，以記錄歷史最優狀態。通過實驗對算法中各參數的選擇進行了研究，得到了較優的參數組合，并驗證了改進算法的有效性。

2　算法性能評價研究現狀

目前，常見的禁忌搜索算法、模擬退火算法、粒子群優化算法、遺傳算法、蟻群算法等常被用來解決各個領域的NP完全問題。智能優化算法對解決組合優化問題都有較好的應用，但隨著實際問題的變化，各智能算法都有其不足之處。因此，建立一套符合智能優化算法特點的評價標準對于其改進與應用研究十分必要。傳統優化算法的性能指標主要有兩個[42]：收斂性和收斂速度，但其基于確定型的搜索算法，并不適合用于智能優化算法的評價。

動態路徑誘導算法應用研究當中，主要通過比較算法時間復雜度、收斂速度等傳統優化算法評價指標評價算法應用的有效性，也有通過比較找到最優解的概率及其穩定性等模糊性指標，但缺乏完整的評價體系及理論依據。楊勁秋[4]詳細分析了傳統優化算法的評價標準在智能優化算法評價中的局限性，根據智能優化算法的特點，提出了智能優化算法的一系列具有可操作性的評價指標，并提出了基于隨機搜索的性能評價及優化解概率的分階段估計方法，對智能優化算法的行為及其算子給出了具體的評價方法。

3　結論與展望

動態路徑誘導是智能交通系統中最為人們所期許的功能之一，一般應具有通過考慮交通網絡的變化來提供最小出行時間路徑的功能。本文研究了目前常見智能優化算法在動態路勁誘導中的應用研究情況，為了更好地評價各種智能優化算法在動態交通誘導問題上的應用效果，提出了具有偏好的智能優化算法多指標評價模型。國內外有很多學者都曾對動態交通網絡的特點，有針對性地進行算子設計、參數優化等研究工作，但該問題的研究大多停留在假定性較強的理論層次，動態路徑誘導算法的實時性仍然還是一個很少有人涉足的研究領域[2]。

智能交通系統中的路徑誘導算法是一個復雜的系統工程，具有很強的理論性和實現上的挑戰性。隨著車聯網、移動互聯網等技術的發展，結合智能交通系統的實際需求，基于智能優化算法的動態路徑誘導算法將會有更廣闊的前景，其應用研究可以分為以下三個方向。

（1）應用算法類型的多元化。一方面，隨著研究的不斷深入以及遺傳算法與蟻群算法的應用實踐，智能優化算法的優勢逐漸表現出來，受到更多研究者和交通部門的重視；另一方面，最優路徑搜索問題也屬于組合優化問題，智能優化算法在一系列NP問題已經證明了其優越性，而傳統算法難以解決規模越來越龐大的動態交通網絡尋優問題。

（2）算法之間的結合性發展。單個智能優化算法具有的某些缺點難以滿足動態交通網絡實際需要，如果采用混合算法，用其他智能優化算法的思想對某種智能優化算法進行改進，往往能取得更好的效果。（3）發展基于多目標優化的智能優化算法。

實際問題中常常需要同時考慮路程最短、時間最少、費用最省、風險最小等多種因素，即節點之間的權重屬性有多個。因此研究多目標具有很現實的意義，多目標所得的解是一種“折中”的解。

[1]李威武，王慧.智能交通系統中路徑誘導算法研究進展[J].浙江大學學報：工學版，2005，39（6）：819-825.

[2]黃席越，張著洪，胡小兵，等.現代智能算法理論及應用[M].北京：科學出版社，2005.

[3]鐘一文.智能優化方法及其應用研究[D].杭州：浙江大學，2005.

[4]楊勁秋.智能優化算法評價模型研究[D].杭州：浙江大學，2011.

[5]Schoonderwoerd R,Holland O,Bruten J,et al.Ant-Based Load Balancing in Telecommunications Networks[J].Adap?tive Behavior,1996,5(2):169-207.

[6]Colorni A,Dorigo M,Maniezzo V,et al.Ant System for Job-Shop Scheduling[J].Belgian J of Operations Research Statis?tics and Computer Science,1994,34(1):39-53.

[7]Dorigo M,Maniezzo V,Colorni A.Ant System:Optimization by a Colony of Cooperating Agents[J].IEEE Transactions on System,Man,and Cybernetics-Part B,1996,26(1):29-41.

[8]Dorigo M,Gambardella L M.Ant Colony System:A Coopera?tive Learning Approach to the Traveling Salesman Problem [J].IEEE Transactions on Evolutionary Computation,1997,1 (1):53-66.

[9]Mohemmed A W,Sahoo N C,Geok T K.Solving Shortest Path Problem Using Particle Swarm Optimization[J].Applied Soft Computing,2008,8(4):1643-1653.

[10]杜長海，黃席樾.改進的蟻群算法在動態路徑誘導中的應用研究[J].計算機工程與應用，2008，44（27）：236-239.

[11]YANG Jian-ren.A Dynamic Route Guidance Algorithm Based on Modified Ant Colony Optimization[C]//Computer Network and Multimedia Technology.Wuhan:IEEE,2009: 1-3.

[12]周明秀，程科.動態路徑規劃中的改進蟻群算法[J].計算機科學，2013，40（1）：314-316.

[13]黨希望.基于主次種群蟻群算法的動態路徑優化研究[D].成都：西南交通大學，2013.

[14] 劉偉.基于蟻群算法的動態路徑誘導研究[D].成都：西南交通大學，2008.

[15]董永峰，劉艷柳，張娜.基于改進蟻群算法的動態多路徑誘導系統研究[J].河北工業大學學報，2010，39 （3）：46-51.

[16] 林娜，霍志勝.一種基于免疫遺傳的多路搜索蟻群動態路徑誘導算法[J].小型微型計算機系統，2013（3）：590-594.

[17]HUANG Yan-guo,LUO Qiang.Dynamic Path Optimization Method Based on Ant Colony Algorithm and Group Deci?sion-making[C]//Proceedings of the 10th World Congress on Intelligent Control and Automation.Beijing:IEEE, 2012:300-304.

[18]牛新征，佘堃，路綱.蟻群算法研究的新進展和展望[J].計算機應用研究，2007，2（4）：12-15.

[19]Holland J H.Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology,Con?trol,and Artificial Intelligence[M].Ann Arbor:The Univer?sity of Michigan Press,1975.

[20]WEN Hui-min,YANG Zhao-sheng.Study on the Shortest Path Algorithm Based on Fluid Neural Network of In-Vehi?cle Traffic Flow Guidance System[C]//Proceedings of the IEEE International Conference on Vehicle Electronics. Changchun:IEEE,1999:110-113.

[21]Hitoshi Kanoh,Hideki Kozuka.Evaluation of GA-Based Dynamic Route Guidance for Car Navigation Using Cellu?lar Automata[C]//Intelligent Vehicle Symposium.IEEE, 2002:178-183.

[22] 張水艦，李永樹.利用GA和GIS的動態路徑誘導算法[J].武漢大學學報：信息科學版，2009，34（12）：1476-1479.

[23]鄒亮，徐建閩.基于遺傳算法的動態網絡中最短路徑問題算法[J].計算機應用，2005，25（4）：742-744.

[24]李松江.基于改進遺傳算法的動態路徑誘導系統的研究[D].長春：長春理工大學，2010.

[25]李春元，魏武.基于改進遺傳算法的最優路徑求解[J].交通與計算機，2007，25（5）：88-92.

[26] 孫霞，黃席樾.基于改進遺傳算法的城市交通路徑誘導系統的研究[D].重慶：重慶大學，2007.

[27]趙丹.城市交通路徑誘導算法研究[D].西安：長安大學，2009.

[28]Mainal M K,Mabu S,Hirasawa K.Pruning High-Level Net?work Using Genetic Algorithm for Efficient Hierarchical Route Planning in Road Networks[C]//IEEE Annual Confer?ence.Tokyo:IEEE,2011:2903-2909.

[29]Chang W A,Ramakrishna R S.A Genetic Algorithm for Shortest Path Routing Problem and the Sizing of Popula?tions[J].IEEE Transactions on Evolutionary Computation, 2002,6(6):566-579.

[30]DING Zhen,Leung Henry,ZHU Zhi-wen.A Study of theTransiently Chaotic Neural Network for Combinatorial Opti?mization[J].Mathematical and Computer Modeling,2002, 36(2):1007-1020.

[31]Bo-Yang Q U,Ponnuthurai Nagaratnam Suganthan,Shi-Zheng Zhao.Current Position-Based Fitness Euclideandistance Ratio Particle Swarm Optimizer for Multi-Modal Optimization[C]//Nature and Biologically Inspired Comput?ing.Fukuoka:IEEE,2011:383-388.

[32]Glover F.Future Paths of Integer Programming and Links to Artificial Intelligence[J].Computer and Operations Research,1986(5):533-549.

[33]LV Guang-ming,SUN Xiao-meng,WANG Jian.A Simulat?ed Annealing-New Genetic Algorithm and its Application [C]//Electronics and Optoelectronics.Dalian:IEEE,2011: 246-249.

[34]李菲，肖洪祥.基于神經動態規劃算法的最優路徑選擇[J].桂林工學院學報，2009，29（1）：54-57.

[35]馬艷麗，裴玉龍.基于混沌神經網絡的駕駛員動態路徑誘導算法研究[J].交通運輸系統工程與信息，2007，7 （1）：57-60.

[36]吳成東，楊麗英，許可.神經網絡和遺傳算法在動態路徑誘導中的應用[J].計算機應用研究，2006（5）：177-179.

[37]CHEN Qun.Dynamic Route Guidance Method Based on Particle Swarm Optimization Algorithm[C]//2009 Second International Conference on Intelligent Computation Tech?nology and Automation.Changsha:IEEE,2009:267-270.

[38]陳曦.粒子群優化算法的改進及在動態交通分配問題中的應用[D].長沙：長沙理工大學，2007.

[39]DENG Yan-fang,TONG Heng-qing,et al.Dynamic Short?est Path in Stochastic Traffic Networks Based on Fluid Neu?ral Network and Particle Swarm Optimization[C]//2010 Sixth International Conference on Natural Computation. Yantai:IEEE,2010:2325-2329.

[40]楊清波.GIS環境下的動態交通最優路徑算法研究[D].長沙：中南大學，2012.

[41]李曉磊，邵之江，錢積新.一種基于動物自治體的尋優模式：魚群算法[J].系統工程理論與實踐，2002，22 （11）：32-38.

[42]FU L P,LRILETT R.Expected Shortest Paths in Dynamic and Stochastic Traffic Networks[J].Transportation Re?search B,1998,32(7):499-516.

New Trends of Dynamic Route Guidance Methods Based on Intelligent OptimizationAlgorithms

YOU Yao,LIN Pei-qun
(School of Civil Engineering and Transportation,South China University of Technology, Guangzhou 510640,China)

Some representative intelligent optimization algorithms in the dynamic route guidance meth?ods were discussed and summed up by the review method,which laid a foundation for the future research in the intelligent transportation system deeply and widely.The improvement mechanism and the applica?tion results of the intelligent optimization algorithm are analyzed from the view of the algorithm character?istics,improvement effect,performance evaluation,etc.And the basic idea,advantages,disadvantages and limitations of these algorithms were given.Besides,the research status of evaluation methods of the intelligent optimization algorithm performance was analyzed,which helped engineers and researchers to select the most suitable variability modeling techniques.Finally,combining with the analysis results of algorithms application,the application prospect and some important research directions in the future fur?ther research of the intelligent optimization algorithms in intelligent transportation system were forecast. Key words:dynamic route guidance methods;research progress;intelligent optimization algorithms; ant colony optimization;genetic algorithm

U495

A

2095-9931（2015）01-0020-07

10.16503/j.cnki.2095-9931.2015.01.004

2014-10-22