考慮信號交叉口轉(zhuǎn)向類型的最優(yōu)路徑規(guī)劃算法*

周熙陽　楊兆升,2,3　張偉,2,4?　邴其春　商強(qiáng)

(1.吉林大學(xué) 交通學(xué)院， 吉林 長春 130022； 2.吉林大學(xué) 汽車仿真與控制國家重點實驗室， 吉林 長春 130022；

3.吉林大學(xué) 吉林省道路交通重點實驗室，吉林長春 130022； 4.山東高速股份有限公司， 山東 濟(jì)南 250014)

考慮信號交叉口轉(zhuǎn)向類型的最優(yōu)路徑規(guī)劃算法*

周熙陽1楊兆升1,2,3張偉1,2,4?邴其春1商強(qiáng)1

(1.吉林大學(xué) 交通學(xué)院， 吉林 長春 130022； 2.吉林大學(xué) 汽車仿真與控制國家重點實驗室， 吉林 長春 130022；

3.吉林大學(xué) 吉林省道路交通重點實驗室，吉林長春 130022； 4.山東高速股份有限公司， 山東 濟(jì)南 250014)

摘要:針對現(xiàn)有最優(yōu)路徑規(guī)劃算法沒有充分考慮不同轉(zhuǎn)向類型的車輛在信號交叉口處的等待時間,導(dǎo)致算出的最優(yōu)路徑實際效果不佳等問題,提出了一種考慮信號交叉口轉(zhuǎn)向類型的最優(yōu)路徑規(guī)劃算法.首先,根據(jù)不同的轉(zhuǎn)向類型構(gòu)建了信號交叉口等待時間模型；然后，提出了一種改進(jìn)的星型表,對路網(wǎng)中鄰接路段之間的轉(zhuǎn)向類型與相應(yīng)參數(shù)進(jìn)行表達(dá)和存儲優(yōu)化；在此基礎(chǔ)上，提出了考慮信號交叉口轉(zhuǎn)向類型的拓展A*算法(CMTA*算法),并進(jìn)行了算例驗證.結(jié)果表明,相比于傳統(tǒng)算法和考慮信號交叉口等待時間的CWTSI-SP算法,CMTA*算法所計算出的最優(yōu)路徑時間費用更低,并且運(yùn)算效率更高.

關(guān)鍵詞：最優(yōu)路徑規(guī)劃算法；交叉口；轉(zhuǎn)向類型；等待時間；交通工程

最優(yōu)路徑規(guī)劃是智能交通誘導(dǎo)系統(tǒng)研究中的一項重要內(nèi)容.不同于一般抽象網(wǎng)絡(luò),城市路網(wǎng)包含大量動態(tài)交通信息與約束條件,研究如何在實際的城市路網(wǎng)中為駕駛員規(guī)劃最優(yōu)路徑,保證路徑行程時間最短,對提高出行效率具有重要意義.城市路網(wǎng)中,駕駛員于信號交叉口等待的時間在其行程時間中占較大比重,而大多數(shù)最優(yōu)路徑規(guī)劃算法(包括標(biāo)號法[1- 2]、啟發(fā)式算法[3- 6]等)僅考慮了路段的行程時間,導(dǎo)致所求最優(yōu)路徑與實際最優(yōu)路徑之間存在較大差異.因此,需研究考慮信號交叉口等待時間的最優(yōu)路徑規(guī)劃算法.

目前,國內(nèi)外學(xué)者主要研究將信號交叉口延誤疊加進(jìn)最優(yōu)路徑規(guī)劃算法[7- 10].信號交叉口延誤一般通過延誤模型求得.若路段劃分時將交叉口作為路段的一部分,則路段平均行程時間已包含交叉口延誤[11].但交叉口延誤只能反映車流的總體特征,通常取均值,而每一輛車的實際等待時間會因所遇信號燈狀態(tài)的不同而呈現(xiàn)出較大差異.同樣的“最優(yōu)路徑”,若某駕駛員不幸頻遇紅燈,那么對他而言,該路徑可能并非最優(yōu).針對這一問題,楊帆等[12]通過對單車信號交叉口等待時間進(jìn)行建模,提出了一種考慮信號交叉口等待時間的標(biāo)號算法(CWTSI-SP算法),并用一個算例證明該算法所求的最優(yōu)路徑更貼近駕駛員的實際情況.

