高速公路交通量优化配置

1、高速公路交通量优化配置摘要：行车时间估测和最优路径选择是当今智能交通系统中的研究热点，特别是对于车辆诱导 和导航系统更具有深远的意义。本文以传统的交通流理论为理论基础，以某部门收集的多个 监测器的检测数据为资料，着重从数学的角度研究行车时间估计和最优路径选择的数学模 型，提出了几种合理的数学模型，并通过仿真实验验证了模型的合理性和可行性。首先，通过对大量实测数据的分析，发现了的方法，提出了用间接模型和动力学模型两 种方法来进行行车时间估计，并引用车流量信息对所得结果进行修正。接着根据交通流理论， 重点提出了更能准确地估算行车时间的交通流模型。然后，以应用较为广泛的Dijkstra算法为基础，建

2、立适用于静态状态下寻找最短路径 的一般算法，并且结合本文建立的时间估计模型，给出了适用于动态随机状态下的路径寻优 算法，用以解决实际状况下路段行车时耗期望随时间变化的问题。本文用matlab作为仿真工具，对整个数据的分析和算法的实现过程进行了仿真。通过 对仿真结果的对比和分析，验证了本文所提算法的准确性和合理性。最后，针对尚存在的缺 陷提出了模型的改进方向和思路。关键字： 动态最优路径高速公路交通交通流动力学车辆诱导系统一、问题的重述高速公路行车时间估计对于旅行者来说是一个至关重要的问题。因此，在美国许多高速 路口都悬挂着监视器。监控器可以用来监测车辆每天24小时通过检测器的速度，每隔20 秒

3、的时间监控器将报告20秒内的平均速度并进行刷新。本题一共包括三个大问题，每个大问题以及其中的各个小问题如下：第I大问题1、下表中给出了每个检测器处每隔2分钟最后20秒的平均速度，请根据数据分析高速路 上的路况信息（例如，堵车和消散等情况）。2、如果一辆车在t时刻通过某一监测器，那它会在什么时刻到达第五个监测器？3、请设计算法估计行车时间，并确定算法的合理性和准确性。4、如果行车数据每20秒提供一次而不是每2分钟提供一次，这些信息会怎样影响你的估 计值？5、如果所有的条件和上述的相同，监测器不仅给出了车辆的平均速度，而且给出了单位时 间的交通流量，这些额外的信息能不能改进你的算法的合理性和精确性

4、？如果可以，请 重新设计你的算法。第II大问题题目给出了美国圣安东尼奥市的城市地图，并反映了该城市的交通状况。旅行者可以 向车载导航系统中输入当前所在的位置及目的地，系统将帮助选择一条行驶路线并估计行车 时间。然而，因为每一路段行车时间的不确定性，现行系统提供的最优路线选择和行车时间 估计的可靠性并不能令人满意。1、请问能不能基于问题I的模型来改进导航系统？2、假设各路段行车时间是相互独立的随机变量。请设计一种算法进行最优路线的选择和行 车时间的估计，并请阐明对于最优路线的定义。3、如果各路段的行车时间依赖于起始时间，而且它们之间是相互关联的。请使用上面的地 图信息设计一个合理的协方差矩阵并设

5、计一种最优路线选择的算法，同样要阐明对于最 优路线的定义。第III大问题在第三幅图中，两条粗线指定了高速公路的行车方向均是靠右行驶。两节点间的车辆 可以到达与这些节点相连的任意路段，每两点的距离在表中给出。请分别找出由14节点到3节点和由3节点到14节点的最优路线，并且估计出行车时间。 行车时间遵循问题1中的行驶规律，行车时间的均值与路段的长度成正比，行车时间的方差 与路段的长度的2/3次方成反比，与路段两端（节点）所连接的高速公路路段数的乘积成正 比。二、模型描述及问题假设模型描述高速公路上的交通流问题对车辆诱导系统和车载导航系统有着重要的现实意义。根据 描述对象的不同，交通流模型可分为微观

6、模型和宏观模型;根据模型和其中变量的不同形态， 可分为静态模型和动态模型。其中，宏观动态交通流模型既能描述交通流沿道路空间的分布， 又能反映其随时间的变化规律，能够比较准确的描述交通流行为。本文通过最简单的间接法入手求解行车时间，然后使用动力学模型对算法进行改进，虽 然对行车时间的估计有了提高，但是仅仅有时间间隔比较大的速度信息并不能很好地描述交 通流的实际状态。为此，在给出密度信息和时间间隔缩短的情况下，我们使用了交通流模型 来模拟车辆在高速公路的通行过程，发现该算法能更好地逼近真实值，我们得到了行车时间 随出发时间t变化的曲线图，同时也发现交通流模型对于交通严重阻塞的情况下也有较大的 误差

