改進(jìn)Floyd算法在城市交通網(wǎng)絡(luò)優(yōu)化中的應(yīng)用

（上海建橋?qū)W院 商學(xué)院，上海 201306）

1 引言

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

2 傳統(tǒng)最短路徑算法

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

2.1 Floyd算法思路

Floyd算法的迭代公式為：

式中的φ為運(yùn)算號(hào)，其運(yùn)算規(guī)則是：

反復(fù)迭代式（1），直至Ds=Ds-1，則最后的Ds就是最短路權(quán)矩陣?？疾?，如果前者小，表示路徑不經(jīng)過節(jié)點(diǎn)k，則其最短路徑為，同時(shí)；如果后者小，則表示經(jīng)過節(jié)點(diǎn)k,其最短路徑為與兩者的連接，設(shè)i,k兩點(diǎn)最短路徑，k,j兩點(diǎn)最短路徑其中，q,r≤s-1，u1,u2,...,uq,t1,t2,...,tr是節(jié)點(diǎn)集{v1,v2,...,vs-1}中q+r個(gè)不同節(jié)點(diǎn)的排列，則i,j兩點(diǎn)最短路徑，最短路長(zhǎng)

2.2 Floyd算法復(fù)雜度

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

3 改進(jìn)的Floyd算法

傳統(tǒng)的Floyd算法，是求解網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)間最短路的有效算法，但是關(guān)于最短路徑的標(biāo)記方法不盡相同，大部分算法使用一串?dāng)?shù)字作為下標(biāo)來記錄最短路徑，標(biāo)記的最短路徑需逆向找尋。另外，F(xiàn)loyd算法在無向網(wǎng)絡(luò)中運(yùn)用時(shí)，在下標(biāo)遍歷時(shí)會(huì)出現(xiàn)大量重復(fù)的計(jì)算。為解決上述不足，本文基于傳統(tǒng)的Floyd算法，提出了一種簡(jiǎn)便可行的無向網(wǎng)絡(luò)上最短路徑求解方法（有向圖可視為無向圖的特殊情形），并給出了避免重復(fù)計(jì)算的實(shí)例。

3.1 改進(jìn)的算法思想

改進(jìn)Floyd算法在計(jì)算最短路徑過程中，采用雙標(biāo)號(hào)法，同時(shí)顯示最短路徑序列和最短路徑長(zhǎng)。同時(shí)，對(duì)最短路徑長(zhǎng)無影響的節(jié)點(diǎn)間路徑值可以不予考慮，在整體上降低求解最短路徑計(jì)算量，從而提高計(jì)算效率。

3.2 改進(jìn)的算法步驟

步驟1 根據(jù)無向網(wǎng)絡(luò)圖得到距離矩陣。

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

（1）i=j時(shí)

（2）i與j不相連

（3）i與j相連時(shí)

采用雙標(biāo)號(hào)法建立初始表，行標(biāo)用i，列標(biāo)用j表示；每個(gè)單元格記，即對(duì)于初始表，每個(gè)單元格的雙標(biāo)號(hào)的前一位記最短路長(zhǎng)，后一位記最短路徑序列。為避免逆序出現(xiàn)，在節(jié)點(diǎn)i到節(jié)點(diǎn)j的路徑上，tij表示節(jié)點(diǎn)i首先應(yīng)到達(dá)的節(jié)點(diǎn)，在初始表中，，這就使得最終輸出的tij（i,j=1,2,...,n-1,n）可順序顯示節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑。

3.3 改進(jìn)的算法復(fù)雜度

4 建模與分析

4.1 建模實(shí)例

為了模擬城市交通網(wǎng)絡(luò)節(jié)點(diǎn)之間的最短路徑規(guī)劃，選取某城市核心區(qū)域的交通網(wǎng)絡(luò)結(jié)構(gòu)圖作為初始的模型案例（如圖1所示），模擬城市道路交通網(wǎng)絡(luò)，構(gòu)建無向網(wǎng)絡(luò)賦權(quán)圖（可假定道路可雙向行駛，如圖2所示）。運(yùn)用改進(jìn)的Floyd算法對(duì)任意兩個(gè)節(jié)點(diǎn)之間的最短路徑進(jìn)行規(guī)劃。

圖1 城市交通網(wǎng)絡(luò)圖

圖2 無向網(wǎng)絡(luò)賦權(quán)圖

4.2 模型假設(shè)

（1）本模型將城市道路交叉點(diǎn)視為網(wǎng)絡(luò)節(jié)點(diǎn)，交叉口之間的路徑抽象成為城市交通的網(wǎng)絡(luò)邊，保留了節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系，是城市道路交通網(wǎng)的拓?fù)浣Y(jié)構(gòu)圖。

（2）圖2所示的有向賦權(quán)圖節(jié)點(diǎn)記為城市交通網(wǎng)絡(luò)區(qū)域中選取的節(jié)點(diǎn)，未被選取的節(jié)點(diǎn)暫不納入規(guī)劃考慮范圍之內(nèi)。

（3）城市道路交通網(wǎng)絡(luò)中的權(quán)值綜合考慮了節(jié)點(diǎn)之間路徑的實(shí)際長(zhǎng)度、交通便捷程度及路況等信息，并結(jié)合谷歌地圖的出行時(shí)間建議進(jìn)行標(biāo)注，在本文中視為兩節(jié)點(diǎn)之間的路徑長(zhǎng)度。

4.3 算法求解

按改進(jìn)的Floyd算法步驟，采用雙標(biāo)號(hào)法，建立初始表，見表1。

表1 k=1初始表

在表1基礎(chǔ)上進(jìn)行算法迭代，即插入節(jié)點(diǎn)②后，計(jì)算出最優(yōu)路徑，見表2。

表2 k=2最優(yōu)路徑表

在表2基礎(chǔ)上進(jìn)行算法迭代，即插入節(jié)點(diǎn)③后，計(jì)算出最優(yōu)路徑，見表3。

表3 k=3最優(yōu)路徑表

在表3基礎(chǔ)上進(jìn)行算法迭代，即插入節(jié)點(diǎn)④后，計(jì)算出最優(yōu)路徑，見表4。

表4 k=4最優(yōu)路徑表

在表4基礎(chǔ)上進(jìn)行算法迭代，即插入節(jié)點(diǎn)⑤后，計(jì)算出最優(yōu)路徑，見表5。

表5 k=5最優(yōu)路徑表

在表5基礎(chǔ)上進(jìn)行算法迭代，即插入節(jié)點(diǎn)⑥后，最優(yōu)路徑表（見表6）與表5時(shí)相同。此時(shí)對(duì)于j＜i且在上述迭代過程中最短路徑有更改的單元格中，將原tij=j改為對(duì)稱單元格相同的標(biāo)號(hào)。

表6 k=6最優(yōu)路徑表

由此得出所有兩節(jié)點(diǎn)間的最短路徑序列與最短路徑，見表7。

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

4.4 結(jié)果分析

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

5 結(jié)語

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