蔣云，陳鋒（中國科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院，安徽 合肥 230026）

基于路段轉(zhuǎn)向流量的擁擠路網(wǎng)OD矩陣估計

蔣云，陳鋒
（中國科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院，安徽 合肥 230026）

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

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

0 引言

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

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

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

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

1.1 OD估計基本原理

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

q0：先驗OD矩陣。

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

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

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

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

1.3 雙層規(guī)劃模型

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

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

分配矩陣p可以由下層模型（UE模型）解得。其中，δis為1表示路徑s經(jīng)過路段i，否則為0；fi表示路徑流量；W表示所有的路徑集合；Wi表示OD對i之間的所有路徑集合；ce（x）是路段旅行費用函數(shù)。

已知q，UE模型可以求得估計流量r^，分配矩陣p。

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

下層UE模型也可以求得估計r^l，分配矩陣 pl。

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

2 求解算法步驟

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

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

求解步驟如下：

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

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

（4）檢查終止準則，若不能終止則轉(zhuǎn)步驟（2），并令k=k+1。終止準則由下式?jīng)Q定：其中，ε為誤差上限值。

3 仿真實驗與分析

一個六路口的實驗網(wǎng)絡(luò)如圖1所示，一共34個路段，90個OD對。除了10個出口路段，其他路段均有3個轉(zhuǎn)向流量。基于路段流量的方程組總數(shù)為34個，基于路段流量和路段轉(zhuǎn)向流量的方程組總數(shù)為 24×3+10=82個，其中有部分方程是線性相關(guān)的。

圖1 交通網(wǎng)絡(luò)圖

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

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

Ce為道路通行能力；

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

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

除此之外，還給出一個直觀的指標 θx，表示OD估計的結(jié)果中與真實OD相對誤差小于等于x的OD對個數(shù)占總OD對個數(shù)的百分比。表示如下：其中，card表示取集合元素總數(shù)。

表1為模型估計精度對比。從表1可以看出，基于路段流量和轉(zhuǎn)向流量的模型各項統(tǒng)計指標均優(yōu)于單純基于路段流量的模型。當路網(wǎng)的路段流量和路段轉(zhuǎn)向流量均可觀測時，路段流量總約束條件為34個，而路段流

表1 模型估計精度對比

量和轉(zhuǎn)向流量的總約束條件為82個，顯然后者包含的信息量更多，這使得OD估計的精度提高。

4 結(jié)論

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

［1］丁革媛，李振江，鄭宏云.智慧城市中的智能交通系統(tǒng)構(gòu)建［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 oftrip matricesfrom traffic counts and survey data： a generalized leastsquares 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］.Transportation Research Part B，1983，17（6），435-447.

［5］SPIESSH.A maximum likelihood modelforestimating origin-destination matrices［J］.Transportation Research Part B：Methodological，1987，21（5）：395-412.

［6］SHEFFIY.Urban transportation networks： equilibrium analysis with mathematical programming methods［M］. Englewood Ciiffs：Prentice-Hall Inc，1985.

［7］YANG H，SASAKIT，IIDA Y，etal.Estimationof origin-destination matrices from link traffic counts on congested networks［J］.Transportation Research Part B，1992，26（6），417-434.

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

OD matrix estimation based on turning traffic flow for congested networks

Jiang Yun，Chen Feng
（School of Information Science and Technology，University of Science and Technology of China，Hefei 230026，China）

Conventional methods for estimating origin-destination（OD）trip matrices are primarily based on link traffic counts.In a real traffic scenario，due to the numbers of links are much smaller than the number that of OD pairs，it greatly limits the accuracy of these methods.This paper proposed an OD matrix estimation method based on turning traffic flow to improve estimation accuracy in congested networks.This method can considerably reduce the range of feasible solution set.The bi-level programming model is further applied to solve OD matrix estimation problem.The upper model is the entropy maximization（EM）model which is independent of the prior matrix.The lower model is the user equilibrium（UE）model.The experimental results show that our method can increase estimation accuracy effectively.

OD matrix estimation；turning traffic flow；EM；UE；bi-level programming model

TH122

A

1674-7720（2015）20-0018-03

蔣云，陳鋒.基于路段轉(zhuǎn)向流量的擁擠路網(wǎng)OD矩陣估計［J］.微型機與應(yīng)用，2015，34（20）：18-20，24.

2015-04-24）

蔣云（1989-），男，碩士研究生，主要研究方向：智能交通、數(shù)值優(yōu)化。

陳鋒（1966-），男，博士，副教授，主要研究方向：智能交通、人工智能。