徐 達(dá)，蔡滿春，陳 悅

(中國(guó)人民公安大學(xué) 網(wǎng)絡(luò)安全保衛(wèi)學(xué)院，北京100038)

?

基于改進(jìn)Floyd算法的城市交通網(wǎng)絡(luò)最短路徑規(guī)劃

徐 達(dá)，蔡滿春，陳 悅

(中國(guó)人民公安大學(xué) 網(wǎng)絡(luò)安全保衛(wèi)學(xué)院，北京100038)

改進(jìn)Floyd算法；最短路徑；城市交通網(wǎng)絡(luò)

城市交通道路高速發(fā)展使得交通網(wǎng)絡(luò)間節(jié)點(diǎn)與路段日趨復(fù)雜，在城市交通網(wǎng)上規(guī)劃最短路徑也成為研究熱點(diǎn)之一。最短路徑規(guī)劃不局限于路徑規(guī)劃，還可引申至?xí)r間、費(fèi)用等其他度量，在城市最短路徑規(guī)劃算法選擇上，使用最頻繁算法為Floyd算法。劉海洋等[1]在研究分析公交車道設(shè)置的基礎(chǔ)上，提出基于Floyd算法城市最短路徑的規(guī)劃，有效解決公交車道設(shè)置問題，但未將算法改進(jìn)，從而導(dǎo)致在公交車道設(shè)置過程中出現(xiàn)計(jì)算量大、計(jì)算效率低的情況；張榮等[2]在分析了城市建筑較多導(dǎo)致交通道路趨于復(fù)雜和到達(dá)目的地線路過多導(dǎo)致出行路徑不合理后，結(jié)合 Floyd 算法體系，提出最優(yōu)路徑、動(dòng)態(tài)調(diào)整的思路，雖然有效解決城市交通節(jié)點(diǎn)最短路徑規(guī)劃問題，但也未將Floyd算法進(jìn)行改進(jìn)，從而使得整個(gè)城市交通節(jié)點(diǎn)規(guī)劃最短路徑過程中冗余計(jì)算量增大，效率降低。國(guó)內(nèi)外學(xué)者對(duì)Floyd算法進(jìn)行深入研究[3-9]，提出了改進(jìn)思想。林華珍等[10]將Floyd算法進(jìn)行優(yōu)化，降低計(jì)算量，提高了算法計(jì)算效率；趙禮峰等[11]將Floyd算法改進(jìn)，并通過添加下標(biāo)更直觀展示最短路徑規(guī)劃過程中選擇的節(jié)點(diǎn)，進(jìn)一步優(yōu)化Floyd算法，大幅提高了計(jì)算效率。本文總結(jié)分析了現(xiàn)有研究成果，在城市交通道路節(jié)點(diǎn)最短路徑規(guī)劃過程中選擇改進(jìn)Floyd算法，減少Floyd算法計(jì)算過程的非必要計(jì)算，整體提高計(jì)算效率，完成城市交通網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)之間最短路徑規(guī)劃。

1 相關(guān)知識(shí)分析

1.1 城市交通網(wǎng)絡(luò)特點(diǎn)分析

城市交通道路節(jié)點(diǎn)在整個(gè)交通網(wǎng)絡(luò)中發(fā)揮著重要功能，在道路的機(jī)動(dòng)性、通行能力、路網(wǎng)容量都具有較大影響，根據(jù)文獻(xiàn)[12]可歸結(jié)為數(shù)據(jù)量大和結(jié)構(gòu)復(fù)雜，城市道路的復(fù)雜性給在城市交通網(wǎng)絡(luò)節(jié)點(diǎn)與節(jié)點(diǎn)間最短路徑選擇造成一定困難。

根據(jù)實(shí)際需求對(duì)包括大量節(jié)點(diǎn)及路段的城市交通網(wǎng)絡(luò)進(jìn)行抽象，表現(xiàn)其復(fù)雜特性，建立合適模型對(duì)其進(jìn)行分析，將改進(jìn)Floyd算法應(yīng)用到城市交通網(wǎng)絡(luò)節(jié)點(diǎn)間路徑規(guī)劃，能夠有效解決最短路徑規(guī)劃問題。

