《超速行车最优路线分析》由会员分享，可在线阅读，更多相关《超速行车最优路线分析（13页珍藏版）》请在金锄头文库上搜索。
1、超速行车最优路线分析摘要我们每个人都有因某种原因外出从 A 地到达 B 地的经历，这时可以选择的交通工具多种多样，此处的交通工具统一为汽车，如今的交通四通八达，交通路线也是多种选择，如今选择最经济实惠又方便快捷的出行路线是人们关心的问题，在充分理解题意的基础上，我们提出了合理的假设.通过对问题的深入分析，我们将本题归结为一个带有约束条件的优化问题.采用了动态规划的方法.本文的核心是最优路线选择的模型与算法，我们应用图理论和最短路径算法（Floyd 算法）并借助 MATLAB 得出最优路线。针对问题一的第一小问：主要利用 Floyd 的最短路算法根据时间邻接矩阵对模型进行求解，输出最短时间 mi
2、n1=17.7809（小时）和时间最短的路线path1 =91 92 93 94 84 85 86 76 66 56 46 47 48 49 39 29 19 20 10（这里的数字代表图中的编号） 。连接节点间的路径并标出方向，路线如图 2 鲜绿色线所示。针对问题一的第二小问：解题方法如第一小问一样，只是更改了邻接矩阵，将花费作为每段路段的权，即根据费用邻接矩阵，同样利用 Floyd 算法求解，输出最少花费 min2=274.6458 (元)和花费最少的路线 path2=91 81 82 72 62 52 53 54 44 34 35 25 26 16 6 7 8 9 10（这里的数字代表图
3、中的编号） 。连接节点间的路径并标出方向，路线如图 2 黄色线所示。针对问题二：在问题一时间最短路径的基础上，根据变化的费用与减少的时间的比值，确定选择走超速路段还是走限速路段。经过计算得出最少时间为 14.2247（小时） ，最少花费为 528.4438（元） ，路线与最短路径一样path3=91 92 93 94 84 85 86 76 66 56 46 47 48 49 39 29 19 20 10（这里的数字代表图中的编号） 。连接节点间的路径并标出方向，路线如图 2 鲜绿色线所示。关键词：邻接矩阵 Floyd 算法 最优路径 等概率1、问题重述我们每个人都有因某种原因外出从 A 地到
4、达 B 地的经历，现要从 A 城出发赶往 B 城，A 城和 B 城间的道路情况可用图 1 表示，A 城在图的左下角，B 城在右上角，横向与纵向各有 10 条公路，且任意两相邻的十字路口距离为 100 公里，即 A 到 B 相距 1800 公里，任意相邻的十字路口间的一段公路（以下简称路段）都有限速（公里每小时） ，标注在图上，标注为 130 的路段为高速路段，每段收费 3 元。整个旅途中有两类费用，第一类与花费的时间相关，由公式 给15ct出， 单位小时。第二类是汽车的油费，每百公里油量（升）由公式t（ ）给出， 的单位为公里每小时。汽油每升 1.32cavb0.625,1.87bv元。图 1
5、根据上述已知条件及所给数据并结合实际情况回答下列问题：问题一：若遵守所以限速规定，分别求出时间最短的路线和花费最少的路线。问题二：为了防止超速行驶，交警放置了为了防止超速行驶，交警放置了一些固定雷达在某些路段上，如图上红色的路段。另外，他们放置了 20 个移动雷达。这些雷达等概率地出现在各个路段，一个路段可能同时发现多个雷达，也可能在装有固定雷达的路段发现移动雷达。每个雷达都监控了自身所在的整个路段。如超速 ，则有 的可能被雷达探测到，届时会被罚款 100 元；%10%70如超速 ，则有 的可能被雷达探测到，届时会被罚款 200 元。59假设 是遵守所有限速规定所花的最少时间，想在 时间内到达
6、 B 城，T 0.8T那么包括罚款在内最少花费多少？路线又是哪一条？2、问题分析2.1（问题一）图的编号：由题意可知，A 城和 B 城间的道路情况可用图 1 表示，图中共有 100 个节点，分为 10 行 10 列，第一行依次编号为：1、210；第二行依次编号为：11 12 20；以此类推第十行编号为：91 92 100由对题目的第一问分析，可知本题主要最优路线问题，我们应用图理论和最短路径算法（Floyd 算法）分别根据时间邻接矩阵和费用邻接矩阵对模型进行求解，并借助 MATLAB 得出最优路线及与之对应的时间和花费。2.1.1（第一小问）本小问主要解决的问题是找出时间最短的路线。首先经审题
7、可知图 1 中的交点可看成 100 个节点可把问题转换为图论问题，然后根据所给数据及公式得出以时间为权的时间邻接矩阵，最后运用最短路径 Floyd 算法在 MATLAB 中编程求得相应的时间最短的路线和所对应的时间。2.1.2（第二小问）本小问主要解决的是的问题是找出花费最少的路线。思路与第二小问一样，只是这里只是根据所给数据和公式得出相应的费用邻接矩阵，利用费用和速度建立线性方程，求出各段在限速下的最适合速度，最后运用最短路径 Floyd 算法在 MATLAB 中编程求得相应的花费最少的路线和所对应的花费。2.2（问题二）问题二分析：本文主要是求包括罚款在内的最少花费和路径，在问题一最短的时
8、间路径的基础上求解增加的费用与减少的时间的比值，确定合理的超速路段和超速多少。再跟据费用公式，便可以求解 18 段路得总费用。3、模型假设假设 1、本题所给的数据真实，可靠假设 2、住店、饮食和加油的时间忽略不计，假设 3、在限速的路段上，大部分路段采用最大速度行驶。假设 4、在每一段路上速度保持不变。4、模型建立与求解问题一的模型建立针对问题一的最短时间的路线问题，利用图论知识，对所给的各路段的限速图建立关于速度的时间邻接矩阵，运用 Floyd 算法，在 MATLAB 中运行可得结果。针对问题一的花费最少的路线问题，首先建立费用与时间的线性方程，求出最小费用下每一段最适合的速度，再利用图论知
9、识，对所给的各路段的限速与费用建立费用邻接矩阵，运用 Floyd 算法，在 MATLAB 中运行可得结果。问题一的模型求解问题一的第一小问：，A城和B城间的道路情况可用图1表示，图中共有100个节点，分为10行10列，第一行依次编号为：1、210；第二行依次编号为：11 12 20；以此类推第十行编号为：91 92 100，计算出一个100*100的关于速度的时间邻接矩阵X，在根据Floyd算法在MATLAB中设计程序并运行。运行结果：min1 =17.7809path1 =Columns 1 through 16 91 92 93 94 84 85 86 76 66 56 46 47 48
10、49 39 29 Columns 17 through 19 19 20 10所以求得最短时间为 17.7809 小时，路径为 91-92-93-94-84-85-86-76-66 -56-46-47-48-49-39-29-19-20-10。问题一第二小问：计算各段在限速下最小费用对应的速度：50(.621.875).301,23.,4i iii ii vviv 、 、（1）在 MATLAB 中运行得12345078.6v（2）将每段的最少费用对应的最小速度写成费用邻接矩阵 R,再利用 Floyd 算法在 MATLAB 中运行。运行结果：Min2 =274.6458Path2 =Column
11、s 1 through 16 91 81 82 72 62 52 53 54 44 34 35 25 26 16 6 7Columns 17 through 19 8 9 10所以求得最少费用为 274.6458 元 91-81-82-72-62-52-53-54-44-34-35-25-26 -16-6-7-8-9-10。根据所求得的路线在图中连接节点间的路径并标出方向，路线如图 2 鲜绿色线和黄色线所示。图 2问题二的模型建立对问题二的费用路段问题，首先利用问题一的最短时间路径，根据概率论建立罚款的金额，建立增加的费用与减少的时间的比值方程，求出 ，确定Q超速路段与限速路段，然后求出总费用
12、。问题二的模型求解确定罚款金额公式为 （3）170992车辆行驶的油费和住店饮食的费用和为： 5(0.6251.87).tv增加的费用和减少的时间及比值如下表提速 10% 提速 50%QTQTQ1300.06993.84320.25649.000854.981435.10451100.08263.74430.30308.421345.330527.7931900.10103.67380.37047.945836.374321.4519500.18183.75270.66677.802220.641911.7027表 1根据结果分析，50 路段选择 1 个超速 的路段。90 路段选择 2 个超速
13、50%的路段和 1 个正常行驶的限速路段。110 路段选择 9 个超速 的路段和10% 50%3 个正常行驶的限速路段。130 路段选择 2 个正常行驶的限速路段。综合上述费用总公式，求解得出总费用为 528.4438 元。参考文献（1）张凯杰; 潘奇：基于最短路径的求解与创新 ；科技创新导报； 2012（2）陈明椿 数学教育中的数学建模方法；福建师范大学 ；2002（3）李明树;杨秋松;翟健 软件过程建模方法研究； 软件学报；2009（4）李洪波;王茂波 Floyd 最短路径算法的动态优化；计算机工程与应用；2006（5）张德全;吴果林最短路问题的 Floyd 算法优化；许昌学院学报；200
14、9（6）王海江;陈瑾; 徐卫忠基于 Matlab 编程方法实现模糊推理及解模糊的方法；研究现代电子技术；2004附录在MATLAB中的程序如下：求最短时间的路线输出邻接矩阵X：X=zeros(100);for i=1:100for j=1:100if i=jX(i,j)=inf;end endendA=100./90 90 90 90 50 90 90 90 90;90 90 90 90 50 50 110 110 110;90 90 50 50 90 90 110 110 110;50 50 90 90 50 50 50 90 50;90 90 110 110 110 110 110 110
15、 90;90 90 90 90 90 90 90 90 50;50 90 110 110 110 90 90 90 90;50 90 90 90 90 90 50 50 50 ;90 110 110 110 110 90 90 50 50;110 130 130 130 130 130 130 130 130;B=100./90 90 110 90 90 90 110 90 90 110;90 90 110 50 50 90 90 90 110 90;50 50 110 50 50 50 50 50 110 50;90 50 110 90 50 90 50 50 50 50;90 90 110 90 90 90 90 90 50 50;50 90 110 90 50 90 90 90 50 130;50 90 90 90 90 110 90 50 50 130;50 90 90 90 50 110 90 90 90 130;90 110 90 90 50 50 50 90 90 130;for a=0:9for b=1:9X(a*10+b,a*10+b+1)=A(a+1,b);X(b-1)*10+a+1+10,(b-1)*10+a+1)=B(b,a+1);endendX;D,path,min1,path1=floyd(X,9
