超速行车最短路径模型.doc

超速行车最短路径模型 摘要 最短路径问题是网络理论中应用最为广泛的问题之一，也是在进行物流规划和设计路线是遇到的最常见的问题之一。这里是由城赶往城，是求网络中两点间的权数最小的问题。算法是比较好解决此类问题的一种方法。 对于问题，求解时间最短路径和花费最小路径。首先将点到点关于时间的带权邻接矩阵，通过算法求解出最短路径和其权数和，也就是时间最优路径、时间和花费。 对于问题，结合题意提出四种预案，同样通过算法求解最优路径和权数和。经比较方案和方案能够满足条件要求，即除在安装固定雷达路段限速行驶，方案全程提速， ；方案向右提速，向上提速， 。对于花费较小的方案，可进行一定改进，即在向上限速提速的某一路段不进行提速，可计算得 花费更少。 关键词：最短路径 权数 算法 邻接矩阵 1.问题重述 A城和B城间的道路如下图所示，横向纵向各有10条公路，任意两个相邻的十字路口距离为100公里， A城到B城相距1800公里。任意一段公路都有限速，如图所示，单位为公里每小时。标注为130的路段是高速路段，每段收费3元。 费用有如下两类。与花费时间相关，如住店和饮食，由公式给出。是汽车的油费，每百公里油量(升)由公式给出，其中。单位为小时，的单位为公里每小时。汽油每升1.3元。 图上红色的路段放置了一些固定雷达。另外， 20个移动雷达等概率地出现在各个路段。一个路段可能同时发现多个雷达，每个雷达都监控了自身所在的整个路段。超速，有的可能被雷达探测到，会被罚款100元；超速，有的可能被雷达探测到，会被罚款200元。 本文解决的问题是： （1）遵守所有的限速规定，时间最短的路线和花费最少的路线分别是哪一条？ （2）是遵守所有限速规定所花的最少时间，要在时间内赶往B城，那么包括罚款在内最少花费多少？路线又是哪一条？ 2.问题分析 问题1： 求时间最短的路线问题，我们知道有向图可以用来解决人们提出的从出发点到目的地的各种问题。其中对应着站点，被赋予权值（两个站点之间的里程权重），表示站点之间赋予权值的交通联系。根据条件时间最短可以求出各站点的权重，然后运用matlab中的循环语句for求出整个路线图的权值矩阵，再用用Floyd算法可以求出任意两点间的时间最短路径，通过代人、点坐标从而求出的时间最短路径； （2）求花费最少的路线问题，首先根据每百公里花费与速度之间的函数关系，求出各站点的权重，再采用（1）中同样的方法求出其相应的权值矩阵，最后用Floyd算法求出的花费最少路径； 问题2： 由问题知遵守限速规定所花的最少时间为小时，在时间内赶到B城。设为了使所花费用尽可能少，在装有固定雷达的地段限速行驶，为了使时间尽可能少，在其余路段都进行超速。为此我们假设种预案。 、其它路段都超速，同样由算法求解时间最短路径和时间。 、其它路段都超速，同样由算法求解时间最短路径和时间。 、其它路段，横行路段都按超速，竖行路段都按超速，同样由算法求解时间最短路径和时间。 、其它路段，横行路段都按超速，竖行路段都按超速，同样由算法求解时间最短路径和时间。 发现种情况下的时间最短路径相同，但是只有在、两种方案所花费的最短时间小于，在此基础上我们在通过求其花费，得到最优模型。 3.模型假设与符号说明 3.1模型假设 假设1：假设题目中所给的数据都是正确的、合理的。 假设2：假设在每一个十字路口逗留所花费的时间较短，忽略不计。 假设3：为了使花费时间最短，假设在每一段路上都是最高速度行驶的、忽略其他的堵车、超车、让车等因素。 假设4：假设在超速10%或50%的情况下行驶是可行的，忽略外界因素的干扰。 3.2符号说明 符号 符号说明 表示的邻接矩阵 表示权向量（其中） 表示从所花费的最短时间 表示从车的行驶速度 表示从的最优路径 表示从所花费的费用 表示从行驶过程中全程提速10%的时间 表示从行驶过程中全程提速50%的时间 全程中向上行驶时提速，向右行驶时提速的时间 全程中向上行驶时提速，向右行驶时提速的时间 4．模型建立 根据题目中的图中数据，运用Floyd算法的基本原理和实现方法，构造一个邻接矩阵其中表示与间的距离,若与间无路可通,则为无穷大。与间的最短距离存在经过与间的和不经过两种情况,所以可以令,(其中为节点数)。检查与的值,在此,与分别为目前所知的到与到的最短距离,因此,就是到经过的最短距离。所以,若有,就表示从出发经再到的距离要比原来的到距离短,自然把到的重写成。每当一个有哪些信誉好的足球投注网站完,就是目前到的最短距离。重复这一过程,最后当查完所有时,就为到的最短距离。 为了方便计算,先作出该图的邻接矩阵,如下: 5模型求解 问题1：（1）先用附录1.1.1在时间最短条件下求权值矩阵，再用附录1.1Floyd算法