基于不確定因素下的Floyd算法改進(jìn)

在錯綜復(fù)雜的現(xiàn)實(shí)交通網(wǎng)絡(luò)中，如何尋找一條可靠、安全、耗時短的最優(yōu)路徑是所有駕駛?cè)藛T關(guān)心的問題。目前傳統(tǒng)算法尋找最優(yōu)路徑，多數(shù)是以行車距離最短為目標(biāo)，通過研究最短的路程來確定最優(yōu)路徑。在現(xiàn)實(shí)交通狀況下，大多數(shù)駕駛員更希望找到一條行車時間最短的路徑，然而行車時間會受到多種（不確定性）因素，如：紅綠燈、交通擁堵、早中晚高峰期、道路自身狀況、天氣（霧霾、暴雨、地面結(jié)冰等）等因素的影響。因此在實(shí)際交通狀況下，車輛的行駛時間長短存在著不確定性。

當(dāng)今車載導(dǎo)航在尋找最優(yōu)路徑時，多數(shù)以最短路徑為目標(biāo)，雖然近些年不少人開始研究不確定因素對最優(yōu)路徑的影響，但仍舊沒有具體的算法模型能運(yùn)用到導(dǎo)航中，幫助駕駛員快速高效的尋找出行車時間最短的路徑。本文提出改進(jìn)的Floyd算法，為此類問題的解決提供了一個很好的思路。

Floyd算法

傳統(tǒng)Floyd算法

1978年該算法由羅伯特.佛洛伊德命等人創(chuàng)立，主要用來尋找最優(yōu)路徑。算法步驟如下：

算法基本步驟：

（1）輸入邊矩陣D（0）=D。

以總路程最短來尋找最優(yōu)路徑，忽略不確定因素的影響，這樣的狀態(tài)為理想狀態(tài)，求出的是距離最短的路徑，并不一定是時間最短的路徑?，F(xiàn)對該算法進(jìn)行如下改進(jìn)。

改進(jìn)Floyd算法

對于傳統(tǒng)的算法，利用最短距離為目標(biāo)來尋找最優(yōu)路徑，把路程作為路徑優(yōu)良的唯一衡量目標(biāo)，但是實(shí)際生活中，人們一般追求的是行車路徑可靠、安全、耗時短。所以，本文提出改進(jìn)的Floyd算法，以行車時間最短為目標(biāo)，考慮紅綠燈、交通擁堵、天氣變化等因素的影響，其基本思想如下。

（1）算法改進(jìn)的基本思想

在理想交通狀況下，設(shè)第i n 段路程的行車時間為t tn；實(shí)際交通狀況下，由第m 種因素造成的第i n段路程延遲時間設(shè)為從而得到各路段的行車時間。將傳統(tǒng)Floyd算法中，從而得到新定義的以時間為邊權(quán)的矩陣A，按照傳統(tǒng)Floyd算法的步驟，計算得出行駛最短時間的最優(yōu)路徑。

（2）改進(jìn)算法步驟

step1：利用每兩個節(jié)點(diǎn)間的理想行駛時間加上每段路的延遲時間，計算得到每兩個節(jié)點(diǎn)間的實(shí)際行駛時間ti。

step2： 從任意一條單邊路徑開始，各節(jié)點(diǎn)之間的行駛時間表示為時間邊權(quán)值，如果從節(jié)點(diǎn)i 到j(luò) 有路可達(dá)，則T［i，j］=t，t表示兩節(jié)點(diǎn)間的實(shí)際行車時間，如果兩點(diǎn)之間無邊直接連接，則其邊權(quán)值為無窮大，即T［i，j］=∞。以此類推，將圖用鄰接矩陣T 表示。

step3： 定義一個矩陣Path ，用于記錄所插入點(diǎn)的信息，Path［i，j ］表示從節(jié)點(diǎn)i 到j(luò) 需要經(jīng)過的點(diǎn)，初始化Path［ i，j］=0。對于每一對節(jié)點(diǎn)i 和j ，尋找是否存在一個節(jié)點(diǎn)k 使得從i→k→j 比已知時間更短。如果存在，即T［i，j］＞T［i，k］+T［k，j］，則T［i，j］=T［i，k ］+T［k，j］，同時將k 點(diǎn)信息記入矩陣Path［i，j ］；如果不存在，則繼續(xù)遍歷下一個節(jié)點(diǎn)。以此類推，當(dāng)遍歷完所有節(jié)點(diǎn)時，輸出矩陣T，Path 。矩陣T包含了各節(jié)點(diǎn)間的最短行車時間的數(shù)據(jù)，矩陣Path包含了到達(dá)各節(jié)點(diǎn)所經(jīng)過的路徑數(shù)據(jù)。

算法用流程圖如圖1所示。

不確定因子的量化

根據(jù)調(diào)查，自貢市行車時間主要受紅綠燈、路面狀況、車輛數(shù)目的影響，因?yàn)檐囕v數(shù)目和路況對行車的影響主要是通過擁堵來表現(xiàn)，因此本文針對紅綠燈與道路擁堵情況進(jìn)行以下研究。

