基于云計算的并行動態路徑搜索算法研究

武濤

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

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

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

0.引言

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

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

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

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

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

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

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