但CWTSI-SP算法存在以下不足:①沒有考慮車輛在交叉口處的轉(zhuǎn)向類型.在實際中,車輛從當(dāng)前交叉口駛向同一個下游交叉口,根據(jù)來向的不同,可能進(jìn)行直行、左轉(zhuǎn)和右轉(zhuǎn),其中左轉(zhuǎn)和直行可能分屬不同的相位,而右轉(zhuǎn)因控制方式相對獨立,故不屬于任何一個相位.但CWTSI-SP算法將駛向同一個下游交叉口的車輛歸入同一個相位,與實際中的信號相位形式不符.②CWTSI-SP算法將等待時間模型疊加進(jìn)傳統(tǒng)Dijkstra算法,導(dǎo)致算法運(yùn)行時間慢于傳統(tǒng)Dijkstra算法.

針對上述方法的不足之處,文中提出了考慮信號交叉口轉(zhuǎn)向類型的最優(yōu)路徑規(guī)劃算法.首先,根據(jù)不同的轉(zhuǎn)向類型,構(gòu)建了信號交叉口等待時間模型.然后,提出了一種改進(jìn)的星型表對鄰接路段之間的轉(zhuǎn)向類型進(jìn)行表達(dá)和存儲,并在此基礎(chǔ)上設(shè)計了一種考慮信號交叉口轉(zhuǎn)向類型的拓展A*算法.

文中的研究重點為考慮不同轉(zhuǎn)向類型的最優(yōu)路徑搜索，研究的假設(shè)前提如下：①路網(wǎng)交叉口采用單點信號控制，交叉口信號周期已知且固定；②各信號相位相互獨立，且相位起始時刻已知；③路段行程時間固定.

1考慮轉(zhuǎn)向類型的信號交叉口等待時間模型

在信號交叉口,右轉(zhuǎn)車輛往往不受信號燈控制,在禮讓行人的前提下可即時通行,部分信號交叉口有專門的右轉(zhuǎn)信號燈(多見于沖突點密集的交叉口),通常紅燈時間較短.因此,當(dāng)其它通行方向因紅燈必須停車等待時,右轉(zhuǎn)車輛往往可以快速通過交叉口.在如圖1所示的路網(wǎng)中(無右轉(zhuǎn)信號燈),車輛從節(jié)點4出發(fā),經(jīng)節(jié)點5駛向節(jié)點3.當(dāng)車輛于ta時刻到達(dá)節(jié)點5時,節(jié)點5的燈態(tài)為南北直行方向綠燈,根據(jù)等待時間的不同,駕駛員有3種可能的選擇:①等待直行綠燈,路徑為5- 6- 3;②等待左轉(zhuǎn)綠燈,路徑為5- 8- 9- 6- 3;③即刻右轉(zhuǎn),路徑為5- 2- 3.

圖1　路徑選擇示意圖

機(jī)動車到達(dá)交叉口的時刻不同,所遇燈態(tài)也不同,因此等待時間隨到達(dá)時刻發(fā)生變化.

ta,k=tl,k′+ωk′,k

(1)

tl,k′=ta,k′+tw,k′

(2)

式中,ta,k為到達(dá)節(jié)點k的時刻,tl,k′為離開上游節(jié)點k′的時刻,ωk′,k為有向路段k′,k的行程時間,tw,k′為節(jié)點k′的等待時間.

由于右轉(zhuǎn)控制的特殊性,下面分右轉(zhuǎn)與非右轉(zhuǎn)兩種情況對交叉口等待時間進(jìn)行建模.

1.1右轉(zhuǎn)等待時間

將有專門信號燈控制的右轉(zhuǎn)定義為非自由右轉(zhuǎn),將沒有專門信號燈控制的右轉(zhuǎn)定義為自由右轉(zhuǎn),對兩種右轉(zhuǎn)分別進(jìn)行討論.

(1)非自由右轉(zhuǎn)

右轉(zhuǎn)信號燈的信號配時如圖2所示,若右轉(zhuǎn)車輛在紅燈期間到達(dá),等待時間為紅燈剩余時間;若右轉(zhuǎn)車輛在綠燈期間到達(dá),等待時間為0.

(3)

