不確定性條件下最優(yōu)路徑的研究

顧愛華++郭青慧

摘 要：城市交通情況復(fù)雜多變，交通事故、突發(fā)事件等更增加了車輛行駛時(shí)間的不確定性。本文是在此基礎(chǔ)上進(jìn)行的最優(yōu)路徑的研究，旨在不確定條件下，找到可靠、快速、安全的最優(yōu)路徑。首先，不確定條件下分析不同車輛經(jīng)過每條路徑的時(shí)間均值和標(biāo)準(zhǔn)差，給出每條路徑的時(shí)間代價(jià)，所有路徑中花費(fèi)時(shí)間代價(jià)最小的即為最優(yōu)路徑。而最優(yōu)路徑模型就是在合理的假設(shè)下利用迪杰斯特拉算法得到最小的時(shí)間代價(jià)，并實(shí)際應(yīng)用到市區(qū)交通網(wǎng)絡(luò)，得到繞過擁擠路段的最優(yōu)路徑。本文主要敘述不確定條件下兩點(diǎn)交通的最優(yōu)路徑以及交通網(wǎng)絡(luò)的最優(yōu)路徑研究。

關(guān)鍵詞：最優(yōu)路徑；時(shí)間代價(jià)；迪杰斯特拉算法；兩點(diǎn)交通；交通網(wǎng)絡(luò)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言（Introduction）

目前，交通擁擠和事故正越來越嚴(yán)重的困擾著城市交通。隨著我國(guó)交通運(yùn)輸事業(yè)的迅速發(fā)展，交通“擁塞”已經(jīng)成為很多城市的“痼疾”。在復(fù)雜的交通環(huán)境下，如何尋找一條可靠、快速、安全的最優(yōu)路徑，已經(jīng)成為所有駕駛員的共識(shí)。圖結(jié)構(gòu)被應(yīng)用描述數(shù)據(jù)之間的復(fù)雜結(jié)構(gòu)，對(duì)海量圖數(shù)據(jù)的分析和挖掘越來越重要[1，2]。在現(xiàn)實(shí)世界中還有邊對(duì)應(yīng)的權(quán)值不是一個(gè)而是多個(gè)，并且源節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)的最短路徑是有限制條件的，這就成為多約束最優(yōu)路徑問題[3]。傳統(tǒng)的最優(yōu)路徑問題的研究大多數(shù)是基于“理想”的交通狀況下分析的，即：假設(shè)每條路段上的行駛時(shí)間是確定的。在這種情況下，最優(yōu)路徑就是行駛時(shí)間最短的路徑。目前的車輛路徑導(dǎo)航系統(tǒng)也大都是基于這種理想的狀況下的最優(yōu)路徑算法，尋找行駛時(shí)間最短的路徑。事實(shí)上，由于在現(xiàn)實(shí)生活中，會(huì)受到很多不確定性因素的影響，例如：交通事故、突發(fā)事件等，車輛的行駛時(shí)間存在著不確定性。所以，城市智能交通系統(tǒng)中，如何設(shè)計(jì)一款可靠、快速和安全的最優(yōu)路徑，成為駕駛員的共識(shí)。

針對(duì)這些問題，進(jìn)行“不確定條件下最優(yōu)路徑的研究”。首先，在不確定條件下分析不同車輛經(jīng)過路徑的時(shí)間均值和標(biāo)準(zhǔn)差，給出每條路徑的時(shí)間代價(jià)；在此基礎(chǔ)上，在合理假設(shè)下利用迪杰斯特拉算法得到起點(diǎn)和終點(diǎn)之間的最小時(shí)間代價(jià)，即為最優(yōu)路徑。本文按照此思路，將設(shè)計(jì)的最優(yōu)路徑應(yīng)用到兩點(diǎn)網(wǎng)絡(luò)和交通網(wǎng)絡(luò)中，得到相應(yīng)的結(jié)果，驗(yàn)證了最優(yōu)路徑的合理性。

2 兩點(diǎn)交通（Two-point traffic）

2.1 兩點(diǎn)交通的最優(yōu)路徑模型

