高速公路行车时间估计和最优路径

1、高速公路行车时间估计和最优路径许小可 孟凡志 苗瑞（大连海事大学信息工程学院 大连 116026）原始参赛论文摘 要：行车时间估测和最优路径选择是当今智能交通系统中的研究热点，特别是对于车辆诱导和导航系统更具有深远的意义。本文以传统的交通流理论为理论基础，以某部门收集的多个监测器的检测数据为资料，着重从数学的角度研究行车时间估计和最优路径选择的数学模型，提出了几种合理的数学模型，并通过仿真实验验证了模型的合理性和可行性。首先，通过对大量实测数据的分析，发现了的方法，提出了用间接模型和动力学模型两种方法来进行行车时间估计，并引用车流量信息对所得结果进行修正。接着根据交通流理论，重点提出了更能准确

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

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

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

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

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

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

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

9、义密度(辆/mile)，t时刻x点处单位长度所有的车辆数车流速度（辆/小时），t时刻x点处的车流密度加速度（米/s2），速度对时间的变化率，时间平均速度（mile/小时），在一定时间内，通过某定点的各车辆车速的算术平均值空间平均速度（mile/小时），在某一瞬间沿车道行驶一定长度内各车辆速度的算术平均值流量，t时刻点x处单位时间通过的车辆数畅通时的速度（米/s）阻塞密度（辆/mile）最大交通流量时的交通速度（米/s）最大交通流量时的车辆密度（辆/mile）v,w从v到w的弧c<v,wc<v,w是弧v,w的非负权值由vs到vt的一条路径延迟时间（s）延时后考察点x所处的位置用户通过

10、路段(i,j)的行驶时间（s）和的联合概率密度函数车辆路段行驶时间的协方差DPi自起始节点S沿路线Pi到达节点i的行驶时间的方差TPi自起始节点S沿路线Pi到达节点i的行驶时间的期望值四、第大问题的求解问题1：分析高速路上的路况信息我们得到的已知信息是某日从3:40:07pm到6:58:07pm时间段内，一条公路上五个检测器每隔2分钟给出的这两分钟内最后20秒内其监测到的平均速度。我们将各检测器对于时间变化的规律表示成图1-1。在图中我们可以得到如下的关于道路拥挤和消散的信息：检测器1：在时间段几乎不发生堵塞，速度比较恒定，绝大多数时间保持在50mile/h以上；检测器2：在多数时间内也不发生

11、堵塞，但在5:34到5:54时间段平均速度小于50mile/h,即会发生堵塞，这种情况可能是由于车流的高峰带来的，而且在曲线中还可以看到检测器处有一个交通堵塞到消散的过程。检测器3：此节点处的基本情况与检测器2相似，但阻塞的时间更长一些。检测器4：在整个时间段内几乎都有堵塞发生，而且在检测器2、检测器3发生堵塞时，该处的速度更低，疏散所需时间更长，是路况最差的路段。检测器5：同样有很长的一段时间监测到的平均速度小于50mile/h,但与检测器4相比，路况要好很多。图1-1 各检测处速度随时间变化曲线(红线代表50mile/h，横轴代表真实的时刻值)从图中我们可以得到以下路段信息：(1) 从图中

12、可以看出整个路段对应于不同时刻的堵塞情况，可以看出在5:34到5:54时间段最容易发生堵塞，从5:24 到6:12时间段的堵塞情况仅次之。(2) 在路段上行车速度的数值，很大程度上反映了路段的交通状况，是通畅还是阻塞，以及阻塞程度。(3) 高速公路交通流空间平均速度的动态变化，从顺畅交通过渡到拥挤交通再由拥挤交通消散到顺畅交通。(4) 高速公路上前后节点的交通情况互相影响，互相制约，组成一个非常复杂的动态系统。问题2：计算t时刻从第i检测器出发经过多长时间通过第五个检测器1 时间估计的简单模型题目中给出了一段时间内五个检测器检测到的平均速度，根据题目中给出的数据采用间接法求解行车时间的步骤如下

