论文部分内容阅读
摘要:文章根据极大熵基本原理并运用排列组合理论推导出OD矩阵反推的极大熵模型;然后用拉格朗日乘子法求得该模型的非线性方程组,并运用Newton算法对此非线性方程组求解,得到动态OD估计矩阵。最后,在实例应用中,应用此模型和文章给出的模型解法取得了令人满意的结果。
关键词:交通网络;动态OD矩阵;极大熵;非线性;反推算法
中图分类号:U491文献标识码:A
OD是取自英文单词Origin(起点)和Destination(终点)的第一个字母。从单词的意思我们可以知道,OD矩阵即起讫点矩阵,反映了用户对交通网络的基本需求。它是进行交通网络规划和交通管理的重要依据。动态OD矩阵则反映了每个OD对间特定的时段内时变的交通需求模式。随着智能交通系统(ITS)的发展,动态OD估计与预测越来越受到重视。对于ITS中先进的交通管理系统(ATMS)和先进的出行者信息系统(ATIS),交通控制与路径诱导方案的制定不仅依赖于当前交通需求模式,而且有赖于未来的交通需求状况。因此,动态OD矩阵估计与预测是必需的。
历史上,OD数据是作大量的交通调查得到的,代价十分高昂。通过这种调查,得到的一般是所研究区域内的平均意义上的静态OD矩阵。目前,广为采用的方法是通过观察到的路段交通量和一些先验信息(如历史OD矩阵)来推算未知的OD矩阵,这比前者要先进许多。在OD矩阵反推模型中,极大熵模型具有模型结构简单,推算精度极高的特点,而且由于充分利用了路段交通量信息以及先验OD出行信息,模型推算结果比较符合实际的交通出行状况。本文就给出了极大熵模型的基本原理,以及用于OD矩阵反推模型的推导过程和求解方法。
一、极大熵模型
极大熵模型(Maxium Entropy,简称ME)是由Willumsen于1978年提出,极大熵模型原理认为车辆的出行是随机的,每种可能出现的OD出行分布状态,都有一个相应的存在概率。实际存在的OD出行分布状态,就是存在概率最大的那一个。由于存在概率函数大多有概率熵的形式,所以此模型称为最大熵模型。在众多的OD矩阵推算模型中,极大熵模型由于其模型结构简单、推算精度高且求解方便,应用最为广泛。如果把每个OD对Tij的出行看作一次随机事件,事件的总次数为:
(1)
根据排列组合原则,形成矩陣[Tij]的办法有:
(2)
极大熵的思想是寻找使W(Tij)最大的矩阵,即认为这样的矩阵出现的可能性最大,为求解方便,将目标函数设为:
(3)
使用Stirling逼近公式,则
(4)
忽略常数项ln(T!),则ME模型可表述为:
(5)
利用OD分配与路段流量之间的线性关系:
k =1,2,…,K.(6)
该问题即变成这样一个带约束的优化问题:
(7)
式中:Vk表示路段k上的流量,pijk表示OD对Tij在路段k上的分配比。
二、模型求解
理论上讲,只要按熵函数分别计算出满足流量约束关系的可行矩阵的熵值,选取最大,即可获得最优解。
对于上述非线性极值问题,不考虑其特殊性,有许多数学方法可用来求解,但其求解过程编制程序比较复杂,并且求解效率不够高。以下探讨的解法,是充分利用了极大熵模型中存在的具体情况,先将其转化为非线性方程组,再转化为以迭代过程求解一系列非线性方程的形式,从而达到简化求解算法,提高求解速度的目的。
使用Lagrange乘子法求解EM模型,将其转化为非线性方程组:
(8)
式(8)中,?姿k为Lagrange乘子。对式(8)中Tij进行求导:
(9)
由(9)式求得:
(10)
记,则:
(11)
(12)
式(12)是含有K变量和K个方程的非线性方程组,通过求解上述未知数即Lagrange乘子然后再由下式求出OD矩阵:
令;k =1,2,…,K.(13)
利用Newton法解非线性方程组(13),计算步骤如下:
(1)给处初始近似x0及计算精度?着1和?着2;
(2)假定已进行了k次迭代,以求出xk及F(xk),计算
,
并记;
(3)利用Gauss-Seidel解线性方程组Ak△xk=-bk得△xk;
(4)求xk+1=xk+△xk及F(xk+1);
(5)若或 ,则置x=xk+1,输出x,转入(6),否则转入(2);
(6)结束。
利用Newton法解非线性方程组具有收敛快和自校正等优点。但此算法对初始值的近似要求严格,鲁棒性较差,不好的近似值会导致Newton法局部收敛。为了克服之一缺陷,可以利用已有的OD矩阵初步估计出x的区间范围;然后利用估计值按照上述步骤进行迭代计算,能够极大地提高运算的成功率和效率。
三、算例测试
现有一交通网络,小区和路网结构图见图1,各路段交通量和初始OD见表1:
图1 交通网络图
表1 路段交通量和OD矩阵分布表
本文在VisualC++6.0环境下编程对算法进行仿真和实现,其中取?着1=?着2=0.01作为计算精度,进行了k=100次迭代运算,得到估计OD出行矩阵见表2。从表2的数据来看,估计OD矩阵与真实值比较符合,而且具有较高的精度。
表2 OD矩阵估计值
四、结论
本文详细介绍了由路段流量及相关信息反推OD矩阵的极大熵模型的推导和求解过程,并提出弥补Newton算法缺陷的方法。动态OD矩阵的获取一直是交通科研人员研究的热门课题,具有重要的理论意义和实用价值。
参考文献
[1]Cascetta E.Estimation of trip matrices from traffic counts and survey data:A generalized least squares estimator [J].Transportation Research,1984.
[2]马光英,李平,等.基于极大熵模型的交通出行矩阵解法研究[J].浙江大学学报,2006,10(10).
[3]黄海军.由路段交通量推算OD矩阵的EM和IM模型[J].系统工程,1993,11(5).
[4]李庆扬,莫孜中,祈力群.非线性方程组的线性解法[M].北京:科学出版社,1987.文章编号:1009-2374(2009)10-0018-02
关键词:交通网络;动态OD矩阵;极大熵;非线性;反推算法
中图分类号:U491文献标识码:A
OD是取自英文单词Origin(起点)和Destination(终点)的第一个字母。从单词的意思我们可以知道,OD矩阵即起讫点矩阵,反映了用户对交通网络的基本需求。它是进行交通网络规划和交通管理的重要依据。动态OD矩阵则反映了每个OD对间特定的时段内时变的交通需求模式。随着智能交通系统(ITS)的发展,动态OD估计与预测越来越受到重视。对于ITS中先进的交通管理系统(ATMS)和先进的出行者信息系统(ATIS),交通控制与路径诱导方案的制定不仅依赖于当前交通需求模式,而且有赖于未来的交通需求状况。因此,动态OD矩阵估计与预测是必需的。
历史上,OD数据是作大量的交通调查得到的,代价十分高昂。通过这种调查,得到的一般是所研究区域内的平均意义上的静态OD矩阵。目前,广为采用的方法是通过观察到的路段交通量和一些先验信息(如历史OD矩阵)来推算未知的OD矩阵,这比前者要先进许多。在OD矩阵反推模型中,极大熵模型具有模型结构简单,推算精度极高的特点,而且由于充分利用了路段交通量信息以及先验OD出行信息,模型推算结果比较符合实际的交通出行状况。本文就给出了极大熵模型的基本原理,以及用于OD矩阵反推模型的推导过程和求解方法。
一、极大熵模型
极大熵模型(Maxium Entropy,简称ME)是由Willumsen于1978年提出,极大熵模型原理认为车辆的出行是随机的,每种可能出现的OD出行分布状态,都有一个相应的存在概率。实际存在的OD出行分布状态,就是存在概率最大的那一个。由于存在概率函数大多有概率熵的形式,所以此模型称为最大熵模型。在众多的OD矩阵推算模型中,极大熵模型由于其模型结构简单、推算精度高且求解方便,应用最为广泛。如果把每个OD对Tij的出行看作一次随机事件,事件的总次数为:
(1)
根据排列组合原则,形成矩陣[Tij]的办法有:
(2)
极大熵的思想是寻找使W(Tij)最大的矩阵,即认为这样的矩阵出现的可能性最大,为求解方便,将目标函数设为:
(3)
使用Stirling逼近公式,则
(4)
忽略常数项ln(T!),则ME模型可表述为:
(5)
利用OD分配与路段流量之间的线性关系:
k =1,2,…,K.(6)
该问题即变成这样一个带约束的优化问题:
(7)
式中:Vk表示路段k上的流量,pijk表示OD对Tij在路段k上的分配比。
二、模型求解
理论上讲,只要按熵函数分别计算出满足流量约束关系的可行矩阵的熵值,选取最大,即可获得最优解。
对于上述非线性极值问题,不考虑其特殊性,有许多数学方法可用来求解,但其求解过程编制程序比较复杂,并且求解效率不够高。以下探讨的解法,是充分利用了极大熵模型中存在的具体情况,先将其转化为非线性方程组,再转化为以迭代过程求解一系列非线性方程的形式,从而达到简化求解算法,提高求解速度的目的。
使用Lagrange乘子法求解EM模型,将其转化为非线性方程组:
(8)
式(8)中,?姿k为Lagrange乘子。对式(8)中Tij进行求导:
(9)
由(9)式求得:
(10)
记,则:
(11)
(12)
式(12)是含有K变量和K个方程的非线性方程组,通过求解上述未知数即Lagrange乘子然后再由下式求出OD矩阵:
令;k =1,2,…,K.(13)
利用Newton法解非线性方程组(13),计算步骤如下:
(1)给处初始近似x0及计算精度?着1和?着2;
(2)假定已进行了k次迭代,以求出xk及F(xk),计算
,
并记;
(3)利用Gauss-Seidel解线性方程组Ak△xk=-bk得△xk;
(4)求xk+1=xk+△xk及F(xk+1);
(5)若或 ,则置x=xk+1,输出x,转入(6),否则转入(2);
(6)结束。
利用Newton法解非线性方程组具有收敛快和自校正等优点。但此算法对初始值的近似要求严格,鲁棒性较差,不好的近似值会导致Newton法局部收敛。为了克服之一缺陷,可以利用已有的OD矩阵初步估计出x的区间范围;然后利用估计值按照上述步骤进行迭代计算,能够极大地提高运算的成功率和效率。
三、算例测试
现有一交通网络,小区和路网结构图见图1,各路段交通量和初始OD见表1:
图1 交通网络图
表1 路段交通量和OD矩阵分布表
本文在VisualC++6.0环境下编程对算法进行仿真和实现,其中取?着1=?着2=0.01作为计算精度,进行了k=100次迭代运算,得到估计OD出行矩阵见表2。从表2的数据来看,估计OD矩阵与真实值比较符合,而且具有较高的精度。
表2 OD矩阵估计值
四、结论
本文详细介绍了由路段流量及相关信息反推OD矩阵的极大熵模型的推导和求解过程,并提出弥补Newton算法缺陷的方法。动态OD矩阵的获取一直是交通科研人员研究的热门课题,具有重要的理论意义和实用价值。
参考文献
[1]Cascetta E.Estimation of trip matrices from traffic counts and survey data:A generalized least squares estimator [J].Transportation Research,1984.
[2]马光英,李平,等.基于极大熵模型的交通出行矩阵解法研究[J].浙江大学学报,2006,10(10).
[3]黄海军.由路段交通量推算OD矩阵的EM和IM模型[J].系统工程,1993,11(5).
[4]李庆扬,莫孜中,祈力群.非线性方程组的线性解法[M].北京:科学出版社,1987.文章编号:1009-2374(2009)10-0018-02