紅綠燈

紅綠燈是行車時間延誤的重要影響因素，當(dāng)下有很多方法試圖解決信號交叉口時間延誤問題，比如，流體力學(xué)法、排隊(duì)論法、協(xié)調(diào)變換法等，但是均不能很好的解決實(shí)際問題。

因此，本文采用統(tǒng)計學(xué)方法，確定紅綠燈造成的時間延誤為該段路程理想行車時間的25%～33%。考慮到不同地區(qū)紅綠燈時長設(shè)置不一樣，同一地區(qū)不同地段紅綠燈設(shè)置也不一樣，因此對紅燈時長在70s及其以上的地方，設(shè)置其造成的時間延誤為該段路程理想行車時間的33%，60s～70s設(shè)置為30%，60s及其以下為26%。

圖2　自貢市汽車站到彩燈公園交通網(wǎng)絡(luò)圖

擁堵影響

在實(shí)際交通網(wǎng)絡(luò)中，不同時間段的擁堵情況不同，因此對行車造成的延誤也不同，根據(jù)時間將擁堵劃分為高峰期和非高峰期兩類。

高峰期

早中晚高峰期對車速有一定影響，參考當(dāng)?shù)匾酝缰型砀叻迤诮煌〝?shù)據(jù)，由于擁堵對車速造成的影響，根據(jù)調(diào)查研究，對每段路在高峰期和平常的擁堵情況作了一個調(diào)查，根據(jù)調(diào)查數(shù)據(jù)將每段路的擁堵程度進(jìn)行定量分析，（通暢、擁堵、較擁堵、很擁堵四個級別，分別代表行使速度在40km/h以上、40～30km/h、30～10km/h、5km/h以下），每段路所引起的時間延誤

其中，si為第i 條路長；

v 為理想行駛速度；

vi為實(shí)際該段路的行駛速度。

由于車速受早中晚高峰期影響，造成行車時間延長。根據(jù)懲罰函數(shù)，設(shè)定路段擁堵程度的判斷標(biāo)準(zhǔn)，其標(biāo)準(zhǔn)如下。

參照當(dāng)?shù)卦缰型頃r期車速、車輛數(shù)目等數(shù)據(jù)，對其擁堵情況按上述標(biāo)準(zhǔn)進(jìn)行判斷。每段路所引起的延誤時間：

非高峰期

由于路況較差或者該地區(qū)過于繁華及其他原因，會造成某些路段即使在非高峰期時也比較擁堵，這些路段造成的行車時間延誤在實(shí)際交通網(wǎng)絡(luò)中不可忽略，為保持變量的統(tǒng)一性，非高峰期擁堵因子量化同早中晚高峰期。

案例分析

本文以自貢市汽車站到彩燈公園為例，截取其交通網(wǎng)絡(luò)圖如圖2所示。

采用上述研究方法將不同路段紅綠燈及擁堵造成的時間延誤量化如下（以s計）。

表1　各路段不確定因素量化結(jié)果

采用傳統(tǒng)Floyd算法可得到如下最短距離路徑：

0→1→2→5→4→11

將傳統(tǒng)Floyd算法得出的路徑加入不確定因子，分別對紅綠燈和擁堵情況進(jìn)行量化，得到延誤時間，根據(jù)定義，實(shí)際行車時間為理想行車時間與延遲時間之和，計算得到傳統(tǒng)Floyd算法的實(shí)際行駛時間為1189s。

改進(jìn)后的Floyd算法得出的最優(yōu)路徑結(jié)果如下：

A.高峰期：0→1→6→7→8→9→10→11

B.非高峰期：0→1→2→5→4→11

采用改進(jìn)后的算法所得總時間為716.9s。

可以看出，在非高峰期，傳統(tǒng)算法和改進(jìn)后算法所得搜尋結(jié)果一致，而在高峰期二者差異較大，現(xiàn)對高峰期二者搜尋路徑的行車時間進(jìn)行比較。

表2　傳統(tǒng)算法和改進(jìn)算法結(jié)果對比

從上表可以看出，傳統(tǒng)算法只在搜索最短路徑具有較大優(yōu)勢，加入不確定因子的影響以后，本文所改進(jìn)的算法搜尋出的路徑結(jié)果明顯優(yōu)于傳統(tǒng)算法。

總結(jié)

本文考慮的不確定性因素為紅綠燈影響、早中晚高峰期及非高峰期擁堵因素影響，在生活中不可忽略的還有季節(jié)因子影響（霧霾、暴雨、地面結(jié)冰等）等因素，在真正的車輛導(dǎo)航系統(tǒng)中必須將當(dāng)?shù)厮幸蛩乜紤]全面，因此在將來的研究中會重點(diǎn)對這些不確定性因素進(jìn)行考察，將其量化，模擬出更真實(shí)的交通網(wǎng)絡(luò)影響因子。

10.3969/j.issn.1001- 8972.2016.18.017