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

關(guān)鍵詞：最短路徑問題，動態(tài)和隨機網(wǎng)絡(luò)，K-最短路徑問題，智能交通系統(tǒng)，路徑引導(dǎo)系統(tǒng)

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