数学建模y05A高速公路行车时间估计和最优路径选择问题.pdf

全国第二届部分高校研究生数模竞赛 题 目 高速公路行车时间估计及最优路径选择问题 要： 本文研究了高速公路行车时间估计及最优路径选择问题。通过对原始数据的 分析及定义相应的指标，详细考察了高速公路上的行车时间变化规律，给出了不 同路段在正常、拥塞、严重拥塞等3 种模式下行车时间的期望和标准差。对插值 预测进行了讨论，根据插值算法对于交通高峰期行车时间巨涨落的预测能力不强 的问题，提出用卡尔曼滤波来预测的方法，并说明了其优越性。 通过建立每个路段运行时间的分布函数，得到了一般道路的行车时间分布 的密度函数。通过把寻找最优路径问题转换为不确定的PERT 网问题，给出了寻 找在一定概率下行驶时间最小的路径的方法。通过利用随机过程理论和卡尔曼滤 波理论，分别定义了每段路相互之间行车时间的协方差矩阵。 最后，根据本文取得的结果，针对一个具体的最优 （最快）路径问题，给 出了具体的求解过程，及其置信度，并对模型的优缺点进行了讨论。 2005 年全 研究生数学建模竞赛一等奖 1 防科技大学：朱延广，刘慧超，石福丽 速公路行车时间估计及最优路径选择问题 1 问题复述 I 行车时间的估计对于旅行者来说非常重要。因此，有些 国高速公路安装了 传感器。比如在圣安东尼奥 （San Antonio）市在所有的双向六车道的高速路上 都安装了传感器。但是车辆往往会不停的变换车道，为了简化问题我们可以忽略 换道的影响，而只考虑一个车道的交通问题 （如下图所示 （参见原题），正方形 代表传感器）。 1. 传感器可以每天24 小时探测每个车辆的速度。每辆车的速度信息每20 秒刷新一次记录。下表是一组真实数据 （由于交通数据非常巨大，因此只记录了 每2 分钟间隔中最后20 秒的数据，单位：英里/小时）。请分析高速公路上的路 况特点（如：拥塞及其疏导。一般来说时速高于50 英里/小时认为不存在拥塞问 题。）如果车辆在时间t 经过传感器，那么经过多久它通过第5 个传感器？请设 计一种算法来估计车辆的运行时间，并证明算法的合理性和精确性。如果路况信 息每20 秒 （而不是每2 分钟）刷新一次，那么这对你们的估计算法有影响吗？ 在上面问题条件的基础上，如果传感器不仅能探测车辆速度，而且能探测单 位时间的交通流量 （如下表，流量的单位是：车辆数/每20 秒）。这些信息是否 有助于算法的合理性和精确性的提高？如果是，请重新设计你的算法。 II 第一 图（参见原题）是 德克萨斯州圣安东尼奥市的地图。第二 图（参 见原题）反映了圣安东尼奥市的路况信息。旅行者可以在车辆内置的导引系统中 输入当前位置和目的地，系统会帮助选择路径并估计需要的时间。不幸的是，由 于每一路段 （两个十字路口之间的道路）的路况是随机的，系统不能很好地确定 最优 （最快）路线和可靠的时间估计。 你能在问题1 的基础上改进这个系统吗？ 1.假设每段路的运行时间是互相独立的随机变量，请为系统设计一种算法来 确定最优路线及时间估计。请明确你的 “最优”是如何定义的。 2.每一段路的行车时间依赖于其出发时间，并且行车时间之间具有相关性。 为了考察相关性如何随时间变化，通常会建立一个和时间有关的协方差矩阵 Cov(ij , kl ) ，i, j ,k ,l 分别表示两端路的两个交叉口。用上图设计一个合理矩阵和 算法来寻找最有路线。请定义清楚最优路线的含义。如果有n 个交叉口，那么时 间相关的函数Cov(ij , kl ) 是一个n(n 1) / 2 阶的矩阵每一行或列代表路段： 12, ..., 1n, 2 1, ..., 2n, n1, ...,n(n 1) 。 III 上图 （参见原题），粗线表示高速公路的不同方向，上面的表示从左到右， 左边的表示从上到下。车辆通过十字路口时，可以到达其它连接的路段。图中共 有14 个路口。路口之间的距离如上表所示。请分别找出从路口3