基于广义最小二乘模型的动态交通OD矩阵估计.pdf
2004年1月系统工程理论与实践第1期文章编号:100026788(2004)0120136205基于广义最小二乘模型的动态交通OD矩阵估计林勇,蔡远利,黄永宣(西安交通大学电子与信息工程学院,陕西 西安710049)摘要:基于广义最小二乘模型,建立了一种带滑动窗的动态OD矩阵估计算法,可通过对路段交通量和行程时间的检测来估计时变的OD数据 对模型中关键的交通分配矩阵,给出了解析的计算公式 算法是一种递推的估计过程,仅需较少的先验信息,且估计过程不会发散;滑动窗的引入可充分利用量测信息,抑制量测噪声关键词:动态OD矩阵;广义最小二乘法;估计中图分类号:U 491文献标识码:AGLSM odelBased Dynam ic O rigin2Destination M atrixEstimation for T raffic System sL I N Yong,CA I Yuan2li,HUAN G Yong2xuan(School of Electronic and Information Engineering,Xian Jiaotong U niversity,Xian 710049,China)Abstract:Based on GeneralizedL east Square(GL S)model,a dynam ic origin2destination(OD)matrixesti mation algorithm w ith sliding w indow is proposed.The OD matrix can be esti mated through thesurveillance of traffic counts and traveling ti me on links in a traffic network.A n analytical formula tocalculate the key assignment matrix is also presented.The algorithm is a recursive procedure w ith fewapriori data,and there exists no divergence in the esti mation.W ith the sliding w indow,more surveil2lance data can be utilized effectively,and measurement noises can be restrained efficiently.A lot of si m2ulation tests show that the esti mation accuracy of the proposed method is much higher than that ofCascettas recursive algorithm,and there is only a little increase in computation cost.Key words:dynam icOD matrix;GL S algorithm;esti mation收稿日期:2002211204资助项目:国家自然科学基金(60175015)作者简介:林勇(1973-),男,四川人,博士研究生,主要研究方向为智能交通系统中的微观交通仿真与动态OD矩阵估计,Email:yong_;蔡远利(1963-),男,贵州人,博士,教授,研究方向为人工神经网络控制技术,智能交通系统,飞行器制导、控制与仿真等;黄永宣,男,教授,博士生导师1引言OD矩阵,或称OD表,是交通网络中所有起点(O rigin)与终点(Destination)之间出行交换数量的表格,反映了用户对交通网络的基本需求它是进行交通网络规划和交通管理的重要依据动态OD矩阵则反映了每个OD对(每个OD对与交通网络中一个特定的起点终点对组合相对应)间特定的时段内时变的交通需求在智能交通系统(ITS)中,动态OD矩阵是先进的旅行者信息系统(A T IS)和先进的交通管理系统(A TM S)的重要输入,也是动态交通分配模型和一些实用的微观交通仿真器的基础输入数据,如Param ics1、M ITSi m2等历史上,OD数据是作大量的交通调查得到的,代价十分高昂通过这种调查,得到的一般是所研究区域内的平均意义上的静态OD矩阵目前,广为采用的方法是通过观察到的路段交通量和一些先验信息(如历史OD矩阵)来推算未知的OD矩阵,这比前者要先进许多OD估计有一个基本的特点,即对于中大规模的交通网络,通常OD对的数量远大于网络中路段的数量因此,仅通过测量路段上的交通量来间接估计OD矩阵通常不能得到唯一的估值3 补充测量数据不足的常用方法是提供诸如 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.历史的OD矩阵等一些先验信息国内外对传统的静态OD矩阵估计已作了大量研究,但动态的情况较为困难,所做的工作也相当有限 由于动态交通分配模型的理论研究还不成熟4,目前进行过现场测试的动态OD估计算法大多是针对高速公路或环城快速路开展的 此时,OD对间的路径选择模型较为简单,通常可按最短路径处理;另外,历史的OD矩阵数据较易得到(如可通过对收费亭的票据做统计),这可用于保证得到的OD矩阵估值是唯一的迄今为止,动态OD估计的方法可分为两大类:参数优化法和统计法 前者通过最小化实测的路段交通量和分配交通量间的差值(也可同时最小化先验OD矩阵和待估计OD矩阵间的差值)得到动态的OD矩阵;后者进一步可分为统计推断模型和卡尔曼滤波模型 其中,卡尔曼滤波模型可用于动态OD矩阵的实时估计与预测,但存在滤波容易发散的问题5 在参数优化法中,以最小二乘原理为基础的广义最小二乘模型不必对数据的分布进行假设,是一大优点,且通常不存在估计发散的问题;另外,可为实时OD估计与预测算法提供历史数据,用以标定这些算法中的模型参数和提供所需的先验信息Cascetta等学者6较早将静态OD估计中的广义最小二乘法推广到动态OD矩阵估计中 通过最小化实测的路段交通量和分配交通量间的差值,并同时最小化先验OD矩阵和待估计OD矩阵间的差值得到动态的OD数据他们提出了两种估计算法:递推法和一步法前者在每一步内,根据当前与先前时段的路段交通量,还可包括先前时段的OD估计值,来得到当前时段内的OD矩阵;后者使用所有时段内的路段交通量,一步内即可估计出所有时段的OD数据Cascetta等的算法针对一条意大利高速公路作了现场测试,取得了较为满意的结果6 由于他们首先建立了模型中关键的分配矩阵的计算公式(描述OD量与路段交通量之间的动态映射关系),因而其工作是先驱性的 然而,Cascetta等的工作有如下不足:递推法仅利用了非常局部的信息,即仅利用一个时段的量测交通量来估计该时段的OD矩阵,对于后续的估计时段,先前时段的OD矩阵保持恒定这在量测噪声较大时可能导致估计误差偏大然而,它的计算量很小,在缺乏好的先验OD矩阵时,每个时段估计得到的OD矩阵又可作为估计下一时段的OD矩阵所需的先验值一步法则充分利用了量测信息,能够获得更高的估计精度,但计算量显然远大于前者另外,他们得到的交通分配矩阵的计算公式仅在很理想的情况下适用为此,本文的工作主要为:结合递推法与一步法的优点,建立了带滑动窗的广义最小二乘模型,并提出一种更切实际的分配矩阵计算公式2动态OD矩阵估计算法2.1递推法与一步法6为描述方便,下文将OD矩阵称作OD流向量,即将OD矩阵按列展开所得的列向量递推法通过求解如下的优化问题得到动态OD流向量估值xh=arg m inf1(xh,xah)+f2(yh,yh),xh 0(1)式中,xhRnOD为待估计的OD流向量,其元xrh(r=1,2,nOD)为在时间段h内离开起点的第r个OD对的出行量,nOD为网络中OD对的个数;xah是xh的先验值,可令xah=xh-1;yhRnl为时间段h内路段交通量的检测值,nl为安装有流量检测装置的路段数;yh是路段的分配交通量向量,即通过交通分配模型将式(1)中的优化向量xh分配到路网中后得到的路段交通量;f1和f2由所采用的估计算法确定 上式的广义最小二乘形式如下xh=arg m in(xh-xah)TW-1h(xh-xah)+yh-6h-1p=h-paphxp-ahhxhTR-1hyh-6h-1p=h-paphxp-ahhxh(2)式中,aph为nlnOD的交通分配矩阵,定义p时段内出行的OD流向量xp与h时段内的路段交通量观测向量间的动态映射关系;p 为网络中任一OD对间所需的最大旅行时段数一步法则可同时估计出所有时段内的OD流向量,如下所示731第1期基于广义最小二乘模型的动态交通OD矩阵估计 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.(x1,x2,xN)=arg m in f1(x1,x2,xN,xa1,xa2,xaN)+f2(y1,y2,yN;y1,y2,yN)(3)其中优化变量xi0,i=1,2,N 同理,f1和f2由所采用的估计算法确定,式(3)的广义最小二乘形式如下xh=arg m in6Nh=1(xh-xah)TW-1h(xh-xah)+6Nh=1yh-6hp=h-paphxpTR-1hyh-6hp=h-paphxp(4)2.2带滑动窗的广义最小二乘模型基于引文中的讨论,我们建立带滑动窗的广义最小二乘模型以组合上述的一步法和递推法的优点重新定义状态向量为Xh=xThxTh-1xTh-pT(p+1)为网络中任一OD对间所需的最大旅行时段数,也是窗口宽度 令分配矩阵Ah=ahhah-1hah-ph先验OD流向量的方差阵Wh=V ar(Xah)则带滑动窗的广义最小二乘公式如下Xh=arg m in(Xh-Xah)TW-1h(Xh-Xah)+(yh-AhXh)TR-1h(yh-AhXh)(5)与递推法类似,在缺乏足够的先验OD流向量时,可令Xah=Xh-1;若有足够的历史数据,则Xah可取为前一天同一时段的OD流向量 上述估计算法中,OD流向量xh将被估计(p+1)次,各次估值分别由扩展的OD流向量Xi(i=h,h+1,h+p)的序号为1nOD,(nOD+1)2nOD,pnOD(p+1)nOD的元素构成由于第(p+1)次估值利用了最多的信息,因而可能是统计上最有效的估计,可作为xh的最终估计值使用式(5)需已知W-1h和R-1h 如有可能,我们可通过对前几天的残量数据进行分析得到 在缺乏任何先验信息的情况下,一般可假设Wh和Rh均为单位阵,求出简单最小二乘估计(OL S),然后通过残差分析,对误差向量提出一些特殊结构,这时误差协方差阵就具有特定形式式(5)为一个简单的二次优化问题,存在有效的求解算法,本文不再赘述2.3分配矩阵的计算上述估计算法中,关键的参数是分配矩阵aphCascetta等6利用离散路径选择模型首先给出了较一般情况下的分配矩阵计算公式,他们假定p时段(长度为H)沿第k条路径出行的所有车辆组成一个包(k,p),包中车辆间的时头距始终均匀分布,且在网络中的行程时间不超过H事实上,包(k,p)通过网络时既可被“拉伸”,也可被“压缩”,这在OD对间的行程时间较长时尤为突出,且行程时间不超过H的假定也不尽合理为此,我们假定任一OD对r间的有效路径集为Kr,网络中的nOD个OD对间总共存在K条有效路径,即K=K1K2KnOD任一路径k=1,2,K对应于唯一的一个OD对,其包含的所有路段的集合为Lk 令Fkh为在时段h内离开起点且沿路径k的OD出行量 则在任意时段h,如下关系总成立xrh=6kKrFkh(6)令qkh为相应于OD对r、出行时段h、路径为k的出行分配比例,满足6kKrqkh=1,且对r,h均成立,则可得OD流向量和路径交通量之间的映射关系Fkh=xrhqkh(7)831系统工程理论与实践2004年1月 时头距定义为:hn(t)=Xn(t)?Vn(t)其中,Vn(t)与Xn(t)分别表示t时刻后车的当前速度及后车与前车车头间的距离 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.式中qkh可由交通分配模型得到,如可采用Logit型的分配模型由于各路段的交通量是由若干路径交通量构成的,则任一路段l的量测交通量满足ylh=6hp=h-p6Kk=1kplhFkp+vlh(8)其中,kplh定义路径交通量和路段交通量之间的动态映射关系,即在p时段内离开起点的第k条路径的交通量对h时段内流过l路段上的检测站的交通量的贡献大小 由此,可得如下形式的分配矩阵arplh=6kKrkplhqkp(9)路段和路径交通量之间关系的解析算式可利用路段行程时间以及关于车辆运动的假设等前提条件导出剩下的问题是kplh如何得到和Cascetta等的方法类似,假定包(k,p)中任意相邻两车间的时头距均匀分布;并且,我们还假定这些时头距可按相同比例拉伸或压缩,则可通过对时间比的计算得到 令包(k,p)中所有的车辆先后通过l路段的检测站所需时间段为 k=kp1l,kp2l,kp1l,kp2l分别为包(k,p)中首车与尾车通过检测站l(在l路段上)的时刻;h时段所占的时间区间为 h=(h-1)H,hH,H为任一时段p的长度,则kplh=h k?k(10)式中,为求区间长度算子应用上述公式需已知 kp1l和 kp2l可假定包(k,p)中的首车在p时段的起始时刻出行,尾车在该时段的终止时刻出行,通过对路段行程时间的测量,可得到这两个参数上述假定下,分配矩阵的计算精度可受到如下几个因素的影响:交通分配模型的不精确;路段行程时间的测量误差;车辆间时头距均匀分布的假设在特定的情况下可能是不正确的,如某些交通事件(事故、交通信号等);首车与尾车的真正出行时间实际上是不可知的 由于我们更关心的是具有较大流量的OD流的时变规律,并且只要估计时段长度H足够大,从统计意义上说,式(10)仍具实用价值根据经验3,动态OD流估计中的H可选为1015分钟,更小则由于随机因素太多,已无规律可言3仿真算例图1交通网络如图1所示的交通网络,共有四个OD对(1,5),(1,6),(2,6),(2,5),估计时段数N=15,每个时段长度为15分钟 为简化起见,假定车辆在每条路段上的行程时间均为15分钟,路段容量无限;车辆间时头距均匀分布,且保持不变 显然,此时p=3,OD对(1,5)、(1,6)的历史OD量相同,数据来源于我们开发的微观城市交通仿真器7中收集到的某个时变的OD流数据,数据采集周期为15分钟OD对(2,6)的OD量为(1,5)的两倍,对(2,5)的OD量为对(1,5)的1.5倍 各OD流的历史数据见图2,其中,时段-30的OD量用于启动仿真过程,以保证估计开始时各路段的车流量非空 假定各路段上的车流检测器位于距下游节点1?3处,则有如下的交通分配矩阵ahh=1?31?300001?31?3000000000000ah-1h=2?32?300002?32?31?31?31?31?300000000ah-2h=000000002?32?32?32?31?3001?301?31?30ah-3h=0000000000002?3002?302?32?30实际的OD量通过对历史值叠加随机噪声得到,假定噪声服从N(0,2InOD)的正态分布;测量噪声服从931第1期基于广义最小二乘模型的动态交通OD矩阵估计 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.N(0,10Inl的正态分布,其中nl为安装有交通量检测站的路段数 图3(a)为 2=40时利用递推法得到的OD对(1,5)的估计结果;图3(b)为采用带滑动窗的广义最小二乘法得到的相应结果,其精度优于前者由于实际的OD量数据是基于历史值随机产生的,为此,本文把通过大量仿真实验(仿真次数为100次)所得的OD估计平均相对误差作为最终结果相对误差计算公式为x-x?x,其中x和x分别为所有估计时段内的实际的OD流向量(即将所有估计时段内的OD流向量排为一列所得的列向量)与其估计值表1为所有估计时段的历史数据均存在的情况,各时段的先验数据取为相应时段的历史数据 此时,递推法的估计精度甚至比历史数据的还差,且在实际值相对先验值的方差较大时,估计效果明显变坏;滑动窗法的估计精度明显优于递推法,估计值比历史数据的精度更高 表2为仅有部分历史数据时的情况,此时各时段的先验数据取为前一时段的估计值,第一个时段的先验数据可由历史资料或根据经验猜测得到显然,此时滑动窗法的估计精度仍优于递推法尽管如此,由于递推法仅需一个时段的先验OD数据,且计算量很小,在特定的场合仍可用作初略的动态OD流向量估计另外,根据递推法或滑动窗法的估计结果,运用OD预测模型,可进行实时OD矩阵预测由于估计与预测是分离的模型,预测可能不是最优的一步法由于计算量很大,需已知所有估计时段内的全部历史数据,且完全是一种事后处理过程,本文不再讨论图2OD量历史数据图3OD量估计值表1全部历史数据下的OD估计相对误差全部历史数据2=402=802=2002=1000历史值0.05780.0810.12750.2730递推法0.07390.32230.79001.0419滑动窗法0.04700.06390.09660.2025表2部分历史数据下的OD估计相对误差全部历史数据2=402=802=2002=1000递推法0.24280.48411.18031.4137滑动窗法0.12980.13310.15170.23944结束语通过大量的仿真实验可得如下结论:对于动态OD矩阵的估计,本文建立的带滑动窗的广义最小二乘模型的估计精度明显优于递推法,且计算量远小于一步法 对模型中关键的分配矩阵,本文给出了一种更切实际的解析计算公式,这对于高速公路或环城快速路或许更为实用 在城市交通网络中,由于受交通控制信号的作用,城市交通流通常是不连续的,此时车辆间时头距均匀分布的假设通常不能成立,建立随机交通分配矩阵模型或许更为合理,这有待于进一步的研究参考文献:1Q uadstone L i m ited.Param ics V 4.0 system overview BD?OL.http:?www.param ?tech_support?documents?v4?Param icsV4-SystemOverview.zip,2002.2Q i Yang.A si mulation laboratory for evaluation of dynam ic trafficmanagement system sD.M assachusetts Instituteof Technology,Cambridge,MA,1997.(下转第144页)041系统工程理论与实践2004年1月 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.经分析可见,按正、负隶属度确定最优方案其结果是一致的4结束语1)模糊综合评判中方案因素指标所赋予的权重变化时,对评价结果有影响 例如当权向量为:W=0.48 0.06 0.36 0.04 0.06得各方案综合评价结果表3.表3方案L1(R,)L2(R,)ivi备注?0.01410.02560.320.680.02890.01390.810.190.02110.010.820.18?0.00290.03180.010.99m invmax即方案?最优,?次之,较差,最差本项工程权重结合场地环境、资金注入状况、施工力量以及气候等多种因素,并与外国监理工程师、业主(沈阳市环保局多次协商后确定)具体方法是经专家定性后,按语气算子与模糊标度、隶属度对应关系,来确定相对优属度,并对权向量归一化2)多目标模糊决策问题的关建是目标之间难以公度,甚至于不能严格定量,对此类问题通常有两种解法:一是简化法二是协调规划法(Comprom ise Programm ing亦称距理想点最短距离法)本项目中采用了后一种方法方案优选后经业主,监理审查、核对得到赞同并于1997年-1999年间进行施工,实践证明方案的选择是非常正确的沈阳工业危险固体废物处置中心是世界银行贷款期、国家环保项目示范工程随着我国经济的发展、技术提高,越来越多的工业危险废物填埋场将在全国涌现,多目标模糊综合评判法也将得到广泛应用参考文献:1沈阳工业危险废物处置二期土建招标文件Z,1998.2夏绍玮,等.系统工程概论M.北京:清华大学出版社,1995.3林启太.多目标模糊优选模型在露天矿山设计中的应用J.武汉理工大学学报,2002,24(2):76-78.(上接第140页)3KalidasA shok.Esti mation and prediction of ti me2dependent origin2destination flow sD.M assachusetts Institute ofTechnology,Cambridge,MA,1996.4陆化普,史其信,等.动态交通分配理论的回顾与展望J.公路交通科技,1996,13(2):34-43.5Hanif D.Sherali,Taehyung Park.Esti mation of dynam ic origin2destination trip tables for a general network J.T ransportation Research,2001,35B:217-235.6Ennio Cascetta,Domenico Inaudi,Gerald M arquis.Dynam ic esti mators of origin2destination matrices using trafficcountsJ.T ransportation Science,1993,27(4):363-373.7Yong L in,YuanliCai.A m icroscopic si mulator for urban traffic system sA.Proceedings of the IEEE 5th Interna2tional Conference on Intelligent T ransportation System sC,622-626,Singapore,2002.441系统工程理论与实践2004年1月 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.
