苗澤霖，劉 鄧，任雪晴，趙浩淋

(北方工業(yè)大學(xué)城市智能交通控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100144)

0 引言

駕駛者的路徑選擇行為導(dǎo)致的最主要的結(jié)果就是路網(wǎng)中交通流量的重新分配，交通分配是指交通需求基于已知的道路網(wǎng)絡(luò)參數(shù)信息，在路網(wǎng)上進(jìn)行規(guī)則分配，其中涉及駕駛者的路徑選擇行為和如何均衡的分配等問(wèn)題.最初研究學(xué)者大多使用全有全無(wú)(All-or-Nothing)的方法分配流量，該方法的使用場(chǎng)景為：簡(jiǎn)單的城市路網(wǎng)，車輛不會(huì)出現(xiàn)排隊(duì)等待，并且路段的時(shí)間成本不隨交通量的改變而改變.20世紀(jì)50年代，Wardrop[1]提出了網(wǎng)絡(luò)平衡分配的第1、第2原理，隨后該原理在交通流量分配中被廣泛應(yīng)用.在實(shí)際的交通出行中，人們更加青睞于通過(guò)第1種分配原理來(lái)進(jìn)行交通流量分配.隨后，Beckmann等[2]用數(shù)學(xué)語(yǔ)言描述了這一問(wèn)題，并提出相應(yīng)的數(shù)學(xué)規(guī)劃模型.LeBlanc等[3]使用Frank-Wolfe算法對(duì)規(guī)劃模型進(jìn)行求解.LeBlanc[4]通過(guò)實(shí)例驗(yàn)證了該算法用于交通流量分配的可靠性，從而形成了現(xiàn)在的實(shí)用解法.在此之后，交通工作者們又分別通過(guò)改進(jìn)Frank-Wolfe算法的搜索步長(zhǎng)和搜索方向給出了各種不同的改進(jìn)Frank-Wolfe算法[5-7]，提升算法的運(yùn)行效率.然而，在現(xiàn)實(shí)中，路網(wǎng)交通量的分配受到信號(hào)控制的影響，F(xiàn)rank-Wolfe算法無(wú)法用于求解信號(hào)控制網(wǎng)絡(luò)中的路段交通量.在信號(hào)控制網(wǎng)絡(luò)中計(jì)算最短路徑時(shí)，許多工作都涉及轉(zhuǎn)向延遲和停車延誤問(wèn)題.Ziliaskopoulos等[8]在1966年提出了一種有效的方法，對(duì)交叉口的交通流移動(dòng)進(jìn)行懲罰來(lái)解釋這些延遲.Chen and Yang[9]提出了一種計(jì)算周期性交通信號(hào)控制下的交叉口懲罰的方法，并給出了計(jì)算這樣一個(gè)網(wǎng)絡(luò)的最小時(shí)間路徑.

在現(xiàn)實(shí)中，路網(wǎng)交通量的分配受到信號(hào)控制的影響，F(xiàn)rank-Wolfe算法無(wú)法用于求解信號(hào)控制網(wǎng)絡(luò)中的路段交通量.基于此，本文考慮路網(wǎng)中交叉口信號(hào)控制的影響，在計(jì)算各個(gè)路段的阻抗函數(shù)時(shí)，把信號(hào)控制所引起的延誤作為自變量加入到其中，通過(guò)更新阻抗函數(shù)，確定OD對(duì)之間的最短路徑進(jìn)而求解出各路段相應(yīng)的路段交通量.

1 Frank-Wolfe算法

1.1 用戶平衡分配模型

1.1.1 模型中所用的變量和參數(shù)

表1 模型中所用的變量和參數(shù)

1.1.2 交通平衡分配模型

Beckmann提出的具有固定需求的用戶均衡模型(User Equilibrium，UE)如下：

(1)

(2)

(3)

(4)

