交通網絡最優安全路徑選擇模型與算法

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

關鍵詞：交通網絡；最優安全路徑；路徑選擇

中圖分類號：TP393 文獻標識碼：A 文章編號：0253—987X(2008)04—0395—04