超速行车最短路径模型

1、超速行车最短路径模型摘要最短路径问题是网络理论中应用最为广泛的问题之一，也是在进行物流规划和设计路线是遇到的最常见的问题之一。这里是由城赶往城，是求网络中两点间的权数最小的问题。算法是比较好解决此类问题的一种方法。对于问题，求解时间最短路径和花费最小路径。首先将点到点关于时间的带权邻接矩阵，通过算法求解出最短路径和其权数和，也就是时间最优路径、时间和花费。对于问题，结合题意提出四种预案，同样通过算法求解最优路径和权数和。经比较方案和方案能够满足条件要求，即除在安装固定雷达路段限速行驶，方案全程提速， ；方案向右提速，向上提速， 。对于花费较小的方案，可进行一定改进，即在向上限速提速的某一路段不

2、进行提速，可计算得 花费更少。关键词：最短路径 权数 算法 邻接矩阵1.问题重述A城和B城间的道路如下图所示，横向纵向各有10条公路，任意两个相邻的十字路口距离为100公里， A城到B城相距1800公里。任意一段公路都有限速，如图所示，单位为公里每小时。标注为130的路段是高速路段，每段收费3元。费用有如下两类。与花费时间相关，如住店和饮食，由公式给出。是汽车的油费，每百公里油量(升)由公式给出，其中。单位为小时，的单位为公里每小时。汽油每升1.3元。图上红色的路段放置了一些固定雷达。另外， 20个移动雷达等概率地出现在各个路段。一个路段可能同时发现多个雷达，每个雷达都监控了自身所在的整个路段

3、。超速，有的可能被雷达探测到，会被罚款100元；超速，有的可能被雷达探测到，会被罚款200元。本文解决的问题是：（1）遵守所有的限速规定，时间最短的路线和花费最少的路线分别是哪一条？（2）是遵守所有限速规定所花的最少时间，要在时间内赶往B城，那么包括罚款在内最少花费多少？路线又是哪一条？2.问题分析问题1：求时间最短的路线问题，我们知道有向图可以用来解决人们提出的从出发点到目的地的各种问题。其中对应着站点，被赋予权值（两个站点之间的里程权重），表示站点之间赋予权值的交通联系。根据条件时间最短可以求出各站点的权重，然后运用matlab中的循环语句for求出整个路线图的权值矩阵，再用用Floyd算

4、法可以求出任意两点间的时间最短路径，通过代人、点坐标从而求出的时间最短路径；（2）求花费最少的路线问题，首先根据每百公里花费与速度之间的函数关系，求出各站点的权重，再采用（1）中同样的方法求出其相应的权值矩阵，最后用Floyd算法求出的花费最少路径；问题2：由问题知遵守限速规定所花的最少时间为小时，在时间内赶到B城。设为了使所花费用尽可能少，在装有固定雷达的地段限速行驶，为了使时间尽可能少，在其余路段都进行超速。为此我们假设种预案。、其它路段都超速，同样由算法求解时间最短路径和时间。、其它路段都超速，同样由算法求解时间最短路径和时间。、其它路段，横行路段都按超速，竖行路段都按超速，同样由算法求

5、解时间最短路径和时间。、其它路段，横行路段都按超速，竖行路段都按超速，同样由算法求解时间最短路径和时间。发现种情况下的时间最短路径相同，但是只有在、两种方案所花费的最短时间小于，在此基础上我们在通过求其花费，得到最优模型。3.模型假设与符号说明3.1模型假设假设1：假设题目中所给的数据都是正确的、合理的。假设2：假设在每一个十字路口逗留所花费的时间较短，忽略不计。假设3：为了使花费时间最短，假设在每一段路上都是最高速度行驶的、忽略其他的堵车、超车、让车等因素。假设4：假设在超速10%或50%的情况下行驶是可行的，忽略外界因素的干扰。3.2符号说明符号符号说明表示的邻接矩阵表示权向量（其中）表示

6、从所花费的最短时间表示从车的行驶速度表示从的最优路径表示从所花费的费用表示从行驶过程中全程提速10%的时间表示从行驶过程中全程提速50%的时间全程中向上行驶时提速，向右行驶时提速的时间全程中向上行驶时提速，向右行驶时提速的时间4模型建立根据题目中的图中数据，运用Floyd算法的基本原理和实现方法，构造一个邻接矩阵其中表示与间的距离,若与间无路可通,则为无穷大。与间的最短距离存在经过与间的和不经过两种情况,所以可以令,(其中为节点数)。检查与的值,在此,与分别为目前所知的到与到的最短距离,因此,就是到经过的最短距离。所以,若有,就表示从出发经再到的距离要比原来的到距离短,自然把到的重写成。每当一

