超速行车的路线分析.doc

超速行车的路线分析摘 要当今，在车辆越来越多的情况下，超速行车成为了一种普遍的社会问题，为了节约时间和费用，人们都会考虑选择最优路线。本文就是利用数学模型来选择出时间最短的路线和花费最少的路线。先将路线中的十字路口进行标号，从左至右依次进行，第一行的第一个路口记为1，第一行的第二个路口记为2，第一行的第三个路口记为3,以此类推，B城记为10，A城则记为91。问题一：利用Floyd算法和Matlab软件，计算出在遵守所有的限速规定下，时间最短的路线是：，时间小时；花费最少的路线是：，费用元。问题二：首先，分别考虑四种情况下从A点到达B点所花的时间，即所有的路线都加速；所有的路线都加速；水平路线加速、垂直路线加速和水平路线加速，垂直路线加速的情况，根据时间要小于，选择符合条件的一种情况。其次计算包括被雷达检测到所花的费用总和，最后，利用Floyd算法和Matlab软件，挑选出所花费用最少的路线是：，费用。关键词： Floyd算法 Matlab软件 时间最短路线 费用最少路线1问题重述你驱车从A城赶往B城。A城和B城间的道路如下图所示， A在左下角，B在右上角，横向纵向各有10条公路，任意两个相邻的十字路口距离为100公里，所以A城到B城相距1800公里。任意相邻的十字路口间的一段公路(以下简称路段)都有限速，标注在图上，单位为公里每小时。标注为130的路段是高速路段，每段收费3元。整个旅途上的费用有如下两类。第一类与花费时间相关，如住店和饮食，由公式给出，单位小时。第二类是汽车的油费，每百公里油量(升)由公式给出，其中，的单位为公里每小时。汽油每升1.3元。本文所要解决的问题是：问题1. 若你遵守所有的限速规定，那么时间最短的路线和花费最少的路线分别是哪一条？问题2.为了防止超速行驶，交警放置了一些固定雷达在某些路段上，如图上红色的路段。另外，他们放置了20个移动雷达。这些雷达等概率地出现在各个路段，你可能在一个路段同时发现多个雷达，也可能在装有固定雷达的路段发现移动雷达。每个雷达都监控了自身所在的整个路段。如果你超速，你有的可能被雷达探测到，届时会被罚款100元；如果你超速，你有的可能被雷达探测到，届时会被罚款200元。假设是遵守所有限速规定所花的最少时间，但你有急事想在时间内赶往B城，那么包括罚款在内最少花费多少？路线又是哪一条？2问题分析A城到B城相距1800公里，从A城到B城的路线有很多，根据要求选择出最佳路线。 问题一：遵守所有的限速规定下，速度越大，所需要的时间越短。所以时间最短的情况下，每一路段都得以最大速度（即限速）行驶，但每一段的速度均不同，需要的时间也就不同，故需要考虑整个路线所需要的总时间。花费最少的路线的决定因素是速度，只要算出费用最少时的速度，就可以算出总的最少的花费。问题二：遵守所有限速规定所花的最少时间，要在时间内赶往B城，那么一定得超速才能到达。但超速有可能被雷达探测到，探测到的话则要罚款，增加了费用，故在超速的前提下，要尽量降低被雷达探测到的概率。为使问题简单化，我们先只考虑四种情况：1、每段速度均超速且限速； 2、每段速度均超速且限速；3、横向速度均超速且限速，竖向速度均超速且限速；4、横向速度均均超速且限速，竖向速度均超速且限速。然后选择出时间小于的路线，运用Floyd算法和Matlab软件计算出各自的费用，再考虑雷达的费用，总费用小的即为所求。3模型假设和符号说明模型假设：假设一：假设题目给的数据是正确、合理的。假设二：假设车经过每一段路的速度是匀速的。假设三：假设车在路口拐角处的时间可忽略不计。假设四：假设车在路口拐角处的速度变化是瞬时的。假设五：假设移动雷达等概率地出现在各个路段。符号假设：符号符号说明每段路所需时间（小时）A城到B城所需最短时间（小时）每段路的行驶速度（公里/每小时）每段路的路程（公里） 雷达探测到的罚款费用（元） 雷达探测罚款的数学期望 移动雷达出现在一个路段的概率 第一类费用，如住店和饮食（元） 第二类费用，汽车的油费（元）A城到B城所需最少费用（元）4模型建立与求解问题一：Floyd算法的基本思路是：从图的带权邻接矩阵开始，递归地进次更新，即由矩阵，按一个公式，构造出矩阵；又由用同样的公式构造出矩阵；最后又由用同样的公式构造出矩阵。矩阵的行列元素便是号顶点到号顶点的最短路径长度，称为图的距离矩阵，同时还可以引入一个后继点矩阵path来记录两点间的最短路径。其递推公式为时间最短路线的模型建立与求解：每段路所需时间为： （1）当时，所需时间为 （2）当，所需时间为 （3）当，所需时间为 （4）当，所需时间为 （5）把每行每段所需时间写成一个矩阵形式为：A = 把每列每段所需时间写成一个矩阵形式为：B = 再利用Matlab软件写出矩阵A，B，分别为：A = 1.1111 1.1111 1.1111 1.1111 2.0000 1.1111 1.1111 1.1111 1.1111 1.1111 1.1111 1.1111 1.1111 2.0000 2.0000 0.9091 0.9091 0.9091 1.1111 1.1111 2.0000 2.0000 1.1111 1.1111 0.9091 0.9091 0.9091 2.0000 2.0000 1.1111 1.1111 2.0000 2.0000 2.0000 1.1111 2.0000 1.1111 1.1111 0.9091 0.9091 0.9091 0.9091 0.9091 0.9091 1.1111 1.1111 1.1111 1.1111 1.1111 1.1111 1.1111 1.1111 1.1111 2.0000 2.0000 1.1111 0.9091 0.9091 0.9091 1.1111 1.1111 1.1111 1.1111 2.0000 1.1111 1.1111 1.1111 1.1111 1.1111 2.0000 2.0000 2.0000 1.1111 0.9091 0.9091 0.9091 0.9091 1.1111 1.1111 2.0000 2.0000 0.9091 0.7692 0.7692 0.7692 0.7692 0.7692 0.7692 0.7692 0.7692B = 1.1111 1.1111 0.9091 1.1111 1.1111 1.1111 0.9091 1.1111 1.1111 0.9091 1.1111 1.1111 0.9091 2.0000 2.0000 1.1111 1.1111 1.1111 0.9091 1.1111 2.0000 2.0000 0.9091 2.0000 2.0000 2.0000 2.0000 2.0000 0.9091 2.0000 1.1111 2.0000 0.9091 1.1111 2.0000 1.1111 2.0000 2.0000 2.0000 2.0000 1.1111 1.1111 0.9091 1.1111 1.1111 1.1111 1.1111 1.1111 2.0000 2.0000 2.0000 1.1111 0.9091 1.1111 2.0000 1.1111 1.1111 1.1111 2.0000 0.7692 2.0000 1.1111 1.1111 1.1111 1.1111 0.9091 1.1111 2.0000 2.0000 0.7692 2.0000 1.1111 1.1111 1.1111 2.0000 0.9091 1.1111 1.1111 1.1111 0.7692 1.1111 0.9091 1.1111 1.1111 2.0000 2.0000 2.0000 1.1111 1.1111 0.7692再通过Matlab,运用Floyd算法求得结果为：所以时间最短的路线是： 时间为： 小时花费最少路线模型建立与求解：整个旅途上的费用有两类，第一类与花费时间相关，如住店和饮食，关系为： （6）第二类是汽车的油费，每百公里油量(升)为： （7）汽油每升1.3元。又标注为130的路段是高速路段，每段收费3元。每一路段所需时间为： （8）所以每一路段费用为： （9）再利用 （10）得到每一路段费用最少时的速度 由（8）、（9）有：当速度时，费用元，当速度时，费用元，当速度时，元。所以在不同速度下的每一路段费用： （11） 把每一路段费用写成矩阵形式，A表示行费用组成组成的矩阵，B表示列费用组成的矩阵，则有：A = 15.1850 15.1850 15.1850 15.1850 16.5000 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 16.5000 16.5000 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 16.5000 16.5000 15.1850 15.1850 15.1850 15.1850 15.1850 16.5000 16.5000 15.1850 15.1850 16.5000 16.5000 16.5000 15.1850 16.5000 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 16.5000 16.5000 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 16.5000 15.1850 15.1850 15.1850 15.1850 15.1850 16.5000 16.5000 16.5000 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 16.5000 16.5000 15.1850 19.8460 19.8460 19.8460 19.8460 19.8460 19.8460 19.8460 19.8460B = 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 16.5000 16.5000 15.1850 15.1850 15.1850 15.1850 15.1850 16.5000 16.5000 15.1850 16.5000 16.5000 16.5000 16.5000 16.5000 15.1850 16.5000 15.1850 16.5000 15.1850 15.1850 16.5000 15.1850 16.5000 16.5000 16.5000 16.5000 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 16.5000 16.5000 16.5000 15.1850 15.1850 15.1850 16.5000 15.1850 15.1850 15.1850 16.5000 19.8460 16.5000 15.1850 15.1850 15.1850 15.1850 15.1850 15.1850 16.5000 16.5000 19.8460 16.5000 15.1850 15.1850 15.1850 16.5000 15.1850 15.1850 15.1850 15.1850 19.8460 15.1850 15.1850 15.1850 15.1850 16.5000 16.5000 16.5000 15.1850 15.1850 19.8460再通过Matlab,运用Floyd算法求得结果为：所以花费最少的路线是：费用为： 元。问题二：情形一：每段速度均超速且限速。则每一路段所需时间 （12）然后运用问题一的方法，先写出时间的行矩阵和列矩阵，再通过Matlab,运用Floyd算法求得结果为：所以最短时间因此，不符合，不能走该路线。情形二：每段速度均超速且限速。则每一路段所需时间 （13）然后运用问题一的方法，先写出时间的行矩阵和列矩阵，再通过Matlab,运用Floyd算法求得结果为：所以最短时间因此，符合，该路线为：该路线总费用由固定费用和雷达探测到的罚款费用组成，固定费用公式： （14）由路线可以计算出固定费用其次是雷达探测到的罚款费用。为使问题简单化，当每段速度均超速50%且限速时，用数学期望来算罚款费用。由当超速时，有的可能被雷达探测到，届时会被罚款200元，则有雷达检测到的概率雷达未检测到的概率0.90.1罚款金额2000所以数学期望 一个移动雷达落到一路段的概率为，两个雷达以上落到一路段的概率 是小概率事件，故该情况不用考虑。路段总共18段，所以该路线的罚款总费用该路线总费用为 （15）情形三：把每行每段路线的速度超速，每列每段路线的速度超速。运用问题一的方法，写出时间的行矩阵和列矩阵，在通过Matlab软件，运用Floyd算法求得结果为：所以最短时间为 因此，不合题意，不能走该路线。情形四：把每行每段路线的速度超速，每列每段路线的速度超速。运用问题一的方法，写出时间的行矩阵和列矩阵，在通过Matlab软件，运用Floyd算法求得结果为：所以最短时间为因此，符合题意，该路线为：由路线可以计算出固定费用超速时，有的可能被雷达探测到，届时会被罚款100元，则有雷达检测到的概率雷达未检测到的概率0.70.3罚款金额1000所以，数学期望 则罚款总费用为：该路线总费用为： （16）比较情形二和情形四的总费用可知，故应选择情形四，最少费用为515.3110元，路线为5模型评价优点：1、采用定性和定量的方法结合起来，能处理许多用传统的最优化技术无法着手的实际问题，应用广泛，具有实用性。2、充分利用了Floyd算法和Matlab软件，迅速而且准确地找出答案，节约时间与人力。缺点： 太过理想化，没有考虑实际过程中速度不可能会达到限速的情况。6参考文献1席少霖等.最优化计算方法.上海：上海科学技术出版社，20012卢开澄等.图论及其应用.北京：清华大学出版社，19963粟塔山等.最优化计算原理与算法程序设计M.长沙：国防科技大学出版，20024盛骤等.概率论与数理统计（第二版）M.北京：高等教育出版社，19897附录问题一的Matlab程序：M文件：function D,path,min1,path1=floyd(a,start,terminal) D=a;n=size(D,1);path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j;end, end, endfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j) X=zeros(100); %情形一：所有的速度都提高10%for i=1:100 for j=1:100 if i=j X(i,j)=inf; end endendA=100/1.1./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 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/1.1./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:9 X(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,91,10) X=zeros(100); %所有的速度都提高50%for i=1:100 for j=1:100 if i=j X(i,j)=inf; end endendA=100/1.5./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 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/1.5./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:9 X(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,91,10) X=zeros(100); %水平路段的速度提高50%垂直路段的速度提高10%for i=1:100 for j=1:100 if i=j X(i,j)=inf; end endendA=100/1.5./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 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/1.1./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=