13、：1我们假定同一时刻相邻检测器检测到的速度为交通流在路段上的瞬时速度，；2在给定的时间间隔内，计算空间平均速度；3利用公式（1）将空间平均速度转化为时间平均速度； (1)4求两个速度的调和中项； (2)5求路段的行驶时间；6求多个路段的时间： (3)根据上面的算法，我们编制程序，求出在不同时刻由节点到达下一节点的时间，如表1-1所示。表1-1 不同时刻由节点到达下一节点的时间(单位：s)起始时刻X1-X2X2-X3X3-X4X4-X5起始时刻X1-X2X2-X3X3-X4X4-X53:40:07 PM25.6 16.1 28.5 27.3 5:20:07 PM25.0 15.3 33.9 11

14、8.1 3:42:07 PM21.9 14.2 27.8 26.6 5:22:07 PM25.6 15.7 37.1 92.4 3:44:07 PM24.1 15.2 29.2 26.9 5:24:07 PM26.6 21.7 53.1 55.9 3:46:07 PM23.9 15.6 28.5 25.3 5:26:07 PM27.6 31.6 333.7 64.4 3:48:07 PM24.3 14.8 21.8 20.4 5:28:07 PM27.1 23.6 80.5 73.3 3:50:07 PM23.0 14.5 18.5 17.9 5:30:07 PM28.7 34.6 155.7

15、 101.2 3:52:07 PM24.1 15.2 20.3 18.6 5:32:07 PM32.0 38.9 194.7 101.2 3:54:07 PM23.5 14.9 18.2 17.7 5:34:07 PM40.7 46.7 54.3 38.6 3:56:07 PM22.8 14.5 19.3 16.7 5:36:07 PM42.5 71.8 166.9 48.3 3:58:07 PM23.1 15.3 18.7 16.7 5:38:07 PM53.7 124.4 467.2 49.4 4:00:07 PM23.9 14.9 18.5 17.1 5:40:07 PM53.7 116

16、.6 584.0 53.1 4:02:07 PM23.5 15.4 18.7 16.2 5:42:07 PM56.9 186.6 584.0 46.2 4:04:07 PM23.5 15.3 18.8 17.6 5:44:07 PM56.9 311.0 467.2 51.8 4:06:07 PM23.3 14.6 21.4 20.4 5:46:07 PM54.7 109.8 166.9 40.9 4:08:07 PM24.1 14.8 36.5 36.6 5:48:07 PM63.2 133.3 122.9 59.0 4:10:07 PM23.1 15.8 32.4 26.9 5:50:07

17、PM58.1 71.8 93.4 66.4 4:12:07 PM23.3 14.9 18.5 18.3 5:52:07 PM37.0 30.1 75.4 73.3 4:14:07 PM23.5 14.9 22.9 21.3 5:54:07 PM35.6 45.5 93.4 64.4 4:16:07 PM25.0 15.8 19.3 17.9 5:56:07 PM28.7 22.8 77.9 106.3 4:18:07 PM23.0 14.5 20.0 20.6 5:58:07 PM27.4 22.8 97.3 132.9 4:20:07 PM22.8 13.9 20.7 21.3 6:00:0

18、7 PM27.1 17.8 45.8 73.3 4:22:07 PM26.1 15.7 19.8 22.4 6:02:07 PM27.9 18.7 40.3 46.2 4:24:07 PM23.9 15.0 25.7 25.6 6:04:07 PM27.4 24.9 155.7 81.8 4:26:07 PM23.3 14.7 18.7 23.1 6:06:07 PM28.2 23.3 101.6 163.5 4:28:07 PM24.3 15.6 35.4 51.8 6:08:07 PM28.5 27.9 122.9 101.2 4:30:07 PM20.8 13.4 23.4 23.6 6

19、:10:07 PM28.2 19.6 75.4 132.9 4:32:07 PM22.6 14.6 19.8 18.3 6:12:07 PM25.2 18.8 53.1 75.9 4:34:07 PM24.1 15.2 19.3 17.4 6:14:07 PM23.3 17.9 58.4 177.1 4:36:07 PM22.8 13.9 18.0 23.9 6:16:07 PM24.5 15.7 40.3 303.7 4:38:07 PM23.0 14.6 29.2 30.8 6:18:07 PM23.7 15.9 44.1 354.3 4:40:07 PM24.3 14.9 22.9 24