圖2　非自由右轉(zhuǎn)信號配時

(2)自由右轉(zhuǎn)

在自由右轉(zhuǎn)條件下,右轉(zhuǎn)車輛不受路口紅燈的限制,通常假設(shè)其tw,k為0,但在實際中,車輛右轉(zhuǎn)時需給行人與非機(jī)動車流讓行,因而會產(chǎn)生一定的隨機(jī)等待時間.由于在無信號燈控制的條件下難以對每輛右轉(zhuǎn)車的具體等待時間單獨建模,因此,文中基于實際交通數(shù)據(jù)，為自由右轉(zhuǎn)的車輛加上一個懲罰時間，從而對模型進(jìn)行修正:

(4)

自由右轉(zhuǎn)平均停車時間為自由右轉(zhuǎn)車輛在停車線處的平均停車時間,由交通調(diào)查數(shù)據(jù)統(tǒng)計獲得.處理時只統(tǒng)計在停車線處停車的右轉(zhuǎn)車輛,因為后續(xù)車輛的排隊時間仍屬于路段行程時間.

由于右轉(zhuǎn)車輛停車時間相對較短，往往能快速駛離交叉口,因此在交叉口處適當(dāng)選擇右轉(zhuǎn)可顯著縮短路徑行程時間.

1.2非右轉(zhuǎn)等待時間

非右轉(zhuǎn)車輛包含直行車輛和左轉(zhuǎn)車輛,它們共同接受信號燈控制,文獻(xiàn)[12]中證明信號相位的切換將使等待時間發(fā)生突變,但其并未考慮兩個相位之間的綠燈間隔時間(黃燈時間+全紅時間).綠燈間隔時間內(nèi)到達(dá)停車線的非右轉(zhuǎn)車輛必須停車等待,因此綠燈間隔時間將影響等待時間的突變.文中考慮綠燈間隔時間,對非右轉(zhuǎn)等待時間進(jìn)行建模.

假設(shè)節(jié)點k共有N個信號相位,信號周期為Ck,綠燈間隔時間為h,車輛到達(dá)時相序為n,離開時相序為m.

圖3　非右轉(zhuǎn)信號配時

(1)m>n時,如圖3(a)所示,車輛可以在當(dāng)前周期內(nèi)離開.

(5)

(2)m

(6)

(7)

顯然,當(dāng)m=n時,表示非右轉(zhuǎn)車輛到達(dá)交叉口即遇到綠燈,此時tw,k為0.

2考慮轉(zhuǎn)向類型的最優(yōu)路徑規(guī)劃算法

2.1路網(wǎng)模型優(yōu)化

為將文中的等待時間模型疊加進(jìn)最優(yōu)路徑規(guī)劃算法,路網(wǎng)模型必須能有效表達(dá)鄰接路段之間的轉(zhuǎn)向信息(為表述簡便,界定“直行”也屬于一種轉(zhuǎn)向情況).Anez等[13]提出了對偶圖表思想,將原圖中的弧段映射為新圖中的節(jié)點,而將原圖中節(jié)點的轉(zhuǎn)向映射為新圖中的弧段,從而表達(dá)了路段之間的轉(zhuǎn)向關(guān)系.但傳統(tǒng)表達(dá)法(鄰接矩陣、鄰接表、星型表等)無法表達(dá)出鄰接路段之間的轉(zhuǎn)向類型(非自由右轉(zhuǎn)、自由右轉(zhuǎn)、非右轉(zhuǎn)),以及其對應(yīng)的交叉口相位相序.

文中提出一種改進(jìn)的星型表,結(jié)合對偶圖思想,以路段為存儲對象,并引入3個數(shù)組:轉(zhuǎn)向類型數(shù)組(Movetype)、末端節(jié)點數(shù)組(Relaynode)和相序數(shù)組(Phaseorder),從而表達(dá)鄰接路段之間的轉(zhuǎn)向類型、發(fā)生轉(zhuǎn)向的節(jié)點以及轉(zhuǎn)向所對應(yīng)的相序.

