城市動態(tài)時(shí)間最短路徑誘導(dǎo)系統(tǒng)實(shí)現(xiàn)研究
劉張雷，史忠科
（西北工業(yè)大學(xué)白動化學(xué)院，陜西西安71 0129）
摘 要：就城市路同動態(tài)時(shí)間最短路徑誘導(dǎo)系統(tǒng)的實(shí)現(xiàn)展開研究：針對鄰接表和鄰接矩陣在保存完整的路網(wǎng)信息時(shí)出現(xiàn)高冗余并導(dǎo)致算法計(jì)算時(shí)間成倍增加的現(xiàn)象，以改進(jìn)的前向關(guān)聯(lián)邊結(jié)構(gòu)作為路網(wǎng)的存儲結(jié)構(gòu)，并依此對dijkstra算法進(jìn)行改進(jìn)，用于路網(wǎng)節(jié)點(diǎn)之間動態(tài)時(shí)間最短路徑的求取，在此基礎(chǔ)上，基于市區(qū)實(shí)時(shí)交通流數(shù)據(jù)和相位配時(shí)信息，結(jié)合高精度交通電子地圖，開發(fā)了東莞市動態(tài)路徑誘導(dǎo)系統(tǒng)進(jìn)行實(shí)驗(yàn)仿真。該系統(tǒng)針對改進(jìn)后的算法與原算法的差異，設(shè)置了靜態(tài)和動態(tài)兩種最短路徑計(jì)算模式，對兩種模式的計(jì)算時(shí)間和計(jì)算結(jié)果進(jìn)行了對比。結(jié)果表明改進(jìn)算法能夠在不增加時(shí)間復(fù)雜度的前提下，充分考慮動態(tài)交通流狀況、交叉口限向和轉(zhuǎn)向延誤，有效解決城市路網(wǎng)動態(tài)時(shí)間最短路徑問題。
關(guān)鍵詞：動態(tài)時(shí)間最短路徑；前向關(guān)聯(lián)邊；dijkstra
申圖分類號：tp 27 文獻(xiàn)標(biāo)識碼：a
1引言
城市路網(wǎng)動態(tài)時(shí)間最短路徑的計(jì)算，不僅要考慮交叉口之間路段上的行程時(shí)間，還需要考慮交叉口各轉(zhuǎn)向的信號相位延誤和轉(zhuǎn)向限制。因此，路網(wǎng)的存儲結(jié)構(gòu)不僅要能夠存儲路段權(quán)重，還要體現(xiàn)交叉日節(jié)點(diǎn)自身的權(quán)重。
解決這個(gè)問題的一般思路是通過城市路網(wǎng)轉(zhuǎn)換模型，把節(jié)點(diǎn)權(quán)重轉(zhuǎn)換為邊的權(quán)重，從而實(shí)現(xiàn)城市路網(wǎng)圖向普通賦權(quán)有向圖的轉(zhuǎn)換，再利用鄰接矩陣或鄰接表存儲轉(zhuǎn)換后的有向圖。
本文首先就鄰接矩陣或鄰接表存儲轉(zhuǎn)換路網(wǎng)信息這一方法展開分析，指出了它容易造成存儲空間高冗余并導(dǎo)致算法汁算時(shí)間成倍增加的弊端。由此，本文采用一種改進(jìn)的前向關(guān)聯(lián)邊結(jié)構(gòu)作為存儲結(jié)構(gòu)，同時(shí)依照此結(jié)構(gòu)對dijkstra算法進(jìn)行了改進(jìn)，并開發(fā)了東莞市動態(tài)路徑誘導(dǎo)系統(tǒng)進(jìn)行動態(tài)時(shí)間最短路徑求取的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明改進(jìn)算法能夠在不增加時(shí)間復(fù)雜度的前提下，充分考慮交叉口限向和轉(zhuǎn)向延誤，有效解決城市路網(wǎng)動態(tài)時(shí)間最短路徑問題。
2鄰接矩陣或鄰接表存儲轉(zhuǎn)換路網(wǎng)信息時(shí)的弊端
常用的路網(wǎng)模型轉(zhuǎn)換方法有兩種：增設(shè)虛擬邊法和對偶圖法。增設(shè)虛擬邊法根據(jù)交叉口實(shí)際構(gòu)造（丁字路口、十字字路口或其他），將此交叉口節(jié)點(diǎn)進(jìn)行一對多的擴(kuò)展。并將各個(gè)可行的轉(zhuǎn)向以虛擬有向線段加以表示，該轉(zhuǎn)向的延誤對應(yīng)于有向線段的權(quán)值。利用這種方法，可以從路網(wǎng)圖中清晰地看出，交叉口哪些入口禁止左轉(zhuǎn)，同時(shí)電能夠看到各個(gè)直行、左轉(zhuǎn)或右轉(zhuǎn)路線在此交叉口的延誤時(shí)間。但由于在交叉口進(jìn)行節(jié)點(diǎn)擴(kuò)展時(shí)，它將路網(wǎng)的節(jié)點(diǎn)數(shù)擴(kuò)大了8倍。設(shè)城市路網(wǎng)包括n個(gè)交叉日，由上述分析中已知一個(gè)十字路口節(jié)點(diǎn)經(jīng)增設(shè)虛擬邊處理后變成了8個(gè)節(jié)點(diǎn)表示，如圖l，圖2所示．
假設(shè)以鄰接表：3l存儲有向圖的方式存儲轉(zhuǎn)換后的路網(wǎng)信息，并采用算法復(fù)雜度的dijkstra算法進(jìn)行時(shí)問最短路徑的計(jì)算，所需運(yùn)算時(shí)間相應(yīng)要擴(kuò)大64倍。對偶圖法是一種新穎的路網(wǎng)結(jié)構(gòu)表示形式，將路段以圖中節(jié)點(diǎn)表示，交叉日各個(gè)路口轉(zhuǎn)向以有向線段表示；路段的權(quán)重轉(zhuǎn)化為節(jié)點(diǎn)的權(quán)熏，交叉口各轉(zhuǎn)向延誤轉(zhuǎn)化為相應(yīng)有向線段的權(quán)值。它同樣使得路網(wǎng)的節(jié)點(diǎn)數(shù)成倍地?cái)U(kuò)張，如果也以鄰接表作為存儲結(jié)構(gòu)，也會導(dǎo)致計(jì)算時(shí)間的成倍增長。
3 改進(jìn)的前向關(guān)聯(lián)邊結(jié)構(gòu)
前向關(guān)聯(lián)邊結(jié)構(gòu)最早由dial等人在1979年提出。對于n個(gè)交叉口，m條路段的城市路網(wǎng)。這種結(jié)構(gòu)利用一個(gè)一維數(shù)組pointednodes，按n個(gè)節(jié)點(diǎn)的編號順序，依次保存從各個(gè)節(jié)點(diǎn)出發(fā)的有向線段的終止節(jié)點(diǎn)的編號，同時(shí)用另外一個(gè)一維數(shù)組traveltime來保存各條有向線段的相應(yīng)權(quán)值（對于時(shí)問最短路徑問題，權(quán)值取該路段的行程時(shí)間），pointednodes數(shù)組和traveltime數(shù)組都占用了m個(gè)存儲單元。由每個(gè)節(jié)點(diǎn)出發(fā)的有向線段不止一條，即路網(wǎng)中各個(gè)節(jié)點(diǎn)的出度大于等于1，pointednodes數(shù)組中對應(yīng)于每個(gè)節(jié)點(diǎn)的終止節(jié)點(diǎn)的個(gè)數(shù)也是大于等于1的。前向關(guān)聯(lián)邊結(jié)構(gòu)用一維數(shù)組pointer，保存各個(gè)起始節(jié)點(diǎn)所指向的第一個(gè)終止節(jié)點(diǎn)在數(shù)組中的索引值，pointer數(shù)組占用的存儲單元數(shù)與路網(wǎng)節(jié)點(diǎn)數(shù)是相同的。
結(jié)合具體路網(wǎng)實(shí)例對前向關(guān)聯(lián) |