7、个搜索完,就是目前到的最短距离。重复这一过程,最后当查完所有时,就为到的最短距离。为了方便计算,先作出该图的邻接矩阵,如下:5模型求解问题1：（1）先用附录1.1.1在时间最短条件下求权值矩阵，再用附录1.1Floyd算法运算出的时间和时间最短路径，通过调用语句D,path,min1,path1=floyd(X,91,10):时间最短：其路径为：path1 = 91 92 93 94 84 85 86 76 66 56 46 47 48 49 39 29 19 20 10（2）先用附录1.1.2在时间最短条件下求权值矩阵，再用附录1.1Floyd算法运算出的时间和时间最短路径，通过调用语句D,

8、path,min1,path1=floyd(X,91,10):花费最小：其路径为：Path1 = 91 81 82 72 62 52 53 54 44 34 35 25 26 16 6 7 8 9 10所以由最短的路径如图1所示，图绿色所标注的路线为时间最短路线，最短时间为小时，紫色所标注的路线为花费最短路线，最小花费为元。问题2：由问题1我们知道，因为有急事想在时间内赶往B城,则。假设1：行驶过程中全程提速先用附录2.1在时间最短条件下求权值矩阵，再用附录1.1Floyd算法运算出的时间和时间最短路径，通过调用语句D,path,min1,path1=floyd(X,91,10):花费的时间为

9、：其路径为：path1 = 91 92 82 83 73 63 53 43 44 45 46 47 48 49 39 29 19 20 10 假设2：行驶过程中全程提速先用附录2.2在时间最短条件下求权值矩阵，再用附录1.1Floyd算法运算出的时间和时间最短路径，通过调用语句D,path,min2,path2=floyd(X,91,10):花费的时间为：其路径为：path2 = 91 92 82 83 73 63 53 43 44 45 46 47 48 49 39 29 19 20 10 假设3：行驶过程中向右行驶时提速，向上行驶时提速先用附录2.3在时间最短条件下求权值矩阵，再用附录1.

10、1Floyd算法运算出的时间和时间最短路径，通过调用语句D,path,min3,path3=floyd(X,91,10):花费的时间为：其路径为：path3 = 91 92 82 83 73 63 53 43 44 45 46 47 48 49 39 29 19 20 10假设4：行驶过程中向右行驶时提速，向上行驶时提速先用附录2.4在时间最短条件下求权值矩阵，再用附录1.1Floyd算法运算出的时间和时间最短路径，通过调用语句D,path,min4,path4=floyd(X,91,10):花费的时间为：其路径为：path4 = 91 92 82 83 73 63 53 43 44 45 4

11、6 47 48 49 39 29 19 20 10我们发现假设1、2、3、4所得到的最短路径是同一条路径，且如下图2所示：图2由，所以成立的假设只有假设2和假设4中所花费的最短时间是符合条件的。再求出两个假设的花费：假设2：行驶过程中全程提速的最小花费：=假设4：行驶过程中向上行驶时提速，向右行驶时提速假设5：由于比大，说明假设比假设更合理，在假设的基础上我们可以发现如果任选向上行驶的限速为的一个路段不超速行驶，那么其所花费的时间；花费的费用元。总结：问题2要我们求解的是在时间内花费最少的费用和路线。由假设1、2、3、4、5方案求解结果可以看出假设5方案既符合条件,同时花费的费用为所有假设方案

12、中的最低，因此假设5是最合理的，花费的费用，其路径如图2所示。6.模型评价、改进和推广6.1模型评价优点：（1）本模型的结论和结果是和实际较吻合的，说明本模型比较合理。（2）利用Floyd算法，大大地减少了计算量，同时提高了计算的准确性。（3）在求最短路径问题，将问题按实际常理出发，将一个有向与无向结合的图，转化为一个单一的有向图，使得问题变得简化易解，该模型有利于解决一些解决常见的最短路问题。缺点：由于模型假设忽略了实际的一些因素，及模型过于简单化和Floyd算法的欠缺，使结果存在一定的偶然误差。6.2模型改进可将超车行驶过程中的超车、堵车和让车所花费的时间及每个十字路口花费的时间考虑进去，

13、使得模型更符合生活实际。6.3模型推广在现实生活中，我们可以选择的交通工具多种多样和交通路线四通八达，本模型也推广与解决出行时的遇到如何选择最经济实惠又方便快捷的路线问题。7.参考文献1 耿素云，屈婉玲，离散数学。北京：高等教育出版社，2001.2 耿素云，离散数学图论分册。北京：北京大学出版社，1990.3 数学软件与数学实验（第二版）汪晓银 周保平 科学出版社20014 数学建模及其基础知识详解 费普生 武汉大学出版社 2006.5 韩中庚 宋明武 邵广纪，数学建模竞赛获奖论文精选与点评，北京：科学出版社，2007。8.附录%1、在matlab中建立M-fil