7、。高速公路交通流模型是随时间、空间而变化、分布的规律及其与交通控制变量之间的 复杂关系。在车辆诱导系统和车载导航系统对于行车时间的估计大部分是基于静态的路径规划，而 这与动态的交通现实相悖。本文首先使用Dijkstra算法进行最短距离估计，然后通过对该算 法的距离值加权解决了静态最优路径的求解问题。并对该算法进行适当的改造，求解出无方 差约束条件和有方差约束条件下的以最小行车时间数学期望为最优线路的行车时间随机变 化的问题。当行车时间是一个与出发时间t相关的变量时，我们使用kalman滤波算法求解某 路径受到的其他路段行车时间产生的影响（协方差矩阵关系），该算法虽然计算量比较大， 但是能够表示

8、出复杂的系统相互干涉的情况。最后我们编程实现了我们前面理论探讨的各种算法，并且对问题I和问题III中的实际情 况作了计算和处理，得到了需要的数值结果。问题假设根据问题的描述及题中给定的已知条件，我们进行以下的假设：（1）只考虑在单一车道上行驶的车流，并且符合车辆跟驰理论，不考虑超车情况及由 于交通灯的控制造成的影响。（2）如果某车前面有足够的空间，该车将加速行驶；相反，若前面有车辆阻塞造成空 间不足，该车将减速行驶；（3）司机的反映动作只限于加、减速等正常行驶状况；（4）不考虑车道宽度的影响，并假设路面状况良好，无道路禁行和道路修建等情况。三符号说明文中出现的符号及其说明如下：符号定 义p（v

9、）密度（辆/mile），t时刻x点处单位长度所有的车辆数R (x, t)车流速度（辆/小时），t时刻x点处的车流密度a加速度（米/s2），速度对时间的变化率，dv/dtV t时间平均速度（mile/小时），在一定时间内，通过某定点的各车辆车速 的算术平均值Vs空间平均速度（mile/小时），在某一瞬间沿车道行驶一定长度内各车辆 速度的算术平均值q (x, t)流量，t时刻点x处单位时间通过的车辆数Vk畅通时的速度（米/s）k j阻塞密度（辆/mile）J 最大交通流量时的交通速度（米/s）J k m最大交通流量时的车辆密度（辆/mile）v,w从v到w的弧cv,wc50mile/h)的密度一速

