附件C：譯文


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

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

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