城市道路网络OD 估计模型及算法研究

杨晓光，刘 斌，张 晔

（1.同济大学 道路与交通工程教育部重点实验室，上海201804；2.中国城市规划设计研究院，北京100044；3.北京市城市规划设计研究院，北京100045）

对交通流的起讫点OD矩阵进行估计一直都是学者们普遍关注的话题.以往对较封闭的高速公路或快速路的研究较多，随着交通检测技术日新月异，出现了大量多源检测数据，这就对城市道路OD估计研究提出新的要求.

国内外学者利用路段流量提出了很多OD估计模型，LiDa Yasunoyi提出了改进重力模型，将OD小区用研究区域界线加以划分，并将小区吸引量以及吸引概率用小区发生量来表示，大大减少了未知量；然后结合路段流量最小二乘目标函数，给出了简化的求解算法［1］.Sasaki提出交通流在交叉口以一定的转移概率改变行驶方向，然后进入下一个交叉口，可以运用马尔可夫过程描述交通分配问题［2］，Akamatsu证明这种方法可以看作是一种随机用户均衡［3］.J.Takayama 将马尔可夫理论应用到大规模路网仿真上，获得了满意结果［4］.随着浮动车、视频等多源检测数据的挖掘利用，可以获得更多的交叉口及出入口转向数据.基于吸收马尔可夫过程的OD估计方法可以较充分地利用多源数据信息，因此，在进行城市道路网OD估计时具有一定的优越性.

1 马尔可夫过程建模分析

在交通网络中，假定车辆在当前交叉口的转向行为与之前所有交叉口的转向状态均无关，车辆从一个路段（小区）转移到另一个路段（小区）的概率集合就组成了马尔可夫链.交叉口或路段出入口的转向比例在短时间内可以看作是不变的（这里的短时间指满足路网中的车辆从O点行驶到D点的时间），因此，对于每一个小时间段内的交通流转向概率矩阵，都可以看作齐次马尔可夫链.

随机游动是指一个质点在直线（或平面或空间）上的某个范围内随机地逐步移动.在交通网络中，车辆在交叉口之间、小区进出口与路段之间的随机移动可以看作是随机游动.当车辆进入目的地小区后，将消失在网络中，因此，可以将吸引小区看作吸收壁，用吸收马尔可夫过程来描述网络中交通流的转移现象.只要求出n步转移概率矩阵Pij（n），就可以得出车辆选择各个目的地的概率，即OD矩阵.

考虑一般路网情况，假定路网有r个发生点或吸引点（小区），有s个路段（直接与小区相连接），这些路网元素变量可表示路网的状态，发生点代表交通产生量，吸引点代表交通吸引量，路段表示路段交通量.马尔可夫过程中的转移概率代表机动车在路网元素之间的转向概率，转移概率矩阵可表达为

式中：I表示一个单位阵（r，r）；O表示空矩阵（r，r＋s）；R表示车辆从发生点或路段向吸引点转移的概率矩阵（r＋s，r）；Q表示车辆在发生点以及路段间转移的概率矩阵（r＋s，r＋s）.

由于发生点和吸引点之间不存在直接的转移，也不存在向发生点转移的车辆，所以R（r＋s）×r和Q（r＋s）×（r＋s）有如下特性：

式中：R1，r×r为空矩阵；R2，s×r为路段到吸引点的转移概率；Q1，r×s为发生点到路段的转移概率；Q2，s×s为路段之间的转移概率；Qn，ij为车辆从i出发经n步转移到j的概率，i，j代表路段、产生点或吸引点.

由于城市道路网络交通流的复杂性，OD相同的各车辆路径往往不同.到达目的地所需要的状态转移次数也不相同.为了描述这种情况，需要综合计算各种可能的转移路径，使交通流分配结果更符合实际情况.考虑OD的所有转移情况，由切普曼－柯尔莫哥洛夫方程［5］加和得到从发生点产生的车辆经过各个路段的全概率矩阵

［I－Qij］－1R是（r＋s，r）矩阵，表示从发生点或路段离开的车辆到达各吸引点的概率.进一步得

式（5）表示车辆在各路段之间的转移概率矩阵；V1×（r＋s）＝（v1，v2，…vr，0…0），表示发生小区以及路段的交通产生量，表示产生矩阵；U1×r表示吸引小区的吸引量；x1×s表示路段流量；MOD表示OD矩阵.

1.1 模型一，由小区发生量估计OD 矩阵模型

对于路段出入口不太密集的路网来说，交通组织形式较为简单，交通流的波动性较小，V1×r、吸引量U1×r通常可以通过在小区出入口观测交通流量或布设线圈检测器来确定.由模型可知，如果已知马尔可夫1步转移概率矩阵，［I－Qij］－1R（r＋s）×r的运算结果就包含了所有小区以及路段之间的交通流转移概率信息.式（6）是V1×r和U1×r之间的相互转换，式（7）用以求出路段流量，式（8）可求得OD矩阵.

1.2 模型二，由若干路段流量估计OD 矩阵的线性方程组模型

