摘  要： 傳統(tǒng)的OD矩陣估計(jì)方法大部分都是基于路段流量的，由于路段流量數(shù)目遠(yuǎn)小于OD對(duì)的個(gè)數(shù)，因而限制了這些方法的推算精度。針對(duì)擁堵路網(wǎng)，提出了一種基于路段轉(zhuǎn)向流量的OD估計(jì)方法，以提高OD估計(jì)的精度。分析了路段轉(zhuǎn)向流量能夠降低OD的可行解集的范圍。通過雙層規(guī)劃模型求解擁擠路網(wǎng)上OD估計(jì)問題。由于最大熵模型不依賴于先驗(yàn)OD矩陣，可以應(yīng)用到更多的OD估計(jì)場(chǎng)景中，因此上層模型采用的是最大熵模型，下層采用用戶均衡模型。實(shí)驗(yàn)結(jié)果表明：基于路段轉(zhuǎn)向流量可以增加估計(jì)的精度。

　　關(guān)鍵詞： OD矩陣估計(jì)；路段轉(zhuǎn)向流量；最大熵模型；用戶均衡模型；雙層規(guī)劃模型

0 引言

　　OD矩陣（Origin-Destination matrix），描述了一段時(shí)間內(nèi)交通網(wǎng)絡(luò)的所有起點(diǎn)到終點(diǎn)的交通出行量，反映了交通出行者對(duì)交通網(wǎng)絡(luò)的基本需求。OD矩陣是城市交通規(guī)劃、控制、交通流預(yù)測(cè)和智能交通系統(tǒng)[1]等的重要基礎(chǔ)數(shù)據(jù)。而獲取OD矩陣的傳統(tǒng)方法需要非常大的時(shí)間成本和經(jīng)濟(jì)成本。一種替代的方法就是通過更易獲取的路段流量和相關(guān)信息等來估計(jì)OD矩陣。

　　近幾十年，已經(jīng)有許多模型被開發(fā)出來用于OD估計(jì)，如最大熵模型[2]、廣義最小二乘模型[3]、貝葉斯統(tǒng)計(jì)推斷模型[4]和極大似然模型[5]等。上述的幾種模型都將交通分配矩陣作為常量處理，即交通出行者的路徑選擇行為與OD矩陣無關(guān)，這種方法只適合擁擠效應(yīng)不明顯的路網(wǎng)，一般是交通量較小的路網(wǎng)。而在實(shí)際情況中，許多路網(wǎng)都是擁擠路網(wǎng)。擁擠路網(wǎng)的交通分配模型更加接近于用戶均衡模型（UE）[6]，交通出行者的路徑選擇受OD矩陣的影響，即不同的OD矩陣會(huì)產(chǎn)生不同的交通分配矩陣。YANG H提出了將OD估計(jì)和交通分配過程進(jìn)行綜合考慮的雙層規(guī)劃模型[7]。在雙層規(guī)劃模型中，交通分配矩陣由模型本身確定，不是給定的常量，非常適合擁擠路網(wǎng)的OD估計(jì)問題。以上方法均是基于路段流量，通常情況下，由于路段流量的個(gè)數(shù)遠(yuǎn)小于OD對(duì)個(gè)數(shù)，OD矩陣可行解集較大，限制了OD估計(jì)的精度。于凱在最大熵模型中引入路段轉(zhuǎn)向流量[8]，增加了模型的估計(jì)精度，但是模型基于不變的分配矩陣，不適用于擁擠網(wǎng)絡(luò)。

　　近年來，一些新的觀測(cè)手段用于OD估計(jì)，比如手機(jī)信息、GPS信息，這些信息可以增加OD估計(jì)的精度，但是不易獲取而限制了其應(yīng)用。通過傳統(tǒng)方法進(jìn)行OD估計(jì)仍然為目前的主要方法，本文基于易于獲得的路段轉(zhuǎn)向流量，提出了一種基于路段轉(zhuǎn)向流量的OD估計(jì)雙層規(guī)劃模型。仿真實(shí)驗(yàn)表明：該方法可以提高擁擠路網(wǎng)OD估計(jì)的精度。

