梅 朵 袁夢柯 鄭黎黎 鄂 旭

(渤海大學(xué)信息科學(xué)與技術(shù)學(xué)院1) 錦州 121013) (吉林大學(xué)交通學(xué)院2) 長春 130012)

0 引 言

交通信號(hào)控制和交通誘導(dǎo)是解決城市交通擁堵的主要手段.然而單一的交通信號(hào)控制只能在時(shí)間上改變交通流的分布，單一的交通誘導(dǎo)只能在空間上均衡交通流，因此，交通信號(hào)控制與交通誘導(dǎo)協(xié)同運(yùn)作才能有效緩解城市交通擁堵，保證城市交通順暢.

Li等[1]采用仿真方法研究的VMS和交通信號(hào)控制系統(tǒng)協(xié)同問題.保麗霞等[2]提出的雙目標(biāo)協(xié)同模型.徐立群[3]提出的一體化協(xié)同模型.孫智源等[4]提出的雙層規(guī)劃模型.通過分析發(fā)現(xiàn)，交通信號(hào)控制與交通誘導(dǎo)的協(xié)同時(shí)機(jī)有兩種情況：①通過預(yù)測交通流設(shè)計(jì)高峰時(shí)段的預(yù)先協(xié)同方案；②通過實(shí)時(shí)交通流設(shè)計(jì)擁堵發(fā)生中的協(xié)同方案[5-7].文中針對第一種情況，研究城市區(qū)域范圍內(nèi)的交通信號(hào)控制與交通誘導(dǎo)的預(yù)先協(xié)同優(yōu)化，引入飽和度、有效綠燈時(shí)長、周期時(shí)長和相位差作為約束，構(gòu)建了一種城市區(qū)域交通信號(hào)控制與誘導(dǎo)協(xié)同的一體化模型，提出了一種基于MapReduce的并行遺傳算法對所提出的協(xié)同模型進(jìn)行求解，并基于VISSIM仿真數(shù)據(jù)驗(yàn)證所提出的協(xié)同模型和求解算法的有效性和可行性.

1 問題描述

城市道路網(wǎng)是一個(gè)復(fù)雜的大系統(tǒng)，具有動(dòng)態(tài)性、復(fù)雜性，也具有規(guī)律性.每天的早晚高峰時(shí)段，隨著交通需求的不斷增加，路網(wǎng)容量不能滿足需求，一些脆弱的交叉口和路段首先發(fā)生交通擁堵，如果不能進(jìn)行行之有效的處理，極易出現(xiàn)交通流量上溢，造成區(qū)域交通擁堵.為了避免發(fā)生區(qū)域交通擁堵，在日常交通信號(hào)控制的基礎(chǔ)上，有效監(jiān)控路網(wǎng)的實(shí)時(shí)交通流參數(shù)，如果發(fā)現(xiàn)某些交叉口或路段的流量變大、運(yùn)行速度降低、排隊(duì)長度增加，則說明該交叉口或路段發(fā)生交通擁擠，當(dāng)即將形成區(qū)域交通擁堵時(shí)，啟動(dòng)交通控制與誘導(dǎo)協(xié)調(diào)方案，避免區(qū)域交通擁堵的發(fā)生.

文中所提出的交通控制與誘導(dǎo)協(xié)同方案的基本思想是：①從交通控制角度出發(fā)，通過不斷優(yōu)化擁堵路段上下游交叉口的信號(hào)配時(shí)參數(shù)，及時(shí)有效地降低路段上的交通量，避免路段上的排隊(duì)長度增加；②從交通誘導(dǎo)角度出發(fā)，有效均衡整個(gè)路網(wǎng)的交通量，保證所有路段的總行程時(shí)間最小.

2 模型建立

在建模時(shí)，充分考慮了交通管理者和駕駛員的目標(biāo)，以“準(zhǔn)系統(tǒng)最優(yōu)”的指導(dǎo)思想為原則，構(gòu)建區(qū)域交通控制與誘導(dǎo)協(xié)同模型[8].文中所構(gòu)建的區(qū)域交通控制與誘導(dǎo)協(xié)同模型的目標(biāo)函數(shù)如下.

(1)

