基金項目：湖南省教育廳科學(xué)研究項目《基于云計算的智能交通系統(tǒng)的研究》（課題號：17C0279）

摘要：路徑選擇技術(shù)作為交通誘導(dǎo)系統(tǒng)的核心，近年來已經(jīng)有了很大的發(fā)展。交通道路的路徑選擇又稱車輛行駛路徑優(yōu)化或者最短路徑搜索，在實際的交通誘導(dǎo)系統(tǒng)通常轉(zhuǎn)化為圖論中的最短路徑搜索問題來求解得到。而目前應(yīng)用在交通路徑選擇領(lǐng)域的算法主要是 Dijkstra 算法，本文將以 Dijkstra 算法為切入點，在流量預(yù)測的基礎(chǔ)之上進(jìn)行路徑選擇技術(shù)的研究。

關(guān)鍵詞：路徑選擇;Dijkstra 算法;路徑優(yōu)化

路徑選擇在城市道路的交通流分配中最關(guān)鍵的問題之一。對出行者來說，最優(yōu)化的行駛路線就是最快到達(dá)目的地，即行程時間最短或者是行駛的路程距離最短。交通信息具有隨機、動態(tài)、復(fù)雜以及不確定的特性。在海量交通信息中， 快速提取有效信息并高效地反饋給出行者是至關(guān)重要， 路徑優(yōu)化算法成為解決問題的關(guān)鍵。本文將在交通流量預(yù)測的基礎(chǔ)上，對出行者提供準(zhǔn)確的最優(yōu)化行駛路線進(jìn)行研究，設(shè)計基于 Dijkstra算法的路徑選擇。

一、路徑選擇

1、路徑選擇問題描述及分析

（1）路徑選擇數(shù)學(xué)描述

路徑的選擇過程通常要考慮交通道路網(wǎng)絡(luò)的等級、長度、類別、行程時間等屬性數(shù)據(jù)，在處理交通路網(wǎng)時通常將其作為圖論中的“圖”。道路的交叉口或者路口的終點即為圖論中的結(jié)點（Node）;兩個結(jié)點之間的路段即為圖中的邊（Edge），帶有方向的邊稱為弧;每條邊都有自己的權(quán)值，用路段的某些屬性特征值來表示。根據(jù)這些可以將城市路網(wǎng)抽象化成一個帶有權(quán)值的圖，從而把最優(yōu)行駛路線問題轉(zhuǎn)化為圖論中的尋找最短路徑問題。

（2）道路權(quán)重的確定

道路權(quán)重的值直接關(guān)系者路徑優(yōu)化搜索，主要的道路權(quán)重有效指標(biāo)有出行時間、出行的距離、出行費用等。

（3）路徑優(yōu)化處理過程

路徑優(yōu)化的處理過程主要是路網(wǎng)的抽象、確定道路權(quán)重的大小、采用合適的搜索算法求解抽象化之后的圖中的最短路徑、最后得到最優(yōu)化的行駛路線提供給出行者。

2、路徑優(yōu)化的步驟

路徑優(yōu)化的根本問題是最短路徑問題，大多數(shù)路徑優(yōu)化問題都可以轉(zhuǎn)化為最短路徑問題，由此可知，路徑優(yōu)化的基本步驟與最短路徑求解相似，路徑優(yōu)化的一般步驟如下：

（1）對現(xiàn)實的路網(wǎng)進(jìn)行數(shù)據(jù)化。路徑優(yōu)化算法處理的是數(shù)據(jù)信息，因此要首先把實際路網(wǎng)信息轉(zhuǎn)化為算法可以處理的路網(wǎng)信息。

（2）路網(wǎng)權(quán)值的適應(yīng)性轉(zhuǎn)化。由于路徑優(yōu)化的標(biāo)準(zhǔn)不一樣，算法處理路網(wǎng)權(quán)值的依據(jù)也不相同，因此，路網(wǎng)的權(quán)值要做一些適應(yīng)性的改變，把原有的距離權(quán)值轉(zhuǎn)換為目標(biāo)性的權(quán)值。如路段行車時間、路段行車花費等。

（3）路徑尋優(yōu)。利用路徑優(yōu)化算法處理路網(wǎng)權(quán)值，求解最優(yōu)路徑。

（4）路徑還原。將算法求取的最優(yōu)解轉(zhuǎn)化為實際的路網(wǎng)路徑。

