周 佳，沈 巖，夏 宇，韓大明

（東北林業(yè)大學(xué) 交通學(xué)院，黑龍江 哈爾濱150040）

伴隨著城市化的發(fā)展，最短路徑選擇問題已經(jīng)成為解決交通問題的關(guān)鍵。與此同時(shí)，許多解決這一問題的方法也應(yīng)運(yùn)而生，如零空間LDA法、PCA結(jié)合LPP法等。但這些方法普遍受算法求取離散值分類的影響，速度較慢，而本文提出了一種基于模糊的Dijkstra最短路徑的動(dòng)態(tài)算法，能很好地解決這一問題。

目前，Dijkstra算法是公認(rèn)的處理最短路徑的較好方法，由于它只處理數(shù)字，許多語言變量的數(shù)量優(yōu)化方法不能直接應(yīng)用于模糊數(shù)，因此，Dijkstra算法在使用前需要進(jìn)行修改。許多典型的做法是通過去除模糊化的方法把模糊數(shù)轉(zhuǎn)化為確定數(shù)。在應(yīng)用模糊算法時(shí)，需要解決三個(gè)關(guān)鍵問題:量化的語言變成模糊數(shù)，采用梯級(jí)平均綜合表示方法使兩個(gè)數(shù)相加的和可用一個(gè)確定數(shù)來表示，從而在Dijkstra算法中被輕易實(shí)現(xiàn)。

該算法的復(fù)雜性為O（｜E｜＋｜V｜log｜V｜，其中｜V｜為頂點(diǎn)的數(shù)目，｜E｜為邊數(shù)），該算法不適于在模糊環(huán)境下應(yīng)用，因此，本文應(yīng)采用模糊集理論修改該算法。首先，利用模糊數(shù)代表用戶的參數(shù)，然后用模糊數(shù)的模糊算法來找到最短路徑，得到模糊的Dijkstra算法（FDA），因此，F(xiàn)DA處理模糊最短路徑問題更具靈活性和有效性。此外，F(xiàn)DA的特點(diǎn)之一就是模糊數(shù)間不具有秩序關(guān)系。

1 數(shù)學(xué)模型

1.1 Dijkstra算法概述

Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家Dijkstra在1956提出的，是典型的最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層擴(kuò)展，直至擴(kuò)展到終點(diǎn)為止。最終Dijkstra算法通過層層迭代能得出最短路徑的最優(yōu)解。本文算法是在Dijkstra算法的基礎(chǔ)上結(jié)合模糊理論求最優(yōu)解算法。

1.2 Dijkstra算法流程

如圖1所示，設(shè)A為源點(diǎn)，求A到其他各頂點(diǎn)（B，C，D，E，F(xiàn)，G，H，I，J，K，L）的最短路徑。線上所標(biāo)注為相鄰線段之間的距離，即權(quán)值。求各點(diǎn)最短路徑的流程，如圖1所示。

圖1 加權(quán)連通

2 模糊Dijkstra算法流程

模糊邏輯處理不確定性的影響因素較多，如語言的模糊性和人類介入等因素。還有一些情況也會(huì)影響到駕駛員對路徑的選擇，如旅行時(shí)間、旅行距離、交通信號(hào)數(shù)、娛樂路線、路徑駕駛困難等因素。旅行時(shí)間、旅行距離等因素也可被用于尋找最短路徑，因此，當(dāng)同時(shí)考慮到交通信號(hào)數(shù)、娛樂路線、路徑困難等多種因素的路線才是最佳路線，所以，可以通過模糊理論得到將多種情況綜合考慮后的最佳路線。

2.1 模糊Dijkstra算法具體步驟

模糊Dijkstra算法流程如圖2所示，具體運(yùn)算可以分為5個(gè)步驟，如下所示。

步驟1:構(gòu)建一個(gè)網(wǎng)絡(luò)G＝（V，E），V為頂點(diǎn)集，E為邊的集合；

步驟2:獲得交通信號(hào)的三角模糊數(shù)（見圖3）或梯形模糊數(shù)（見圖4），每邊的邊權(quán)值根據(jù)具體的道路情況，如娛樂路段、繁忙路段、駕駛難度等因素進(jìn)行設(shè)置；

圖2 Dijkstra算法流程

圖3 三角模糊數(shù)

圖4 梯形模糊數(shù)

步驟3:使用模糊數(shù)運(yùn)算來添加收費(fèi)關(guān)卡質(zhì)量路段的模糊參數(shù)；

步驟4:使用模糊化方法計(jì)算每個(gè)邊緣的危險(xiǎn)因素；

步驟5:計(jì)算所有可能路徑中的PI，使用Dijkstra最短路徑算法計(jì)算出從源頂點(diǎn)s到所有其他頂點(diǎn)的最短路徑值。

運(yùn)用模糊Dijikstra最短路徑算法找到每個(gè)頂點(diǎn)的最短路徑，并結(jié)合給定源點(diǎn)模糊值進(jìn)行運(yùn)算。首先，找到最短路徑從源點(diǎn)到一個(gè)擁有和它最近模糊值的頂點(diǎn)；然后找到第二近的頂點(diǎn)，依此類推；直至找到所有頂點(diǎn)最短路徑。

