劉張雷，史忠科
西北工業(yè)大學(xué)自動化學(xué)院，陜西西安

摘　　　要：就城市路網(wǎng)動態(tài)時間較短路徑誘導(dǎo)系統(tǒng)的實(shí)現(xiàn)展開研究。針對鄰接表和鄰接矩陣在保存完整的路網(wǎng)信息時出現(xiàn)高冗余并導(dǎo)致算法計(jì)算時間成倍增加的現(xiàn)象，以改進(jìn)的前向關(guān)聯(lián)邊結(jié)構(gòu)作為路網(wǎng)的存儲結(jié)構(gòu)，并依此對Ｄｉｊｋｓｔｒａ算法進(jìn)行改進(jìn)，用于路網(wǎng)節(jié)點(diǎn)之間動態(tài)時間較短路徑的求取。在此基礎(chǔ)上，基于市區(qū)實(shí)時交通流數(shù)據(jù)和相位配時信息，結(jié)合高精度交通電子地圖，開發(fā)了東莞市動態(tài)路徑誘導(dǎo)系統(tǒng)進(jìn)行實(shí)驗(yàn)仿真。該系統(tǒng)針對改進(jìn)后的算法與原算法的差異，設(shè)置了靜態(tài)和動態(tài)兩種較短路徑計(jì)算模式，對兩種模式的計(jì)算時間和計(jì)算結(jié)果進(jìn)行了對比。結(jié)果表明改進(jìn)算法能夠在不增加時間復(fù)雜度的前提下，充分考慮動態(tài)交通流狀況、交叉口限向和轉(zhuǎn)向延誤，有效解決城市路網(wǎng)動態(tài)時間較短路徑問題。

關(guān)　鍵　詞：動態(tài)時間較短路徑；前向關(guān)聯(lián)邊；Ｄｉｊｋｓｔｒ

１　引　言
城市路網(wǎng)動態(tài)時間較短路徑的計(jì)算，不僅要考慮交叉口之間路段上的行程時間，還需要考慮交叉口各轉(zhuǎn)向的信號相位延誤和轉(zhuǎn)向限制。因此，路網(wǎng)的存儲結(jié)構(gòu)不僅要能夠存儲路段權(quán)重，還要體現(xiàn)交叉口節(jié)點(diǎn)自身的權(quán)重。解決這個問題的一般思路是通過城市路網(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)致算法計(jì)算時間成倍增加的弊端。由此，本文采用一種改進(jìn)的前向關(guān)聯(lián)邊結(jié)構(gòu)作為存儲結(jié)構(gòu)，同時依照此結(jié)構(gòu)對Ｄｉｊｋｓｔｒａ算法進(jìn)行了改進(jìn)，并開發(fā)了東莞市動態(tài)路徑誘導(dǎo)系統(tǒng)進(jìn)行動態(tài)時間較短路徑求取的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明改進(jìn)算法能夠在不增加時間復(fù)雜度的前提下，充分考慮交叉口限向和轉(zhuǎn)向延誤，有效解決城市路網(wǎng)動態(tài)時間較短路徑問題。

登錄網(wǎng)站后可下載文件