Movetype中存儲的值為mtk,i,j,表示經(jīng)節(jié)點k由路段i駛?cè)肼范蝚方向的轉(zhuǎn)向類型:非自由右轉(zhuǎn)則mtk,i,j=1，自由右轉(zhuǎn)則mtk,i,j=2，非右轉(zhuǎn)則mtk,i,j=3.稱路段j為路段i的后繼路段,節(jié)點k為路段i的末端節(jié)點,Relaynode中存儲末端節(jié)點信息.Phaseorder中存儲由路段i至路段j通行方向在節(jié)點k處所屬的相序,由于相位相序僅針對非右轉(zhuǎn),故對于右轉(zhuǎn),賦值為NULL.

以圖4所示的有向圖為例,規(guī)定右轉(zhuǎn)(2- 1- 5)和(5- 1- 4)為非自由右轉(zhuǎn),其余右轉(zhuǎn)為自由右轉(zhuǎn),用改進(jìn)的星型表對其進(jìn)行表達(dá),如圖5所示.

圖4　示例路網(wǎng)

圖5　改進(jìn)的星型表結(jié)構(gòu)

圖5中,數(shù)組ArcID存儲路段信息,在該例中,路段13表示從節(jié)點1至節(jié)點3的路段,以此類推.數(shù)組Linkcost存儲路段權(quán)重.數(shù)組Pointer存儲指針,初始指向每一條路段的第一條后繼路段所在地址.數(shù)組PointedarcID儲存后繼路段信息,每一條路段的后繼路段按ArcID中的順序排列.以路段21為例,路段權(quán)重為5,共3條后繼路段:13、14、15,末端節(jié)點皆為節(jié)點1,故在Relaynode中皆賦值為1,指針指向路段13;21- 13為左轉(zhuǎn),對應(yīng)節(jié)點1相位2,21- 14為直行,同樣對應(yīng)節(jié)點1相位2,21- 15為非自由右轉(zhuǎn),不分相位,故在Movetype中依次賦值為3,3,1,在Phaseorder中依次賦值為2,2,NULL.由于路段13、56無后繼路段,故指針及其后續(xù)信息皆懸空,賦值為NULL.

以節(jié)點1為例,從圖5中可看出節(jié)點1共有2個相位,第1相位為51- 13,第2相位為21- 13、21- 14同時放行,因此該星型表可以表達(dá)一個相位多種通行方向的情況.節(jié)點所包含的配時參數(shù)信息如表1所示.

表1　節(jié)點信號配時參數(shù)

表1中,若節(jié)點k為自由右轉(zhuǎn)控制,則右轉(zhuǎn)信號周期與右轉(zhuǎn)綠燈時長皆賦值為NULL,若為非自由右轉(zhuǎn),則自由右轉(zhuǎn)懲罰值為NULL.黃燈時長與全紅時長之和為綠燈間隔時間,其取值由交管部門確定,一般黃燈時長3 s,全紅時長2～3 s.

結(jié)合改進(jìn)的星型表與節(jié)點配時參數(shù)表,即可完整表達(dá)與存儲鄰接路段間的轉(zhuǎn)向類型、對應(yīng)節(jié)點、對應(yīng)相序,以及對應(yīng)節(jié)點的具體配時信息,為最優(yōu)路徑規(guī)劃算法計算交叉口等待時間提供條件.同時,改進(jìn)的星型表存儲了路段與節(jié)點之間的映射關(guān)系,通過指針可快速定位到節(jié)點,從而減小搜索空間,提高算法的搜索效率.

2.2考慮轉(zhuǎn)向類型的拓展A*算法

A*算法是一種啟發(fā)式搜索算法,利用估價函數(shù)限制搜索范圍,具有搜索效率高,易于實現(xiàn)等優(yōu)點.一般的A*算法并沒有考慮信號交叉口等待時間,文中基于等待時間模型對A*算法進(jìn)行拓展,提出考慮轉(zhuǎn)向類型的A*算法(CMTA*算法).

在改進(jìn)星型表的基礎(chǔ)上,CMTA*算法由路段搜索節(jié)點.為便于描述,引入“弧節(jié)點”概念,定義如下：弧節(jié)點j即為以路段j為前驅(qū)路段的末端節(jié)點k(j).CMTA*算法的估價函數(shù)如式(8)所示.

(8)

