交通網(wǎng)絡(luò)最優(yōu)安全路徑選擇模型與算法

摘要：針對(duì)交通網(wǎng)絡(luò)任意路段均可能發(fā)生中斷的最小損失路徑選擇問(wèn)題，提出交通網(wǎng)絡(luò)最優(yōu)安全路徑選擇模型，并設(shè)計(jì)了2種不同網(wǎng)絡(luò)結(jié)構(gòu)下最優(yōu)安全路徑選擇算法。首先用模型計(jì)算任意一條路徑上每條邊中斷后產(chǎn)生的從起點(diǎn)到終點(diǎn)最短替代路徑長(zhǎng)度的最大值，然后選擇一條最短替代路徑長(zhǎng)度最大值最小且自身長(zhǎng)度最小的路徑。在網(wǎng)絡(luò)中，當(dāng)最短路徑刪除后該網(wǎng)絡(luò)依然連通時(shí)，最優(yōu)安全路徑問(wèn)題轉(zhuǎn)化為最短路徑問(wèn)題，其計(jì)算復(fù)雜度為O(n²)；當(dāng)最短路徑刪除后該網(wǎng)絡(luò)不再連通時(shí)，最優(yōu)安全路徑問(wèn)題轉(zhuǎn)化為最小最大問(wèn)題，其計(jì)算復(fù)雜度為O(mn)，且僅與網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的數(shù)量有關(guān)。最后，結(jié)合交通網(wǎng)絡(luò)的實(shí)際情況對(duì)最優(yōu)安全路徑進(jìn)行了算例分析。

關(guān)鍵詞：交通網(wǎng)絡(luò)；最優(yōu)安全路徑；路徑選擇

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：0253—987X(2008)04—0395—04