1 基于路段轉(zhuǎn)向流量的OD估計(jì)模型

　　1.1 OD估計(jì)基本原理

　　交通網(wǎng)絡(luò)可以用一個(gè)有向圖G（V，E）表示，V為所有路段的集合，E為所有節(jié)點(diǎn)的集合。假設(shè)交通網(wǎng)絡(luò)有m個(gè)路段觀測(cè)流量，n個(gè)待估計(jì)的OD對(duì)，則基于路段流量的OD估計(jì)的基本方程組如下：

　　r=pq（1）

　　r=[r1r2…ri…rm]T，為路段觀測(cè)流量向量；

　　q=[q1q2…qi…qn]T，是待估計(jì)的OD矩陣的向量形式；

　　p是m×n的交通分配矩陣，描述了路段流量r和OD向量q的線性關(guān)系；

　　p=[p1Tp2T…piT…pmT]T，其中（pi）1×n表示了第i個(gè)路段流量ri與q的線性關(guān)系。

　　OD估計(jì)問題就是在已知r和p的情況下求解方程組（1）的解q，通常情況下由于m<<n，q有無窮多解。為了求得唯一的q，可以引入一些模型將OD估計(jì)變?yōu)橐粋€(gè)數(shù)學(xué)規(guī)劃問題，形式如下：

　　min f（r，，q0，q）

　　s.t. r=pq（2）

　　q≥0

　　：OD估計(jì)時(shí)求得的路段流量；

　　q0：先驗(yàn)OD矩陣。

　　1.2 引入路段轉(zhuǎn)向流量的基本方程組

　　設(shè)第i個(gè)路段有si個(gè)轉(zhuǎn)向，ri1，…，分別表示第1個(gè)，…，第si個(gè)轉(zhuǎn)向流量。根據(jù)路段流量守恒有：

　　（3）

　　第i個(gè)路段的第j個(gè)轉(zhuǎn)向流量方程可以表示為：

　　（4）

　　pikj表示第k個(gè)OD量qk分配到i個(gè)路段的第j個(gè)轉(zhuǎn)向流量rij的比例。

　　由式（4）易知同一個(gè)路段的流量方程與路段轉(zhuǎn)向流量方程組線性相關(guān)，因此可以用路段i的轉(zhuǎn)向流量方程組代替關(guān)于路段流量ri的方程，則可將式（1）的方程組改為：

　　表示了路段轉(zhuǎn)向流量與q的線性關(guān)系。上面的方程組也可以表示為：

　　rl=plq（6）

　　rl表示既有路段流量，也有轉(zhuǎn)向流量的向量；

　　pl矩陣表示rl與OD向量q的線性關(guān)系。

　　同理，其他有轉(zhuǎn)向流量的路段都能引入到方程組r=pq中。實(shí)際上，一個(gè)路網(wǎng)的許多路段都能引入幾個(gè)轉(zhuǎn)向流量，使得方程組的個(gè)數(shù)增加，結(jié)果就是矩陣pl的秩增加，q解集的范圍降低。

　　1.3 雙層規(guī)劃模型

　　雙層規(guī)劃模型的上層模型是最大熵模型EM，表示如下：

　　s.t. r=pq（7）

　　q≥0

　　已知r和p，模型EM可求得OD向量q。

　　分配矩陣p可以由下層模型（UE模型）解得。

　　其中，δis為1表示路徑s經(jīng)過路段i，否則為0；fi表示路徑流量；W表示所有的路徑集合；Wi表示OD對(duì)i之間的所有路徑集合；ce（x）是路段旅行費(fèi)用函數(shù)。

　　已知q，UE模型可以求得估計(jì)流量，分配矩陣p。

　　引入部分路段上的轉(zhuǎn)向流量后可以將上層規(guī)劃模型EM中的等式約束改為rl=plq。

　　下層UE模型也可以求得估計(jì)，分配矩陣pl。

