基于云計算的并行動態(tài)路徑搜索算法研究

武濤

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

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

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

0.引言

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

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

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

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

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

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

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