在不確定性條件下，以經(jīng)典的最短路徑算法來搜索的車輛路徑導(dǎo)航系統(tǒng)是有缺陷的。例如，為了準(zhǔn)時(shí)到達(dá)目的地，駕駛員通常寧愿避免擁擠的市區(qū)道路，而選擇路程稍遠(yuǎn)的繞城快速路。經(jīng)典的最短路徑算法是假定每條路段上的行駛時(shí)間為確定值，而不同數(shù)量的車輛實(shí)際經(jīng)過同一條路段的時(shí)間不可能為確定值。其中有諸多的因素對(duì)我們的駕駛狀況有影響，如道路的維護(hù)，早中晚的時(shí)間段，道路周圍的設(shè)施和建筑，道路本身的狀況等等。這些都是導(dǎo)致不確定性的原因，從而使道路的流量變化。我們以某一個(gè)城市中某一區(qū)域，私家車經(jīng)過同一條路段的不同行駛時(shí)間和影響道路的狀況的事物（如，紅綠燈的數(shù)量、紅綠燈等待時(shí)間）為參數(shù)，計(jì)算該路段的平均時(shí)間和時(shí)間的標(biāo)準(zhǔn)方差，建立車輛從起點(diǎn)到終點(diǎn)的最優(yōu)路徑的定義和數(shù)學(xué)表達(dá)式。

本文研究的目的是找出起點(diǎn)到終點(diǎn)之間花費(fèi)時(shí)間最短的車輛行駛路徑。但傳統(tǒng)最優(yōu)路徑算法只考慮了車輛在路段上的行駛時(shí)間，因此無法搜索到符合實(shí)際情形的最優(yōu)，所以在這里我們?cè)黾右恍┖饬孔顑?yōu)路徑的指標(biāo)。具體的指標(biāo)有時(shí)間的均值、時(shí)間的標(biāo)準(zhǔn)差，以及影響兩者的權(quán)重指標(biāo)。根據(jù)實(shí)際的情況出發(fā)，在駕駛的過程中由于道路不穩(wěn)定的狀況，而導(dǎo)致時(shí)間的波動(dòng)較大，所以我們給標(biāo)準(zhǔn)差賦以較大的權(quán)值。在最優(yōu)路徑算法中應(yīng)加入每個(gè)路段的行駛時(shí)間的方差，方差的數(shù)值越大說明該路段擁擠概率越大，反之越小。定義某段道路的行駛時(shí)間的均值和該段道路行駛時(shí)間的標(biāo)準(zhǔn)差分別為

（1）

（2）

節(jié)點(diǎn)和節(jié)點(diǎn)之間的道路權(quán)值為

（3）

選擇節(jié)點(diǎn)和節(jié)點(diǎn)的時(shí)間最小代價(jià)，提出的基于均值和方差的最優(yōu)路徑模型為

（4）

2.2 模型的具體應(yīng)用

以圖1為示例，將我們的模型應(yīng)用到圖1的例子，其中大學(xué)為起始點(diǎn)，火車站為終點(diǎn)，并且取。

經(jīng)過市區(qū)道路的時(shí)間代價(jià)為

（5）

經(jīng)過繞城快速道路的時(shí)間代價(jià)為

（6）

雖然經(jīng)過市區(qū)道路時(shí)間的均值為30分鐘，而繞城快速路需要的時(shí)間均值為33分鐘，其時(shí)間代價(jià)為19.5。但是由于市區(qū)道路擁擠，其標(biāo)準(zhǔn)差為15分鐘，而繞城快速路的標(biāo)準(zhǔn)差只要1分鐘，時(shí)間代價(jià)為10.6。通過本模型的應(yīng)用，選擇繞城快速路的時(shí)間代價(jià)要小于選擇市區(qū)道路的時(shí)間代價(jià)。

3 交通網(wǎng)絡(luò)（Traffic network）

3.1 交通網(wǎng)絡(luò)的最優(yōu)路徑模型

在兩點(diǎn)道路的最優(yōu)路徑模型中，提出的基于均值和方差的最優(yōu)路徑模型只是針對(duì)簡(jiǎn)單的兩個(gè)點(diǎn)計(jì)算道路的時(shí)間代價(jià)。因此在實(shí)際的交通網(wǎng)絡(luò)中，我們建立城市道路網(wǎng)絡(luò)模型，G表示城市道路網(wǎng)絡(luò)模型。該模型由集合共同描述，即抽象為“{節(jié)點(diǎn)集合}+{弧段集合}+{路權(quán)集合}的帶權(quán)復(fù)雜交通網(wǎng)絡(luò)來描述，其中為城市道路網(wǎng)絡(luò)的節(jié)點(diǎn)（公交站臺(tái)）集合；為城市道路網(wǎng)絡(luò)的路段（公交站臺(tái)之間的路段）集合。為城市道路網(wǎng)絡(luò)的路段權(quán)值（時(shí)間代價(jià)）集合，實(shí)際上兩個(gè)道路節(jié)點(diǎn)之間的行駛代價(jià)不僅和路段的長(zhǎng)度有關(guān)，還與道路擁擠程度有關(guān)。