14、e如下：%1.1（1）先建立一个floyd.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)<D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k);end, end, end,end if nargin=3 min1=

15、D(start,terminal); m(1)=start; i=1; path1= ; while path(m(i),terminal)=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m;end （2）再建立一个 xout.M的文件%1.1.1、求时间最短的路线X=zeros(100);for i=1:100 for j=1:100 if i=j X(i,j)=inf; end endendA=100./90 90 90 90 50 90 90 90 90;90 90 90 90 50

16、 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./90 90 110 90 90 90 110 90 90 110; 9

17、0 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(

18、a+1,b); X(b-1)*10+a+1+10,(b-1)*10+a+1)=B(b,a+1); endendX%1.1.2、求花费最少的路线X=zeros(100);for i=1:100 for j=1:100 if i=j X(i,j)=inf; end endendA=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

19、 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=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

20、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;c1=500./A+(0.0625*1.3).*A+1.875*1.3;c2=500./B+(0.0625*1.3).*B+1.875*1.3;for a=0:9for b=1:9 X(a*10+b,a*10+b+1)=c1(a+1,b); X(b-1)*10+a+1+10,(b-1)*10+a+1)=c2(b,a+1); en

21、dendX问题2%2.1、求提速时间最短的路线的时间X=zeros(100);for i=1:100 for j=1:100 if i=j X(i,j)=inf; end endendA= A=(1000/11)./90 90 90 90 50 90 90 900/11 90;900/11 90 90 90 50 50 110 110 110;90 90 50 50 900/11 90 110 110 110;50 50 90 90 500/11 50 50 90 50;900/11 90 110 110 110 110 110 110 90;90 90 90 900/11 90 90 90

22、90 50;50 90 110 110 110 900/11 90 90 90;50 90 900/11 90 90 90 50 50 50 ;90 110 110 110 110 90 90 50 500/11;110 130 130 1300/11 130 130 130 130 130;B=(1000/11)./900/11 90 110 90 90 900/11 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 900/11 50 90 50 50 50

23、500/11; 90 900/11 110 90 90 90 90 90 50 50; 50 90 110 90 50 900/11 90 90 50 130; 50 900/15 90 90 90 110 90 500/11 50 1300/11; 50 90 90 90 50 110 90 90 90 130; 90 110 900/11 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%2.2、求提速时

24、间最短的路线的时间X=zeros(100);for i=1:100 for j=1:100 if i=j X(i,j)=inf; end endendA=(1000/15)./90 90 90 90 50 90 90 900/15 90;900/15 90 90 90 50 50 110 110 110;90 90 50 50 900/15 90 110 110 110;50 50 90 90 500/15 50 50 90 50;900/15 90 110 110 110 110 110 110 90;90 90 90 900/15 90 90 90 90 50;50 90 110 110

25、110 900/15 90 90 90;50 90 900/15 90 90 90 50 50 50 ;90 110 110 110 110 90 90 50 500/15;110 130 130 1300/15 130 130 130 130 130;B=(1000/15)./900/15 90 110 90 90 900/15 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 900/15 50 90 50 50 50 500/15; 90 900/15 11

26、0 90 90 90 90 90 50 50; 50 90 110 90 50 900/15 90 90 50 130; 50 900/15 90 90 90 110 90 500/15 50 1300/15; 50 90 90 90 50 110 90 90 90 130; 90 110 900/15 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%2.3、行驶过程中向上行驶时提速10%，向右行驶时提速5

27、0%X=zeros(100);for i=1:100 for j=1:100 if i=j X(i,j)=inf; end endendA=(1000/11)./90 90 90 90 50 90 90 900/11 90;900/11 90 90 90 50 50 110 110 110;90 90 50 50 900/11 90 110 110 110;50 50 90 90 500/11 50 50 90 50;900/11 90 110 110 110 110 110 110 90;90 90 90 900/11 90 90 90 90 50;50 90 110 110 110 900

28、/11 90 90 90;50 90 900/11 90 90 90 50 50 50 ;90 110 110 110 110 90 90 50 500/11;110 130 130 1300/11 130 130 130 130 130;B=(1000/15)./900/15 90 110 90 90 900/15 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 900/15 50 90 50 50 50 500/15; 90 900/15 110 90 90 90 90 90 50 50; 50 90 110 90 50 900/15 90 90 50 130; 50 900/15 90 90 90 110 90 500/15 50 1300/15; 50 90 90 90 50 110 90 90 90 130; 90 110 900/15 90 50 50 50 90 90 130;for a=0:9for b=1:9 X(a*10+b,a*10+b