武濤

摘要：由于動態(tài)路徑導(dǎo)航系統(tǒng)中總會出現(xiàn)預(yù)測不準確和重新計算時間長的問題，因此需要有一個高效的動態(tài)路徑搜索算法作為系統(tǒng)的有益補充。路徑搜索算法中蟻群算法具有很好的并行特性，但目前針對路徑搜索中應(yīng)用的蟻群算法在并行性分布方面存在重復(fù)搜索和難以找到最優(yōu)解的一些缺陷。因此，本文研究針對路徑搜索的更加合理的并行蟻群算法，通過合理劃分數(shù)據(jù)域，使得計算結(jié)果的準確性和計算資源的利用效率都能有很大提高，最后用實驗結(jié)果的對比來進一步說明算法的高效和準確性。

關(guān)鍵詞：智能交通；蟻群算法；并行性部署；優(yōu)化問題

中圖分類號：TP312 文獻標識碼：A DOI：10.3969/j.issn.1003-6970.2015.04.029

0.引言

隨著城市化的發(fā)展，車輛擁堵、交通意外等現(xiàn)象越來越頻繁地影響著人們的出行，為社會生活的各個方面帶來了不必要的損失。動態(tài)路徑導(dǎo)航系統(tǒng)運用智能交通技術(shù)，引入了云計算的新興前沿技術(shù)，加強車輛、道路、使用者三者之間的聯(lián)系，緩和道路堵塞和減少交通事故，提高人民群眾出行便利性，對于智能交通的發(fā)展推廣具有重要意義。

由于導(dǎo)航系統(tǒng)中出行者OD（origin-destination）信息來自于基于歷史信息平均的預(yù)測，或者是依據(jù)歷史信息和進行計算前收集的實時交通流情況倒推的預(yù)測，這就總會出現(xiàn)預(yù)測不準確的問題。當真實OD需求超過了預(yù)測，或者某段道路情況由于事故等原因突發(fā)擁堵，上述數(shù)據(jù)會與實際偏差較大。理想的解決方法是根據(jù)當前網(wǎng)絡(luò)情況再重新計算交通分配，但計算耗時較長，根據(jù)前期實驗達15分鐘以上，具體時間由待處理網(wǎng)絡(luò)規(guī)模、路網(wǎng)狀態(tài)以及計算效率等決定。出行者無法等待，因此需要有一個高效的動態(tài)路徑搜索算法作為系統(tǒng)的有益補充。

大規(guī)模動態(tài)路徑搜索問題對運算效率要求很高，雖然很早時就有了經(jīng)典的Diikstra和Floyd算法，不過當面對大規(guī)模網(wǎng)絡(luò)時仍然達不到要求。對于該問題，一些學者提出了許多動態(tài)路徑導(dǎo)航算法，如楊易等人提出的病毒化遺傳算法、Marco Dorigo提出的蟻群算法等，但是就性能而言，蟻群算法相對較好。

盡管傳統(tǒng)蟻群算法在求解小規(guī)模路徑導(dǎo)航問題或者TSP（Traveling Salesman Problem）問題（或其他優(yōu)化問題）時，表現(xiàn)出極高的性能，但是隨著問題規(guī)模的增大，傳統(tǒng)蟻群算法的缺點也暴露出來：①收斂速度明顯減慢，也就是說，算法找到目前已知的最優(yōu)解所需的時間急劇增加；②搜索易于停滯，即當搜索到一定程度后，所有個體所發(fā)現(xiàn)的解完全一致，不能對空間進一步搜索。

而在實際的導(dǎo)航問題中，要尋找的街道路口等構(gòu)成的數(shù)據(jù)規(guī)模比較大，若采用傳統(tǒng)蟻群算法則可能導(dǎo)致求解速度過慢，很難滿足實際導(dǎo)航對于實時性的要求。為了解決這一難題，不少學者曾提出了改進算法，如Tsai C，Wei Gao等人提出的改進算法，經(jīng)研究發(fā)現(xiàn)，如果能在導(dǎo)航問題中采用若干蟻群并行執(zhí)行，通過合理的劃分蟻群來減小每個蟻群的搜索范圍，這樣就可以極大的提高搜索速度，避免傳統(tǒng)蟻群算法由于搜索范圍太大而帶來的收斂速度慢的問題。

目前已經(jīng)有學者提出了一些并行蟻群算法，如Xu JunYong、ChengyongLiu等提出的并行蟻群算法，這些并行蟻群算法的并行策略可以歸納為以下兩類：螞蟻級并行策略和數(shù)據(jù)級并行策略，兩者皆有其缺點和局限性：①如果采用螞蟻級并行策略，則服務(wù)器云端在實際的尋路計算中，很有可能出現(xiàn)很多螞蟻多次重復(fù)沿同一路徑查找的問題，這樣會造成極大的計算資源浪費，嚴重影響并行算法的效率。②如果采用數(shù)據(jù)級并行策略，則可以避免螞蟻級策略所遇到的計算資源浪費問題，但是如果數(shù)據(jù)域劃分的太小，由于各個蟻群無法跨區(qū)域搜索，則會造成很難找到真正的最優(yōu)解的問題，因此對于數(shù)據(jù)級并行策略，如何合理劃分數(shù)據(jù)域是一個十分關(guān)鍵的問題。

本文將交通信息數(shù)據(jù)與實時通信有機結(jié)合，以動態(tài)交通地理信息（如路網(wǎng)中的動態(tài)交通分配信息、交通事件信息等）為主，以物理上的道路距離為輔設(shè)計動態(tài)交通路網(wǎng)模型，以旅行時間最少作為搜索準則，設(shè)計啟發(fā)式算法以及在云平臺的部署方法。算法設(shè)計目標是提高求解最優(yōu)路徑的速度和精確性，本文將具體研究如何將云計算模型與并行蟻群算法相結(jié)合來求解融入動態(tài)交通信息的最優(yōu)路徑，并通過實驗驗證算法的高效和準確性。endprint