1.2 算法相關(guān)知識(shí)

賦權(quán)圖：有向網(wǎng)絡(luò)圖D={v，w}，節(jié)點(diǎn)依次標(biāo)號(hào)為vi(i=1,2,3,…,n)，在節(jié)點(diǎn)vi與vj之間的距離為wij=m，并將其標(biāo)示在網(wǎng)絡(luò)中。

回路：在有向網(wǎng)絡(luò)圖D={v，w}中含有一條起點(diǎn)和終點(diǎn)相同的路。

負(fù)回路：回路的一種，其權(quán)值總和在回路上是負(fù)值。

距離矩陣：把最短路徑的長(zhǎng)度記錄在一個(gè)n階矩陣D中，矩陣的第i行到第j列的元素dij指出了從第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)之間最短路徑的長(zhǎng)度。

最短路徑：一般指距離長(zhǎng)短，也可引申為花費(fèi)時(shí)間、消耗代價(jià)等。

Floyd算法：Floyd算法與Warshall算法相類似，通過一系列n階矩陣來計(jì)算一個(gè)n頂點(diǎn)加權(quán)圖的距離矩陣，其核心思想表述為

(1)

2 改進(jìn)Floyd算法

2.1 改進(jìn)算法思想

2.2 改進(jìn)算法步驟

改進(jìn)Floyd算法的主要步驟如下：

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

(2)

(3)

(3)i>j時(shí)

(4)

在此步驟中能將D(k)現(xiàn)有最短路徑與基于D(k)基礎(chǔ)新得出最短路徑進(jìn)行比較，從而選出兩者之間的最小值作為D(k+1)的最短路徑；

步驟6 若D(k+1)=D(k),則表明當(dāng)前路徑矩陣為最終結(jié)果，否則跳轉(zhuǎn)至步驟2，進(jìn)行新一輪計(jì)算。

2.3 改進(jìn)Floyd算法分析

Floyd算法的基本定理保證了Floyd算法的可行性和正確性[15]。本文改進(jìn)算法基于Floyd算法，思路與Floyd算法無太大差異，只在計(jì)算步驟上進(jìn)行改進(jìn)，可見改進(jìn)算法是正確可行的。

3 建模與分析

3.1 建模實(shí)例

模擬城市交通網(wǎng)絡(luò)節(jié)點(diǎn)之間最短路徑規(guī)劃，截取城市某個(gè)區(qū)域的交通網(wǎng)絡(luò)結(jié)構(gòu)圖作為模型背景圖案，如圖1所示。

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

對(duì)圖1進(jìn)行分析，構(gòu)建合適的有向網(wǎng)絡(luò)賦權(quán)圖模擬城市道路交通網(wǎng)絡(luò)，在圖2的網(wǎng)絡(luò)圖中，通過改進(jìn)Floyd算法對(duì)任意兩個(gè)節(jié)點(diǎn)之間最短路徑進(jìn)行規(guī)劃。

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

3.2 本文建模說明

說明1 本文在建模中保留城市道路交通的部分屬性以及完整的拓?fù)浣Y(jié)構(gòu)，道路交叉抽象為網(wǎng)絡(luò)節(jié)點(diǎn)，交叉口之間路徑抽象為城市交通網(wǎng)絡(luò)邊；

說明2 文中有向網(wǎng)絡(luò)賦權(quán)圖節(jié)點(diǎn)代表從城市交通網(wǎng)絡(luò)區(qū)域中選取的節(jié)點(diǎn)，未被選取的節(jié)點(diǎn)不納入規(guī)劃考慮范圍之內(nèi)；

說明3 城市道路交通網(wǎng)絡(luò)中的通行道路在實(shí)際中均為雙向路徑，在本文中標(biāo)注為單向；

