《2005研究生数学建模竞赛优秀论文a题1418-a题》由会员分享，可在线阅读，更多相关《2005研究生数学建模竞赛优秀论文a题1418-a题（15页珍藏版）》请在金锄头文库上搜索。
1、1高速公路行车时间估计及最优路径选择问题1 问题复述问题复述I 行车时间的估计对于旅行者来说非常重要。因此，有些美国高速公路安装 了传感器。比如在圣安东尼奥（San Antonio）市在所有的双向六车道的高速路 上都安装了传感器。但是车辆往往会不停的变换车道，为了简化问题我们可以 忽略换道的影响，而只考虑一个车道的交通问题（如下图所示（参见原题）， 正方形代表传感器）。 1.传感器可以每天 24 小时探测每个车辆的速度。每辆车的速度信息每 20 秒刷新一次记录。下表是一组真实数据（由于交通数据非常巨大，因此只记录 了每 2 分钟间隔中最后 20 秒的数据，单位：英里/小时）。请分析高速公路上
2、的路况特点（如：拥塞及其疏导。一般来说时速高于 50 英里/小时认为不存在 拥塞问题。）如果车辆在时间 t 经过传感器，那么经过多久它通过第 5 个传感 器？请设计一种算法来估计车辆的运行时间，并证明算法的合理性和精确性。 如果路况信息每 20 秒（而不是每 2 分钟）刷新一次，那么这对你们的估计算法 有影响吗？ 在上面问题条件的基础上，如果传感器不仅能探测车辆速度，而且能探测 单位时间的交通流量（如下表，流量的单位是：车辆数/每 20 秒）。这些信息 是否有助于算法的合理性和精确性的提高？如果是，请重新设计你的算法。 II 第一张图（参见原题）是美国德克萨斯州圣安东尼奥市的地图。第二张图 （
3、参见原题）反映了圣安东尼奥市的路况信息。旅行者可以在车辆内置的导引 系统中输入当前位置和目的地，系统会帮助选择路径并估计需要的时间。不幸 的是，由于每一路段（两个十字路口之间的道路）的路况是随机的，系统不能 很好地确定最优（最快）路线和可靠的时间估计。 你能在问题 1 的基础上改进这个系统吗？ 1.假设每段路的运行时间是互相独立的随机变量，请为系统设计一种算法 来确定最优路线及时间估计。请明确你的“最优”是如何定义的。 2.每一段路的行车时间依赖于其出发时间，并且行车时间之间具有相关性。 为了考察相关性如何随时间变化，通常会建立一个和时间有关的协方差矩阵 ，分别表示两端路的两个交叉口。用上图设
4、计一个合理矩阵和( ,)Cov ij kl, , ,i j k l 算法来寻找最有路线。请定义清楚最优路线的含义。如果有 n 个交叉口，那么 时间相关的函数是一个阶的矩阵每一行或列代表路段：( ,)Cov ij kl(1)/2n n 。12,.,1 , 21,.,2 , 1,., (1)nn nn n III 上图（参见原题），粗线表示高速公路的不同方向，上面的表示从左到右， 左边的表示从上到下。车辆通过十字路口时，可以到达其它连接的路段。图中 共有 14 个路口。路口之间的距离如上表所示。请分别找出从路口 3 到路口 14，从路口 14 到路口 3 的最优路线和时间估计。旅行时间的条件同问题
5、 1，每 一段路的运行时间的期望和该路段长度成比例，方差和（路段长度）2/3的倒数 成比例，同时也和路段两头的连接的道路数量的乘积成正比。22 基本假设基本假设（1） 认为道路上行驶的车辆只有一种，即不考虑由于车辆种类而造成路 况及行车时间的影响； （2） 道路每个方向上只有一个车道； （3） 道路发生拥塞时能够有效疏导，即不会发生长时间的严重拥塞；3 符号说明符号说明：两个路口之间的一条道路；iL ：传感器 到的距离（英里）；ili1i ：车辆到达第 个传感器的时刻；iti：时刻从第 个传感器出发，到达第个传感器的行车时间；( )iktkti1i ：道路在 时刻出发需要的行车时间；tTt ：
6、 时刻传感器 处的速度；tiuti ： 时刻路段上探测点的平均速度，tut4 模型背景及分析模型背景及分析道路交通状态是非线性的，而且车辆、速度、路况之间具有交互作用。其 研究一般有二种模型：宏观、微观。宏观模型主要考察一些描述整体行为的变 量，如单位时间流量、流量密度、平均速度等。而微观模型主要考察单个车辆 的瞬时速度、车距等指标。从问题本身来看主要考察的是交通的宏观行为。 高速公路（highway）是国内较普遍的翻译，但在美国高速公路有另外一个 单词 freeway，其实 highway 大致相当于我国的一级公路或主干公路。由于美国 交通特别发达，而且没有中国这样多的收费站，因此高速公路（
7、highway）是美 国最繁忙的公路。其特点是：1.上下班有明显的高峰期；2. 由于公路建设时间 较长，很多车道需要维修，因此经常会有临时的车道封闭，从而造成交通拥挤 的情况。 对高速公路行车时间的预测和当时的路况、天气、地形等因素有关，当拥 塞现象比较明显时，行车时间的随机性和非线性更加显著，因此造成预测值可 靠性非常差。 从旅行者的出行角度考虑，一般用四个指标来衡量，一是考虑期望的行车 时间最短；二是考虑路线具有较高的可靠性，即发生严重阻塞的概率较小；三 是考虑路程最短；四是考虑费用最低。而有时这些指标之间往往是互相矛盾的， 需要在两者间做出平衡，在本文中我们把行车时间最短作为设计目标。5
8、 问题（问题（I）的分析与建模）的分析与建模令 表示车辆到达第 个传感器的时刻，表示 时刻出发，从第 个传iti( )iititi感器到第个传感器的行车时间。易知，从 时刻出发，到达各传感器的时刻1it 分别为：312111111( ). ()nnnntttttttt 整个路段的运行时间为：* 1( )ntii iTtMERGEFORMAT (1) 因为传感器之间的距离不大，因此可以认为速度线性变化，此时每一个路 段的运行时间可以用* MERGEFORMAT (2)式计算：* ,1()( )2tit i iiiuutlMERGEFORMAT (2) 这个算法可用以下模型表示：* 1,111(
9、)()1,.,( )2( )ntii itit i iiiiiiiTtuuintlttttt MERGEFORMAT (3) 针对题目中的数据，用 Matlab 计算出了从某一时刻出发从第 1 个传感器到 第 5 个传感器的行车时间，结果如下图所示：4图图 1 不同出发时刻总行车时间的变化图不同出发时刻总行车时间的变化图为了考察不同时刻出发运行时间的变差情况，我们把每 10 分钟的探测信息 作为一组（共 20 组），然后计算每组的变差值，计算公式如下：i5,55ii n i i iT T 5 2 ,5 1()5i li i l iTT 图 2 为总行车时间标准差随出发时刻不同的变化图；图 3
10、是每段路行车时 间标准差随出发时刻不同的变化图。5图图 2 不同时刻出发的总行车时间标准差不同时刻出发的总行车时间标准差图图 3 不同路段不同时刻出发的行车时间标准差不同路段不同时刻出发的行车时间标准差6从图中可以看出在 5:18:07PM（分组 11）到 6:18:07PM（分组 17）这段时 间变差比较大，这反映了下班时间道路比较拥挤的情况。路段三在高峰期的方 差最大，其次是路段四，这说明这两段路的通行能力较差（可能是本身的原因， 也可能是受交通信号、意外事故的影响）。 为了刻画不同时间出发，所经历的路程上路况的变化，我们定义了空间变 差，它表示从 时刻出发，路程上速度的变化，计算公式如下
11、：S tt21()intit Si t iuun 其中表示 时刻传感器 处的速度，表示 时刻路段上探测点的平均速tiutitut度，为探测点数量。针对题目中数据，可得图形如下：in图图 4 不同时刻出发旅行者所经历的速度变差图不同时刻出发旅行者所经历的速度变差图为了进一步分清道路所处的状态，可以用两个探测点的探测速度（英里/小 时）来定义此段路所处的状态：,1,1,1,150,50 50, 50,50 50,50 tit itit itit itit iuuuuuuuu 正常或拥塞严重拥塞1,2,3,4i 此时，我们可以计算出每一段路在不同路况情况下每英里行车时间（秒/英 里）的期望和标准差：
12、7表表 1 不同路况下行车时间的期望和标准差不同路况下行车时间的期望和标准差 路段一路段一路段二路段二路段三路段三路段四路段四 路段路段 路况路况期望标准差期望标准差期望标准差期望标准差 正常正常59.826.057.325.258.425.960.029.1 拥塞拥塞74.627.886.529.688.045.984.539.8 严重拥塞严重拥塞132.038.4392.1168.7536.0347.9283.4225.2 从表中可以看出在正常情况下车辆的速度非常稳定，在拥塞的情况下变动 要大一些，而在严重拥塞的情况下车辆的速度变化非常剧烈。 我们可以对两个传感器之间运行时间进行一种很简单
13、的预测：用从时刻kt开始和从时刻开始走完两个传感器间距离的时间的平均值，预测从时刻1kt2kt 开始走完这段路所需要的时间。即：1 2( )()()2ikik ikttt 然后根据公式* MERGEFORMAT (3)既可预测走完整段路的时间。下图是 4 个路段预测值和真实值的比较图。图图 5 预测值和真实值比较图预测值和真实值比较图从图中可以看出虽然预测方法简单，但是大部分时间预测值和实际值非常 接近；但是在路况拥塞的情况下，预测误差就比较大。这是因为模型考虑因素 较为简单，无法反映交通流的不确定性与非线性特征，抗干扰能力差。8卡尔曼滤波(Kalman Filtering) 是一种先进的控制
14、方法, 是一种基于线性回归 的预测方法。其采用由状态方程和观测方程组成的线性随机系统的状态空间模 型来描述滤波器, 并利用状态方程的递推性, 按线性无偏最小均方误差估计准则, 采用一套递推算法对滤波器的状态变量作最佳估计, 从而求得滤掉噪声的有用信 号的最佳估计。卡尔曼滤波具有独特的优点: 具有广泛的适应性, 由于卡尔曼滤 波采用较灵活的递推状态空间模型, 既能处理平稳数据, 也能处理非平稳数据; 只要对状态变量作不同的假设, 就可使其描述及处理不同类型的问题; 模型具有 线性、无偏、最小均方差性; 模型便于在计算机上实现, 且大大减少了计算机的 存储量和计算时间, 适于在线分析;预测精度较高
15、。 设为要预测的 时刻出发的行车时间，是状态转移参数（通过历史( )x tt( ) t数据获得），为随机干扰，服从参数为的正态分布。则状( )w t2(0,( )Q t 态转移方程为：* ( )(1) (1)(1)x ttx tw t MERGEFORMAT (4) 令为区段运行时间的观测值（需要通过观测的速度计算出来），为( )z t( )v t 观测误差（在此表示用速度均值计算区段运行时间的误差），它服从参数为 的正态分布。因为只有区段运行时间一个参数，所以观测方程2(0,( )R t 为：* ( )( )( )z tx tv t MERGEFORMAT (5) 对任意，有。令为预测方差。根据卡尔曼滤波理论, i j ( ) ( )0E w i v j( )P t 可以得到如下的计算步骤： 初始化：20, (0)(0),( (0)(0)(0)tE xxExxP 外推：( )(1) ( )( )(1) (1)(1)(1)x ttx tP ttP ttQ t 卡尔曼增益矩阵：1( )( ) ( )( )K tP tP tR t 更新：( )( ) ( )( ) ( )( ) ( )x tK tz tx tP tIK t P t
