考慮路段流量不確定性的OD矩陣反推算法

1、考慮路段流量不確定性的OD矩陣反推算法ODMatrixEstimationAlgorithmwithConsiderationtoUncertaintyofLinkFlows成衛(wèi)陳月明董玉佩（昆明理工大學(xué)交通工程學(xué)院，昆明650224）ChengWei,ChenYuemingandDongYupei(FacultyofTrafficEngineering,KunmingUniversityofScienceandTechnology,Kunming650224,China)摘要：現(xiàn)有OD矩陣反推技術(shù)大都將路段流量確定為穩(wěn)定不變的，導(dǎo)致反推精度不高。為了解決這一問題，以交通網(wǎng)絡(luò)平衡和雙層規(guī)劃模型

2、為理論基礎(chǔ)，選取路段流量與實(shí)測(cè)流量之間的偏差平方和最小作為目標(biāo)函數(shù)，刪除OD矩陣的判別誤差函數(shù)，將雙層規(guī)劃模型簡(jiǎn)化為單層規(guī)劃，從而減少了計(jì)算量。以云南省某城市中心城區(qū)路網(wǎng)作為實(shí)際算例，采取用戶平衡分配模型進(jìn)行驗(yàn)證。結(jié)果表明，分配得到的路段流量與實(shí)測(cè)流量的相對(duì)誤差都在12%以內(nèi)，證明該方法與已有研究中以網(wǎng)絡(luò)行駛時(shí)間最小作為目標(biāo)函數(shù)的反推模型相比，精度更高。Abstract：Linkflowsareusuallyhypothesizedasconstantvari-ablesintheexistingODmatrixestimationtechnology,whichyieldsalowaccur

3、acy.Copingwiththisproblem,thispaperde-velopsamethodforODmatrixestimationbasedonnetworkequilibriumtheoryandthetwo-tierplanningmodelbyminimiz-ingthesquaredeviationsoftheestimatedandtheobservedlinkflows.ThismethodreducesthecalculationloadbytossingouttheODmatrixerror-checkingfunctionandbysimplifyingthet

4、wo-tierplanningmodelasasingle-tierplanningmodel.Anu-mericalexampleutilizinguser-equilibriumassignmentmodelappliedtoanurbancentralareanetworkinYunnanProvince,China,showsthatthedifferencebetweenthemodeledandtheobservedlinkflowsislessthan12%,ahigheraccuracycom-paredwithotherODmatrixestimationmodelsusin

5、gthemini-mumnetworktraveltimeastheirobjectivefunction.關(guān)鍵詞：交通規(guī)劃；交通模型；OD矩陣；反推模型；雙層規(guī)劃；用戶平衡分配Keywords：transportationplanning;transportationmodel;ODmatrix;estimationmodels;two-tierplanning;userequilibrium中圖分類號(hào)：U491.1+2收稿日期：2007-05-21作者簡(jiǎn)介：成衛(wèi)，男，博士，昆明理工大學(xué)交通工程學(xué)院教授，主要研究方向：交通信息工程與控制，交通規(guī)劃與設(shè)計(jì)。E-mail:chengwei_din

6、g文獻(xiàn)標(biāo)識(shí)碼：A0引言在交通規(guī)劃、交通管理與控制中，OD矩陣是一項(xiàng)非常重要而且有用的數(shù)據(jù)，其獲得通常有3種途徑：通過家庭調(diào)查、城市出入口調(diào)查等方式獲得調(diào)查數(shù)據(jù)，整理出OD矩陣；應(yīng)用交通分布模型計(jì)算(如重力模型等)獲得；基于路段流量反推獲得。在這3種方法中，第1種方法獲得的數(shù)據(jù)準(zhǔn)確度比較高，但其耗費(fèi)也最大，不能經(jīng)常大范圍地開展，同時(shí)，調(diào)查和整理所需時(shí)間比較長(zhǎng)，因此，獲得的數(shù)據(jù)實(shí)時(shí)性差；第2種方法只適用在一些粗略的交通分布中；第3種方法是目前國(guó)內(nèi)外許多學(xué)者都在研究的一種方法。OD矩陣和路段流量有著極為密切的聯(lián)系，目前，城市路網(wǎng)中鋪設(shè)的流量檢測(cè)器或是交叉口攝像頭等使路段流量的獲得更為方便，而且最重要

