在動態(tài)和隨機交通網絡期待的最短路徑
EXPECTED SHORTEST PATHS IN DYNAMIC AND STOCHASTIC TRAFFIC NETWORKS
摘要
動態(tài)和隨機最短路徑問題（DSSPP）的定義是在連接旅行時間模擬為隨機過程連續(xù)時間的交通網絡中尋找預期最短路徑。本文的目的是研究問題的性質，并確定一個能夠用提供資料來解決DSSPP的技術，并在網絡與智能交通系統（ITS）得到應用。本文首先對這些網絡提出了一整套一個特定的路徑的旅行時間在動態(tài)和隨機鏈接旅行時間中均值、方差的關系?；谶@些關系，它表明該DSSPP是復雜運算和傳統的最短路徑算法不能保證最佳的解決方案。啟發(fā)式演算法是基于K最短路徑算法來建議，以解決這個問題。最后，解決質量和效率計算之間的轉換，提出的方案算法是基于現實的網絡來自Edmonton ，Alberta。

關鍵詞：最短路徑問題，動態(tài)和隨機網絡，K-最短路徑問題，智能交通系統，路徑引導系統

1 內容介紹
在近年來最短路徑問題在交通運輸工程中的應用又被重新掀起熱潮。這是直接歸因于近期智能交通系統（ITS）的發(fā)展，尤其是對外地使用中的車輛進行路線引導（RGS）。中央任何型RGS則是用來計算從原產地到目的地最優(yōu)路線。對于大多數型RGS目前正在開發(fā)的是明確一個始發(fā)地和目的地之間最低預計行車時間的最優(yōu)路徑之間。這個最優(yōu)路徑計算普遍應用Dijkstra式在確定路段行程時最短路徑算法（Dijkstra 1959年）。這種類型的不利之處是確定性計算，它使得最短路徑問題在確定條件下可以在事實上產生分最優(yōu)解。
反過來說，當雙方的性質是動態(tài)和隨機的路段行程時，很明顯，最佳的最短路徑算法就成為高成本的無效和/或不切實際的內部使用的一個應用。本文的目的是考察預期的最短路徑在交通網絡中的問題，在隨機性質的路段行程中模擬確定，并發(fā)展一種算法，可以提供更好的解決方案，在沒有明顯增加投入的情況下以計算整體時間。