10、度曲线v 七(1 - )(11)j其中，九，k .分别是畅通时的速度和阻塞密度。接着引入安德伍德模型拟合阻塞状态(v d + c .则修改dk为：dk =气+孔。4）重复操作2），3）步骤n-1次，由此求得按路线长度递增次序排列的从出发至图中 其余各项点的最短路线序列。以上算法将产生从源点出发至其余各顶点的最短路线，是一个行之有效的通用算法。2以行车时间最短为最优路线在路段上有交通堵塞发生时和考虑到其他因素，需要给路段要素增加一个加权系数属性, 并将路段长度与加权系数的乘积称为路段的加权长度。路段的交通越堵塞，此路段的加权系 数越大，对应路段的加权长度也越长。用路段的加权长度表示车辆通过此路段

11、的时间。此时 最优路线也可以表示为加权长度最短的路线。将Dijkstra算法中的长度替换为路线的加权 长度，就可求出连接起点和终点的最短路线，也即考虑了有交通堵塞发生时的最短路线。算法如下：设0 （V，E，w）为有向权图，其打是其顶点集合，E是边的集合，w是E中边（i,j） 的权的集合，称为该边的长度，记为w（i,j）。下面求从起点s到终点e的最短路线。设T是V的一个子集，且S不属于T ,记S=V-T(S顺序记录着最优路线上的结点)。对T中每一 个顶点t,记WL(t)为s到t的所有路线(这些路线不包括T中其它的任何点)中加权长度最短的 路线的长度,WL(t)称为t关于s的指标。若此路线不存在，

12、则令WL(t)=8。对T中每一顶点t,求WL(t)。设m是T中具有关于s的指标值最小的顶点，即WL(m) = min(WL(t)teT如果m就是终点e ,则结束；否则令S =SY m,T= T-m。如果T为空，则 到(4)；否则计算T中每个顶点关于S的指标。WLJ (m) = minWL(t), WL(m) + w(m, t)teT用S代替S，T代替T,重复的操作，直至m到达e为止。声明s到e不存在最短路线。3动态随机状态下的路线寻优交通流的动态特性交通流在整个交通系统中最具多变性，其变化往往难以预料。尽管如此，现代通讯技术 和预测技术的发展已使得对交通流的预测成为可能。通过对历史数据的分析并

13、结合实测数据 可以实现对交通流的实时预测。不过由于其极大的随机性，还是有一小部分变化无法预测到。 因此可以用普通变量和随机变量综合描述交通流的变化。此外，虽然交通流极易变化，它还 是具有一定的惯性，即在很短的时间内难以变化。通过以上分析可以看到，尽管交通系统极其庞大，富于变化，但其变化大致能被预测到。 其中不能被预测到的小波动，可以看作随机扰动。交通系统的这些特性决定了对车辆的导航 必然是在动态随机状态下的导航。在此状态下的导航既要把握住交通状况的变化趋势，对未 来的交通状况进行可靠的预测，又要详细地研究交通的随机特性，正确地刻画随机因素的分 布特征。动态随机特性的数学描述由以上对交通系统的分

14、析可知，可用普通变量和随机变量来综合描述各种因素对用户行 车的影响。依据车辆运行的特性，便可以建立起车辆运行速度的数学模型。将实时测得的各 种参数带入模型，并结合用户自身特性，可以估计其在未来某时刻路网的各路段的运行速 度，再结合各路段的长度，便可以准确地估计用户通过各路段的消耗的时间。以t表示用户通过路段(i,j)的行驶时间，由上述分析可知它是一个随机变量。根据对 /，j.一. .一.一一 .一 . 一.,.交通系统的分析可以认为，系统中发生的较大波动都能被预测到，而无法预测的都是小波动， 它们通常只影响本路段内的车辆。因此对于路网中的两条路段(i,j )和(k,l),其行驶时间的 概率密度

15、函数满足下述关系：f(x，y) = f (X) f (y)=jj xyf (x)f (y) = +3xf (x )dx f+3 yf (y)、jk.，l、j-3k，l-3(x)dx J+3-3yft (y )dy = E (t, ) E (t.k，l TOC o 1-5 h z ti，j，tk，lti，jL，l& 数。3, y) dxdyj*k，l其中，f(x，y)是t .和t f的联合概率从Ji，j k，l i，j k,l.,+3根据数学期望的定义有：k，lE(t t ) = JJ xyf(x，y)dxdy = JJ xyf (x)fl，j k，lfi，j k，l，j+3于是对于路段行驶时间

16、的协方差有:Cov(t t) = E(t-E(t)(t- E(t) =E(tt ) - E(t)E(t) = 0i, j, k ,li, ji, jk ,lk ,li, j k，/i, jk ,l根据方差的定义有:= E (tI, j(i, j )是-E(t )2 + 2 Cov(t t )(i, j )eP(k ,l )ePD( t ) = E( t- E( t . )2(i, j )eP(i, j )eP(i j )eP= E(t- E(t )2 = D(t ) TOC o 1-5 h z (i, j)eP(i, j )eP既有下式成立D( t.) = D(t.)(2-1)(i, j )e

17、P (i, j )云其中P是路网中任意一条路线。由于路段的行驶时间的方差在短期内不会变化，故在路线寻优时可将其看作常量。(2-1) 式可改写为D = D(2-2)(i, j )eP 式中D = D( t )D . = D(t .)(i j )eP 有数学期望的性质可知下式成立E ( t ) = E (t ) TOC o 1-5 h z (i, j )eP (i, j )eP或(2-3)T = TPi, j寸(i,式中 Tp= E ( ti ) ； Tj = E (tj。(i, j )eP 点i的行驶时间的期望值及方差,且令TS = 0 , = 0。根据式(2-2)和式(2-3),有 T = T

18、 = T + T = T + T对于路网中的任意节点i及其后继节点j，Pi和Pj分别是自起始节点S到节点i和节点的某 一路线且满足条件Pju P.O TPj、TPj和DPj、DPj分别表示自起始节点S沿路线Pj和Pj到达节Pk ,lk ,l I, JPI=DPIi, j+DI, J总结上述推理有以下等式成立:=Tp + T=Dp + D道路网的用户总是希望尽可能地减少路线的行驶时间期望值和行驶时间方差。然而，在 现实中，这两个目标常常相互矛盾，而呈现出此增彼减的情形。一个比较现实的思路是寻求二 者之间的相对平衡，比如，可在一定的行驶时间方差约束下寻求具有最小行驶时间期望值的 路线。动态随机状态

19、下的路线寻优当时耗在路网中各路段的随机波动不大时，即当各路段的时耗方差很小时，可暂时忽略 方差，而仅考虑用户在各路段的行驶时间期望值。此时的路线寻优，就是寻求具有最小行驶 时间期望值的路线。由于各路段的行驶时间期望值j（t）随时间t而变化，故而用于静态寻 优的Dijkstra算法不再适用。对其进行适当的改造，可获得较为理想的算法。在行车时间是一个独立的随机变量情况下，在不考虑方差只考虑数学期望的前 提下，以估计时间期望值最小为最优路线用OPEN表存放已经产生但还没有扩展的节点，用CLOSED表存放已经扩展的节点。求 解时耗期望值最小路线的算法可表述如下：1）设初始表中仅含起始点S，且T0；对于

20、其余节点有二二8。2）OPEN表为空，则出错；否则，从OPEN表中选择具有最小行驶时间期望值的节点i， 设其为BEST。确认BEST是否是目标节点，如果是，转步骤4）；否则，根据其在路网中的连 接路段属性生成节点i的后继节点j。对于每一后继节点j，如果它不和CLOSED表中的节点 相匹配，则完成下列步骤：由式（4）计算节点j的行驶时间期望值；如果节点j已和OPEN表中的一个节点相匹配，检查节点j是否具有较小的行驶时间 期望值，如果j节点的值较小，则用节点j的值代替匹配节点的值，然后设置匹配节点的后 向指针指向BEST节点；如果节点j不在OPEN表中，设置节点j的后向指针指向BEST节点，然后将

21、节点j 放入OPEN表中。3）从OPEN表中移出节点BEST，加入CLOSED表中，重复步骤2）。4）从BEST节点，遍历后向指针到原节点，报告路线解BES节点的值就是用户从起始 点到终点的最小行驶时间期望值。5）依据求出的解路线，由式（2）计算路线她亍驶时间方差Dp。由标准正态分布计算 其置信度为1-a的单侧估计区间（0，Tp +七而），其中中（已 T-a。该置信区间 表明若用户选择解路线，有1-a的概率保证用户能在T + N 时间以内到达终点。算法中的步骤2）不断地优化着从起始节点到其余节点的路线保证了算法的正确性。 此外，算法不仅求出了具有最小行驶时间期望值的路线解，还算出刻画路线时耗统

22、计特征的 单侧置信区间，以便于用户更好地进行选择。当行驶时间在路网中各路段的随机波动较大时，即当各路段的行驶时间方差较大时，就 不能暂时忽略路线的行驶时间方差，必须同时考虑时行驶时间的数学期望与方差。此时，上 述算法已不再适用，须另外设计新的算法。在行车时间是一个独立的随机变量情况下，在既考虑方差又考虑数学期望的前 提下，以估计的时间期望值最小为最优路线在随机因素严重地影响用户通过路网的行驶时间时,可考虑在合理的行驶时间方差范围 之内求解具有最小行驶时间期望值的路线。设合理的路线行驶时间的总方差应不超M，用 OPEN表存放已经产生但还没有扩展的节点，用CLOSED表存放已经扩展的节点。这里，

23、OPEN表和CLOSED表允许同一节点多次出现。算法的搜索步骤如下：1）设初始表中仅含起始点S，且Ts=0, Ds=0；对于其余节点有4=8。2）如果OPEN表为空，则出错；否则，从OPEN表中选择具有最小行驶时间期望值的节 点i，设其为BEST。确认BEST是否是目标节点，如果是，转步骤4）；否则，根据其在路网 中的连接路段属性生成节点i的所有后继节点。对于每一后继节点j,完成下列步骤：由式（5）计算节点j的方差；如果D M则转向下一个节点，并重复步骤1）；Pj由式(4)计算节点j的行驶时间期望值；设置节点j的后向指针指向BEST节点，然后将节点放入OPEN表中。从OPEN表中移出节点BES

24、T，加入CLOSED表中。重复步骤2)。从BEST节点，遍历后向指针到原节点，报告路线解。BEST节点的行驶时间期望值 和方差值就是用户从起始点到终点的最小行驶时间期望值和方差。由标准正态分布计算路线解时耗的置信度为1 - a的单侧估计区间(0， Tp + ND )，其中中(NJ T-a。该置信区间表明若用户选择解路线，有1-a的概 率保证用户能在T + N亨时间以内到达终点。在上述算法设计中：步骤2)在优化路线的同时，还不断地检验各路线能否满足时耗方 差的约束条件(DpWM)。这既保证了算法的有效性，又能减少不必要的计算，提高了运算 速度。算法所求得的路线解将随时耗方差上限M的变化而变化。同

25、一对起讫点的不同用户 会根据其出行需要选择彼此互异的方差上限M和最优路线。这将导致用户路线选择行为的 多样性，从而有力地抑制了 Braess悖论的发生。问题3:如果各路段的行车时间倚赖于出发时间，而且它们之间是相互关联的。 请使用上面的地图信息设计一个合理的矩阵并阐明最优化路线选择的算法动态路网模型是动态寻路算法的实施基础。适合车辆动态导航系统的交通路 网模型最需要考虑的是车辆通过某一路段的通行时间的特性，可以将实际的路网 抽象成由车流通过时间相连接的路口结点集合。设i,j,k,l分别代表地图中的节点，整个路网共有n个结点。T (t)为车辆 从i点行进到j点的行进时间，T (t )为车辆从k点

26、行进到l点的行进时1司。他们都 是与时间相关的一个量。在实际当中，每条路段上的T (t)数据一般可通过实际 统计数据与交通流预测模型结合计算得到，可按照一定的时间分辨率离散存储数 据，然后利用。T (t)的取值时间分辨率应根据特定应用需求而定，同时要受现 有的交通系统数据采集设施和交通预测模型的限制,并且寻路算法计算的精度也 直接和T (t)函数的取值时间分辨率相关。在不同路段的交通流不是孤立存在 的，他们相互联系相互影响，我们使用表征不同路段(i,j节点)该时刻行车时间 T (t)对下一时刻一个路段(k,l)的行车时间T (t )的影响作为他们之间的协方 差ICov(ij,kl)。然后使用k

27、alman滤波算法作彳行车时间的估计和选择最优路径。卡尔曼滤波法简介设被估计系统是下列线性离散时间系统：x ( k + 1)=(k + 1 , k) x ( k) + E( k) , y ( k) = C( k) x ( k) +v( k) 式中：x是n维状态变量，中(k + 1 , k)是nXn阶一步转移矩阵，w是p维的系统 噪声向量；y是m维测量向量；C( k)是m Xn阶的输出矩阵；v是m维的测量噪声 向量。假设系统噪声w(k)与测量噪声v(k)是互不相关的、零均值的噪声序列，即对所有的k有：Ew( k) = 0 , Ew( k) w t ( k) = Q ( k) , Ev( k) =

28、 0 , Ev( k)v t ( k) = R ( k)式中：E表示均值；pXp阶的系统噪声协方差阵Q(k)是对称正定的；mXm阶测量噪声协方差 阵R(k )是对称正定的。又设系统的初始状态x是n维随机向量，已知其一、二阶统计特征为E( x ) = x, E( x - x0) ( x - x ) t = Po其中初态x的协方差阵PO对称正定。再者设x0与讶改均不相关，即对所有的k,有EX0WT ( k) = 0 ,EX0VT ( k) = 0。当获得了测量信息y，y，y ( k)之后，假定已求得了状态x(k)的最优滤波 估计X ( k),在t(k + 1)瞬间的新测量信号y ( k + 1)尚

29、未获取之前，由于3( k)是完全 不可预测的白噪声序列。因此，从直观上说，根据已有的测量信息，只能用下式作为x (k + 1) 的一个预测估计：X ( k+11 k)=Q( k + 1 , k) X ( k)对测量信号y ( k + 1)的预测估计为y ( k + 1) = C( k + 1) x ( k + 1) . y ( k + 1)预测估计值的误差为 y( k + 1lk) = C( k + 1) X ( k + 11 k) +v( k + 1)因状态x ( k + 1)的最优预测估计X ( k + 1l k)有误差，应设法补偿之。可以得到的 反馈信息就是对测量信号预测估计的误差信号y

30、( k + 1lk)。它包含有新的测量y(k+1)的信 息，故名“新息”，即通过设反馈增益矩阵为K(k+1)来修正估计值。为便于P(k+1|k)的计算， 还需确定P(k+1|k)与P(k+1)的递推关系：P ( k + 1) = P ( k + 1l k) - K( k + 1) C( k + 1) P ( k + 1l k)综上所述，卡尔曼滤波器递推方程组如下所示：X ( k + 1l k)取 k + 1, k) X ( k)X ( k + 1) = x( k + 1lk) + K( k +1) y ( k + 1) - C()k +1) x (k+1lk)K( k + 1) = P ( k

31、 + 1lk) Ck + 1)C( k + 1) P ( k + 1lk)( C+1)+ 7 84 8 5 9 3.15 6 5.25 3在第II大问题中考虑了行车时间最短作为最优路径的情况，因为问题中没有给出实际行 车过程中存在交通拥挤和各种路段间的延时，我们就这里不讨论这种情况了。2）在行车时间独立量情况下，考虑方差，以动态估计时间期望值最短为最优路 径和时间估计。以下是根据题意所画出的路段的连接关系和长度的示意图。如图3-2其算法的搜索步骤如下所示：1）建立时耗期望与时耗方差矩阵据已知条件，时耗期望与两点间距离成正比，时耗方差与距离的负3/2次方成比例，还 和一路段两个终点所连路段数目的

32、乘积成正比。两点间距离矩阵在上一问题中已经给出，这 里我们设两点之间距离矩阵为W .lengthWt=kW,n,h3W广 k2 N N2W4th通过计算得出个路段n1n2的乘积矩阵如下表06000800D00D00606n120nnDC-0D0D060a00000C00C03:a0160126LZ：a：）0;0项12016012i；D0孑D0n00C0120,00900D003:0120司012D012D006V060120IE001200J0cU90D0芟D600012U0uaDi 012D060V0000IF0D0o1203j00000012ju120旦u000c0uaa8Jn80i：i0

33、0000aaD06gD003将Wlengh中的每一个元素按式atj = a2计算，在与上面的矩阵做点乘，可得耗时的方 差矩阵wD/k2如下表。J0.2170006650U0u0000o. m00.26JC:0:JCJ（：Ji： J. 441000000J00000 0.44101.389JC.78681C0C. 4034GJ0Ji：00.34801.湫0二J0j. 408.5000i：00C. 6茹001.0900J1.60980000a00 0.787G004.4C6960W.g000JG,00&064, 406901.389203l.494166000001.6101.0419 Uij00

34、1.77780JCCO. 4030JC0000.47999GJ0. 45889JC:i：0G0L 9469000ft3.22750o.:牡弟00i：00002.4例 L31c3.227500.39340d0000001. 77780e0.蹄400a.ai：0J00P&0.45889室也30002）设置起始节点S，且T = 0，D = 0；T = 0 D = 0；3）从S点出发，搜索与其相邻的节点中苴有最小行驶时间期望值的节点i，设其为 BEST。确认BEST是否是目标节点D，如果是，转步骤4）；否则，根据节点i在路网中的 连接路段的属性生成节点i的所有后继节点苔。对于每一后继节点苔，完成下列步

35、骤：由式Dp = Dp + D计算节点j的方差；如果Dp 疗则转向下一个节点，j=j+1并重复步骤1）；由式T=Tp + T/计算节点j的行驶时间期望值；设置节点j I的为bESt节点，然后将节点j作为下次循环的起始点。4）重复步骤2）。5）从BEST节点，遍历后直到目的点D为止，报告总时间解和路线解。6）由标准正态分布计算路线解时耗的置信度为1- a的单侧估计区间（0， Tp+叽近），其中中（脂 = 1-a。该置信区间表明若用户选择解路线，有1-a的概 率保证用户能在Tp + ND时间以内到达终点。根据上述的算法编写程序（见附录），并对题目给出的实际问题进行求解。当匕=1，k2=1时，M （

36、合理的路径总方差门限）取不同的值，其路线的走向会发生变化， 如图所示。起始点起始点当k1=1,k2=1,M=1时的走向图当k1=1,k2=1,M=4时的走向图当k1=1,k2=1,M=5时的走向图图4当选取不同M值时的路径选择图在上述算法设计中，步骤2)在优化路线的同时，还不断地检验各路线能否满足时耗方 差的约束条件(DpWM)。这既保证了算法的有效性，又能减少不必要的计算，提高了运算 速度。算法所求得的路线解将随时耗方差上限M的变化而变化。同一对起讫点的不同用户 会根据其出行需要选择彼此互异的方差上限M和最优路线，这也将导致用户路线选择行为 的多样性,。在具有时间相关系数时以动态估计时间期望

37、值最短为最优路径和时间估计。在实践中，很难确切掌握系统初始状态的验前知识，甚至根本不能掌握这些统计特征。但 由于卡尔曼滤波器在递推过程中不断用新息对状态估计进行修正，所以卡尔曼滤波器是渐近 稳定的，也就是说当滤波时间充分长时,状态初值的估计值对x(k)的估计的影响将衰减至近于 零,初始协方差阵P。对滤波估计误差协方差阵p(k)的影响也将衰减至近于零。因此,滤波的 初始条件可以用近似的算法确定。每一步迭代的过程与卡尔曼滤波器的递推过程相近，所不 同的是，每递推一次，需要计算系统噪声向量3 ( k)和测量噪声向量k)，然后把每一步测量 和计算出的参数 C ( k) , u( k) , 3( k)

38、记录下来，最后计算出系统噪声协方差阵Q和测量 噪声协方差阵R，一次迭代完成.将刚求出的 Q , R代入卡尔曼递推方程组再次进行迭代, 直至前后两次求出的 Q , R的相对误差小到预定的值为止。结语搜索最优路径是车辆导航系统的关键技术之一，静态型最优路径与真实最优路径存在 较大差异，基于动态行程时间的实时动态最优路径是具有真实意义的最优路径。预测路网上 各路段未来各时段的行程时间是搜索动态最优路径的基础，尚需深入研究提高路段行程时 间预测精度的预测策略、方法与技术；交通参数采集周期和引导信息更新周期对预测结果 与引导效果有重要影响，需要进一步研究合适的周期。文献11对行车时间和最优路径的计算作了

39、如下总结，路K类迎削潞径荧型计弃依据参数荻地方法计捉特点.行核时间离散为短时段历史静态易优路径过主尾一时段各路段行程时 问实钏宇前il佛计算量小动态昂仇旃径各辟段过去告盯段行程时叵实测事前叶察计算量较大盯静念最优路径当前或未米菜一时段各路段 行程时问英测成预测实时H算i|算量大动态最优帝径各廓段当前与未来齐EJ段行 程时倾基于实测的预测:时预制与计算、计算后很 X长町段静态路径当前或预洲1长段时闭内各 路段行程时问实洲或预测实时C预测)计第计第星大本文在上表的指导下，总结了智能交通系统的行驶时间估测与最优路线选择问题的一 些研究方法，建立了基于经典交通流理论的几个时间估计模型，可以更好地对拥挤

40、交通流情 况下行驶时间进行估测。以应用较为广泛的Dijkstra算法为基础，建立适用于静态状态下 寻找最短路径的一般算法，并且结合本文建立的时间估计模型，给出了适用于动态随机状态 下的路径寻优算法，用以解决实际状况下路段行车时耗期望随时间变化的问题。参考文献1张国强，晏克非动态随机状态下的车辆导航及其路径寻优算法，长沙交通学院学报，2002.92张怡.复杂环境下车辆导航系统最优路径规划算法研究，导弹与制导学报，2005.13杨昊，忠雁，钱大琳.城市交通流路段行程时间预测模型，北方交通大学学报，2001.44晏克非，苏永云，黄翔，覃煜，朱培康.车辆导航系统基于IJK的动态L最短路递推解 法，西安

41、公路交通大学学报，2001.1张可，刘小明，王笑京.车辆自动导航的路线优化系统，系统工程，2001.3张亚平，张起森.高速公路速度一流量模型研究，中国公路学报，2000.7曹丽，刘杰，尹朝征，路加.行驶时间估测及多点交通流数据融合，仪器仪表学报，2001.06王殿海，严宝杰.交通流理论.北京:人民交通出版社,2002.09韩凤春，刘东编.交通工程学.北京：中国人民公安大学出版社,2002.08倪江华编著.交通工程学计算示例.人民交通出版社，1993.06苏永云等.车辆导航系统的动态最优路径搜索方法研究.系统工程，2000.07附录1源程序%路况分析程序v=dlmread(v.txt,);n=d

42、lmread(n.txt,);ls=length(v);t=3.4007:3.18/(ls-1):6.5807;u=50.*ones(1,ls);p1,p2=size(v);for i=1:5figure(1)subplot(5,1,i)plot(t,v(i,:);hold on ;plot(t,u,r.-)ylabel(v mile/h);xlabel(t)title(Detector,num2str(i)axis(3.4007,6.5807,0,80)% hold on;endz=zeros(1,p2);for i=1:p2for j=1:p1if(v(j,i)50)z(i)=z(i)+1

43、;endendendfigure(2)plot(t,z);xlabel(时刻 T)ylabel (堵塞次数统计)；title(路段各时刻堵塞情况统计)axis(3.4007,6.5807,0,5.1)%间接法模型 % v=dlmread(v.txt,);n=dlmread(n.txt,);v=v.*1609/3600;n=n./20;p1,p2=size(v);mi=zeros(p1,p2);% vspace=zeros(p1,p2);% vtime=zeros(p1,p2);% %密度%for i=1:p1for j=1:p2mi(i,j)=n(i,j)./v(i,j);endend% %

44、%5len=636 417 522 475;for i=1:p1for j=1:p2-1vspace(i,j)=(v(i,j+1)+v(i,j)/2;%空 间平均速度vtime(i,j)=vspace(i,j)+var(v(i,j),v(i,j+1)/vspace(i,j);vmean(i,j)=2/(1/vspace(i,j)+1/vtime(i,j);endend% for j=2:p1%vtime(j,:)=(v(j,:)-v(j-1,:)/120;% end% 初始条件 % t=60007%起始时刻% x=3%起始监测点% 时间换算 %iii=1;timesum=0; x=1;vsum

45、=0;m=0;n1=0;for time=13207:120:25087ppT;x=1;for ii=x:1:4standard=13207;% a=floor(t/10000);% a1=t-a*10000;% b=floor(a1/100);% c=a1-b*100;% time=a*3600+b*60+c;q1=floor(time-standard)/120);% %vv=vmean(q1+1,x);% %t=len(x)/vv;%m=m+t*n(q1+1,x);n1=n1+len(x)*n(q1+1,x+1);%vsum(iii,pp)=vv;timesum(iii,pp)=t;%对

46、应各个时刻到下一路段所需时间PP=PP+1;x=x+1;endresult(iii,1)=sum(timesum(iii,:);result1(iii,1)=sum(len)*m/n1;iii=iii+1;m=0;n1=0;endt=3.4007:3.18/(length(result)-1):6.5807;figure(3)plot(t,result);hold on;plot(t,result1,r*)plot(t,result1,r)axis(3.4007,6.5807,0,900);xlabel(起始时刻)ylabel(从监测器1到监测器5所需时间估计)legend(修正前时间估计，修

47、正后时间估计)% 验证 %vvv=v(:,2:5);m,n=size(vvv);cha1=vvv-vsum;cha=(cha1).A2;cha=sum(cha);cha=mean(mean(cha1);%动力学模型 %v=dlmread(v.txt,);n=dlmread(n.txt,);v=v.*1609/3600;n=n;p1,p2=size(v);mi=zeros(p1,p2);vspace=zeros(p1,p2);vtime=zeros(p1,p2);% 密度 % for i=1:p1%for j=1:p2%mi(i,j)=n(i,j)./v(i,j);%end% end% % %5

48、len=636 417 522 475;for i=1:p2-1vspace(:,i)=(v(:,i+1)-v(:,i)./len(1,i);endfor j=2:p1vtime(j,:)=(v(j,:)-v(j-1,:)/120;end% 初始条件 % t=60007%起始时刻% x=3%起始监测点% 时间换算 %iii=1;timesum=0; x=1;vsum=0;for time=13207:120:25087ppT;x=1;for ii=x:1:4standard=13207;% a=floor(t/10000);% a1=t-a*10000;% b=floor(a1/100);%

49、c=a1-b*100;% time=a*3600+b*60+c;q1=floor(time-standard)/120);% %atime=vtime(q1+1,x+1);aspace=vspace(q1+1,x);vv=v(q1+1,x);atime+vv*aspace;% u=sym(u);t2=0.1;% %y1=0;for t1=t2:t2:480% vv=vv+(atime+vv*aspace)*t2;vv=vv+(vv*aspace)*t2;% if(vvlen(x)break;endendvsum(iii,pp)=vv;timesum(iii,pp)=t1;pp=pp+Ltime=time+t1;x=x+1;endresult(iii,1)=sum(timesum(iii,:);iii=iii+1;endt=3.4007:3.18/(length(result)-1):6.5807;% 验证 %;%result1=zeros(1,100);for i=1:100result1(i)=sum(len)*(timesum(i,:)*n(i,2:5)/(l