由于受实际条件的限制，若大量小区出入口无法观测交通流量或没有布设检测器，就限制了模型一的实际应用，此时需采用路段流量来估计OD矩阵.

当小区发生量未知时，考虑由若干路段流量反推小区发生量，再由马尔可夫转移概率矩阵分配得到所有路段流量，同时估计OD矩阵.V1×r未知，将其看作r个未知数，通过式（7）计算得到马尔可夫分配后的路段流量，结合路段检测流量（真实值）可以得到一个线性方程组

求解可得小区发生量，然后由模型一估计得OD矩阵.

1.3 模型三，由若干路段流量估计OD 矩阵的非线性规划模型

若布设检测器的路段数量不足以准确估计OD矩阵，已知流量的路段数量小于小区数量，即线形方程组（9）欠定，则需要利用若干路段流量对OD矩阵反复逼近，即求解如下最优化问题：由路段流量估计出交通产生量V1×r，从而估计出OD矩阵

式（10）约束条件为式（7）；x＊为观测到的路段流量；x是通过式（7）计算得到的路段流量；目标函数Z为模型计算路段流量与真实路段流量的误差.

若已知先验OD矩阵Y＊，可以对式（10）的目标函数优化，变成如下最小化问题：

式中：Y为模型估计得到的OD矩阵；λ［0，1］为先验矩阵的信任度系数，先验矩阵越精确，λ越大.

2 城市道路网络拓扑及矩阵描述

基于上述吸收马尔可夫模型，综合考虑城市道路网络的复杂性，以井字型路网为例对城市道路网络进行拓扑描述，如图1所示.

图1 井字路网Fig.1 The structure of Network like Chinese Character“井”

目标区域被道路网划分为若干小区，每个小区都有1个发生点和1个吸引点，并通过进出口与特定路段连接.假定发生点或吸引点只存在于路段上，交叉口范围内不存在交通发生或吸引.交通流从发生点产生，消失于吸引点.小区及道路分布如图1所示：井字路网为开放路网，ABCD为4 个十字交叉口，小区（1）～（4）是研究区域内的小区，小区（5）～（12）是外部小区，外部交通流从外部小区流入，与该路网交换交通流.该路网包含12个小区（以圆圈数字表示，后同），32个路段（以数字表示，后同）及4个交叉口.因此，小区数r＝12，路段数s＝32，以r＊表示吸引点，r表示发生点，则转移概率矩阵可描述为

式中：R为（44，12）矩阵；Q为（44，44）矩阵.矩阵中各元素代表小区及路段之间的交通流转移概率，可以通过线圈或视频检测器获取.

3 模型算法研究

从路网的矩阵描述可以看出，基于马尔可夫过程的OD估计模型算法涉及庞大的矩阵参数存储与运算.对于一个用矩阵来描述的线性恰定方程组来说，n个未知数的问题就需要操作一个n×n阶的矩阵.也就是说，对于一个拥有100 MB内存的计算机来说，也只能求解10 000个未知数的问题.对于本算例中的井字型路网，转移概率矩阵P（2r＋s）×（2r＋s）共有56个未知数.随着路网中小区和路段数的增加，未知数的数目将随之增长，所需计算机内存将以平方的速度增长.对于复杂的城市道路网络来说，势必大大提高所需的存储空间，并降低运算速度.为了解决这一问题，需要简化马尔可夫转移概率矩阵.不难发现，该矩阵中的零元素较多，尤其对于城市快速路网，OD对数量较少，路段关联性也不是很强，造成了转移矩阵中大量元素为零.对于这种情况，Matlab［6］提供了一种高级的存储方式：稀疏矩阵技术.就是不存储矩阵中的零元素，而只操作非零元素.这就大大减少了储存空间和计算时间.

对于模型一，可由Matlab直接稀疏矩阵，运算求解.

对于模型二，一般采用线性方程组的直接解法.大多数数值分析的书中对此都有比较详尽的论述，如Gauss消去法、选主元消去法、平方根法、追赶法等.在Matlab编程仿真中，只需用1个“／”或“＼”即可求解完成.该运算符号内部包含着许多自适应算法.例如解超定方程组时用最小二乘法；解欠定方程组时，将给出范数最小的一个解；解三对角阵方程组时，用追赶法等.对于超定线性方程组，经常遇到的问题是数据的曲线拟合，常用的方法是最小二乘法.在Matlab中，利用左除命令（x＝A／b）来寻求最小二乘解.还可以用广义逆法来求解，即x＝pinv（b），所得的解不一定满足Ax＝b，x只是最小二乘意义上的解.左除的方法是建立在奇异值分解基础之上，由此获得的解最可靠；广义逆法是建立在对原超定方程直接householder变换的基础上的，算法可靠性稍逊于奇异值求解，但速度较快.

对于模型三，如果Q已知，可采用传统经典最优化算法［7］求解最小化问题，包括frank－wolf算法、惩罚函数法、最速下降法、牛顿迭代法、最小二乘法等.

以阻尼牛顿算法为例，目标函数中的Z是交通发生量V的二次函数，因此，目标函数为凸函数，存在唯一解.算法如下：

（1）给定初始点x（1），允许ε＝10－6，置k＝1.