式中,f(j)為弧節(jié)點j的估價值,g(j)為從初始弧節(jié)點j到達(dá)弧節(jié)點的實際費用,ta,k(o)為初始弧節(jié)點的到達(dá)時刻,為已知量,ta,k(j)、ta,k(i)分別為弧節(jié)點j和弧節(jié)點i的到達(dá)時刻(弧節(jié)點j為弧節(jié)點i的后繼弧節(jié)點),tl,k(i)為弧節(jié)點i的離開時刻,ωj為弧節(jié)點j的權(quán)重,即路段j的行程時間,tw,k(i)為弧節(jié)點i的交叉口等待時間,h(j)為弧節(jié)點j到目標(biāo)弧節(jié)點的估計費用,D(j)為弧節(jié)點j與目標(biāo)弧節(jié)點的歐式距離,Vmlim為路網(wǎng)最高限速值.

為保證找到最優(yōu)路徑,h(j)必須小于等于弧節(jié)點j到目標(biāo)弧節(jié)點的實際費用.由于路網(wǎng)中兩點之間的歐式距離最短,將其比上全路網(wǎng)的最高限速值,所得的行程時間必定小于實際行程時間.

CMTA*算法具體步驟如下:

步驟1初始化,將所有弧節(jié)點的估價值f和實際費用g設(shè)為無窮,清空OPEN表和CLOSE表;

步驟2將初始弧節(jié)點加入OPEN表,并作為當(dāng)前弧節(jié)點i,更新g(i)=0,然后將弧節(jié)點i從OPEN表移入CLOSE表;

步驟3將弧節(jié)點i的后繼弧節(jié)點加入OPEN表,若后繼弧節(jié)點已在CLOSE表中,則不加入;

步驟4對OPEN表中弧節(jié)點i的每一個后繼弧節(jié)點j,按以下步驟計算f(j):

(1)按式(9)計算弧節(jié)點i的到達(dá)時刻ta,k(i)：

ta,k(i)=g(i)+ta,k(o)

(9)

(2)對mtk,i,j進(jìn)行判斷:若mtk,i,j=1,按式(3)計算tw,k(i),轉(zhuǎn)步驟(4);若mtk,i,j=2,按式(4)計算tw,k(i),轉(zhuǎn)步驟(4);若mtk,i,j=3,轉(zhuǎn)步驟(3);

(4)按下式計算弧節(jié)點j當(dāng)前實際費用g(j):

g(j)=g(i)+tw,k(i)+ωj

(10)

若當(dāng)前g(j)小于原先值,則更新g(j),并按式(8)計算f(j);否則g(j)、f(j)保留原值;

步驟5對OPEN表中所有弧節(jié)點的估價值f進(jìn)行排序,選擇f最小的弧節(jié)點,將其作為當(dāng)前弧節(jié)點i,并從OPEN表移入CLOSE表;

步驟6終止條件判別,若目標(biāo)弧節(jié)點移入CLOSE表,表明找到最優(yōu)路徑,轉(zhuǎn)步驟7;若OPEN表已空,且CLOSE表中沒有目標(biāo)弧節(jié)點,表明目標(biāo)弧節(jié)點不可達(dá),沒有最優(yōu)路徑,算法終止;若非上述兩種情況,轉(zhuǎn)步驟3;

步驟7從目標(biāo)弧節(jié)點回溯,輸出最優(yōu)路徑,并順序輸出路徑上所有末端節(jié)點,算法終止.

CMTA*算法在A*算法的基礎(chǔ)上疊加了信號交叉口等待時間模型,利用A*算法的啟發(fā)性進(jìn)行有向搜索,避免了傳統(tǒng)標(biāo)號算法必須遍歷到目標(biāo)節(jié)點的缺陷,提高了路徑規(guī)劃的效率.同時,CMTA*算法充分考慮了信號交叉口的控制方式與配時參數(shù),在進(jìn)行最優(yōu)路徑規(guī)劃時根據(jù)車輛在交叉口處可能存在的各種轉(zhuǎn)向類型,分別計算相應(yīng)的交叉口等待時間,并以此作為路徑費用的一部分,是一種考慮了交通控制系統(tǒng)的誘導(dǎo)算法.

3算例驗證

以某城市試驗區(qū)路網(wǎng)為算例路網(wǎng),如圖6所示.

該路網(wǎng)包含45條路段、20個參與試驗的信號交叉口(以黃點標(biāo)出),其中十字交叉口16個,T型交叉口4個,其坐標(biāo)通過谷歌電子地圖提取.算例條件設(shè)置如下.

