武濤

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

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

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.3969/j.issn.1003-6970.2015.04.029

0.引言

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

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

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

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

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

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

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