研究的目的是找出起點(diǎn)到終點(diǎn)之間花費(fèi)時(shí)間最短的車輛行駛路徑。但傳統(tǒng)最優(yōu)路徑算法只考慮了車輛在路段上的行駛時(shí)間，忽略了路段中存在的擁擠程度，因此無法搜索到符合實(shí)際情形的最優(yōu)路徑。所以必須在最優(yōu)路徑算法中應(yīng)加入每個(gè)路段的行駛時(shí)間的方差，方差越大說明該路段擁擠概率越大，反之越小。

以某一個(gè)城市中不同的公交車經(jīng)過同一條路段（，為該路段的二個(gè)公交站臺(tái)）的不同行駛時(shí)間為參數(shù)，計(jì)算該路段的平均時(shí)間和時(shí)間的標(biāo)準(zhǔn)方差，建立車輛從起點(diǎn)到終點(diǎn)的最優(yōu)路徑的定義和數(shù)學(xué)表達(dá)式。

每段道路行駛時(shí)間的均值矩陣和標(biāo)準(zhǔn)差矩陣分別為

（7）

（8）

城市道路網(wǎng)絡(luò)的權(quán)重為

（9）

基于均值矩陣和方差矩陣的最優(yōu)路徑模型為

（10）

在連通網(wǎng)絡(luò)中，找出任意節(jié)點(diǎn)到節(jié)點(diǎn)的一條路徑，使得時(shí)間代價(jià)最小。在Dijkstra最短路徑算法中[4]，該算法是基于貪心策略，按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑的經(jīng)典算法，主要思想是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到目標(biāo)點(diǎn)為止，即以道路的長(zhǎng)度為權(quán)重。類似于Dijkstra最短路徑算法思想，我們把每個(gè)路段的時(shí)間代價(jià)定義為權(quán)重，目標(biāo)為求解。具體算法如下：

（1）用鄰接矩陣來表示為時(shí)間代價(jià)賦權(quán)的圖，集合T=T-S用于存放當(dāng)前還未找到最小時(shí)間代價(jià)的節(jié)點(diǎn)。那么從v1到圖中其余節(jié)點(diǎn)的最小時(shí)間代價(jià)的初值為

（11）

表示節(jié)點(diǎn)v在圖G中的位置。

（2）選擇，使得

（12）

就是當(dāng)前求得的一條從出發(fā)的時(shí)間代價(jià)最小的終點(diǎn)。令

（13）

（3）修改從出發(fā)到集合T上任一階段的最小時(shí)間代價(jià)。如果

，則

（4）重復(fù)（2）（3）共n-1次。由此求得從到圖中其余各節(jié)點(diǎn)的最小時(shí)間代價(jià)路徑。

類似于Dijkstra最短路徑算法，我們提出的算法用最簡(jiǎn)單的實(shí)現(xiàn)方法就是在每次循環(huán)中，再用一個(gè)循環(huán)距離最短的點(diǎn)，然后用任意的方法更新與其相鄰的邊，時(shí)間復(fù)雜度顯然為。對(duì)于空間復(fù)雜度：如果只要求出距離，只要n的附加空間保存距離就可以了（距離小于當(dāng)前距離的是已訪問的節(jié)點(diǎn)，對(duì)于距離相等的情況可以比較編號(hào)或是特殊處理下）。如果要求出路徑則需要另外V的空間保存前一個(gè)節(jié)點(diǎn)，總共需要2n的空間。

基于均值矩陣和方差矩陣的最優(yōu)路徑算法的最小時(shí)間代價(jià)的最優(yōu)子結(jié)構(gòu)性質(zhì)，該性質(zhì)描述為：如果是從頂點(diǎn)i到j(luò)的最小時(shí)間代價(jià)路徑，k和s是這條路徑上的一個(gè)中間頂點(diǎn)，那么必定是從k到s的最小時(shí)間代價(jià)路徑。下面證明該性質(zhì)的正確性。

假設(shè)是從頂點(diǎn)i到j(luò)的最小時(shí)間代價(jià)路徑，則有。而不是從k到s的最小時(shí)間代價(jià)路徑，那么必定存在另一條從k到s的最小時(shí)間代價(jià)路徑，那么。則與是從i到j(luò)的最小時(shí)間代價(jià)路徑相矛盾。因此該性質(zhì)得證。