式中：a為某路段；A(i)為從某節(jié)點(diǎn)到以節(jié)點(diǎn)i的所有弧段總和；xa(t)為t時(shí)刻a上的流量；ta(t)為t時(shí)刻a上車輛的總行程時(shí)間.

一方面從交通管理者的角度出發(fā)，考慮整個(gè)交通網(wǎng)絡(luò)的總行程時(shí)間最小，保證交通網(wǎng)絡(luò)系統(tǒng)流量均衡；另一方面從駕駛員的角度出發(fā)，實(shí)時(shí)調(diào)整交通信號(hào)配時(shí)，迅速卸載路段上的流量.

2.1 行程時(shí)間的表達(dá)

行程時(shí)間由兩部分構(gòu)成：車輛在路段上的運(yùn)行時(shí)間ta,r(t)和車輛通過交叉口的時(shí)間ta,s(t).

當(dāng)路網(wǎng)處于暢通條件時(shí)，

ta,r(t)=Lj/?i

(2)

式中：Lj為路段j的長度；?i為時(shí)間段i內(nèi)，路段j的平均速度的預(yù)測值.

當(dāng)路網(wǎng)處于擁擠條件時(shí)，路段上會(huì)出現(xiàn)排隊(duì)車輛，ta,r(t)等于自由流行駛時(shí)間ta,r,f(t)和擁擠行駛時(shí)間ta,r,c(t)的總和.假設(shè)駕駛員的反應(yīng)時(shí)間和啟動(dòng)加速時(shí)間忽略不計(jì)，自由流行駛時(shí)間為

(3)

式中：Lj為路段j的長度；Lij為實(shí)時(shí)采集的排隊(duì)長度；?i為平均速度的預(yù)測值.

(4)

關(guān)于車輛通過交叉口的時(shí)間ta,s(t)，文中采用修正后的HCM2010進(jìn)行計(jì)算求得.

2.2 約束條件

1) 飽和度 當(dāng)區(qū)域路網(wǎng)的平均飽和度和飽和度方差都比較高的時(shí)候，表明路網(wǎng)中存在交通擁堵，因此路網(wǎng)的平均飽和度和飽和度方差應(yīng)該都小于一定閾值.

(5)

(6)

(7)

2) 有效綠燈時(shí)長 從行人過街的安全性方面考慮，交叉口所有相位的有效綠燈時(shí)長參數(shù)不得小于一個(gè)閾值e(一般e≤6 s)，交叉口所有相位的信號(hào)配時(shí)參數(shù)還應(yīng)該滿足以下條件.

e≤gi≤T-(m-1)e,i=1,2,…,m

(8)

式中：m為交叉口的相位數(shù)；T為路網(wǎng)協(xié)同區(qū)域的統(tǒng)一周期時(shí)長；gi為相位i的有效綠燈時(shí)長.

3) 周期時(shí)長 從駕駛員的心理承受能力方面考慮，在設(shè)計(jì)路網(wǎng)協(xié)同區(qū)域范圍內(nèi)的所有交叉口的統(tǒng)一周期時(shí)長時(shí)，需要滿足以下條件[9].另一方面，因?yàn)轭l繁變換周期時(shí)長會(huì)造成交通混亂，所以路網(wǎng)協(xié)同區(qū)域范圍內(nèi)的所有交叉口的統(tǒng)一周期時(shí)長取各個(gè)交叉口周期時(shí)長的最大值[10].

30≤T≤200,C=max{T1,T2,…,Tn}

(9)

式中：n為協(xié)同區(qū)域內(nèi)交叉口的個(gè)數(shù)；Ti為交叉口i的信號(hào)周期時(shí)長，Ti通過Webster方法獲得，

(10)

(11)

式中：L為損失時(shí)間，s；Y為各個(gè)信號(hào)相位中的總流量比；yj為相位j的流量比；qd為設(shè)計(jì)交通量，pcu/h；Sd為設(shè)計(jì)飽和流量，pcu/h.

4) 相位差 在協(xié)同控制中，相位差是一個(gè)重要參數(shù)，交叉口i到j(luò)的上行相位差ψ上和交叉口j到i的下行相位差ψ下必須滿足下列條件.

(12)

式中：T為協(xié)同區(qū)域范圍內(nèi)統(tǒng)一周期時(shí)長.

綜上，本文構(gòu)建的區(qū)域交通控制與誘導(dǎo)協(xié)同優(yōu)化模型為

