吳華芹

摘要：在現(xiàn)代社會(huì)，城市交通是一個(gè)城市運(yùn)行的基礎(chǔ)，隨著社會(huì)的進(jìn)步和經(jīng)濟(jì)的發(fā)展，交通越來(lái)越發(fā)達(dá)，給人們的生活帶來(lái)極大的便利，但是與此同時(shí)交通擁堵、交通安全等問(wèn)題為人們的出行籠罩上了一片陰影。針對(duì)以上問(wèn)題，最優(yōu)交通路徑選取模型的建立是根本解決途徑。通過(guò)對(duì)城市公交路徑選擇問(wèn)題的分析，在Bellman-Ford算法的基礎(chǔ)上，根據(jù)乘客的不同需求建立不同的最優(yōu)路徑選擇模型，并同時(shí)以算例驗(yàn)證模型和算法的合理性和實(shí)用性。

關(guān)鍵詞：Bellman-Ford算法；最優(yōu)交通路徑；路徑選擇；模型；

中圖分類號(hào)：R179.32 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）09-0192-02

改革開(kāi)放后，我國(guó)經(jīng)濟(jì)得到了大力發(fā)展，科技水平也在不斷增長(zhǎng)，帶動(dòng)了城市交通的興起，各大城市相繼建立了四通八達(dá)的交通網(wǎng)絡(luò)[1]。圖1為2011～2015年某一線城市交通線路增長(zhǎng)情況，由圖1可知在這5年間，交通線路增長(zhǎng)了30%以上。公交線路的增加一方面為人們的出行帶來(lái)了便利，另一方面也給人們帶來(lái)了交通擁堵、交通費(fèi)用、出行時(shí)間等方面的困擾，使得人們不得不面臨多條線路的選擇問(wèn)題。根據(jù)不同出行者的要求，建立一種最優(yōu)交通路徑選取模型是根本解決之道?，F(xiàn)階段，應(yīng)用最廣的最優(yōu)交通路徑選取模型是在Dijkstra算法基礎(chǔ)上建立起來(lái)，但隨著交通線路的不斷增加，交通問(wèn)題的不斷加重，該模型已經(jīng)開(kāi)始流露出“疲態(tài)”，已無(wú)法解決交通網(wǎng)絡(luò)中的實(shí)時(shí)導(dǎo)航、通勤、調(diào)度等時(shí)刻變化的交通流量情況[2]。在此情況下，本文考慮出行者的換乘次數(shù)、出行時(shí)間、出行費(fèi)用等因素，在Bellman-Ford算法的幫助下建立最優(yōu)交通路徑選取模型。

1 Bellman-Ford算法

1.1算法流程

第一，初始化，即把所有頂點(diǎn)的最優(yōu)距離估計(jì)值都進(jìn)行[d=v←+∞，ds←0]處理（出除源點(diǎn)外）[3]。

第二，分布式迭代求解，即對(duì)邊集E中的每條邊進(jìn)行多次松弛操作，讓頂點(diǎn)集中各個(gè)小頂點(diǎn)v的最優(yōu)距離估計(jì)值與最優(yōu)距離[運(yùn)行v-1次]相接近[4]。

第三，檢驗(yàn)負(fù)權(quán)回路，即分析邊集E每條邊的兩個(gè)端點(diǎn)是否收斂。如果頂點(diǎn)都收斂了，算法則是正確的，并把這段距離進(jìn)行保存，說(shuō)明是最優(yōu)的距離；如果沒(méi)有，則說(shuō)明算法是錯(cuò)誤的，這段距離不是最優(yōu)距離[5]。

1.2動(dòng)態(tài)最優(yōu)路徑算法

從出行者的實(shí)際角度出發(fā)，把subgoals method思想與Bellman-Ford算法相結(jié)合，設(shè)計(jì)一個(gè)動(dòng)態(tài)最優(yōu)路徑算法。該算法可以把考察源點(diǎn)與待選點(diǎn)之間，以及待選點(diǎn)與目標(biāo)點(diǎn)之間的路況變化情況，利用下一個(gè)點(diǎn)到目標(biāo)點(diǎn)之間的最優(yōu)距離作為選擇啟發(fā)步。在所有起始點(diǎn)到待選點(diǎn)實(shí)際花費(fèi)時(shí)間與待選點(diǎn)到目標(biāo)點(diǎn)的評(píng)估時(shí)間之和中選擇最小的一個(gè)，則對(duì)應(yīng)的待選點(diǎn)為當(dāng)前點(diǎn)，繼續(xù)考慮下一步的起始節(jié)點(diǎn)，直到選到目標(biāo)點(diǎn)為止[6]。根據(jù)以上描述，算出的最終結(jié)果就是交通最優(yōu)路徑。