說明4 城市道路交通網(wǎng)絡(luò)中的權(quán)值標(biāo)注在實(shí)際運(yùn)用中需綜合考慮節(jié)點(diǎn)之間路徑實(shí)際長(zhǎng)度和路況信息等，并結(jié)合專家建議進(jìn)行標(biāo)注，在本文只考慮節(jié)點(diǎn)之間路徑長(zhǎng)度；

3.3 實(shí)例演示

(5)

通過改進(jìn)Floyd算法由D(0)計(jì)算D(1)之前，將有向網(wǎng)絡(luò)圖進(jìn)行轉(zhuǎn)換，得到如圖3所示的雙節(jié)點(diǎn)之間關(guān)系，更直觀標(biāo)識(shí)出需要參加計(jì)算的節(jié)點(diǎn)和不需要納入計(jì)算的部分節(jié)點(diǎn)。

圖3 有向網(wǎng)絡(luò)圖轉(zhuǎn)換雙節(jié)點(diǎn)權(quán)值圖

由D(0)來計(jì)算D(1)

(6)

(7)

(8)

(9)

經(jīng)比較D(2)=D(1)，則表明當(dāng)前所得結(jié)論為有向網(wǎng)絡(luò)最短路徑規(guī)劃最終值。

3.4 結(jié)果分析

3.4.1 算法的優(yōu)越性

對(duì)于本文的算例，使用Floyd算法需要算法進(jìn)行125次計(jì)算，用文獻(xiàn)[16]中的優(yōu)化矩陣計(jì)算需要進(jìn)行75次計(jì)算，改進(jìn)Floyd算法將非必要計(jì)算省略，只需要33次計(jì)算。Floyd算法在本算例中，由權(quán)值矩陣D(0)將vi到vj經(jīng)過的所有路徑計(jì)算出來，選擇其中最短路徑更新至D(1)中，經(jīng)過如此數(shù)次迭代直至得出D(k)，計(jì)算較繁雜。總結(jié)分析發(fā)現(xiàn)改進(jìn)Floyd算法，在節(jié)點(diǎn)vi和vj之間最短路徑規(guī)劃過程中，不相連的節(jié)點(diǎn)或通過某些中間節(jié)點(diǎn)vs相連的路徑都將在判斷是否應(yīng)當(dāng)舍棄后再進(jìn)入計(jì)算，從而降低計(jì)算復(fù)雜度并完成城市道路交通節(jié)點(diǎn)間最短路徑規(guī)劃。

3.4.2 改進(jìn)算法實(shí)用性

本文改進(jìn)Floyd算法將降低計(jì)算復(fù)雜度，提高工作效率，改進(jìn)Floyd算法能夠較好的完成在城市交通網(wǎng)絡(luò)節(jié)點(diǎn)間的最短路徑規(guī)劃任務(wù)。在城市最短路徑規(guī)劃過程中，各個(gè)節(jié)點(diǎn)之間的路徑權(quán)值賦值，需要根據(jù)城市交通道路寬度、道路質(zhì)量、階段道路車速和路面狀況等信息綜合考慮。改進(jìn)算法提高計(jì)算效率，在碼頭貨物在多倉(cāng)庫之間的分配[17]、分布式電源孤島劃分[18]、帶寬預(yù)分配、空中交通流量管理[19]、道路的優(yōu)化[20]、交通搶修、事故救援和路徑導(dǎo)航中都具有較大實(shí)用價(jià)值。

4 結(jié)束語

改進(jìn)算法基于Floyd算法思想，在算法工作流程上進(jìn)行改動(dòng)，采用先比較再計(jì)算模式降低冗余計(jì)算量，提高計(jì)算效率，完成在城市交通道路節(jié)點(diǎn)之間最短路徑規(guī)劃。在城市交通網(wǎng)絡(luò)中規(guī)劃最短距離的路徑規(guī)劃過程中需要考慮的因素較多，為方便演示，本文路徑權(quán)值未覆蓋全各道路交通因素，下一步工作將綜合多因素到城市交通中，體現(xiàn)基于改進(jìn)Floyd算法城市交通網(wǎng)絡(luò)最短路徑規(guī)劃方法處理復(fù)雜路徑規(guī)劃問題能力。