圖6　算例路網(wǎng)示意圖

(1)路網(wǎng)邊緣的14條路段為單向通行,以駛?cè)肼肪W(wǎng)為允許方向,其余29條路段為雙向通行,兩個方向權(quán)重相等,如表2所示.路網(wǎng)最高限速值設(shè)為70 km/h.

表2　路段權(quán)重表

(2)20個試驗交叉口中,12個交叉口為自由右轉(zhuǎn)(編號2、3、4、6、7、8、9、10、13、14、29、30),其余交叉口為非自由右轉(zhuǎn).文中通過視頻調(diào)查數(shù)據(jù)對這12個交叉口的自由右轉(zhuǎn)平均停車時間進(jìn)行統(tǒng)計,取正常工作日早高峰25個周期的均值(取整)為統(tǒng)計結(jié)果,如圖7所示.

圖7　自由右轉(zhuǎn)平均停車時間統(tǒng)計

(3)對所有試驗交叉口的相位相序作統(tǒng)一規(guī)定:十字交叉口為4相位,相位1為南北向直行,相位2為東西向直行,相位3為南北進(jìn)口左轉(zhuǎn),相位4為東西進(jìn)口左轉(zhuǎn);15、16、17三個T型交叉口為2相位,相位1為南北向直行+南進(jìn)口左轉(zhuǎn),相位2為西進(jìn)口左轉(zhuǎn);18號交叉口為2相位,相位1為南北向直行+北進(jìn)口左轉(zhuǎn),相位2為東進(jìn)口左轉(zhuǎn).

(4)設(shè)定起始點到達(dá)時刻與信號燈啟動時刻均為0,非右轉(zhuǎn)信號燈從相位1開始運(yùn)行,右轉(zhuǎn)信號燈從紅燈啟亮開始運(yùn)行.交叉口的具體配時參數(shù)如表3所示.

選擇80組具有一定距離且不在一條干線上的OD點對作為試驗OD對.將文中提出的CMTA*算法與傳統(tǒng)Dijkstra算法、文獻(xiàn)[12]提出的CWTSI- SP算法進(jìn)行對比,分別用3種算法計算出試驗OD對間的最優(yōu)路徑,然后計算每條路徑的總費用(路徑總費用=路段權(quán)重之和+路徑上所有交叉口的等待時間之和).按路徑總費用對80組試驗結(jié)果進(jìn)行排序整理,如圖8所示.

從圖8中可看出以下兩點:

1)對于同一對OD,用Dijkstra算法所計算的最優(yōu)路徑實際費用最高.這是由于Dijkstra算法并沒有考慮信號交叉口等待時間,計算出的路徑在交叉口處耗費了較多時間.其他兩種算法考慮了信號交叉口等待時間,因此計算出的路徑實際費用更低.并且,當(dāng)OD對距離增大或受信號配時影響而導(dǎo)致路徑費用升高時,CWTSI-SP算法與CMTA*算法的優(yōu)勢也愈加明顯.

表3　交叉口信號配時表

圖8　3種算法路徑總費用對比

2)與CWTSI-SP算法相比,CMTA*算法所計算的路徑實際費用更低.這是由于CWTSI-SP算法雖然考慮了信號相位,但沒有考慮綠燈間隔時間,且沒有考慮轉(zhuǎn)向類型,運(yùn)算過程中會將本向右轉(zhuǎn)歸入垂直方向直行相位或?qū)ο蜃筠D(zhuǎn)相位(由哪個相位更靠前決定),使計算結(jié)果產(chǎn)生偏差.CMTA*算法考慮了轉(zhuǎn)向類型與綠燈間隔時間,能夠準(zhǔn)確地根據(jù)轉(zhuǎn)向類型計算相應(yīng)的等待時間,使計算出的最優(yōu)路徑更符合實際.例如,第80號試驗OD對為11- 30(由西進(jìn)口進(jìn)入起點),CWTSI-SP算法所得路徑為:11- 12- 13- 14- 17- 16- 15- 30,路徑中包含3個周期較小的T型交叉口,但沒有右轉(zhuǎn),路徑費用為1 107 s,CMTA*算法所得路徑為11- 14- 9- 7- 8- 5- 15- 30,包含3個右轉(zhuǎn),路徑費用為934 s,明顯優(yōu)于CWTSI-SP算法.