20、.2 6:20:07 PM24.3 15.0 35.4 303.7 4:42:07 PM24.1 14.5 22.0 25.0 6:22:07 PM24.3 15.0 35.9 236.2 4:44:07 PM23.0 14.7 21.0 21.3 6:24:07 PM22.4 14.6 17.4 28.0 4:46:07 PM24.1 13.8 19.5 28.7 6:26:07 PM23.1 14.8 18.8 31.7 4:48:07 PM24.3 14.7 28.5 41.7 6:28:07 PM22.6 13.7 20.9 37.3 4:50:07 PM25.2 15.3 36.5

21、59.0 6:30:07 PM23.3 14.8 24.3 30.4 4:52:07 PM24.7 16.7 32.9 37.3 6:32:07 PM23.1 14.7 19.6 25.9 4:54:07 PM26.4 15.8 36.5 49.4 6:34:07 PM23.7 14.2 20.5 21.7 4:56:07 PM24.7 15.8 24.9 33.2 6:36:07 PM21.9 13.2 27.5 27.3 4:58:07 PM24.3 15.7 29.2 35.4 6:38:07 PM23.3 14.6 32.0 28.7 5:00:07 PM24.1 15.7 38.3

22、55.9 6:40:07 PM21.9 13.5 31.6 32.7 5:02:07 PM23.9 15.3 38.3 70.9 6:42:07 PM23.3 14.8 25.4 23.1 5:04:07 PM22.8 14.5 21.0 28.0 6:44:07 PM23.3 14.2 21.2 20.6 5:06:07 PM24.1 14.5 22.9 33.2 6:46:07 PM23.9 13.7 18.4 18.2 5:08:07 PM23.0 14.9 23.4 27.6 6:48:07 PM23.0 14.6 22.9 20.4 5:10:07 PM23.0 14.4 25.4

23、38.6 6:50:07 PM23.5 14.5 19.6 18.2 5:12:07 PM23.0 14.6 30.3 41.7 6:52:07 PM22.4 14.1 18.8 17.1 5:14:07 PM24.3 14.6 18.1 21.9 6:54:07 PM22.2 14.0 18.2 16.6 5:16:07 PM25.2 15.8 19.1 24.2 6:56:07 PM21.4 14.2 19.3 17.6 5:18:07 PM23.9 14.7 26.8 53.1 6:58:07 PM21.6 14.9 25.1 21.3 然后，我们将表1-1中不同时刻的对应的段时间值相加

24、，就可以得出车辆在任意到达第五监测器的时间。在这里我们计算出不同时刻从第一个监测器到第五个监测器的时间，绘制成图1-2。图1-2 不同时刻从第一个监测器到第五个监测器的行车时间模型的分析与评价：在模型仿真得到的图像中，我们可以发现其通过整个路段的时间随起始时刻的变化情况。与我们前面所作的路况分析在规律上是一致的，在5:34到5:54时间段最容易发生堵塞。但是分析可知，简单模型只是用空间平均速度和时间平均速度的调和中项近似地表示该路段的平均速度，然后假设成在路段内一直以这个速度匀速行进，这是和实际情况不相符的，假设是不充分的。2 加速度描述与动力学模型(改进模型)针对前面所提简单模型存在的缺点，

25、我们考虑到不同时刻在不同路面车辆行驶的速度和加速度都是变化的，提出用动力学模型来解决这一问题。所谓动力学模型就是对加速度的表示，即动量方程进行描述。加速度即车流流速对时间的导数。注意到这里x与t有关，且就是考察点的车流速度v，加速度的另一表达式为 (4)分析上式可知，加速度是行驶时间和距离的二元函数，当时间加速度和空间加速度已知的时候，其加速度是随着距离而变化的。我们根据加速度模型提出迭代的方法求出其通过各路段所需时间。算法流程如图1-3所示：图1-3根据上面的算法，我们编制程序，求出在不同时刻由节点到达下一节点的时间，如表1-2所示。表12(单位:s)起始时刻X1-X2X2-X3X3-X4X

26、4-X5起始时刻X1-X2X2-X3X3-X4X4-X53:40:07 PM25.716.231.729.85:20:07 PM2515.454.9133.23:42:07 PM2214.330.728.95:22:07 PM25.715.758.5110.43:44:07 PM24.215.232.729.85:24:07 PM26.722.954.156.23:46:07 PM2415.630.727.35:26:07 PM27.859.7356.8140.83:48:07 PM24.414.922.120.65:28:07 PM27.224.7110.41273:50:07 PM2314