2交通最優(yōu)路徑選取模型

2.1出行總距離最短的最優(yōu)路徑選擇模型

該模型是整個(gè)交通體系中最重要的一個(gè)模型，它可以最大限度節(jié)約出行者的時(shí)間。其模型建立步驟如下：

第一步，建立車輛各站點(diǎn)之間的距離矩陣，把各站點(diǎn)作為矩陣中的各個(gè)小頂點(diǎn)，然后根據(jù)車輛的行駛方向，把有往返車輛的站點(diǎn)用邊連接起來(lái)，只有單程車輛經(jīng)過(guò)的站點(diǎn)用弧連接起來(lái)，通過(guò)以上的邊和弧連接構(gòu)成一個(gè)車輛站點(diǎn)鄰接關(guān)系圖，并利用上Bellman-Ford算法進(jìn)行計(jì)算，求出兩個(gè)站點(diǎn)之間的最短距離，以此建立這條路徑的最短距離矩陣[7]。

第二步，在步驟一的基礎(chǔ)上，構(gòu)建總的各車輛站點(diǎn)直達(dá)時(shí)的距離矩陣，然后利用[Λ：aΛb=mina，b]進(jìn)行合成處理，得到距離矩陣[B=B1ΛB2Λ…ΛBn]。

第三步，利用Bellman-Ford算法對(duì)從步驟2中得到的矩陣B進(jìn)行計(jì)算處理。處理完畢后，得到各車輛站點(diǎn)之間的最短直達(dá)距離，輔助出行者選取出出行總距離最短的最優(yōu)路徑。

2.2出行總費(fèi)用最少的最優(yōu)路徑選擇模型

出行費(fèi)用也是制約出行者出行的主要因素，因此在滿足出行者要求的基礎(chǔ)下，建立出行總費(fèi)用最少的最優(yōu)路徑選取模型是十分重要的[8]。其模型建立步驟如下：

第一步，車輛行駛的距離越長(zhǎng)，收費(fèi)越高，因此就可以直接通過(guò)車輛路徑直達(dá)距離矩陣建立直達(dá)費(fèi)用矩陣A。

第二步，把步驟一中的直達(dá)費(fèi)用矩陣?yán)肂ellman-Ford進(jìn)行合成處理，得到總的直達(dá)費(fèi)用矩陣B。

第三步，利用Bellman-Ford算法對(duì)從步驟二中得到的矩陣B進(jìn)行計(jì)算處理。計(jì)算完畢后，選取出各車輛站點(diǎn)之間最少費(fèi)用中的最優(yōu)路徑。

2.3出行總時(shí)間最少的最優(yōu)路徑選擇模型

在城市交通中，上班者占據(jù)大部分，因此建立出行總時(shí)間最少的最優(yōu)路徑選取模型對(duì)于這部分人來(lái)說(shuō)是最重要的，可以更好幫助上班族解決時(shí)間問(wèn)題。其模型建立步驟如下：

第一步，建立車輛各站點(diǎn)之間的時(shí)間矩陣[T0=t0ijn×n]。

第二步，給出至多換乘1次就能到達(dá)的最短時(shí)間矩陣[T1=t1ijn×n，t1ij=mint0ij，t0is+t0sj+t]，其中[t]為換乘時(shí)間[9]。

第三步，給出至多換乘[k-1k≥2]次就能到達(dá)的最短時(shí)間矩陣[T2=t2ijn×n，tkij=mintk-1ij，tk-1is+t0sj+t]。當(dāng)[Tk=Tk-1]時(shí)，得到任意兩個(gè)站點(diǎn)之間的最短通行時(shí)間矩陣。

2.4出行滿意度最大的最優(yōu)路徑選取模型

以上三種交通最優(yōu)路徑選取模型都是以一種考慮因素為中心的。但是在現(xiàn)實(shí)生活中，出行者更希望把這三種因素都納入考慮范圍內(nèi)，建立最令人滿意的交通最優(yōu)路徑選取模型，為此為同時(shí)滿足出行者兩個(gè)或兩個(gè)以上的需求，下文建立了一個(gè)出行滿意度最大的最優(yōu)路徑選擇模型[10]。其模型建立步驟如下：