本文在前者的基礎(chǔ)上把信號(hào)控制所引起的延誤作為自變量加入到路段阻抗函數(shù)ta(xa)中，得到新的阻抗函數(shù)ta=ta(xa,ψa)，其中ψa為路段a對(duì)應(yīng)的下游交叉口信號(hào)控制所引起的延誤. 使用新的阻抗函數(shù)進(jìn)行交通量分配，不僅可滿足用戶均衡原理，還可充分考慮信號(hào)配時(shí)參數(shù)對(duì)分配結(jié)果的影響.

1.2 Frank-Wolfe算法簡(jiǎn)介

Frank-Wolfe算法是一種基于迭代下降的優(yōu)化方法.該算法主要根據(jù)一組線性規(guī)劃的最優(yōu)解確定下一步的迭代方向，然后根據(jù)目標(biāo)函數(shù)的一維極值問(wèn)題求最優(yōu)迭代步長(zhǎng)，其中路段阻抗函數(shù)最為關(guān)鍵.阻抗函數(shù)是以路段流量為自變量的函數(shù)，也稱為行程時(shí)間函數(shù)，與交通量密切相關(guān).在實(shí)際情況中，路段阻抗除了受路段流量的影響之外，還受交叉口信號(hào)控制的影響，駕駛員在進(jìn)行路徑選擇時(shí)，往往會(huì)考慮到交叉口信號(hào)控制的影響.因此，為了使流量分配更符合實(shí)際需要，在改進(jìn)的算法中，將由信號(hào)控制所引起的延誤以懲罰值的形式加入到阻抗函數(shù)中.

2 改進(jìn)Frank-Wolfe算法

2.1 在阻抗函數(shù)中加入懲罰值

2.1.1 懲罰值的計(jì)算

在受信號(hào)控制的交叉口中，連續(xù)的車流由于受到信號(hào)相位的控制，因而會(huì)被暫時(shí)分開避免出現(xiàn)沖突.特定的交通流只能在特定信號(hào)相位內(nèi)被允許通行，如果在當(dāng)前的信號(hào)相位內(nèi)，車輛到達(dá)交叉口時(shí)不被允許通行，駕駛者只能等到允許通行的相位開始后才可通行.從車輛到達(dá)交叉口的那一刻到允許通行信號(hào)相位開始的這段時(shí)間，交通流想要通行的意圖是被允許的，我們將這段時(shí)間稱為這股交通流的懲罰值.本文為了計(jì)算簡(jiǎn)便，假設(shè)車輛在交叉口的等待時(shí)間不會(huì)超過(guò)1個(gè)信號(hào)周期，即路口處沒(méi)有出現(xiàn)排隊(duì)狀況.對(duì)于一股給定的交通流，懲罰值的大小取決于車輛到達(dá)交叉口的時(shí)間，我們把研究期間內(nèi)每個(gè)時(shí)刻的懲罰值構(gòu)成一個(gè)懲罰向量，隨著信號(hào)周期的重復(fù)，懲罰值也會(huì)不斷重復(fù)，因此懲罰值也是和周期時(shí)長(zhǎng)密切相關(guān)的.下面通過(guò)1個(gè)例子來(lái)說(shuō)明如何將延誤以懲罰值的形式加入到路段阻抗函數(shù)中.

車輛從交叉口A行駛到交叉口B，交叉口B為十字路口，共包含2個(gè)信號(hào)相位，相位a和相位b的持續(xù)時(shí)間分別為20 s和18 s，信號(hào)相位按照a→b→a→b的順序交替進(jìn)行循環(huán).路段AB阻抗值由2部分組成，路段AB的行駛時(shí)間和交叉口B信號(hào)控制延誤的懲罰值，不同的行駛時(shí)間對(duì)應(yīng)的懲罰值不同(見(jiàn)圖1).

圖1 交叉口相位分布和各個(gè)相位綠燈持續(xù)時(shí)間