27、.518.617.95:30:07 PM2939.2180.239.23:52:07 PM24.215.220.418.75:32:07 PM32.344.7235.3813:54:07 PM23.61518.317.85:34:07 PM44.146.754.4813:56:07 PM2314.619.416.85:36:07 PM48.872473.677.23:58:07 PM23.215.418.816.85:38:07 PM59.4159.348061.44:00:07 PM241518.617.25:40:07 PM58.5151.948092.84:02:07 PM23.615.

28、518.716.35:42:07 PM69.8215.9171.761.44:04:07 PM23.615.318.917.65:44:07 PM83.7323.5123.192.84:06:07 PM23.414.621.720.65:46:07 PM67.8109.9125.992.84:08:07 PM24.214.985.431.55:48:07 PM78.1133.3123.192.84:10:07 PM23.215.937.431.55:50:07 PM8588.497.567.14:12:07 PM23.41518.618.55:52:07 PM37.130.397.567.14

29、:14:07 PM23.61523.321.65:54:07 PM35.768.8122.5122.84:16:07 PM2515.919.417.95:56:07 PM292499.9205.74:18:07 PM2314.520.120.75:58:07 PM27.624.6168.677.24:20:07 PM22.8142121.46:00:07 PM27.518.154.977.24:22:07 PM26.215.719.922.66:02:07 PM28.419.141.846.54:24:07 PM2415.12726.56:04:07 PM27.729.5238.3101.34

30、:26:07 PM23.414.718.724.26:06:07 PM28.525.5145.4101.34:28:07 PM24.415.646.960.36:08:07 PM28.837.2124172.44:30:07 PM20.913.623.823.86:10:07 PM29.220.911790.24:32:07 PM22.714.619.918.46:12:07 PM25.319.271.290.24:34:07 PM24.215.219.417.56:14:07 PM23.418.4116.5305.84:36:07 PM22.8141825.46:16:07 PM24.715

31、.867305.84:38:07 PM23.114.732.332.96:18:07 PM23.816.179.7368.44:40:07 PM24.41523.624.46:20:07 PM24.415.156.6305.84:42:07 PM24.214.522.625.16:22:07 PM24.415.153.8237.24:44:07 PM2314.721.221.36:24:07 PM22.514.617.546.94:46:07 PM24.413.919.631.26:26:07 PM23.214.918.951.14:48:07 PM24.514.831.342.26:28:0

32、7 PM22.713.821.242.84:50:07 PM25.315.37094.26:30:07 PM23.414.925.230.44:52:07 PM24.816.835.138.26:32:07 PM23.214.819.727.74:54:07 PM26.515.954.465.46:34:07 PM23.814.320.921.84:56:07 PM24.815.925.233.76:36:07 PM2213.333.131.84:58:07 PM24.415.731.336.16:38:07 PM23.414.642.237.65:00:07 PM24.215.759.875

33、.96:40:07 PM2213.646.745.95:02:07 PM2415.472.31086:42:07 PM23.414.92724.45:04:07 PM22.814.521.328.66:44:07 PM23.414.321.620.85:06:07 PM24.214.523.733.56:46:07 PM2413.818.618.25:08:07 PM231523.827.76:48:07 PM2314.623.320.85:10:07 PM2314.427.438.76:50:07 PM23.614.519.818.35:12:07 PM2314.636.945.66:52:

34、07 PM22.514.218.917.25:14:07 PM24.414.618.222.76:54:07 PM22.314.118.316.75:16:07 PM25.215.919.225.66:56:07 PM21.514.319.417.65:18:07 PM2414.729.353.66:58:07 PM21.61525.621.9然后，我们将表1-2中不同时刻的对应的段时间值相加，就可以得出车辆在任意到达第五监测器的时间。在这里我们计算出不同时刻从第一个监测器到第五个监测器的时间，绘制成图1-4。图 1-4 从监测器1到监测器5的时间估计通过与简单模型所得结果的比较，我们验证了结