圖9為3種算法的性能對比.在80條路徑的平均費用方面,CMTA*算法比Dijkstra算法降低了27.1%,比CWTSI-SP算法降低了13.7%;在80條路徑的運(yùn)算總時間方面,CMTA*算法比dijkstra算法降低了24.3%,比CWTSI-SP算法降低了34.9%.由于CWTSI-SP算法是在dijkstra算法的基礎(chǔ)上疊加等待時間模型,因此運(yùn)行時間大于一般dijkstra算法,而CMTA*算法以A*算法為基礎(chǔ),具有啟發(fā)性,且采用改進(jìn)的星型表優(yōu)化了路網(wǎng)表達(dá)與存儲結(jié)構(gòu),因此搜索效率更高.綜上所述,CMTA*算法的性能優(yōu)于其他兩種算法.

圖9　3種算法綜合性能對比

4結(jié)語

文中提出了考慮信號交叉口轉(zhuǎn)向類型的最優(yōu)路徑規(guī)劃算法.通過對不同的轉(zhuǎn)向類型進(jìn)行分析,構(gòu)建了信號交叉口等待時間模型,并提出了一種改進(jìn)的星型表,使路網(wǎng)模型能夠表達(dá)等待時間模型所需的參數(shù),并在此基礎(chǔ)上提出了基于等待時間模型的CMTA*算法.算例驗證表明，CMTA*算法的運(yùn)行效果要優(yōu)于傳統(tǒng)dijkstra算法與考慮信號交叉口等待時間的CWTSI-SP算法,不僅計算出的最優(yōu)路徑行程時間更小,且運(yùn)算時間更低.

后續(xù)研究主要包括以下3個方面:①文中自由右轉(zhuǎn)平均停車時間采用實際調(diào)查統(tǒng)計數(shù)據(jù),而在大范圍路網(wǎng)條件下進(jìn)行交通調(diào)查需消耗較大的人力物力,下一步將研究自由右轉(zhuǎn)停車模型,對自由右轉(zhuǎn)的平均停車時間進(jìn)行估算;②文中算法沒有考慮交叉口協(xié)調(diào)控制的情況,下一步將針對此種情況，引入相位差參數(shù),對算法進(jìn)行改進(jìn);③為進(jìn)一步提高算法運(yùn)行效率,下一步將研究比A*算法更為高效的算法作為依托算法.

參考文獻(xiàn)：

[1]KLUNDER G A,POST H N.The shortest path problem on large-scale real-road networks [J].Networks,2006,48(4):182- 194.

[2]徐長斌,劉艷梅.動態(tài)路徑誘導(dǎo)算法研究 [J].公路交通科技:應(yīng)用技術(shù)版,2007,10(1):35- 36.

XU Chang-bin,LIU Yan-mei.The research of algorithm on dynamic path guidance [J].Journal of High-way and Transportation Research and Development:Applied Technique,2007,10(1):35- 36.

[3]KIM Jinha,HAN Wook-Shin.Processing time-dependent shortest path queries without pre-computed speed information on road networks [J].Information Sciences,2014,255(1):135- 154.

[4]韓李濤,牟乃夏.一種基于分層結(jié)構(gòu)的最優(yōu)路徑算法 [J].山東科技大學(xué)學(xué)報(自然科學(xué)版),2013,32(3):77- 82.

HAN Li-tao,MOU Nai-xia.An optimal path algorithm based on hierarchical structure [J].Journal of Shandong University of Science and Technology(Natural Science Edition),2013,32(3):77- 82.

[5]楊慶芳,梅朵.基于云計算的城市路網(wǎng)最短路徑遺傳算法求解 [J].華南理工大學(xué)學(xué)報(自然科學(xué)版),2014,42(3):47- 58.

YANG Qing-fang,MEI Duo.Cloud computing-based genetic algorithm to solve the shortest path in urban road networks [J].Journal of South China University of Technology(Natural Science Edition),2014,42(3):47- 58.

[6]杜長海,黃希樾.改進(jìn)的蟻群算法在動態(tài)路徑誘導(dǎo)中的應(yīng)用研究 [J].計算機(jī)工程與應(yīng)用,2008,44(27):236- 239.