　　將基于路段流量的模型簡(jiǎn)述為BEMR，基于路段轉(zhuǎn)向流量和路段流量的模型簡(jiǎn)述為BEML。

2 求解算法步驟

　　由于雙層規(guī)劃問題本身有非凸、非光滑的特性，求取最優(yōu)解非常困難，大部分算法只能針對(duì)特定的模型給出近似解。本文給出的迭代求解方法可以求得近似較優(yōu)解。單獨(dú)求解上層最大熵問題（EM）和下層用戶均衡分配問題（UE），目前都有比較有效的算法。并且引入了路段轉(zhuǎn)向流量后，上層問題的搜索的可行解集的范圍大大縮小，也使得求解這個(gè)雙層規(guī)劃問題的一個(gè)相對(duì)較優(yōu)的解更加容易。

　　求解這類雙層規(guī)劃問題的有效算法是迭代優(yōu)化算法。算法的主要思想就是先給出上層規(guī)劃的初始決策變量，將這個(gè)決策變量傳遞到下層規(guī)劃中，下層規(guī)劃求解最優(yōu)解，再將下層規(guī)劃的最優(yōu)決策傳遞到上層規(guī)劃進(jìn)行求解，如此反復(fù)求解上層規(guī)劃和下層規(guī)劃，最后雙層規(guī)劃問題的上層決策變量和下層決策變量趨于平穩(wěn)，此時(shí)就是雙層規(guī)劃問題的相對(duì)較優(yōu)的方案。根據(jù)這個(gè)方法，求解最大熵雙層規(guī)劃模型的思想是，先設(shè)定一個(gè)初始的OD矩陣求解下層的用戶均衡交通分配問題，將下層規(guī)劃求得的交通分配矩陣傳遞到上層最大熵模型中，并求解出最優(yōu)的OD矩陣，最后模型趨于平穩(wěn)，求得較優(yōu)解。

　　用Q表示OD總量，，Vo表示所有入口節(jié)點(diǎn)集合，oi表示O點(diǎn)的流量，通常情況oi都是很容易觀測(cè)到的，所以可以將Q作為一個(gè)常量處理。因?yàn)闆]有先驗(yàn)OD矩陣，而通過分析入口處交通總量來獲取初始迭代點(diǎn)是非常簡(jiǎn)單可行的，所以可以用交通總量的平均值作為初始點(diǎn)。

　　求解步驟如下：

　　（1）初始化qk=[q1k…qik…qnk]T，k=0，其中每個(gè)qik=Q/n。

　?。?）用qk求解下層規(guī)劃問題，本文采用Frank-Wolfe算法求解，在這一步可以求得plk。

　?。?）用rl和plk求解上層規(guī)劃問題來獲取qk+1。設(shè)plk、rl分別是t×n的矩陣，t×1的向量（t>m），解決此問題，先引入拉格朗日乘數(shù)向量（λk）t×1，OD矩陣可以用拉格朗日乘數(shù)表示如下：

　　求解λk，將qk+1代入到（6）中有：

　　本文用Levenberg-Marquardt算法求解上述非線性方程組。求得λk，由式（9）就可以求得qk+1。

　?。?）檢查終止準(zhǔn)則，若不能終止則轉(zhuǎn)步驟（2），并令k=k+1。終止準(zhǔn)則由下式?jīng)Q定：

　　其中，ε為誤差上限值。

3 仿真實(shí)驗(yàn)與分析

　　一個(gè)六路口的實(shí)驗(yàn)網(wǎng)絡(luò)如圖1所示，一共34個(gè)路段，90個(gè)OD對(duì)。除了10個(gè)出口路段，其他路段均有3個(gè)轉(zhuǎn)向流量?；诼范瘟髁康姆匠探M總數(shù)為34個(gè)，基于路段流量和路段轉(zhuǎn)向流量的方程組總數(shù)為24×3+10=82個(gè)，其中有部分方程是線性相關(guān)的。