35、果的正确性。而且可以发现用加速度模型来估算行驶时间，因为充分考虑到了交通延误的灵敏性，更能反映出路况的信息，所得的结果也更加精确。因为在模型中用迭代的方法对时间进行估计，所以对于下一次迭代时的时间来说是一次预测过程，下面我们将预测出的速度和实际测量到的速度进行比较，验证算法的正确性，如图1-5所示。图1-5 预测速度与实测速度比较图问题3：若行车数据每20秒提供一次如何影响算法我们前面得出的模型是基于题目给出数据分析后综合得出的，题目给出的数据是每2分钟最后20秒的平均速度。如果系统每20秒提供一次速度信息，那么对我们上面建立的模型会产生以下影响：由于路段上交通状态是动态变化的, 路段行程时间

36、也是动态变化的。但是受交通参数检测技术和预测分析技术的限制, 难以得到准确的、可用的行程时间随时间变化的关系式, 为此, 对时间作离散化处理, 将系统工作时间划分为若干时段, 认为单个时段内交通状态稳定、行程时当时段划分得较长时, 车辆可能在一个时段内就能完成出行, 这实际忽略掉了行程时间的变化。在一段时期之内,由交通数据采集设施得到的对于某一特定路段的通行时间随进入路段时刻的变化情况如下图所示图 1-6 行车时间随时刻变化的采集数据和拟合曲线考虑到交通车辆流是连续变化的，我们的采集间隔时间越小，采集到的数据和交通流的实际情况就越吻合。我们下面结合题中的信息进行分析：1、从上面计算的结果看，在

37、不发生堵塞的时候，车辆通常会在两分钟（120秒）内行驶通过所在路段。表中出现120秒后仍滞留在该路段的情况，因此表中的时间方向速度很难表征同一交通流，会造成估算的误差。2、在简单模型中，因为表中每两分钟给出一次速度，无法表征该交通流的实际速度，只能通过空间平均速度代替实际速度进行计算，造成估算的不准确。3、在动力学模型中，我们首先要构造时间和空间的加速度矩阵。而由于题目给出的速度变化每120秒变化一次，其中很多加速度也已经不能代表速度随时间的真实变化。虽然用迭代的方法进行估值，但因为其时间加速度矩阵的不够准确，也不能灵敏地反映路况信息。如果我们采用每隔20秒进行数据更新，模型会更好的符合实际情

38、况，更准确地估算行车时间，更具有准确性和合理性。问题4：若监测器再给出流量信息，会对模型有何影响我们在上面已经论证了这是一个交通流问题。在上面的分析中，我们只得到了不同时刻的速度信息，还不能用经典的交通流连续介质模型来进行行驶时间估计。如果系统不仅给出改路段的速度信息，而且给出流量信息，那么肯定能更加准确的知道路况的信息。当驶入该路段的流量增大时，有可能达到该路段的通行能力，从而使该路段交通流产生堵塞，导致下一节点位置出现间歇流。此时单纯使用速度作为参数已经不能恰当描述交通流的实际情况。我们可以用两种方法进行行驶时间估计。方法一：用式(5)对第二问题所建立的两种算法得到的结果进行优化。 (5)

39、图1-6用流量信息对简单模型得出结果进行修正上式融合了流量数据，这将在一定程度上提高精确程度，下面通过仿真试验得到验证。如图1-6和1-7。图1-7 用流量信息对加速度模型进行修正仔细观察上图的修正效果，发现用流量信息对两模型的时间估计结果进行修正，效果几乎一致，即对于已发生交通堵塞的区间修正的效果较大。具体到一般的公路上，由于拥挤时常发生，很容易影响估测结果。结果不够精确的原因主要是在堵塞路段不能准确代表空间平均速度，可用流量信息进行修正。方法二：中国交通部智能交通研究所的技术人员采用方法一，但只在交通顺畅的高速公路上采用。但是，通过上面的仿真分析，我们可以看出即使用流量进行融合，也只有一定

