溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
要解決交通流的誘導問題就必須解決動態和隨機的交通流量或平均車速在路段和交叉路口的分配問題，即“實時動態交通分配”。這一理論的主要功能是：預測交通運輸系統狀況、提供道路引導系統、引導車輛在最佳線路上行駛、為出行者提供出發時間和選擇方式、提供誘導系統與交通控制系統的相互聯系、為先進的交通管理系統和先進的交通信息系統提供了重要的理論基礎。
為了有效的解決這一理論問題，需要運用交通規劃相關理論，設計實際最優和預測最優動態交通分配算法。該模型的輸入數據既是需要實施交通誘導區域內路網中各路段和路口的交通狀態數據，建立目的地最優旅行線路的規劃算法，最后產生誘導發布信息。誘導信息的構成將是當前最佳路徑的引導。
下面簡單介紹誘導系統及誘導算法。
1、智能交通系統（ITS）
意義：解決城市交通問題的最佳途徑
關鍵技術基礎：將信息、通信和計算機網絡等技術有效地綜合運用于地面交通管理體系，從而建立一種大范圍、全方位的實時、準確、高效的交通管理系統。
主要功能：為道路使用者提供實時路況數據、道路圖像信息、旅行時間服務、動態導航等服務，使公眾出行更加便利，降低交通事故的發生率，緩解交通擁堵。
主要手段：
①車輛誘導系統：均衡道路網絡交通負載的有效手段；
②城市交通信號控制：提高通行能力的重要手段。
本次主要對車輛誘導系統進行研究。
2、車輛誘導系統研究現狀
2.1、美國TravTek系統
主要信息源：交叉口線圈、視頻檢測器。
通信模塊：電話線路、調頻廣播、自動撥號蜂窩電話。
路徑計算模塊：車內定位計算機和路徑優化計算機。
能根據用戶的需求，從數據庫中檢索出當地的旅館、飯店、加油站、停車場等服務信息，并制定最優路徑。
屬于分布式動態誘導系統，對車內的設施和信息傳輸技術要求較高，造價相對昂貴。
主要信息源：磁場感應器、行程時間測量儀。
通信模塊：道口兩旁紅外信標雙向通信。
路徑計算模塊：車外路徑誘導計算機。
屬于中心式動態誘導系統，對交通信息處理中心要求較高。
主要信息源：交通流檢測器。
通信模塊：無線電信標（高速公路）、紅外信標（主干道）、FM多路廣播；
屬于中心式動態誘導系統。
日本VICS系統框架
常用路徑優化算法分析
出行者對路徑選擇的要求會有所不同，根據不同的最優目標，定義相應的道路權重，反映到網絡圖上。
具體有以下幾種方法：
①出行距離最短作為最優目標；
②出行時間最短；
③出行費用最小
④廣義費用最小，是以目標中某兩個或更多個的線性組合。
如
也可以采用CONTRAM費用方程:
,
其中C為出行費用，L:路段長度，T:出行時間，V：速度，
：耗油量，S：停車次數，D:延誤，P：價格，R:危險程度，M：邊際費用。
路徑優化算法
①最短路徑問題的經典算法
Dijkstra算法是典型最短路徑算法, 是一種按路徑長度遞增的順序產生最短路徑的方法，能得出最短路徑的最優解, 但由于它遍歷計算的結點很多, 所以效率低。之后出現的Floyd算法在實際中搜索效率要好于Dijkstra算法，而Bellman算法雖然在時間復雜度方面由于Dijkstra算法，但實際效果往往不如Dijkstra算法。
A*算法是一種基于Dijkstra算法的啟發式搜索算法，是目前廣為流行的路徑規劃啟發式算法, 它是一種最佳優先搜索算法, 對實現道路網的最佳優先搜索十分有用。啟發式算法思想是引入啟發式信息來提高搜索的效率，啟發式信息有助于確定哪個結點最有希望成為后繼結點并進行剪枝。
當以出行距離最短等靜態網絡作為路徑優化目標時，可以直接使用Dijkstra算法或者A*算法。
idea：路段的權值也可以設計一個包含長度、交通環境以及時間段的函數。但依然是靜態交通網絡。
②基于時間依賴的動態交通網絡最優路徑算法
上面的算法都假設路段權值固定的靜態網絡，是以路徑的空間距離作為優化目標。而在實際交通中，出行者往往關注的是關于時間費用，而不是空間距離，即網絡中路段權值是依賴于時間的變量，屬于動態交通網絡。直接利用上述算法將出現錯誤。
圖中結點a到d的最小路徑為(a,b,c,d)=20，傳統的Dijkstra算法結果是(a,c,d)=25。
因此我們的算法應該重點關注基于時間依賴網絡的最優路徑規劃。
（1）目前主要的基于時間依賴的交通網絡的最優路徑算法，基本上采用這樣的策略：首先使用Dijkstra或者A*算法根據當前估算的各路段行程時間計算一條從當前點到目標點的最優路徑，以后每到一個路口結點，如果發現即將要通過的道路權重發生了較大改變，則根據當前路網各路段權重重新計算一條從當前點到目標點的最優路徑。
這種方法所得一條路徑實際上并不能保證是一條在動態路況中行程時間最少的路徑。舉個例子說明:假設當天道路的權重隨時間變化的序列己經知道(實際上對將來發生的事情只能預測)，如圖
在t1時刻車輛到達A，采用Dijkstra算法選擇ABD這條路線到達目的地D，行駛了5分鐘到B的時候，四條路段的權重都有了更新，BD從2變為4, CD還是保持3，繼續行駛了4分鐘到達D。實際上走ABD路徑使用了9分鐘，而走ACD只用8分鐘。
《基于Android的車載智能導航系統的研究與設計》夏國平 《一種基于實時路況信息的動態路徑規劃算法》雷東升
（2）基于時間預測的最優路徑算法
算法的核心思想是，使用K條最短路徑算法從靜態權重的路網中選擇K條備選路徑，
然后根據路網中各路段行程時間的變化序列從這K條路徑里面選出行程時間最少的路徑。具體算法暫不在此敘述。
該算法需要知道一天的各路段行程時間序列，己經出現過的歷史行程時間序列是可以確定的，應用算法可以得到實際的行程最少時間路徑，但是實際應用需要知道當天的
行程時間序列，只能通過預測的方法得到，此時應用算法得到的路徑是基于行程時間預測序列的行程時間最少路徑，雖然不一定是實際行程時間最少的路徑，但卻可以隨著預測精度的提高不斷接近時間最少的最優路徑。
該算法選擇的路徑也是一條十分接近實際行程時間最少的路徑，完全可以滿足實際的應用。但是算法的缺點是需要使用K最短路徑算法，以及使用Dijkstra算法求出一個K條最短路徑全程行駛時間的下界，下界如果不能起到過濾大量不可行路徑的作用，還是需要在眾多的路徑中選擇一條最優的路徑，這會增加計算量，比普通的完全基于靜態權重的求最優路徑方法運算量要大，可行的改進方法是，針對使用最大權重計算得到的下界可能比較松的情形，需要對這個下界進一步收緊。具體改進方法不在此敘述。
《基于行程時間組合預測模型的動態路徑誘導系統研究》陳悅
（3）一種時間最短路徑算法
定理1為SPTDN算法的理論基礎。
雖然能夠在一定條件下求得最優解,但是由于其時間復雜度為(nmM2C),n是結點數，m是弧段數，M是時間段數，C是所有弧中最大的權值。當時間段數M比較大時，算法所用時間將比較大。
《時變_隨機網絡最優路徑算法及其應用研究》譚國真
2、在SPTDN算法的基礎上進行改進之后，算法有了更加廣泛的適用范圍。當城市實時導航系統給出的最小行程時間路徑中某路段出現突發事件而被迫改變行進路線時，只要對當前位置進行相鄰次數的計算，即可確定新的最小時間路徑，極大地減少了路徑搜索的次數。這樣可以減少服務器的壓力，這在城市實時導航系統中非常有用。所以改進后的最小時間路徑算法更具實際應用價值。
改進后的最小時間路徑算法已經成功應用于某市交警局中心系統中最短路徑的搜索。該系統中以車牌自動識別系統的識別數據為源數據，通過相鄰監測點間的識別數據比對來得到實測路段行程時間；用指數平滑法預測路段在未來若干個時間段內的行程時間。把行程時間作為時間段的一個函數，城市交通網絡就抽象成了一個時間依賴的網絡。
《車輛誘導系統及關鍵技術研究》翟曉峰
idea：在上述的改進算法中，用到了基于車牌自動識別系統的行程時間預測方法。如果能夠結合已有的牌識實時算法庫來獲得各路段的預測行程時間，將極大地加快誘導算法的開發。
(4)其他算法
1、蟻群算法
將交通實時信息作為選擇影響概率的一個因素—阻抗，應用于蟻群算法。將m只螞蟻放到起點結點，迭代尋找最優路徑，全部螞蟻均將所有結點走過一遍。蟻群算法的準確性要高于Dijkstra算法，但蟻群算法則需要迭代上百次才能找出最優解,而且容易陷入局部最優,無法得到真正的最優路徑，需要對傳統蟻群算法進行改進。改進后的蟻群算法,在效率和準確性方面都遠遠超過前面的兩種算法。
《基于實時交通信息的動態路徑規劃算法性能比較》黃西洲
改進的蟻群算法
給出一種在時變網絡中蟻群算法的信息素更新策略, 使其能正確地反映邊上權值的變化情況。針對傳統蟻群算法收斂過早，容易陷入局部最優的問題，將蟻群算法與遺傳算法相結合。
改進的算法在最優解概率和平均求解時間都得到明顯提高，但是文中建立了40個結點的網絡，只設置了8只螞蟻參與運算。
參照其他資料，一般情況下，網絡規模約為螞蟻數目的1.5倍。螞蟻數目的大小對運行時間的影響基本為線性相關。暫時難以估計實際中多結點的平均求解時間，有待于以后實驗估計。
《改進蟻群算法求解時變網絡中最短路徑問題》劉永強
《交通網絡路徑選擇及應用研究》陳京榮
2、遺傳算法
①以一種隨機Dijkstra算法為基礎，運用遺傳算法來求解動態網絡最優路徑。隨機Dijkstra算法能夠在不增加時間復雜度的基礎上求解兩點間最短路徑問題，得出的路徑適用于遺傳算法初始種群的產生問題。
算法要比改進的Dijkstra算法在計算速度上快得多；同時由于遺傳算法具有很強的魯棒性，且初始種群的產生和交叉操作都是根據動態路徑誘導最短路徑問題(SPDRGS)而特別設計的，因此算法同時也具有很高的收斂效率, 能夠在短時間內達到最優或較優解。
本文所采用的是廣州市電子地圖其中含有20000個結點、40000條路段、144個時間間隔。為了驗證算法的有效性，本文在20000個結點中隨機選取了50對OD，每對OD 進行了10 次計算。
《基于遺傳算法的動態網絡中最短路徑問題算法》鄒亮
《遺傳算法在動態路徑誘導系統中的應用》鄒亮
②交互式遺傳算法
與傳統遺傳算法相比，交互式遺傳算法結合了人的偏好、直覺、情感和心理特征等主觀因素。交互式遺傳算法的優化結果更趨合理，更符合個體的需要。出行者可以根據自己的需要選擇最佳的出行路徑，這可以在一定程度上消除動態路徑誘導中的Bracess現象，在一定程度上避免車輛選擇相同的、以前并不擁擠的道路，使這條道路可能很快變得擁擠。
實驗所用的數據是成都市區道路交通網絡，此交通網絡共有5427個結點，7978條邊;共分260個時間間隔。隨機選取了10對OD。每對OD選取不同的初始種群計算了3次，試驗結果如表所示。
《基于GIS_T的城市交通最優路徑誘導算法研究》張水艦
(5)多目標最優
利用k-最短路算法來獲得雙目標最短路的方法，獲得多條有效路徑,使得決策者可以對這些路徑進行比較和選擇。同時, 在求解的過程中,決策者可以根據獲得有效路徑的情況, 對各個目標的上限進行調整, 獲得滿足決策者要求的有效路徑集合。
屬于靜態網絡最優路徑規劃，只能用以出行距離最短等固定權值作為路徑優化目標時。
《基于一種求解雙目標最短路的方法》魏航
《雙目標最短路有效解的快速算法》郝光
《多目標最短路徑模型及算法》郝光
(6)考慮網絡地理特征的改進思想
①層次型網絡模型
近年來路徑規劃很多研究主要集中在對道路的預處理方法上，通過對道路網絡的預處理來挖掘一些可以提高路徑搜索效率的信息來優化路徑計算的性能。其中的經驗層級路網，是一種對道路網絡做預處理的方法，這種預處理方法使路徑規劃的結果更加高效合理。思路是在預處理階段建立一種經驗的層級路網。首先，這里建立的層級路網，將路徑計算中的道路優先級對應于路網的層級。層級性越高的道路在路徑計算時其優先權越高。其次，這里的道路分層方法是基于一種經驗方法，這種經驗是從對于導航路徑選擇很熟悉的出租車司機的路徑軌跡中挖掘出來的。采用這種經驗來決定路徑規劃的道路網絡層級性，也就是說在我們的經驗層級路網中，層級性越高的應該就是經驗上優先的道路。這樣，在路徑規劃中我們就
可以采用高層道路優先的方法來高效地搜索出符合經驗的“好”路徑。
由于層次網絡模型理論復雜，一般是在遇到現有算法無法滿足復雜道路的情況下的最優路徑規劃時，用來提高路徑搜索效率。
《面向導航路徑選擇的道路網絡經驗層級模型研究》曾喆
《時變_隨機網絡最優路徑算法及其應用研究》譚國真
②限制搜索區域
針對橢圓限制搜索區域算法效率的不足，陸鋒提出了基于橢圓的最小外接正矩形限制搜索區域的算法。矩形限制搜索區域算法的基礎是橢圓限制搜索區域算法，橢圓算法中限制橢圓的長軸是采用統計分析方法完成的。具體方法暫不在此敘述。
《基于GIS的最優路徑算法研究與實現》王海梅
日本VICS系統迅速發展的原因:
1、經過幾十年的ITS建設，各種硬件和相關設施都比較完善；
2、日本各個相關部門有效的合作和積極推動；
3、VICS系統也在不斷豐富信息內容提高信息的精確度；
4、良好的商業運作模式和市場化運作、積極推進國際標準、不斷修正和完善。
與日本相比，目前我國的道路信息系統的不足：
1、道路交通信息采集體系還不夠完善；
2、車載GPS終端種類繁多，車載信息服務標準化滯后， 車載信息服務還沒有走向批量市場
3、各相關部門配合不夠
基于此，對于車輛誘導系統的開發任務，應盡量利用較準確、穩定的交通信息采集方法，綜合分析多種在實際應用中較為成熟的算法，包括數據融合、交通狀態判別算法，最優路徑算法等，以保證系統的準確性要求。
數據融合，在硬件設備不完善的前提下盡量獲得足夠多的交通信息，并進行有效處理，使得信息足夠豐富和可靠。
交通狀態判別，誘導系統可靠性的基礎。
最優路徑算法，系統核心，功能需求的多樣化和用戶個性化，算法的設計也應當豐富化。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