假設(shè)相位a在t=1 s開始顯示綠燈，車輛在路段AB上的行駛時(shí)間為27 s，即在t=27有車輛由西向東駛?cè)虢徊婵贐，并計(jì)劃繼續(xù)向東行進(jìn)，該車輛只允許在相位a為綠燈時(shí)通行.在t=27 s時(shí)相位b為綠燈，相位a為紅燈.因此該車輛在t=27 s時(shí)需要等待，從開始等待到下一個(gè)周期相位a開始顯示綠燈(t=39 s)的這段時(shí)間，稱為相位a在t=39 s的懲罰值，即ψa(27)=12.所以車輛在路段AB上的阻抗值tAB=27+12=39 s.表2顯示交叉口B在不同時(shí)刻下不同相位所對(duì)應(yīng)的懲罰值.如果車輛在路段AB上的行駛時(shí)間為18 s，即t=18 s時(shí)，相位a在t=18 s的懲罰值為ψa(18)=0，車輛在路段AB上的阻抗值tAB=18+0=18 s；如果車輛在路段AB上的行駛時(shí)間為29 s，即t=29 s時(shí)，相位a在t=29 s的懲罰值為ψa(29)=10，車輛在路段AB上的阻抗值tAB=29+10=39 s.由于不同的行駛時(shí)間對(duì)應(yīng)的懲罰值不同，因此，在計(jì)算路段阻抗時(shí)，將由信號(hào)控制所引起的延誤以懲罰值的形式加入其中.

表2 所有交叉口車流所對(duì)應(yīng)的信號(hào)相位和相應(yīng)懲罰

2.1.2 在阻抗函數(shù)中加入懲罰值

車輛在進(jìn)行路徑選擇的時(shí)候，除了考慮各路段行駛時(shí)間之外，還應(yīng)該考慮在交叉口處由于信號(hào)控制而引起的等待時(shí)間.將信號(hào)控制所引起的延誤轉(zhuǎn)化為懲罰值，加入到阻抗函數(shù)中，具體做法如下：

步驟1根據(jù)交叉口的信號(hào)控制參數(shù)，計(jì)算得到各相位在不同時(shí)段的懲罰值列表TT.需要注意，在計(jì)算不同交叉口的懲罰值時(shí)應(yīng)該考慮到相鄰交叉口之間相位差的存在，相應(yīng)的相位開始時(shí)間也應(yīng)該向后延遲.

2.2 改進(jìn)Frank-Wolfe算法

考慮交叉口信號(hào)控制引起延誤的影響，改進(jìn)后的算法主要在路段阻抗的計(jì)算過(guò)程，并將延誤以懲罰值的形式加入其中，在進(jìn)行迭代優(yōu)化的過(guò)程中，使用新的阻抗函數(shù)選擇最短路徑. 交通路網(wǎng)中所有的信號(hào)控制參數(shù)都是提前知道的，各OD對(duì)之間的路徑也是已知的. 在使用改進(jìn)Frank-Wolfe算法分配交通流之前，先計(jì)算各交叉口的懲罰值列表TT.將信號(hào)控制所引起的延誤轉(zhuǎn)化為懲罰值，加入到阻抗函數(shù)的計(jì)算中，之后在進(jìn)行路段流量分配. 步驟如下：

3 算法復(fù)雜度分析

計(jì)算時(shí)間復(fù)雜度，假設(shè)交通網(wǎng)絡(luò)交叉口個(gè)數(shù)為n，OD對(duì)的個(gè)數(shù)為g，在求解交通流量分配時(shí)的迭代數(shù)為l，步驟3中求解最短路徑，時(shí)間復(fù)雜度為O(n2)，原Frank-Wolfe算法的時(shí)間復(fù)雜度為O(gln2). 將懲罰值加入到計(jì)算阻抗函數(shù)的過(guò)程中之后，OD間的所有路徑的最大個(gè)數(shù)仍然為n(n-1)，因此改進(jìn)Frank-Wolfe算法的時(shí)間復(fù)雜度沒(méi)有變化，仍然為O(gln2).

