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

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

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

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

Floyd算法

傳統(tǒng)Floyd算法

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

算法基本步驟：

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

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

改進(jìn)Floyd算法

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

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

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

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

step1：利用每?jī)蓚€(gè)節(jié)點(diǎn)間的理想行駛時(shí)間加上每段路的延遲時(shí)間，計(jì)算得到每?jī)蓚€(gè)節(jié)點(diǎn)間的實(shí)際行駛時(shí)間ti。

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

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

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

不確定因子的量化

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

紅綠燈

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

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

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

擁堵影響

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

高峰期

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

其中，si為第i 條路長(zhǎng)；

v 為理想行駛速度；

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

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

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

非高峰期

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

案例分析

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

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

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

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

0→1→2→5→4→11

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

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

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

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

總結(jié)

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

10.3969/j.issn.1001- 8972.2016.18.017