二、路徑優(yōu)化算法

1、基于 Dijkstra 算法的路徑選擇

Dijkstra 算法是由 E.W. Dijkstra于1959 年提出的一種求解帶權(quán)有向圖中從某一源點到其余各點的最短路徑的一種有效算法， 能夠得到最優(yōu)解， 該算法針對具有非負(fù)權(quán)值的圖。其主要思想是用逐點增長的方法構(gòu)造一棵路徑樹，從而得到從該樹的根結(jié)點（即指定結(jié)點）到其它所有結(jié)點的最優(yōu)路徑，時間復(fù)雜度為 O（n2）。

該算法的路徑選擇基本原理是：在已知的帶有權(quán)值的有向圖中，搜索兩個已知節(jié)點 vo和 vd之間的最短路徑。在搜索的過程中，對于任意節(jié)點m，標(biāo)記該節(jié)點到起點的距離d（m），稱為永久標(biāo)號或臨時標(biāo)號，求解的過程就是臨時標(biāo)號轉(zhuǎn)化為永久標(biāo)號的過程，一般將下一可選節(jié)點中臨時標(biāo)號d（m）最小的標(biāo)號轉(zhuǎn)化為永久標(biāo)號。

2、算法流程

基于 Dijkstra 算法的帶有權(quán)值的有向圖的最短路徑搜索流程如圖所示。

3、算法實現(xiàn)

Dijkstra 算法解決的是單元最短路徑問題，也就是說圖中源點是確定的而另一節(jié)點具有任意性。最短路徑具有一個特性—最優(yōu)子結(jié)構(gòu)性質(zhì)，該性質(zhì)的描述是：假設(shè)P（i，j）={Vi，...，Vk，...，Vs，...，Vj}是從源點 i 到節(jié)點 j 的最優(yōu)化路徑，其中 s 和 k 是該最優(yōu)化路徑上的一個中間點，則 P（k，s）必定是從 k 到 s 的最優(yōu)化路徑。

以上圖的路網(wǎng)結(jié)構(gòu)為研究對象來實現(xiàn) Dijkstra 最短路徑的計算搜索過程，即對圖G=（V， E， W）中節(jié)點間的最短路徑進(jìn)行求解，源點為 V0，集合 U={V0}，集合 T 包含除源點之外的所有節(jié)點，dist[i]為源點 V0與 i 節(jié)點之間的最短距離，path[i]為源點 V0與 i 節(jié)點之間的路段上 i 節(jié)點前的一個節(jié)點，算法的實現(xiàn)過程如下：

（1）從除了源點之外的節(jié)點中找出使得 dist[i]值最小節(jié)點 i，然后將節(jié)點 i 加入到集合 U 中去，此時 U={V0，Vi};

（2）其次，將 Vi作為中間點，修改 T 中各定點的路徑長度，更新與 i 直接相鄰的節(jié)點的 dist 的值。計算公式如下：

（3）重復(fù)以上步驟依次將剩余節(jié)點加入集合 U 中，直到其包含所有節(jié)點，停止迭代。

四、總結(jié)

最短路徑問題，是圖論研究中的一個經(jīng)典算法問題。Dijkstra算法，是解決最短路徑問題的較好算法。本文研究路徑優(yōu)化對象僅僅局限于簡化之后的路網(wǎng)模型結(jié)構(gòu)，而實際道路路網(wǎng)結(jié)構(gòu)較為復(fù)雜且龐大，對于整個城市路網(wǎng)的路徑選擇算法還有待進(jìn)一步的研究。

參考文獻(xiàn)：

[1]張輪，楊文臣，張孟.智能交通與智慧城市[J].科學(xué)（上海），2014，66（1）：33-36

[2]王樹西，吳政學(xué).改進(jìn)的Dijkstra最短路徑算法及其應(yīng)用研究[J].計算機科學(xué)，2012，39（5）：223-228.

[3]王樹西，李安渝.Dijkstra算法中的多鄰接點與多條最短路徑問題[J].計算機科學(xué)，2014，41（6）：217-224.

作者簡介：王柯（1966—），男，教授，湖南城建職業(yè)技術(shù)學(xué)院，研究方向：計算機應(yīng)用技術(shù)。

湖南城建職業(yè)技術(shù)學(xué)院 湖南 湘潭 411101