4 算例分析

4.1 仿真案例

為了驗(yàn)證改進(jìn)算法的有效性，通過(guò)下列算例來(lái)進(jìn)行分析和說(shuō)明. 路口網(wǎng)絡(luò)圖見(jiàn)圖2. 圖3中各個(gè)路段的相關(guān)參數(shù)見(jiàn)表3. 路網(wǎng)共有4個(gè)起點(diǎn)(o1=1，o2=2，o3=3和o4=4)，2個(gè)終點(diǎn)(d1=5和d2=6)，4個(gè)OD對(duì)(1→6、2→5、3→6、4→5)，且OD矩陣Q為：

表3 交通路網(wǎng)的路段參數(shù)

圖2 網(wǎng)絡(luò)簡(jiǎn)圖

模擬1個(gè)受信號(hào)控制的交通網(wǎng)絡(luò)，包含6個(gè)交叉口和14條道路，其中6個(gè)交叉口均受交通信號(hào)控制，車道和其相應(yīng)的相位如圖3所示. 各交叉口均為兩相位交叉口，各個(gè)交叉口信號(hào)控制參數(shù)見(jiàn)表4. 為了便于計(jì)算，假設(shè)每條路段的通行能力相同，且Ca=950 veh/h；每個(gè)交叉口的總損失時(shí)間相同，Li=10 s.

表4 交叉口信號(hào)控制參數(shù)

圖3 算例網(wǎng)絡(luò)

4.2 案例計(jì)算

根據(jù)交通路網(wǎng)信息和信號(hào)控制參數(shù)，先計(jì)算各交叉口各相位對(duì)應(yīng)的懲罰值，由此得到懲罰值列表TT. 根據(jù)該列表，通過(guò)算法計(jì)算，可得到圖2所示網(wǎng)絡(luò)中各個(gè)OD對(duì)的最短路徑集合. 對(duì)于OD對(duì)16來(lái)說(shuō)，最短路徑為：1→2→4→6，u16=75；對(duì)于OD對(duì)25來(lái)說(shuō)，最短路徑為：2→1→3→5，u25=99；對(duì)于OD對(duì)36來(lái)說(shuō)，最短路徑為：3→4→6，u36=53；對(duì)于OD對(duì)45來(lái)說(shuō)，最短路徑為：4→3→5，u45=90. 然后根據(jù)所求得的最短路徑進(jìn)行路段流量分配，算法運(yùn)行共迭代15次，滿足設(shè)置終止條件(ε=0.005)，所得各個(gè)路段交通量的最終結(jié)果見(jiàn)表5，流量數(shù)據(jù)保留到整數(shù).

4.3 結(jié)果分析

通過(guò)MATLB編程，采用原Frank-Wolfe算法，即不考慮交叉口信號(hào)控制對(duì)流量分配的影響，在相同的路網(wǎng)結(jié)構(gòu)和OD交通需求下求解上述算例，結(jié)果如表5所示，Δxa表示相同路網(wǎng)結(jié)構(gòu)和OD交通需求下改進(jìn)后的Frank-Wolfe算法和原Frank-Wolfe算法所得路段交通量的差值.

表5 改進(jìn)算法計(jì)算所得的各路段的流量