第一步，參考出行者需要，明確各考慮因素的權(quán)重，并以此將以上三種矩陣（直達(dá)距離矩陣、直達(dá)時(shí)間矩陣、直達(dá)費(fèi)用矩陣）進(jìn)行標(biāo)準(zhǔn)化處理，然后把處理結(jié)果加權(quán)平均，構(gòu)建綜合滿意度矩陣A。

第二步，利用[Λ]把綜合滿意度矩陣合成總的直達(dá)綜合滿意度矩陣B。

第三步，利用Bellman-Ford算法對(duì)從步驟二中得到的矩陣B進(jìn)行計(jì)算。計(jì)算完畢后，幫助出行者選取出綜合滿意度最大的最優(yōu)乘車路徑。

3具體算例

圖2是某城市由6個(gè)公交站點(diǎn)，2條公交路線構(gòu)成的公交網(wǎng)。

1）建立圖2中兩條公交路線的直達(dá)關(guān)系矩陣。

2）利用Bellman-Ford算法獲得兩條公交線路的最短直達(dá)距離矩陣[Bk=bkij]（其中[bkij]表示k號(hào)線i站到j(luò)站的最短距離）。

3）根據(jù)B1和B2矩陣構(gòu)建總的直達(dá)距離矩陣。

4）利用Bellman-Ford算法構(gòu)建兩個(gè)站點(diǎn)之間最短路徑的距離矩陣。

根據(jù)矩陣C就能知道經(jīng)過(guò)站點(diǎn)最少的乘車路徑。

4結(jié)束語(yǔ)

綜上所述，社會(huì)主義市場(chǎng)經(jīng)濟(jì)的發(fā)展，給我國(guó)交通帶來(lái)了翻天覆地的變化，方便了人們的出行，但是隨著交通線路的增多，對(duì)于出行路徑的選擇成為一大難題。在此背景下，最優(yōu)交通路徑選取模型問(wèn)世，幫助人們解決了這一難題。上文基于Bellman-Ford算法，根據(jù)出行者的不同需求建立了四個(gè)最優(yōu)路徑選取模型，該模型經(jīng)過(guò)具體算例驗(yàn)證，證明了其合理性和實(shí)用性，對(duì)我國(guó)交通事業(yè)的發(fā)展具有重要意義。

參考文獻(xiàn)：

[1] 王超， 高武奇. 基于AHP與Bellman-Ford算法的停車規(guī)劃方法[J]. 數(shù)字技術(shù)與應(yīng)用， 2017， 32（7）：142-143.

[2] 任小聰， 向紅艷， 陳堅(jiān). 交通事故信息對(duì)路徑選擇行為的影響建模與分析[J]. 公路交通科技， 2016， 33（7）：103-107.

[3] 衛(wèi)小偉. 基于改進(jìn)遺傳算法的多目標(biāo)城市交通路徑選擇系統(tǒng)建模與仿真[J]. 計(jì)算機(jī)與數(shù)字工程， 2016， 44（1）：10-15.

[4] 徐廣寧， 王印海， 曾自強(qiáng). 城市路網(wǎng)動(dòng)態(tài)轉(zhuǎn)向建模與優(yōu)先選擇研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息， 2017， 17（4）：132-137.

[5] 潘義勇， 馬健霄. 基于可靠性的隨機(jī)交通網(wǎng)絡(luò)約束最優(yōu)路徑問(wèn)題[J]. 東南大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2017， 75（6）：1263-1268.

[6] 賀政綱， 鄒曄， 楊曉. 報(bào)廢汽車物流網(wǎng)絡(luò)選址-路徑問(wèn)題建模與求解算法研究[J]. 公路交通科技， 2016， 33（3）：138-145.

[7] 汪宏晨， 張霞， 唐爐亮，等. 時(shí)段交通限行的時(shí)空動(dòng)態(tài)建模與路徑優(yōu)化方法[J]. 長(zhǎng)安大學(xué)學(xué)報(bào)：自然科學(xué)版， 2017， 37（5）：89-96.

[8] 李澤平， 楊旋， 鮑序. 對(duì)等網(wǎng)端到端多路徑選擇建模及算法研究[J]. 計(jì)算機(jī)應(yīng)用研究， 2016， 33（4）：1191-1198.

[9] 張京敏， 牛群. 關(guān)于城市物流配送交通路徑規(guī)劃仿真研究[J]. 計(jì)算機(jī)仿真， 2017， 34（6）：367-371.

[10] 楊嘉華. 基于雙向最短路徑的大型停車場(chǎng)停車路徑優(yōu)化算法[J]. 信息技術(shù)與信息化， 2016， 53（9）：58-60.