7、的是實(shí)時(shí)性強(qiáng)。隨著基于路段流量的OD矩陣反推技術(shù)在交通規(guī)劃中越來越多地成功應(yīng)用，出現(xiàn)了許多有效的方法，如重力模型法、熵模型法、極大似然估計(jì)法、貝葉斯推算模型法等。這些方法多將路段流量確定為穩(wěn)定不變的。但實(shí)際中，由于受到調(diào)查時(shí)間、調(diào)查者的素質(zhì)、周圍環(huán)境等因素的影響，調(diào)查所得的數(shù)據(jù)是不確定的。同時(shí)，在數(shù)據(jù)統(tǒng)計(jì)和處理過程中，會(huì)存在一定范圍的偏差。如果在OD矩陣反推過程中，將路段流量看作是穩(wěn)定不變的，勢(shì)必會(huì)造成反推的精確度下降。因此，本文提出一種新的基于路段流量不確定性的OD矩陣反推算法。1理論基礎(chǔ)1.1交通網(wǎng)絡(luò)平衡1952年著名學(xué)者Wardrop提出了交通網(wǎng)絡(luò)平衡定義的兩條79城市交通UrbanTr

8、ansportofChina第6卷第3期原理，奠定了交通流分配的基礎(chǔ)。Wardrop第一原理1也叫用戶平衡(UserEquilibrium，UE)，是指在道路的利用者都明確知道網(wǎng)絡(luò)的交通狀態(tài)并試圖選擇最短路徑時(shí)，網(wǎng)絡(luò)將會(huì)達(dá)到平衡狀態(tài)。Wardrop第二原理2也稱為系統(tǒng)最優(yōu)(SystemOptimaization，SO)，是指在系統(tǒng)平衡的條件下，擁擠的路網(wǎng)上交通流應(yīng)該按照平均或總的出行成本最小為依據(jù)來分配。第一原理反映了道路用戶選擇路線的一種準(zhǔn)則，而第二原理則反映了一種網(wǎng)絡(luò)的設(shè)計(jì)目標(biāo)。在實(shí)際路網(wǎng)中，很難出現(xiàn)第二原理所描述的狀態(tài)，而按照第一原理分配出來的結(jié)果應(yīng)該是路網(wǎng)上用戶實(shí)際路徑選擇的結(jié)果。因此

9、，本文采用Wardrop第一原理進(jìn)行網(wǎng)絡(luò)分配，以使結(jié)果更加符合實(shí)際。2.1模型的建立考慮到交通調(diào)查獲得的數(shù)據(jù)具有不確定性，為此，反推出來的路段流量并不一定要和實(shí)際調(diào)查的路段流量保持完全一致。因此，采用反推路段流量與實(shí)測(cè)路段流量之間的誤差平方和最小為目標(biāo)函數(shù)。同時(shí)，本文采用的路網(wǎng)基于用戶平衡，反推模型必須滿足交通流守恒的條件，即OD對(duì)間各條路徑上的交通量之和應(yīng)該等于OD交通總量，路徑流量也應(yīng)該滿足非負(fù)約束。從而得到反推流量va和觀測(cè)流量a的誤差函數(shù)模型：minZ(v)=(va-a)2，a=1rss.t.fk=trs，n(5)(6)krsfk0，(7)(8)(9)v=pt，v0，1.2OD矩陣反推

10、模型在基于路段流量反推OD矩陣的方法中，文獻(xiàn)3，4提出的雙層規(guī)劃模型是最為全面的一種。該模型描述為：minF1(t，)+F2(v，)，v,ts.t.v=M(t)，v0，(1)rs式中：fk為OD對(duì)(r，s)間第k條路徑上的交通量/(pcu·h-1)；trs為OD對(duì)(r，s)間交通量/(pcu·h-1)。這樣，模型就由雙層規(guī)劃變成了單層規(guī)劃，同時(shí)精度也可以得到保證，大大減少了計(jì)算量。(2)(3)2.2模型的求解在式(5)(9)中，目標(biāo)函數(shù)Z(v)是凸函數(shù)，每個(gè)約束條件都是線性的。根據(jù)線性函數(shù)既是凸的又是凹的這一性質(zhì)，可知該規(guī)劃模型是凸規(guī)劃。因此，目標(biāo)函數(shù)存在最優(yōu)值而且惟一。本

11、文采用Frank-Wolfe算法2求解模型，其實(shí)質(zhì)是根據(jù)一組線性規(guī)劃的最優(yōu)解確定下一步的迭代方向，然后根據(jù)目標(biāo)函數(shù)的一維極值問題求最優(yōu)迭代步長(zhǎng)。模型的求解步驟如下：1)初始化，預(yù)先給定一個(gè)p0和樣本矩陣t0；2)根據(jù)式(8)，計(jì)算路段流量；3)計(jì)算Z(v)，若Z(v)，則停止計(jì)算，此時(shí)t0為最終矩陣；若Z(v)>，則轉(zhuǎn)到4)；4)根據(jù)計(jì)算的路段流量vn，更新路阻函數(shù)，確定pn，參照所選的交通流分配方法進(jìn)行流量分配，得到一組輔助的路段流量yan；5)尋找迭代方向，利用二分法求滿足(10)式的，確定迭代步長(zhǎng)2，其中，01；(yan-van)van+(yan-van)-a=0；a=1l式中，=