2.2 算法的實(shí)現(xiàn)偽碼

2.3 兩種算法計(jì)算過程

圖5所示為一個(gè)簡單的交通網(wǎng)絡(luò)，共擁有5個(gè)節(jié)點(diǎn)和6條路線。從節(jié)點(diǎn)a到d有兩條路線:一條為a→b→c→d；另一條為a→b→d。用更加確切的模糊數(shù)在最短路徑問題中的方式表達(dá)其路線為a→b→c→d，通?？梢杂脙煞N算法進(jìn)行計(jì)算。

2.3.1 dijkstra算法計(jì)算過程

2.3.2 模糊dijkstra算法計(jì)算過程

圖5 一個(gè)簡單的交通網(wǎng)絡(luò)

結(jié)果表明74／6好于153／6。這里的動(dòng)態(tài)路徑采用基于Dijikstras算法與模糊參數(shù)相結(jié)合的算法，通過利用典型的加法運(yùn)算，其結(jié)果為一個(gè)清晰的沒有模糊數(shù)的排序過程。

在圖6中以城市a作為源節(jié)點(diǎn)，城市a將移動(dòng)到其它3個(gè)城市，計(jì)算從源節(jié)點(diǎn)到其它3個(gè)頂點(diǎn)的距離:在它們中，最短的距離是a或者b到3個(gè)頂點(diǎn)的路線，權(quán)值為6.66；下一個(gè)最短路徑為b或者d到其它點(diǎn)的路徑，路線權(quán)值為14.76；接著，城市c從b中被選擇出來的權(quán)值為16.99；最后，城市e從b中被選擇出來的權(quán)值為18.82；剩下的城市成為一個(gè)空集，這個(gè)搜索得以完成。其計(jì)算機(jī)仿真結(jié)果（見圖7）顯示了模糊算法的高效性，其交通網(wǎng)絡(luò)路線的梯形模糊數(shù)隸屬函數(shù)如表1所示。

圖6 Dijkstra模糊算法舉例應(yīng)用

圖7 模糊Dijkstra算法在簡單交通網(wǎng)絡(luò)中的仿真結(jié)果

表1 隸屬函數(shù)參數(shù)計(jì)算表

3 結(jié) 語

通過對Dijkstra算法進(jìn)行分析，求解具有模糊參數(shù)的最短路徑。解決了三個(gè)關(guān)鍵性問題:一是如何添加模糊參數(shù)；二是如何通過模糊化確定路徑權(quán)值，并用其模糊數(shù)表示，使用簡單的網(wǎng)絡(luò)問題例子說明了模糊Dijkstra算法的高效性；三是通過本算法可以比較并確定兩個(gè)不同路徑間的最短模糊化距離。該方法大大優(yōu)化了交通系統(tǒng)，可以應(yīng)用于許多方面，例如火警、救護(hù)車的救援路線選擇、市民出行時(shí)的道路提醒等，能有效地解決城市道路擁堵、道路禁行等實(shí)際問題，對促進(jìn)社會(huì)和諧具有一定積極作用。

［1］王林，石劍鋒.智能交通系統(tǒng)中幾種最短路徑算法分析［J］.2009，54（4）:1008－5696.

［2］王樹西.改進(jìn)的Dijkstra最短路徑算法及其應(yīng)用研究［J］.計(jì)算機(jī)科學(xué)，2012（5）:223－228.

［3］陳亮，何為，韓力群.城市交通最優(yōu)路徑算法［J］.智能系統(tǒng)學(xué)報(bào)，2012，7（2）:1673－4785.

［4］謝海濤，宋奇文.基于交通仿真的區(qū)域交通協(xié)同優(yōu)化控制系統(tǒng)［J］.交通科技與經(jīng)濟(jì)，2014，16（3）:4－7.

［5］鄒濤，陳峰，張凱.智能交通系統(tǒng)中綜合地圖匹配算法［J］.交通科技與經(jīng)濟(jì)，2014，16（2）:48－51.

［6］M.xu，Y.Liu，Q.Huang，Y.Zhang，G.Luan；An improved Dijkstra shortest path algorithm for sparse network，Applied Mathematics and Computation 2007，185:247－254.

［7］X.Lu，M.Camitz；Finding the shortest paths by node combination，Applied Mathematics and Computation 2011，217:6401－6408 .

［8］S.T.Liu，C.Kao；Network flow problems with fuzzy arc lengths，IEEE Transaction on Systems，Man，and Cybernetics，Part B:Cybernetics 2004，34:765－769.

［9］R.E.Belman and L.A.Zadeh；，Decision making in a fuzzy environment，Management science，1970，17，B141－B164.

［10］C.C.Chou.；The canonical representation of multiplication operation on triangular fuzzy numbers，Computers and Mathematics with Applications 2003，45:1601－1610.