(13)

3 求解算法

3.1 染色體編碼和解碼

構(gòu)建的協(xié)同模型包括流量[x1,…xn1]、綠燈時(shí)長[g1,…gn2]和相位差[ψ1,…ψn3]三個(gè)參數(shù)，n=n1+n2+n3為參數(shù)數(shù)目，采用二進(jìn)制編碼方法進(jìn)行編碼，其編碼公式為[11]

(14)

采用二進(jìn)制編碼方法對參數(shù)x、g和ψ進(jìn)行編碼，設(shè)l1、l2和l3為編碼長度，那么l1+l2+l3即為染色體的總長度，解碼公式為

(15)

(16)

(17)

3.2 適應(yīng)度函數(shù)確定

合理的適應(yīng)度函數(shù)可以提高算法的效率和求解解的質(zhì)量[12].基于“界限構(gòu)建法”確定適應(yīng)度函數(shù)為

(18)

該適應(yīng)度函數(shù)可以保證遺傳操作中的概率非負(fù)，也可以避免出現(xiàn)因函數(shù)值差距大引起的種群平均性能變?nèi)醯默F(xiàn)象.

3.3 遺傳操作算子

1) 選擇操作算子 通過選擇運(yùn)算，選出適應(yīng)度值高的個(gè)體，并遺傳給下一代.文中的選擇運(yùn)算采用輪盤賭法，則適應(yīng)度值為f(i)的個(gè)體被選擇的概率為

(19)

2) 交叉和變異操作算子 交叉運(yùn)算采用單點(diǎn)交叉法，即先確定交叉點(diǎn)區(qū)域，再確定交叉點(diǎn)，然后進(jìn)行運(yùn)算，生成新個(gè)體[13].變異操作盡可能地淘汰較差的個(gè)體，提高遺傳算法的全局搜索能力.變異操作運(yùn)算選擇基本位變異法，先根據(jù)變異概率確定變異節(jié)點(diǎn)，然后進(jìn)行基因變換，形成新個(gè)體.為盡量保存優(yōu)秀個(gè)體，采用自適應(yīng)交叉概率和變異概率函數(shù)確定變異點(diǎn).具體函數(shù)分別為

(20)

(21)

3.4 協(xié)同模型求解

文中設(shè)計(jì)的基于MapReduce的并行遺傳算法采用8臺(tái)計(jì)算機(jī)搭建Hadoop并行計(jì)算平臺(tái).所設(shè)計(jì)的算法的詳細(xì)步驟如下.

步驟1種群初始化 主機(jī)器對種群進(jìn)行初始化，并設(shè)置相應(yīng)的參數(shù)，即種群大小M、染色體長度n和進(jìn)化代數(shù)N.主機(jī)器將相應(yīng)的參數(shù)分配到從機(jī)器上去.

步驟2對染色體進(jìn)行二進(jìn)制編碼 主機(jī)器在參數(shù)取值范圍內(nèi)隨機(jī)生成種群大小的染色體，并均分成M個(gè)子種群，分配給M個(gè)從機(jī)器.

步驟3染色體解碼 以子種群編號(hào)為鍵，以染色體為值，組成鍵值對.每個(gè)從機(jī)器分別調(diào)用Map函數(shù)，對所有染色體進(jìn)行解碼，從而得到x1,…,xn1的值.

步驟4計(jì)算信號(hào)周期 每個(gè)從機(jī)器分別調(diào)用Map函數(shù)，通過Webster法求得每個(gè)信號(hào)交叉口的周期時(shí)長.根據(jù)最大值原則，確定周期時(shí)長的最大值為公共信號(hào)周期時(shí)長T=max{T1,T2,…,Tn}.

步驟5染色體解碼，得到T每個(gè)從機(jī)器分別調(diào)用Map函數(shù)，采用公式(16)和(17)對染色體的后幾位進(jìn)行解碼，求得[g1,…,gn2]、[ψ1,…,ψn3]的值.

步驟7計(jì)算適應(yīng)度值 每個(gè)從機(jī)器分別調(diào)用Map函數(shù)計(jì)算適應(yīng)度值，并按照鍵的不同，對其值進(jìn)行歸約，得到各個(gè)小的數(shù)據(jù)集合，并將其保存到本地的HDFS中.