40、的改善。考虑到如果所有的检测器能够被一个中心随时监控，那么车辆经过检测点时，除了改变流量值，得到一个瞬时速度值之外，还查询得到这个时刻其它检测点上的时间平均速度和流量的值。那么一个车辆的一个瞬时速度就能够对应到一个此时刻车辆所在路段对应的密度。由流体力学的有关知识，流量;它表示t时刻点x处单位时间通过的车辆数；速度:它表示t时刻x点处的车流密度；密度：它表示t时刻x点处单位长度所有的车辆数。还有上述三个交通变量的一个关系式 (6)而L-W理论3认为速度应该是密度的一个函数，即假设 (7)对速度密度假设模型，易推出加速度的一般表达式为 (8) 综合交通流建模思想考虑，式(7)可改写成 (9)其中

41、为延迟时间，是延时后考察点x所处的位置，考虑延时时间就等于考虑惯性作用，它必将导出对加速度的描述。以上两式用微分近似公式代替，得到 (10)在将上式得出的加速度和速度、密度的关系式代入到加速度模型的算法中去，得出行车时间估计结果。方法二的实现步骤：1根据已知速度和流量数据求出各时刻密度，绘出密度速度实测关系图。2寻找各已知的密度速度模型，根据其提出的模型拟合出密度速度关系。3根据式10所提供的关系式，找到用速度和密度一起控制加速度的关系4用第（3）步的关系，用问题2中建立的加速度模型迭代求出行驶时间。曲线拟合，绘出密度速度实测曲线如图1-8所示。图1-8 密度速度实测曲线拟合速度和密度的关系，

42、先引入格林息尔治模型，用线性关系拟合畅通状态下（v>50mile/h）的密度速度曲线 (11)其中，分别是畅通时的速度和阻塞密度。接着引入安德伍德模型拟合阻塞状态（v<50mile/h）下的速度和密度的关系. (12)其中， 分别为最大交通流量时的交通速度和密度。图1-9图1-10拟合结果如图1-9，图1-10所示。拟合后所得的关系式：当速度大于50mile/h时， (13)当速度小于50mile/h时， (14) 我们根据拟合得到的关系式，按照上面的步骤进行仿真，估算行车时间，得到的仿真结果图如图1-11所示。图1-11 从监测器1检测器5的时间随时刻变化图五、第大问题的求解问题

43、1：基于问题的模型来改进导航系统目前对于车辆导航的研究多是基于静态的路线规划，而这与动态的交通现实相悖,关于动态导航的最新研究也大多是对静态导航的部分改进，譬如在静态导航的基础上辅之以实时的交通信息。这些导航系统忽略了交通系统动态多变的特性，或对其缺乏充分的考虑，以至于限制了在实际中的应用。并由此引发所谓的Braess 悖论，即当许多接受导航的车辆被分配到某一条先前并不拥挤的道路上时，会引发新的拥挤。要对车辆进行合理的导航，首先需要对交通系统进行分析，以便考察其动态随机的特性。在问题的模型下，我们可以看出当交通流的密度很小时，其对车辆的运行速度没有影响或影响很小，此时在进行车辆的动态导航时，可

44、不予考虑。当密度大到一定程度时，车辆之间的相互作用加强，此时车辆处于非自由行驶状态，其速度强烈地受到交通流的影响。问题2:各路段行车时间是相互独立的随机变量的情况下设计算法进行最优路线的选择和行车时间的估计。在路网中选择最优路线并按最优路线行驶是旅行者的最佳选择。然而交通堵塞的发生,可能对选择最优路线造成困难。车辆如果能够在这样的道路网络找到从起点到目的的最优路线, 则不仅节省了燃油和时间, 而且可以从宏观上改善交通状况, 减少或者避免交通堵塞。但无论哪种情况，最优路线都可归结为在特定道路网络中搜索总代价最小的目标路线问题。在本题中我们分别以下面四种方式定义最优路线：(1) 在路面状况良好且没

45、有交通阻塞的情况下，考虑汽车始终匀速行驶，此时两点间行车距离最短为最优路线，此时这也是两点间行车时间最短的路线。(2) 考虑到实际行车过程中存在交通拥挤和各种路段间的延时，这时我们以两点间行车时间最短作为最优路线。以上两种都是静态估计，没有考虑到交通流是一个时时刻刻的变化过程。(3) 在行车时间是一个独立的随机变量的前提下，在不考虑其方差只考虑数学期望的情况下，以静态估计的时间期望值最短为最优路线。(4) 在行车时间是一个独立的随机变量的前提下，在既考虑方差又考虑数学期望的情况下，以动态估计的时间期望值最短为最优路线。根据不同的最优目标, 可以定义相应的道路权重, 反映到图上, 就是各条弧的权

