附件C：譯文


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

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

1 內(nèi)容介紹
在近年來最短路徑問題在交通運輸工程中的應用又被重新掀起熱潮。這是直接歸因于近期智能交通系統(tǒng)（ITS）的發(fā)展，尤其是對外地使用中的車輛進行路線引導（RGS）。中央任何型RGS則是用來計算從原產(chǎn)地到目的地最優(yōu)路線。對于大多數(shù)型RGS目前正在開發(fā)的是明確一個始發(fā)地和目的地之間最低預計行車時間的最優(yōu)路徑之間。這個最優(yōu)路徑計算普遍應用Dijkstra式在確定路段行程時最短路徑算法（Dijkstra 1959年）。這種類型的不利之處是確定性計算，它使得最短路徑問題在確定條件下可以在事實上產(chǎn)生分最優(yōu)解。
反過來說，當雙方的性質(zhì)是動態(tài)和隨機的路段行程時，很明顯，最佳的最短路徑算法就成為高成本的無效和/或不切實際的內(nèi)部使用的一個應用。本文的目的是考察預期的最短路徑在交通網(wǎng)絡中的問題，在隨機性質(zhì)的路段行程中模擬確定，并發(fā)展一種算法，可以提供更好的解決方案，在沒有明顯增加投入的情況下以計算整體時間。
最短路徑的問題已經(jīng)得到了廣泛的研究，在計算機科學、運籌學、交通運輸工程等。大部分文獻都集中在問題在該路段行程費用（或重量），假設為靜態(tài)和確定性。許多有效的算法已開發(fā)出來（貝爾曼，1958年；Dijkstra，1959年；德萊弗斯，1969年），并在本文中，這些算法被稱為標準的最短路徑算法。應當指出該標準最短路徑算法，也已被證實適用于計算最短路徑，在依賴時間的（但不是隨機）網(wǎng)絡（德萊弗斯，1969年；奧爾達和ROM，1990年；考夫曼等人，1993年；馬赫馬薩尼，1993年；Chabini，1997年）。