　　仿真實(shí)驗(yàn)中用一個(gè)真實(shí)的OD矩陣按照用戶均衡模型分配到路網(wǎng)上，將分配所得的路段流量和路段轉(zhuǎn)向流量作為OD估計(jì)的輸入數(shù)據(jù)。根據(jù)估計(jì)所得的OD矩陣和真實(shí)的OD矩陣，比較BEMR模型和BEML模型的OD估計(jì)精度。

　　路段旅行費(fèi)用函數(shù)采用BPR公式（Bureau of Public Road）：

　　ce（re）=ce（0）（1+0.15（re/Ce）4）（12）

　　Ce為道路通行能力；

　　ce（0）為平均自由流下的道路通行時(shí)間。

　　下面的統(tǒng)計(jì)參數(shù)可以表示OD估計(jì)的精度：均方根誤差rmse，相對(duì)均方根誤差trmse，相對(duì)平均值誤差mae。

　　除此之外，還給出一個(gè)直觀的指標(biāo)?茲x，表示OD估計(jì)的結(jié)果中與真實(shí)OD相對(duì)誤差小于等于x的OD對(duì)個(gè)數(shù)占總OD對(duì)個(gè)數(shù)的百分比。表示如下：

　　其中，card表示取集合元素總數(shù)。

　　表1為模型估計(jì)精度對(duì)比。從表1可以看出，基于路段流量和轉(zhuǎn)向流量的模型各項(xiàng)統(tǒng)計(jì)指標(biāo)均優(yōu)于單純基于路段流量的模型。當(dāng)路網(wǎng)的路段流量和路段轉(zhuǎn)向流量均可觀測(cè)時(shí)，路段流量總約束條件為34個(gè)，而路段流量和轉(zhuǎn)向流量的總約束條件為82個(gè)，顯然后者包含的信息量更多，這使得OD估計(jì)的精度提高。

4 結(jié)論

　　采用基于轉(zhuǎn)向流量的OD估計(jì)算法，能有效降低數(shù)學(xué)規(guī)劃問題的可行解集的范圍，提高了解的準(zhǔn)確性。隨著檢測(cè)技術(shù)的進(jìn)步，越來越多的城市能提供準(zhǔn)確的轉(zhuǎn)彎流量數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明：基于路段轉(zhuǎn)向流量的OD估計(jì)的估計(jì)精度優(yōu)于傳統(tǒng)的基于路段的OD估計(jì)。

參考文獻(xiàn)

　　[1] 丁革媛，李振江，鄭宏云.智慧城市中的智能交通系統(tǒng)構(gòu)建[J].微型機(jī)與應(yīng)用，2013，32（24）：1-3.

　　[2] VAN ZUYLEN H J， WILLUMSEN L G. The most likely trip matrix estimated from traffic counts[J]. Transportation Research Part B： Methodological， 1980，14（3）：281-293.

　　[3] CASCETTA E. Estimation of trip matrices from traffic counts and survey data： a generalized least squares estimator[J]. Transportation Research Part B： Methodological， 1984，18（4）：289-299.

　　[4] MAHER N J. Inferences on trip matrices from observations on link volumes： a Bayesian statistical approach[J]. Transpor-tation Research Part B， 1983，17（6），435-447.

　　[5] SPIESSH. A maximum likelihood model for estimating origin-destination matrices[J]. Transportation Research Part B： Methodological， 1987，21（5）：395-412.

　　[6] SHEFFI Y. Urban transportation networks： equilibrium analysis with mathematical programming methods[M]. Englewood Ciiffs： Prentice-Hall Inc， 1985.

　　[7] YANG H， SASAKI T， IIDA Y， et al. Estimation of origin-destination matrices from link traffic counts on congested networks[J]. Transportation Research Part B， 1992， 26（6）， 417–434.

　　[8] 于凱.基于轉(zhuǎn)彎流量的OD反推算法及基于微觀對(duì)象的動(dòng)態(tài)配流算法研究[D].杭州：浙江大學(xué)工業(yè)控制技術(shù)研究所，2006.