DU Chang-hai,HUANG Xi-yue.Study on application of improved ant colony algorithm in dynamic route guidance [J].Computer Engineering and Applications,2008,44(27):236- 239.

[7]FRANGIONI Antonio,GALLI Laura.Delay-constrained shortest paths:approximation algorithms and second-order cone models [J].Journal of Optimization Theory and Applications,2015,164(3):1051- 1077.

[8]高淑萍,趙會賓.基于信號配時的動態(tài)路徑誘導(dǎo)模型 [J].中國公路學(xué)報,2011,24(1):109- 114.

GAO Shu-ping,ZHAO Hui-bin.Dynamic route guidance model based on signal lamp time assignment [J].China Journal of Highway and Transport,2011,24(1):109- 114.[9]黃美靈,陸百川.考慮交叉口延誤的城市道路最短路徑 [J].重慶交通大學(xué)學(xué)報(自然科學(xué)版),2009,28(6):1060- 1063.

HUANG Mei-ling,LU Bai-chuan.Determination of the shortest path considering delays at intersections [J].Journal of Chongqing Jiaotong University(Natural Science Edition),2009,28(6):1060- 1063.

[10]YANG Bai-yu,MILLER Elise.Adaptive routing considering delays due to signal operations [J].Transportation Research.Part B:Methodological,2003,38(5):385- 413.

[11]李繼偉.城市主次干路的路段行程時間估計與預(yù)測方法研究 [D].長春:吉林大學(xué)交通學(xué)院,2012.

[12]楊帆,楊曉光.考慮信號交叉口等待時間的最短路徑算法 [J].同濟(jì)大學(xué)學(xué)報(自然科學(xué)版),2013,41(5):680- 686.

YANG Fan,YANG Xiao-guang.Shortest path algorithm with a consideration of waiting time at signalized intersections [J].Journal of Tongji University(Natural Science Edition),2013,41(5):680- 686.

[13]ANEZ J,DE La Barra T.Dual graph representation of transport networks [J].Transportation Research.Part B:Methodological,1996,30(3):209- 216.

Optimal Route Planning Algorithm Considering Movement Type at Signal Intersections

ZHOUXi-yang1YANGZhao-sheng1,2,3ZHANGWei1,2,4BINGQi-chun1SHANGQiang1

(1.College of Transportation, Jilin University, Changchun 130022, Jilin, China;2.State Key Laboratory of Automotive Simulation and Control, Jilin University, Changchun 130022, Jilin, China;3. Jilin Province Key Laboratory of Road Traffic, Jilin University,Changchun 130022, Jilin, China;4. Shandong High-Speed Group Co.,Ltd.,Jinan 250014, Shandong, China)

Abstract:As the existing optimal route planning algorithms do not fully consider the waiting time of vehicles with different movement types at signal intersections, no satisfactory optimal routes can be obtained. In order to solve this problem, an optimal route planning algorithm considering the movement type at signal intersections is proposed. In this algorithm, first, a waiting time model considering the movement type at signal intersections is esta-blished. Then, an improved forward star structure is constructed to optimize the representation and storage of the movement type and information in the road network. Moreover, an extended A* algorithm considering the movement type, namely CMTA* algorithm, is developed, and a case study is carried out. The results show that, as compared with the traditional algorithm and the CWTSI-SP algorithm considering the waiting time at intersections, CMTA* algorithm helps to obtain better routes with lower time cost.

Key words:optimal route planning algorithm; intersection; movement type; waiting time; traffic engineering

收稿日期:2015- 07- 22

*基金項目:國家科技支撐計劃項目(2014BAG03B03)

Foundation item:Supported by the National Key Technology Research and Development Program of the Ministry of Science and Technology of China(2014BAG03B03)

作者簡介:周熙陽(1989-),男,博士生,主要從事智能交通運(yùn)輸系統(tǒng)研究.E-mail:xyzhou@vip.126.com ?通信作者: 張偉(1978-),男,博士后,主要從事智能交通運(yùn)輸系統(tǒng)研究.E-mail:z_wei@126.com

文章編號:1000- 565X(2016)04- 0101- 08

中圖分類號：U 491

doi：10.3969/j.issn.1000-565X.2016.04.015