超速行车最优路线分析

《超速行车最优路线分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、超速行车最优路线分析摘要我们每个人都有因某种原因外出从A地到达B地的经历，这时可以选择的交通工具多种多样，此处的交通工具统一为汽车，如今的交通四通八达，交通路线也是多种选择，如今选择最经济实惠又方便快捷的出行路线是人们关心的问题，在充分理解题意的基础上，我们提出了合理的假设•通过对问题的深入分析，我们将木题归结为一个带有约束条件的优化问题•采用了动态规划的方法•木文的核心是最优路线选择的模型与算法，我们应用图理论和最短路径算法（Floyd算法）并借助MATLAB得出最优路线。针对问题一的第一小问：趣利用Floyd的最短路算法根据时间邻接矩阵对模型进行求解，输出最短时间minl

2、=17.7809（小时）和时间最短的路线pathl=91929394848586766656464748493929192010（这里的数字代表图中的编号）。连接节点间的路径并标出方向，路线如图2鲜绿色线所示。针对问题一的第二小问：解题方法如第一小问一样，只是更改了邻接矩阵，将花费作为每段路段的权，即根据费用邻接矩阵，同样利用Floyd算法求解，输出最少花费min2二274.6458（元）和花费最少的路线path2=9181827262525354443435252616678910（这里的数字代表图中的编号）。连接节点间的路径并标出方向，路线如图2黄色线所示。针对问题二：在

3、问题一时间最短路径的基础上，根据变化的费用与减少的时间的比值，确定选择走超速路段还是走限速路段。经过计算得出最少时间为14.2247（小时）,最少花费为528.4438（元），路线与最短路径一样path3二91929394848586766656464748493929192010（这里的数字代表图中的编号）。连接节点间的路径并标出方向，路线如图2鲜绿色线所示。关键词：邻接矩阵Floyd算法最优路径等概率K问题重述我们每个人都有因某种原因外出从A地到达B地的经历，现要从A城出发赶往B城，A城和B城间的道路情况可用图1表示，A城在图的左下角，B城在右上角，横向与纵向各有10条公

4、路，且任意两相邻的十字路口距离为100公里，即A到B相距1800公里，任意相邻的十字路口间的一段公路（以下简称路段）都有限速（公里每小时），标注在图上，标注为130的路段为高速路段，每段收费3元。整个旅途中有两类费用，第一类与花费的时间相关，由公式q=5/给出,/单位小时。第二类是汽车的油费，每百公里油量（升）由公式c2=av--b（6/=0.0625,/?=1.875）岀，u的单位为公里每小时。汽汕每升1.3元。909090901'9—505000090o909009090905050909090-44^504W-11505090seA/QAanuct0(0>09CC0

5、909050109CC09ac09uc01：K)rA110TtU—l0130r—TTtJ»9130TTU0sTTU—05130051300913009130-fyfy'01：1305090130^404^090eeee图l根据上述已知条件及所给数据并结合实际情况冋答下列问题：问题一：若遵守所以限速规定，分别求出时间最短的路线和花费最少的路线。问题二：为了防止超速行驶，交警放置了为了防止超速行驶，交警放置了一些固定雷达在某些路段上，如图上红色的路段。另外，他们放置了20个移动雷达。这些雷达等概率地出现在齐个路段，一个路段可能同时发现多个雷达，也可能在装有固定雷达的路段发现移动雷

6、达。每个雷达都监控了自身所在的整个路段。如超速10%,贝I」有70%的可能被雷达探测到，届时会被罚款100元；如超速50%,则有90%的可能被雷达探测到，届时会被罚款200元。假设7'是遵守所有限速规定所花的最少时间，想在O.M时间内到达B城，那么包括罚款在内最少花费多少？路线又是哪一条？2、问题分析2.1（问题一）图的编号：由题意可知，A城和B城间的道路情况可用图1表示，图中共有100个节点，分为10行10列，第一行依次编号为：1、2……10；第二行依次编号为：1112……20；以此类推第十行编号为:9192……100出对题目的第一问分析，可知本题主要最优路线问题，我们应用

7、图理论和最短路径算法（Floyd算法）分别根据时间邻接矩阵和费用邻接矩阵对模型进行求解,并借助MATLAB得出最优路线及与Z对应的时间和花费。2.1.1（第一小问）木小问主要解决的问题是找出时间最短的路线。首先经审题可知图1中的交点可看成100个节点可把问题转换为图论问题，然后根据所给数据及公式得出以时间为权的时间邻接矩阵，最后运用最短路径Floyd算法在MATLAB屮编程求得相应的时间最短的路线和所对应的时间。2.1.2（第二小问）木小问主要解决的是的问题是找出花费最少的路线。思路与第二小问一样，只是