步驟8算法結(jié)束條件判斷 通過設(shè)置最大進(jìn)化代數(shù)N，來判斷是否結(jié)束算法.如果達(dá)到最大進(jìn)化代數(shù)，則輸出最優(yōu)值J,x,g,ψ,T；否則，跳到步驟10.

步驟9選擇運(yùn)算 主機(jī)器確定中間結(jié)果的位置，并通知Reduce函數(shù).從機(jī)器調(diào)用Reduce函數(shù)，采用輪盤賭法從中間結(jié)果中選擇適應(yīng)度值較高的個(gè)體遺傳給下一代.

步驟10交叉和變異運(yùn)算 從機(jī)器調(diào)用Reduce函數(shù)，運(yùn)用單點(diǎn)交叉法進(jìn)行交叉運(yùn)算，采用基本位變異法進(jìn)行變異運(yùn)算.最終得到的新一代個(gè)體存儲(chǔ)到HDFS中，返回步驟4.

步驟11算法終止條件判斷 當(dāng)算法運(yùn)行到最大進(jìn)化代數(shù)N時(shí)，得到最優(yōu)的J,x,g,ψ,T值，算法終止.

4 仿真模擬驗(yàn)證

以長春市新民大街-自由大路-人民大街-解放大路所構(gòu)成的區(qū)域路網(wǎng)的交通參數(shù)數(shù)據(jù)為基礎(chǔ)，通過VISSIM仿真軟件搭建圖1的區(qū)域路網(wǎng).

圖1 試驗(yàn)路網(wǎng)

在區(qū)域路網(wǎng)中，交叉口6、8的信號(hào)配時(shí)參數(shù)為(C，g)=(80 s，37 s)，其余交叉口的信號(hào)配時(shí)參數(shù)為(C，g)=(90 s，42 s).仿真數(shù)據(jù)獲取時(shí)間為10 800 s，通過流量不斷增加，將仿真時(shí)間劃分為6個(gè)時(shí)間段，并在交叉口入口道的上游30～40 m處設(shè)置檢測器，每300 s完成一次交通參數(shù)數(shù)據(jù)的采集.

4.1 算法參數(shù)設(shè)置

在實(shí)驗(yàn)過程中，分別取Hadoop并行平臺(tái)的2、4、6、8個(gè)節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn).設(shè)置相同的串行算法和并行算法的參數(shù)：區(qū)域交通控制與誘導(dǎo)協(xié)同模型中涉及的參數(shù)有流量x1,…,x34、綠燈時(shí)長g1,…,g12、上行相位差ψ1,…,ψ12和下行相位差，其中，下行相位差可由周期和上行相位差做差得到.因此，算法的一條染色體包括58個(gè)變量，其長度為l=l1+l2+l3=12×34+6×12+7×12=564.種群規(guī)模：M=200；最大迭代代數(shù)：N=200；交叉概率Pc(i)和變異概率Pm(i)：通過自適應(yīng)函數(shù)不斷調(diào)整的自適應(yīng)的概率.

4.2 實(shí)驗(yàn)結(jié)果與分析

運(yùn)行VISSIM仿真軟件，不斷觀測區(qū)域路網(wǎng)的交通流量變化情況.通過交通流量持續(xù)增加，路網(wǎng)中車輛的運(yùn)行速度減慢，并出現(xiàn)排隊(duì)長度.當(dāng)VISSIM仿真進(jìn)行到7 200 s時(shí)，區(qū)域路網(wǎng)中某些路段的排隊(duì)長度比大于0.3，由此判斷區(qū)域路網(wǎng)處于交通擁堵狀態(tài)，實(shí)行區(qū)域交通控制與誘導(dǎo)協(xié)同.

1) 實(shí)施協(xié)同 通過VISSIM仿真軟件采集7 200～7 500 s的路網(wǎng)交通參數(shù)數(shù)據(jù)，并將其作為串行遺傳算法和并行遺傳算法的輸入，運(yùn)行程序獲得交通控制與誘導(dǎo)的參數(shù)值，見表1～2.由表1～2可知：兩種算法在求解交通參數(shù)時(shí)得到的結(jié)果差異不大，但是在求解總行程時(shí)間時(shí)，明顯看出并行算法的優(yōu)勢，因?yàn)椴⑿兴惴◤浹a(bǔ)了遺傳算法的缺陷，提高了最優(yōu)解的質(zhì)量.