3.2 模型的具體應(yīng)用

對(duì)鹽城市區(qū)的交通網(wǎng)進(jìn)行模擬，其中圖2為鹽城市區(qū)圖，途中用粗線標(biāo)出的線路是我們此次建模比賽中所要研究的線路，用紅色標(biāo)志球所標(biāo)識(shí)的是路線中的各個(gè)結(jié)點(diǎn)，共計(jì)20個(gè)。為了使圖示簡(jiǎn)潔明了，將20個(gè)結(jié)點(diǎn)以數(shù)字代替，同時(shí)為了使線路表示的更加的清晰明了，我們以圖2為模型，繪制了如圖3所示的鹽城市區(qū)示例交通網(wǎng)絡(luò)。

根據(jù)真實(shí)路況的數(shù)據(jù)，設(shè)定車輛經(jīng)過各個(gè)路段不同時(shí)間（圖4），求得各個(gè)路段行駛時(shí)間的均值矩陣為（inf表示無窮大，代表兩個(gè)地點(diǎn)之間沒有直接可以到達(dá)的道路）。

同理可求得，道路行駛時(shí)間的標(biāo)準(zhǔn)差矩陣（圖5）。

已知均值和標(biāo)準(zhǔn)差，根據(jù)兩點(diǎn)道路最優(yōu)路徑模型，可得到道路權(quán)值矩陣（圖6）。

根據(jù)模型，在MATLAB上面依據(jù)道路權(quán)值矩陣采用迪杰斯特拉算法編寫程序并運(yùn)行，我們尋找從節(jié)點(diǎn)3到節(jié)點(diǎn)19（人民公園到農(nóng)業(yè)發(fā)展銀行）的最短路徑，運(yùn)行結(jié)果如下：

所經(jīng)道路權(quán)值總和為660，根據(jù)實(shí)際情況，此路徑繞過了路程短卻擁擠的解放路和建軍路，而選擇了路徑較長(zhǎng)卻不太擁擠的其他道路，在不確定的條件下，會(huì)花費(fèi)更少的時(shí)間代價(jià)，通過一條可靠、快速、安全的道路準(zhǔn)時(shí)到達(dá)目的地。

4 結(jié)論（Conclusion）

本文提出的城市道路中搜索最優(yōu)路徑的算法，與以往算法不同的是，本算法不僅僅考慮路徑的距離長(zhǎng)短，更加入了車輛通過路徑的平均時(shí)間與時(shí)間的標(biāo)準(zhǔn)差，以及通過平均時(shí)間和標(biāo)準(zhǔn)差得到的一個(gè)相對(duì)確切的時(shí)間代價(jià)，在不確定條件下（如道路擁擠）給出最優(yōu)的路徑，使得駕駛員能夠可靠、快速、安全到達(dá)目的地。并且在大學(xué)到火車站兩點(diǎn)之間以及鹽城市區(qū)交通網(wǎng)絡(luò)進(jìn)行了具體的應(yīng)用中，使得駕駛員能夠選擇更合理的路線，繞過擁擠的路段，花費(fèi)盡可能少的時(shí)間到達(dá)目的地，運(yùn)行結(jié)果令人滿意，因此本文中提出的算法具有實(shí)際應(yīng)用價(jià)值。

參考文獻(xiàn)（References）

[1] 張素智，張琳，曲旭凱.基于最短路徑的加權(quán)屬性圖聚類算法研究[J].計(jì)算機(jī)應(yīng)用與軟件，2016（11）：212-214.

[2] 孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報(bào)，2008（1）：48-61.

[3] 鄒永貴，魏來.帶多約束條件的最優(yōu)路徑選擇算法研究[J].計(jì)算機(jī)應(yīng)用，2008（05）：1101-1103.

[4] Cormen，H.Thomas，Leiserson，E.Charles，Rivest，L.Ronald，Stein，Clifford （2001）."Section 24.3：Dijkstra's algorithm".Introduction to Algorithms （Second ed.）.MIT Press and McGraw Hill：595-601.

作者簡(jiǎn)介：

顧愛華（1978-），男，碩士，實(shí)驗(yàn)師.研究領(lǐng)域：軟件工程與復(fù)雜網(wǎng)絡(luò).

郭青慧（1995-），女，本科生.研究領(lǐng)域：網(wǎng)絡(luò)系統(tǒng)集成，物聯(lián)網(wǎng)技術(shù).