46、。一般有以下几种选取方法:(1) 将出行距离最短作为最优目标, 选取路段长度作为道路权重。(2) 将出行时间最短作为最优目标, 选取车辆通过路段的平均行使时间作为道路权重。将出行时间最短作为最优目标时, 还可以将表征路段行驶时间与交通流量之间关系的路阻函数作为道路权重。有关路阻函数的选取和标定，可以从现有模型，如美国联邦公路局提出的路阻函数模型、我国提出的回归型路阻函数模型、交通流三参数路阻函数模型等中选择一个，进而利用实测数据标定模型中的待定参数。1 以行车距离最短为最优路线一般来说，由于路段两个方向的交通流情况并不一致, 当采用与交通流有关的路阻函数时, 应采用有向图表示路网。我们选择了应

47、用较为广泛的Dijkstra算法，以下是算法的具体描述。为便于问题的求解，我们采用“结点弧段”的数据组织方式，即将每一个交叉路口抽象为一个结点对象，两结点之间路段为弧段，弧段的长度为该边的权重。给定带权有向图G=（VE），其中V是包含n个顶点的顶点集，E是包含m条弧的弧集，v，w是E中从v到w的弧，cv，w是弧v，w的非负权值，设vs，vt，为V中的顶点，Pst=（v=v，v1，vn）为V中由vs到vt的一条路线，则路线的权值总和可表示为：所谓最短路线问题就是指在带有权的有向图中，寻找从指定起点到终点的一条具有最小权值总和的路线问题。如果把权值看成弧的长度属性（距离），那么目标路线就是从起点到

48、终点的最短路线。如果把路线规划中的优化标准量化为道路的旅行代价，则最优路线规划就可以总结为在特定道路网中寻找具有最小旅行代价总和的最优路线问题。首先讨论单源点最短路线问题，即给定带权有向图C=（V，E）和源点v，求v到G中其余各顶点的最短路线。关于这一问题，Dijkstra提出了按路线长度递增的次序产生最短路线的算法，其产生最短路线的原理如下：先设置一个辅助向量D，它的每个分量di表示当前所找到的从起点到每个终点的最短路线的长度。设置D的初始状态为：若从v到vi有弧，则di为弧上的权值；否则令di为。显然，长度为：的路线就是从v出发的长度最短的一条路线。设S为已求得的最短路线的终点的集合，则可

49、以证明：下一条最短路线（终点为x）或者是弧v，x，或者是中间只经过S的终点而最后到达顶点x的路线。因此，下一条长度次短的最短路线的长度必为：其中di或者弧v，vi的权值，或者是dk（vkS）和弧vk，vi的权值之和。根据以上原理可得到如下描述的最短路线生成算法：1）利用邻接矩阵C来表示带权有向图G，其元素cij表示弧vi，vj的权值；若弧vi，vj不存在，则将cij设为。令S为已找到从vs出发的最短路线的终点的集合，将其初始化为空集。di用表示从vs出发到终点vi的可能到达的最短距离，取其初始值为， 2） 选择vj，使得则vj就是当前从vs出发的最短路线的终点。令S=SUvj3） 修改从vs出

50、发到集合VS中任一顶点vk的可到达最短路线长度，如果则修改dk为：。4）重复操作2），3）步骤n-1次，由此求得按路线长度递增次序排列的从出发至图中其余各项点的最短路线序列。以上算法将产生从源点出发至其余各顶点的最短路线，是一个行之有效的通用算法。2 以行车时间最短为最优路线在路段上有交通堵塞发生时和考虑到其他因素，需要给路段要素增加一个加权系数属性, 并将路段长度与加权系数的乘积称为路段的加权长度。路段的交通越堵塞, 此路段的加权系数越大, 对应路段的加权长度也越长。用路段的加权长度表示车辆通过此路段的时间。此时最优路线也可以表示为加权长度最短的路线。将Dijkstra 算法中的长度替换为路线的加权长度, 就可求出连接起点和终点的最短路线, 也即考