[1] 劉海洋,木仁.基于Floyd算法的公交專用車道設(shè)置路段分析[J].中國(guó)管理科學(xué),2015(S1):5-8.

[2] 張蓉,陳佳俊,顧向濤,等.智能應(yīng)急疏散路徑規(guī)劃系統(tǒng)的實(shí)現(xiàn)[J].江蘇科技大學(xué)學(xué)報(bào):自然科學(xué)版,2016(2):98-103.

[3] Myoupo J F,Fabret A C.A modular systolic linearization of the warshall-floyd algorithm[J]. IEEE Transactions on Parallel & Distributed Systems,1996,7(5):449-455.

[4] Wei D.An optimized floyd algorithm for the shortest path problem[J].Journal of Networks,2010,5(12):1496-1504.

[5] Huang Q R,Cao M.Study on the improvement of floyd algorithm and its application in network plan[J].Applied Mechanics & Materials,2014,64(2):1312-1315.

[6] 葉奇明,石世光.Floyd算法的演示模型研究[J].海南大學(xué)學(xué)報(bào):自然科學(xué)版,2008,26(1):47-50.

[8] 郭強(qiáng).人數(shù)少于任務(wù)數(shù)的全指派問題的迭代算法[J].計(jì)算機(jī)工程與應(yīng)用,2006(4):91-93.

[9] 趙禮峰,梁娟.最短路問題的Floyd改進(jìn)算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014(8):31-34.

[10] 林華珍,周根貴.求解最短路問題的一種優(yōu)化矩陣算法[J].長(zhǎng)江大學(xué)學(xué)報(bào):自然科學(xué)版,2007,4(4):14-16.

[11] 趙禮峰,梁娟.最短路問題的Floyd改進(jìn)算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014(8):31-34.

[12] 鐘茹.路網(wǎng)中關(guān)鍵節(jié)點(diǎn)和重要路段的分析研究[D].北京:北京郵電大學(xué),2013.

[13] Ridi L,Torrini J,Vicario E.Developing a scheduler with difference-bound matrices and the floyd-warshall algorithm[J].IEEE Software,2012,29(1):76-83.

[14] 茆詩松,程依明,濮曉龍.概率論與數(shù)理統(tǒng)計(jì)教程[M].北京:高等教育出版社,2004.

[15] Floyd R W.Algorithm 97 (shortest path)[J].Communications of the Acm,1962,5(6):345-345.

[16] 林華珍,周根貴.求解最短路問題的一種優(yōu)化矩陣算法[J].長(zhǎng)江大學(xué)學(xué)報(bào):自然科學(xué)版,2007,4(4):14-16.

[17] 江建宇.共享腹地港口群集疏運(yùn)系統(tǒng)智能體仿真研究[D].廣州:華南理工大學(xué),2014.

[18] 謝潛,武鵬,周江昕,等.基于Floyd-warshall算法的分布式電源孤島劃分[J].水電能源科學(xué),2015(10):173-177.

[19] 陳世林.協(xié)同式空中交通流量管理關(guān)鍵技術(shù)及若干算法研究[D].南京:南京航空航天大學(xué),2009.

[20] 岳曉鵬,李慧慧.公園內(nèi)道路規(guī)劃的優(yōu)化方法[J].電子科技,2014,27(2):3-6.

Shortest Path of Urban Traffic Based on the Improved Floyd Algorithm

XU Da，CAI Manchun，CHEN Yue

(School of Cyber Security, People’s Public Security University of China, Beijing 100038, China)

floyd algorithm; shortest path; urban traffic network

2016- 09- 04

國(guó)家自然科學(xué)基金(61602489)

徐達(dá)(1991-)，男，碩士研究生。研究方向：算法和大數(shù)據(jù)。蔡滿春(1972-)，男，博士，副教授。研究方向：密碼學(xué)和算法。陳悅(1992-)，男，碩士研究生。研究方向：灰色理論。

10.16180/j.cnki.issn1007-7820.2017.07.005

TP301.6

A

1007-7820(2017)07-017-04