基于Bellman―Ford算法的最優(yōu)交通路徑選取建模

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

2、9.32 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）09-0192-02改革開放后，我國(guó)經(jīng)濟(jì)得到了大力發(fā)展，科技水平也在不斷增長(zhǎng)，帶動(dòng)了城市交通的興起，各大城市相繼建立了四通八達(dá)的交通網(wǎng)絡(luò)1。圖 1 為 20112015 年某一線城市交通線路增長(zhǎng)情況，由圖 1 可知在這 5 年間，交通線路增長(zhǎng)了 30%以上。公交線路的增加一方面為人們的出行帶來了便利，另一方面也給人們帶來了交通擁堵、交通費(fèi)用、出行時(shí)間等方面的困擾，使得人們不得不面臨多條線路的選擇問題。根據(jù)不同出行者的要求，建立一種最優(yōu)交通路徑選取模型是根本解決之道?，F(xiàn)階段，應(yīng)用最廣的最優(yōu)交通路徑選取模型是在 Dijkstra算法

3、基礎(chǔ)上建立起來，但隨著交通線路的不斷增加，交通問題的不斷加重，該模型已經(jīng)開始流露出“疲態(tài)”，已無法解決交通網(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+，ds0處理（出除源點(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)回路，即分析邊

4、集 E 每條邊的兩個(gè)端點(diǎn)是否收斂。如果頂點(diǎn)都收斂了，算法則是正確的，并把這段距離進(jìn)行保存，說明是最優(yōu)的距離；如果沒有，則說明算法是錯(cuò)誤的，這段距離不是最優(yōu)距離5。1.2 動(dòng)態(tài)最優(yōu)路徑算法從出行者的實(shí)際角度出發(fā)，把 subgoals method 思想與 Bellman-Ford 算法https:/相結(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)為

5、止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)用邊連接起來，只有單程車輛經(jīng)過的站點(diǎn)用弧連接起來，通過以上的邊和弧連接構(gòu)成一個(gè)車輛站點(diǎn)鄰接關(guān)系圖，并利用上 Bellman-Ford 算法進(jìn)行計(jì)算，求出兩個(gè)站點(diǎn)之間的最短距離，以此建立這條路徑的最短距離矩陣7。第二步，在步驟一的基礎(chǔ)上，構(gòu)建總的各車輛站點(diǎn)直達(dá)時(shí)的距離矩陣，然后利用

6、：ab=mina，b進(jìn)行合成處理，得到距離矩陣B=B1B2Bn。第三步，利用 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)越高，因此就可以直接通過車輛路徑直達(dá)距離矩陣建立直達(dá)費(fèi)用矩陣 A。第二步，把步驟一中的直達(dá)費(fèi)用矩陣?yán)?Bellman-Ford 進(jìn)行合成處理，得到

7、總的直達(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ì)于這部分人來說是最重要的，可以更好幫助上班族解決時(shí)間問題。https:/其模型建立步驟如下：第一步，建立車輛各站點(diǎn)之間的時(shí)間矩陣T0=t0ijnn。第二步，給出至多換乘 1 次就能到達(dá)的最短時(shí)間矩陣T1=t1ijnn，t1ij=mint0ij，t0is+t0sj+t，其中t為換乘時(shí)間9。第三步，給出至多換乘k-1k2次就能

8、到達(dá)的最短時(shí)間矩陣T2=t2ijnn，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)化處理，然后把處理

9、結(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 站的最短距離）。3）根據(jù) B1 和 B2 矩陣構(gòu)建總的直達(dá)距離矩陣。4）利用 Bellman-Ford 算法

10、構(gòu)建兩個(gè)站點(diǎn)之間最短路徑的距離矩陣。根據(jù)矩陣 C 就能知道經(jīng)過站點(diǎn)最少的乘車路徑。4 結(jié)束語(yǔ)綜上所述，社會(huì)主義市場(chǎng)經(jīng)濟(jì)的發(fā)展，給我國(guó)交通帶來了翻天覆地的變化，方便了人們的出行，但是隨著交通線路的增多，對(duì)于出行路徑的選擇成為一大難題。在此背景下，最優(yōu)交通路徑選取模型問世，幫助人們解決了這一難題。上文基于 Bellman-Ford 算法，根據(jù)出行者的不同需求建立了四個(gè)最優(yōu)路徑https:/選取模型，該模型經(jīng)過具體算例驗(yàn)證，證明了其合理性和實(shí)用性，對(duì)我國(guó)交通事業(yè)的發(fā)展具有重要意義。參考文獻(xiàn)：1 王超， 高武奇. 基于 AHP 與 Bellman-Ford 算法的停車規(guī)劃方法J. 數(shù)字技術(shù)與應(yīng)用， 2

11、017， 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)路徑問題J. 東南大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2017， 75（6）：1263-1268.6 賀政綱， 鄒曄， 楊曉. 報(bào)廢汽車物流網(wǎng)絡(luò)選址-路徑問題建模與求解算法研究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 端到端多路徑選擇建模及算法研究J. 計(jì)算機(jī)應(yīng)用研究， 2016， 33（4