（4）从x（k）出发，沿方向d（k）作一维搜索——令

（5）置k＝k＋1，转步骤（2）.

如果目标函数不是凸函数，例如Q中存在未知变量，传统算法只能得到局部最优解，而不是全局最优解.这时就需要采用遗传算法［8］求解最小化问题.

4 算例分析

按照井字路网结构搭建VISSIM 仿真平台，分别用两个虚拟路段模拟路网中的每个小区，并模拟路网中的禁左、单行道等交通管理措施，以及各通行车辆，见图2.

每个转向都代表马尔可夫转移概率矩阵中的1个元素.为了得到转移概率，在仿真平台布设若干检测器，其中有72个转向检测器（现实中可以采用视频或浮动车数据来检测转向数据）和32个路段流量检测器（用来估计和校验）见图3.

图2 路网仿真运行Fig.2 The simulation of road network

图3 检测器布设图Fig.3 Layout of the detectors

将检测到的转向数据处理后，得到各交叉口及小区出入口的转向比例，即马尔可夫转移概率矩阵，整理得R和Q.由于实际检测器布设的限制，得到的数据会不相同.若能检测到小区发生量，则可直接由模型一估计；对于结构复杂网络，检测所有小区发生量很困难时，可根据模型二构建线性方程组.一般来说，布设检测器的路段数量要大于小区数量，即模型二中的线性方程组不会出现欠定情况，因此，采用模型二的线性方程组直接解法求解大型马尔可夫稀疏阵.下面考虑两种情况，分别运用模型估计.

4.1 情况一，由发生量估计OD 矩阵

将仿真得到的转移概率矩阵代入式（7），采用稀疏矩阵命令导入Matlab运算矩阵，将求得的路段流量与实测路段流量对比，见图4.

路段流量的平均相对误差在7.5%左右，模型可以很好地拟合仿真路段流量.由于路段流量是由OD矩阵经过马尔可夫转移概率矩阵分配计算得到，运用式（8）可计算出OD矩阵.

图4 模型一与模型二仿真流量的对照Fig.4 The contrast of traffic volumes in models and simulation

4.2 情况二，由若干路段流量估计OD 矩阵

路段流量的平均相对误差在8%左右，模型可以较好地拟合仿真产生的路段流量.将数据代入式（8）可估计出OD矩阵.

采用矩阵分布相对误差、均方根相对误差以及相关系数来检验估计的OD矩阵精度.前2个指标是对推算矩阵的整体准确度的评价，相关系数是对矩阵拟合情况的分析.见表1.

由于本算例中OD对较多，会对估计精度产生少许不利影响.情况二由于正反两次采用马尔可夫链计算，相比情况一误差略大.从路段流量的拟合情况来看，该模型还是能够很好地估计实际路段流量.

5 结语

本文对马尔可夫模型求解计算时采用了稀疏矩阵技术，使模型在算法上能够应用于大规模路网的OD估计问题.但该方法有一个缺陷——模型中的路

表1 对OD 矩阵的精度检验Tab.1 The evaluation of OD matrix

注：V＊ij为所估计的OD矩阵元素；Vij为真实OD矩阵元素；V—ij为各元素平均值；m为非零元素个数；n为小区数.径搜索问题.在进行路径加和时，考虑了所有可能的转移次数，而实际中往往不会发生车辆沿重复路径绕行的情况，在对大规模路网进行OD估计时，由此产生的误差对估计精度的影响不应忽略.对于模型如何消除路径中闭合回路的情况，还有待于进一步的研究，以使模型更符合实际.

［1］ Lida Y，Takayama J.Comparative study of model formulations on OD matrix estimation from observed link flows［C］∥Proceedings of 4th World Conference on Transportation Research，Rotterdam：The World Conference on Transport Research Society，1986：570－1581.

［2］ Sasaki T.Theory of traffic assignment through absorbing markov process［C］∥Proceedings of JSCE.Tokyo：Japan Society of Civil Engineering，1965：28－32.

［3］ Akamatsu T.Cyclic flows，Markov process and stochastic traffic assignment［J］.Transportation Research，1996，30B，369.

［4］ Junichi Takayama.Absorbing Markov processODestimation and a transportation network simulation model［C］∥Simulation Approaches in Transportation Analysis，part 2.Istanbul：The World Conference on Transport Research Society，2005：167－182.

［5］ 何迎晖.随机过程简明教程［M］.上海：同济大学出版社，2004.HE Yinghui.A simple tutorial for stochastic process［M］.Shanghai：Tongji University Press，2004.

［6］ 王沫然.Matlab与科学计算［M］.北京：电子工业出版社，2003.WANG Moran.Matlab and scientific computing［M］.Beijing：Publishing House of Electronics Industry Press，2003.

［7］ 陈宝林.最优化原理与算法［M］.北京：清华大学出版社，1989.CHEN Baolin.Principle of optimality and algorithms［M］.Beijing：Tsinghua University Press，1989.

［8］ Goldberg D G.Genetic algorithms in search，optimization，and machine learning［M］.Massachusetts：Addison－Wesley Pub Co，1989.