12、，w，T是目標(biāo)OD矩陣構(gòu)成的列向量，w是OD對(duì)wW(W是所有起訖點(diǎn)的組合)間的交通量/(pcu·h-1)；=，a，T是觀察得到的路段流量向量，a是路段a是所有觀測(cè)路段的集合)的觀測(cè)流量/(pcu·h-1)；t，v分別是反推出來的OD矩陣和路段流量，兩者都是非負(fù)的；F1(t，和F2(v，分別是計(jì)算t和v和之間誤差的函數(shù)；v=M(t)表示v和t之間的函數(shù)關(guān)系式，其具體表現(xiàn)在所采用的交通分配方法上。2模型構(gòu)建由于v和t之間的關(guān)系密切，即t在路網(wǎng)中的表現(xiàn)就是路段流量v，用數(shù)學(xué)公式描述為：v=pt，(4)式中：p是一個(gè)路徑選擇概率矩陣，其值主要取決于所采取的交通分配模型，本文假設(shè)p是

13、一個(gè)正確和已知的值。在路段流量反推OD矩陣中，若能保證v的精確度，就可以保證t的精確度。因此，把OD矩陣的判別誤差函數(shù)去掉，將雙層規(guī)劃簡(jiǎn)化成單層規(guī)劃，既可以簡(jiǎn)化模型，又可以減少計(jì)算量，這對(duì)于大路網(wǎng)具有較大的應(yīng)用意義。(10)6)確定新的迭代起點(diǎn)：vna+1=van+(yan-van)；(11)80成衛(wèi)等考慮路段流量不確定性的OD矩陣反推算法ODMatrixEstimationAlgorithmwithConsiderationtoUncertaintyofLinkFlowsvna+1-a7)收斂判別，若max則停止計(jì)算，進(jìn)入a8)，否則返回到4)；8)計(jì)算OD矩陣t：ntij=oipij，n&

14、#183;h-1)；pij是迭代后第n式中：oi是i小區(qū)的產(chǎn)生交通量/(pcu模型，對(duì)路網(wǎng)進(jìn)行交通分配(見圖2)，得到的路段流量與實(shí)測(cè)流量的相對(duì)誤差均在12%以內(nèi)。可見，利用該模型獲得的OD矩陣是可行的。次路徑選擇概率矩陣中的元素。上述步驟中的和都是在模型計(jì)算前預(yù)先確定的精度判定值，可以根據(jù)規(guī)劃者的需要設(shè)定不同的精度。3實(shí)例分析圖1是云南省某城市中心城區(qū)路網(wǎng)圖。對(duì)城市基礎(chǔ)數(shù)據(jù)進(jìn)行調(diào)查和整理，利用MATLAB和TransCAD軟件運(yùn)算模型。經(jīng)過數(shù)次迭代后，反推出來的OD矩陣如表1所示。為了驗(yàn)證反推OD矩陣的可行性，采取用戶平衡分配O五一路五一路西園老街通商南路滇運(yùn)過街樓7173002801111

15、30931西園686219219129119674老街4671851379093543通商南路31015311373106361滇運(yùn)23615012384107357過街樓803309265100160911Ai,j(12)4結(jié)語由于交通數(shù)據(jù)在調(diào)查和統(tǒng)計(jì)中存在很多的不確定性因素，若一味追求反推出來的流量和調(diào)查統(tǒng)計(jì)的路段流量相等，會(huì)造成OD矩陣與實(shí)際大相徑庭，導(dǎo)致交通規(guī)劃、交通管理與控制等決策過程失誤。一般文獻(xiàn)中的反推模型以網(wǎng)絡(luò)行駛時(shí)間最小作為目標(biāo)函數(shù)，而本文提出的反推模型以路段流量偏差和最小作為目標(biāo)函數(shù)，將常規(guī)的雙層規(guī)劃簡(jiǎn)化成單層規(guī)劃，相比之下，模型更加簡(jiǎn)化，大大減少了計(jì)算量。參考文獻(xiàn)1邵春福.交通規(guī)劃原理M.北京：中國(guó)鐵道出版社，2004pcu/h2黃紅選，韓繼業(yè).數(shù)學(xué)規(guī)劃M.北京：清華大學(xué)出版社，20063高自友，四兵峰.從路段流量估計(jì)OD交通量的新算法J.交通運(yùn)輸系統(tǒng)工程與信息，2001，2(1)：30-414JavierDoblas,Franc