改進Floyd算法在城市交通網絡優化中的應用

（上海建橋學院 商學院，上海 201306）

1 引言

隨著城市交通道路高速發展，交通網絡間節點與路段日趨復雜，最短路徑規劃問題成為城市交通網絡研究熱點之一。最短路徑規劃不僅局限于路線設計及分析，還可引申到其它諸如時間、費用、線路容量等資源分配和優化問題[1-2]。在交通網絡的規劃設計中，大多數的優化模型都是以最短路徑算法為基礎，特別是在迭代的算法結構中，其最短路權矩陣計算子程序的調用頻率較高[3-4]。因此，交通網絡的最短路權矩陣算法的效率，可直接影響到局部規劃設計模塊乃至整個交通規劃程序的運行速度。對Floyd算法進行改進，去除非必要中間節點路徑計算，降低計算量，有效提高Floyd算法的計算效率，成為一個值得研究的課題[5]。

2 傳統最短路徑算法

建立交通網絡最優線路問題數學模型的目的，是為尋找最優路徑，為公眾出行決策提供參考。目前，國際上采用較多的方法主要是Dijkstra算法。此算法可以找出網絡中從某一節點到其余各點間的最短路徑，其時間復雜度為O(n2)，其中n為網絡節點的數目。而對于任意兩點間的最短路徑計算問題，最具有代表性的是Floyd算法。

2.1 Floyd算法思路

Floyd算法的迭代公式為：

式中的φ為運算號，其運算規則是：

反復迭代式（1），直至Ds=Ds-1，則最后的Ds就是最短路權矩陣。考察，如果前者小，表示路徑不經過節點k，則其最短路徑為，同時；如果后者小，則表示經過節點k,其最短路徑為與兩者的連接，設i,k兩點最短路徑，k,j兩點最短路徑其中，q,r≤s-1，u1,u2,...,uq,t1,t2,...,tr是節點集{v1,v2,...,vs-1}中q+r個不同節點的排列，則i,j兩點最短路徑，最短路長

2.2 Floyd算法復雜度

Floyd算法首先調用式（2），即任意i,j兩點之間，需比較原路徑與插入k節點后的路徑長，其中k=1,2,...,n；然后再調用式（1），每次關于k的矩陣迭代還需要i,j取遍1,2,...,n，故整個算法的平均時間復雜度為O(n3)。對于算法的空間復雜度，需要兩個n×n的矩陣，其中一個是最短路徑序列的鄰接矩陣，另一個是最短路長的權矩陣[6]。

3 改進的Floyd算法

傳統的Floyd算法，是求解網絡中任意兩個節點間最短路的有效算法，但是關于最短路徑的標記方法不盡相同，大部分算法使用一串數字作為下標來記錄最短路徑，標記的最短路徑需逆向找尋。另外，Floyd算法在無向網絡中運用時，在下標遍歷時會出現大量重復的計算。為解決上述不足，本文基于傳統的Floyd算法，提出了一種簡便可行的無向網絡上最短路徑求解方法（有向圖可視為無向圖的特殊情形），并給出了避免重復計算的實例。

3.1 改進的算法思想

改進Floyd算法在計算最短路徑過程中，采用雙標號法，同時顯示最短路徑序列和最短路徑長。同時，對最短路徑長無影響的節點間路徑值可以不予考慮，在整體上降低求解最短路徑計算量，從而提高計算效率。

3.2 改進的算法步驟

步驟1 根據無向網絡圖得到距離矩陣。

D0=，其中i,j=1,2,...,n-1,n

（1）i=j時

（2）i與j不相連

（3）i與j相連時

采用雙標號法建立初始表，行標用i，列標用j表示；每個單元格記，即對于初始表，每個單元格的雙標號的前一位記最短路長，后一位記最短路徑序列。為避免逆序出現，在節點i到節點j的路徑上，tij表示節點i首先應到達的節點，在初始表中，，這就使得最終輸出的tij（i,j=1,2,...,n-1,n）可順序顯示節點i到節點j的最短路徑。

3.3 改進的算法復雜度

4 建模與分析

4.1 建模實例

為了模擬城市交通網絡節點之間的最短路徑規劃，選取某城市核心區域的交通網絡結構圖作為初始的模型案例（如圖1所示），模擬城市道路交通網絡，構建無向網絡賦權圖（可假定道路可雙向行駛，如圖2所示）。運用改進的Floyd算法對任意兩個節點之間的最短路徑進行規劃。

圖1 城市交通網絡圖

圖2 無向網絡賦權圖

4.2 模型假設

（1）本模型將城市道路交叉點視為網絡節點，交叉口之間的路徑抽象成為城市交通的網絡邊，保留了節點之間的關聯關系，是城市道路交通網的拓撲結構圖。

（2）圖2所示的有向賦權圖節點記為城市交通網絡區域中選取的節點，未被選取的節點暫不納入規劃考慮范圍之內。

（3）城市道路交通網絡中的權值綜合考慮了節點之間路徑的實際長度、交通便捷程度及路況等信息，并結合谷歌地圖的出行時間建議進行標注，在本文中視為兩節點之間的路徑長度。

4.3 算法求解

按改進的Floyd算法步驟，采用雙標號法，建立初始表，見表1。

表1 k=1初始表

在表1基礎上進行算法迭代，即插入節點②后，計算出最優路徑，見表2。

表2 k=2最優路徑表

在表2基礎上進行算法迭代，即插入節點③后，計算出最優路徑，見表3。

表3 k=3最優路徑表

在表3基礎上進行算法迭代，即插入節點④后，計算出最優路徑，見表4。

表4 k=4最優路徑表

在表4基礎上進行算法迭代，即插入節點⑤后，計算出最優路徑，見表5。

表5 k=5最優路徑表

在表5基礎上進行算法迭代，即插入節點⑥后，最優路徑表（見表6）與表5時相同。此時對于j＜i且在上述迭代過程中最短路徑有更改的單元格中，將原tij=j改為對稱單元格相同的標號。

表6 k=6最優路徑表

由此得出所有兩節點間的最短路徑序列與最短路徑，見表7。

表7 最短路徑序列與最短路徑表

4.4 結果分析

對于本文的案例，用傳統Floyd算法計算，需要進行216次。用文獻[7]中的優化矩陣需要計算108次，改進Floyd算法采用判斷語句將原計算量減少，只需進行五步迭代，60次計算。結果分析發現，在節點i到j之間最短路徑規劃過程中，改進的Floyd算法首先適當選擇節點，然后再進入迭代計算，從而在很大程度上降低了算法所需運算次數、時間及空間復雜度，并有效完成城市道路交通節點間最短路徑規劃。

5 結語

最短路徑算法在交通網絡路徑規劃中有著廣泛應用，除此之外，在設備更新、服務網點、配送中心選址及最小費用最大流等衍生的問題中也有著廣泛的應用。本文提出的改進Floyd算法，采用先篩選再計算的模式，降低了冗余的計算并節省了存儲空間，從而提高了算法的計算效率。以某市的交通網絡為例，利用改進Floyd算法進行建模求解，計算結果表明：優化后的算法計算量明顯減少，同時最短路徑序列無需回溯找尋。在城市交通網絡中實現最短路徑規劃，在理想模型假設條件之外，仍需要綜合考慮眾多元素[8]，為體現改進Floyd算法的可行性和實用性，本文路徑權值并未探討全部交通因素。接下來，可考慮帶負權值或是帶回路或是有向賦權網絡等交通網絡的最短路徑規劃問題，以體現改進Floyd算法處理多因素復雜交通網的有效性。