結(jié)果表明，改進(jìn)后的Frank-Wolfe算法和原Frank-Wolfe算法所得路段交通量存在較大的差別.如表6和表7所示，路段b連接交叉口1和交叉口3，在使用原算法求解時(shí)，OD對(duì)25的最短路徑為2→1→3→5，OD對(duì)16的最短路徑為1→3→5→6，均包含路段b；在使用改進(jìn)算法求解時(shí),考慮到交叉口3信號(hào)控制的影響，在進(jìn)行交通流分配時(shí)交叉口1到交叉口3的時(shí)間成本增加，因此OD對(duì)16不選擇路段b，而轉(zhuǎn)為選擇出行時(shí)間成本相對(duì)較小的路段c，所以路段b的流量采用改進(jìn)后的算法減少47(veh)，而路段c的流量采用改進(jìn)后的算法增加49(veh).路段g連接交叉口3和交叉口5，使用原算法求解時(shí)，OD對(duì)25、OD對(duì)45、OD對(duì)16、OD對(duì)36的最短路徑均包含路段g；在使用改進(jìn)算法求解時(shí),考慮到交叉口5信號(hào)控制的影響，在進(jìn)行交通流分配時(shí)交叉口3到交叉口5的時(shí)間成本增加，因此OD對(duì)16選擇路段d ，OD對(duì)36選擇路段i，因此路段g的流量采用改進(jìn)后的算法減少45(veh)，而路段d的流量增加47(veh).

表6 原算法計(jì)算所得的各路段的流量

除了各路段流量發(fā)生變化外，各個(gè)OD對(duì)之間最短路徑的阻抗值也發(fā)生變化.如表7所示，在使用改進(jìn)Frank-Wolfe算法求解后最短路徑的阻抗值均大于原Frank-Wolfe算法所得結(jié)果，是因?yàn)樵谇蠼庾杩购瘮?shù)時(shí)，考慮了信號(hào)控制延誤的影響，所以阻抗值增加.因此，通過(guò)各個(gè)路段流量和路徑阻抗之間的對(duì)比分析，說(shuō)明交叉口信號(hào)配時(shí)對(duì)交通流量分配具有較大的影響，因此在進(jìn)行流量分配時(shí)考慮交叉口信號(hào)控制引起的延誤，所得的結(jié)果更加符合實(shí)際的交通流分布情況.

表7 最短路徑比較

5 結(jié)束語(yǔ)

本文考慮了路網(wǎng)在受到交叉口信號(hào)控制的影響下，如何進(jìn)行交通流分配.與其他求解算法不同的是，該算法在求解最短路徑的時(shí)候考慮到交叉口信號(hào)控制引起的延誤，并將其以懲罰值的形式加入到計(jì)算過(guò)程中，通過(guò)算法分析和算例驗(yàn)證，得出以下結(jié)論：

1)將由交叉口信號(hào)控制所引起的延誤以懲罰值的形式加入到最短路徑的求解過(guò)程中，所得的結(jié)果更加符合實(shí)際的交通流分布情況.

2)基于路網(wǎng)中信號(hào)控制對(duì)車輛的影響，對(duì)原Frank-Wolfe算法進(jìn)行改進(jìn)，考慮路網(wǎng)中交叉口信號(hào)控制的影響，將由信號(hào)控制所引起的延誤以懲罰值的形式加入到阻抗函數(shù)中，通過(guò)更新阻抗函數(shù)，確定OD對(duì)間的最短路徑進(jìn)而求解出各路段相應(yīng)的路段交通量.

由于交通系統(tǒng)本身的復(fù)雜性和不確定性，研究的過(guò)程中還存在著許多不足，今后需從以下幾個(gè)方面繼續(xù)研究和關(guān)注：

1)該算法僅得到各個(gè)路段的交通量，需要經(jīng)過(guò)進(jìn)一步的計(jì)算才能得到路徑交通量.

2)為了計(jì)算簡(jiǎn)便，在計(jì)算的過(guò)程中假設(shè)車輛在交叉口的等待時(shí)間不會(huì)超過(guò)1個(gè)信號(hào)周期.在之后的研究中，可將車輛在交叉口的等待時(shí)間超過(guò)1個(gè)信號(hào)周期情況考慮進(jìn)去.

3)交通流分配方面.由于交通流在路網(wǎng)中是實(shí)時(shí)變化的，并且交通需求也不是固定不變的，所以可考慮建立動(dòng)態(tài)交通流分配模型.