表1 信號(hào)配時(shí)參數(shù)求解結(jié)果

表2 路段參數(shù)求解結(jié)果

圖2為實(shí)施交通控制與誘導(dǎo)協(xié)同后的區(qū)域路網(wǎng)各路段的流量對比圖和行程時(shí)間對比圖.由圖2a)可知，通過實(shí)施協(xié)同，協(xié)同前比較擁擠的路段上的流量被分配到其他的路段上，從而避免該路段上的擁擠蔓延，說明實(shí)施協(xié)同有效地均衡了整個(gè)區(qū)域路網(wǎng)的流量.由圖2b)可知，通過實(shí)施協(xié)同，減少了區(qū)域路網(wǎng)中各路段的行程時(shí)間，從而減少了整個(gè)路網(wǎng)的總行程時(shí)間，說明所提出模型具有有效性.

圖2 協(xié)同前后流量和行程時(shí)間對比圖

圖3～4為基于MapReduce的遺傳算法求解模型的運(yùn)行時(shí)間對比圖和加速比曲線圖，其中并行節(jié)點(diǎn)數(shù)=1時(shí)是串行算法.由圖3可知，當(dāng)并行節(jié)點(diǎn)數(shù)=2時(shí)，運(yùn)行時(shí)間減少的并不多，因?yàn)椴⑿兴惴ǖ腗ap階段用時(shí)比較長，并行節(jié)點(diǎn)數(shù)過少，并不能明顯提高算法的運(yùn)行速度.然而，當(dāng)并行節(jié)點(diǎn)數(shù)=4和并行節(jié)點(diǎn)數(shù)=6時(shí)，明顯看出運(yùn)行時(shí)間減小的幅度不斷增大，說明并行算法優(yōu)勢表現(xiàn)出來了.但是，當(dāng)并行節(jié)點(diǎn)數(shù)=8時(shí)，運(yùn)行時(shí)間減少的幅度又變小了，主要因?yàn)椴⑿泄?jié)點(diǎn)數(shù)的增加會(huì)導(dǎo)致節(jié)點(diǎn)之間的通信負(fù)荷增大，可見并行節(jié)點(diǎn)數(shù)的選取要因情況而定，通過不斷實(shí)驗(yàn)和反復(fù)對比，選擇合適的并行節(jié)點(diǎn)數(shù)，從而提高并行算法的效率.由圖4可知，通過不斷增加并行節(jié)點(diǎn)數(shù)，并行算法的加速比不斷提高，證明所提出的并行遺傳算法具有良好的擴(kuò)展性.當(dāng)并行節(jié)點(diǎn)數(shù)=8時(shí)，取得最大加速比：S8=238.35 s/39.26 s=6.12，即當(dāng)并行節(jié)點(diǎn)數(shù)=8時(shí)，并行算法比串行算法快6倍多，最小運(yùn)行時(shí)間38.64 s，滿足區(qū)域路網(wǎng)交通控制與誘導(dǎo)的需求.

圖3 運(yùn)行時(shí)間對比圖

圖4 加速比曲線圖

5 結(jié) 束 語

以區(qū)域路網(wǎng)總行程時(shí)間最小為目標(biāo)，構(gòu)建了交通控制與誘導(dǎo)協(xié)同模型.①在計(jì)算行程時(shí)間時(shí)，通過引入排隊(duì)長度參數(shù)，對行程時(shí)間進(jìn)行了更有效的表達(dá)，使計(jì)算得到的行程時(shí)間更加準(zhǔn)確；②在建立模型約束條件時(shí)，通過引入排隊(duì)長度參數(shù)，更好地對相位差和有效綠燈時(shí)長進(jìn)行了約束，使模型求得的參數(shù)更加準(zhǔn)確.為了進(jìn)一步提高協(xié)同模型的求解速度，文中采用基于MapReduce的并行遺傳算法求解協(xié)同模型，通過實(shí)驗(yàn)發(fā)現(xiàn)，所提出的并行遺傳算法在求解協(xié)同模型時(shí)的運(yùn)行速度和所求得解的質(zhì)量均有所提高，從而驗(yàn)證了所提出的協(xié)同模型和并行求解算法的有效性和可行性.