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

(1.吉林大學(xué) 交通學(xué)院， 吉林 長(zhǎng)春 130022； 2.吉林大學(xué) 汽車仿真與控制國(guó)家重點(diǎn)實(shí)驗(yàn)室， 吉林 長(zhǎng)春 130022；

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

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

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

(1.吉林大學(xué) 交通學(xué)院， 吉林 長(zhǎng)春 130022； 2.吉林大學(xué) 汽車仿真與控制國(guó)家重點(diǎn)實(shí)驗(yàn)室， 吉林 長(zhǎng)春 130022；

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

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

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

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

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

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

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

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

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

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

圖1　路徑選擇示意圖

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

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

(1)

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

(2)

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

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

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

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

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

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

(3)

圖2　非自由右轉(zhuǎn)信號(hào)配時(shí)

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

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

(4)

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

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

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

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

假設(shè)節(jié)點(diǎn)k共有N個(gè)信號(hào)相位,信號(hào)周期為Ck,綠燈間隔時(shí)間為h,車輛到達(dá)時(shí)相序?yàn)閚,離開時(shí)相序?yàn)閙.

圖3　非右轉(zhuǎn)信號(hào)配時(shí)

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

(5)

(2)m

(6)

(7)

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

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

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

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

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

Movetype中存儲(chǔ)的值為mtk,i,j,表示經(jīng)節(jié)點(diǎn)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é)點(diǎn)k為路段i的末端節(jié)點(diǎn),Relaynode中存儲(chǔ)末端節(jié)點(diǎn)信息.Phaseorder中存儲(chǔ)由路段i至路段j通行方向在節(jié)點(diǎn)k處所屬的相序,由于相位相序僅針對(duì)非右轉(zhuǎn),故對(duì)于右轉(zhuǎn),賦值為NULL.

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

圖4　示例路網(wǎng)

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

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

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

表1　節(jié)點(diǎn)信號(hào)配時(shí)參數(shù)

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

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

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

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

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

(8)

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

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

CMTA*算法具體步驟如下:

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

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

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

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

(1)按式(9)計(jì)算弧節(jié)點(diǎn)i的到達(dá)時(shí)刻ta,k(i)：

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

(9)

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

(4)按下式計(jì)算弧節(jié)點(diǎn)j當(dāng)前實(shí)際費(fèi)用g(j):

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

(10)

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

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

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

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

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

3算例驗(yàn)證

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

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

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

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

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

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

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

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

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

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

從圖8中可看出以下兩點(diǎn):

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

表3　交叉口信號(hào)配時(shí)表

圖8　3種算法路徑總費(fèi)用對(duì)比

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

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

圖9　3種算法綜合性能對(duì)比

4結(jié)語

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

后續(xù)研究主要包括以下3個(gè)方面:①文中自由右轉(zhuǎn)平均停車時(shí)間采用實(shí)際調(diào)查統(tǒng)計(jì)數(shù)據(jù),而在大范圍路網(wǎng)條件下進(jìn)行交通調(diào)查需消耗較大的人力物力,下一步將研究自由右轉(zhuǎn)停車模型,對(duì)自由右轉(zhuǎn)的平均停車時(shí)間進(jìn)行估算;②文中算法沒有考慮交叉口協(xié)調(diào)控制的情況,下一步將針對(duì)此種情況，引入相位差參數(shù),對(duì)算法進(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]徐長(zhǎng)斌,劉艷梅.動(dòng)態(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é)報(bào)(自然科學(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]楊慶芳,梅朵.基于云計(jì)算的城市路網(wǎng)最短路徑遺傳算法求解 [J].華南理工大學(xué)學(xué)報(bào)(自然科學(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]杜長(zhǎng)海,黃希樾.改進(jìn)的蟻群算法在動(dòng)態(tài)路徑誘導(dǎo)中的應(yīng)用研究 [J].計(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]高淑萍,趙會(huì)賓.基于信號(hào)配時(shí)的動(dòng)態(tài)路徑誘導(dǎo)模型 [J].中國(guó)公路學(xué)報(bào),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é)報(bào)(自然科學(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]李繼偉.城市主次干路的路段行程時(shí)間估計(jì)與預(yù)測(cè)方法研究 [D].長(zhǎng)春:吉林大學(xué)交通學(xué)院,2012.

[12]楊帆,楊曉光.考慮信號(hào)交叉口等待時(shí)間的最短路徑算法 [J].同濟(jì)大學(xué)學(xué)報(bào)(自然科學(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

*基金項(xiàng)目:國(guó)家科技支撐計(jì)劃項(xiàng)目(2014BAG03B03)

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

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

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

中圖分類號(hào)：U 491

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