城市车辆定位系统的分析与研究
摘 要：
行车时间估测和最优路径选择是当今智能交通系统中的研究热点，特别是对于车辆诱导和导航系统更具有深远的意义。本文以传统的交通流理论为理论基础，以某部门收集的多个监测器的检测数据为资料，着重从数学的角度研究行车时间估计和最优路径选择的数学模型，提出了几种合理的数学模型，并通过仿真实验验证了模型的合理性和可行性。
首先，通过对大量实测数据的分析，发现了的方法，提出了用间接模型和动力学模型两种方法来进行行车时间估计，并引用车流量信息对所得结果进行修正。接着根据交通流理论，重点提出了更能准确地估算行车时间的交通流模型。
然后，以应用较为广泛的Dijkstra算法为基础，建立适用于静态状态下寻找最短路径的一般算法，并且结合本文建立的时间估计模型，给出了适用于动态随机状态下的路径寻优算法，用以解决实际状况下路段行车时耗期望随时间变化的问题。
本文用matlab作为仿真工具，对整个数据的分析和算法的实现过程进行了仿真。通过对仿真结果的对比和分析，验证了本文所提算法的准确性和合理性。最后，针对尚存在的缺陷提出了模型的改进方向和思路。
关键字： 动态最优路径 城市公路交通 交通流动力学 车辆诱导系统
一、问题的重述
城市公路行车时间估计对于旅行者来说是一个至关重要的问题。因此，在美国许多城市路口都悬挂着监视器。监控器可以用来监测车辆每天24小时通过检测器的速度，每隔20秒的时间监控器将报告20秒内的平均速度并进行刷新。
本题一共包括三个大问题，每个大问题以及其中的各个小问题如下：
第Ⅰ大问题
1、 下表中给出了每个检测器处每隔2分钟最后20秒的平均速度，请根据数据分析城市路上的路况信息（例如，堵车和消散等情况）。
2、 如果一辆车在t时刻通过某一监测器，那它会在什么时刻到达第五个监测器？
3、 请设计算法估计行车时间，并确定算法的合理性和准确性。
4、 如果行车数据每20秒提供一次而不是每2分钟提供一次，这些信息会怎样影响你的估计值？
5、 如果所有的条件和上述的相同，监测器不仅给出了车辆的平均速度，而且给出了单位时间的交通流量，这些额外的信息能不能改进你的算法的合理性和精确性？如果可以，请重新设计你的算法。
第Ⅱ大问题
题目给出了美国圣安东尼奥市的城市地图，并反映了该城市的交通状况。旅行者可以向车载导航系统中输入当前所在的位置及目的地，系统将帮助选择一条行驶路线并估计行车时间。然而，因为每一路段行车时间的不确定性，现行系统提供的最优路线选择和行车时间估计的可靠性并不能令人满意。
1、 请问能不能基于问题Ⅰ的模型来改进导航系统？
2、 假设各路段行车时间是相互独立的随机变量。请设计一种算法进行最优路线的选择和行车时间的估计，并请阐明对于最优路线的定义。
3、 如果各路段的行车时间依赖于起始时间，而且它们之间是相互关联的。请使用上面的地图信息设计一个合理的协方差矩阵并设计一种最优路线选择的算法，同样要阐明对于最优路线的定义。
第Ⅲ大问题
在第三幅图中，两条粗线指定了城市公路的行车方向均是靠右行驶。两节点间的车辆可以到达与这些节点相连的任意路段，每两点的距离在表中给出。
请分别找出由14节点到3节点和由3节点到14节点的最优路线，并且估计出行车时间。行车时间遵循问题1中的行驶规律，行车时间的均值与路段的长度成正比，行车时间的方差与路段的长度的2/3次方成反比，与路段两端（节点）所连接的城市公路路段数的乘积成正比。
二、模型描述及问题假设
模型描述
城市公路上的交通流问题对车辆诱导系统和车载导航系统有着重要的现实意义。根据描述对象的不同，交通流模型可分为微观模型和宏观模型；根据模型和其中变量的不同形态，可分为静态模型和动态模型。其中，宏观动态交通流模型既能描述交通流沿道路空间的分布，又能反映其随时间的变化规律，能够比较准确的描述交通流行为。
本文通过最简单的间接法入手求解行车时间，然后使用动力学模型对算法进行改进，虽然对行车时间的估计有了提高，但是仅仅有时间间隔比较大的速度信息并不能很好地描述交通流的实际状态。为此，在给出密度信息和时间间隔缩短的情况下，我们使用了交通流模型来模拟车辆在城市公路的通行过程，发现该算法能更好地逼近真实值，我们得到了行车时间随出发时间t变化的曲线图，同时也发现交通流模型对于交通严重阻塞的情况下也有较大的误差。城市公路交通流模型是随时间、空间而变化、分布的规律及其与交通控制变量之间的复杂关系。
在车辆诱导系统和车载导航系统对于行车时间的估计大部分是基于静态的路径规划,而这与动态的交通现实相悖。本文首先使用Dijkstra算法进行最短距离估计，然后通过对该算法的距离值加权解决了静态最优路径的求解问题。并对该算法进行适当的改造，求解出无方差约束条件和有方差约束条件下的以最小行车时间数学期望为最优线路的行车时间随机变化的问题。当行车时间是一个与出发时间t相关的变量时，我们使用kalman滤波算法求解某路径受到的其他路段行车时间产生的影响（协方差矩阵关系），该算法虽然计算量比较大，但是能够表示出复杂的系统相互干涉的情况。
最后我们编程实现了我们前面理论探讨的各种算法，并且对问题Ⅰ和问题Ⅲ中的实际情况作了计算和处理，得到了需要的数值结果。
问题假设
根据问题的描述及题中给定的已知条件，我们进行以下的假设：
（1）只考虑在单一车道上行驶的车流，并且符合车辆跟驰理论，不考虑超车情况及由于交通灯的控制造成的影响。
（2）如果某车前面有足够的空间，该车将加速行驶；相反，若前面有车辆阻塞造成空间不足，该车将减速行驶；
（3）司机的反映动作只限于加、减速等正常行驶状况；
（4）不考虑车道宽度的影响，并假设路面状况良好，无道路禁行和道路修建等情况。
