数学建模期末大作业论文题目：A题美好的一天组长：何曦（2014112739）组员：李颖（2014112747）张楚良（2014112740）班级：交通工程三班指导老师：***美好的一天摘要关键字：Dijkstra算法多目标规划有向赋权图 MATLAB SPSS1 问题的重述Hello！大家好，我是没头脑,住在西南宇宙大学巨偏远的新校区（节点22）。

明天我一个外地同学来找我玩，TA叫不高兴，是个镁铝\帅锅，期待ing。

我想陪TA在城里转转，当然是去些不怎么花钱的地方啦~~。

目前想到的有林湾步行街(节点76)、郫郫公园（节点91），大川博物院（节点72）。

交通嘛，只坐公交车好了,反正公交比较发达，你能想出来的路线都有车啊。

另外，进城顺便办两件事，去老校区财务处一趟（节点50），还要去新东方（节点34）找我们宿舍老三，他抽奖中了两张电影票，我要霸占过来明晚吃了饭跟TA一起看。

电影院嘛，TASHIWODE电影院（节点54）不错，比较便宜哈。

我攒了很久的钱，订了明晚开心面馆（节点63）的烛光晚餐，额哈哈，为了TA，破费一下也是可以的哈。

哦，对了，老三说了，他明天一整天都上课，只有中午休息的时候能接见我给我票。

我主要是想请教一下各位大神：1）明天我应该怎么安排路线才能够让花在坐车上的时间最少？2）考虑到可能堵车啊，TA比较没耐心啊，因为TA叫不高兴嘛。

尤其是堵车啊，等车啊，这种事，万一影响了气氛就悲剧了。

我感觉路口越密的地方越容易堵，如果考虑这个，又应该怎么安排路线呢？3）我们城比较挫啊，连地图也没有，Z老师搞地图测绘的，他有地图，跟他要他不给，只给了我一个破表格（见附件，一个文件有两页啊），说“你自己画吧”。

帮我画一张地图吧，最好能标明我们要去的那几个地方和比较省时的路线啊，拜托了~2 问题的分析2.1 对问题一的分析问题一要求安排路线使得坐车花费的时间最少。

对于问题一，假设公交车的速度维持不变，要使花费的时间最少，则将问题转化为对最短路径的求解。

求解最短路径使用Dijkstra算法很容易进行求解，在运用MATLAB编程，得到最优的一条路径，则这条路径所对应的时间即为最少用时。

2.2 对问题二的分析问题二要求在考虑堵车的情况下，路口越密越容易发生拥堵，安排路线是乘车时间最短。

对于问题二，在问题的基础上增加了附加因素，即公交车的速度会因道路的密集程度而发生改变，从而问题一建立的基本Dijkstra算法对于问题二就不再适用了，因此对问题一的基本Dijkstra算法进行改进，并结合蚁群算法的机理与特点，运用MATLAB求解出最短路径，保证了花费时间的最少性。

2.3 对问题三的分析问题三要求根据提供的附件，画出一张地图，标明要去的那几个地方和比较省时的路线。

对于问题三，在问题一和问题二的基础上，根据求解的结果，运用SPSS软件画出地图。

3 模型假设1、问题一开动中的公交车速度为一恒定值2、问题一公交车不会遇到拥堵情况3、不计公交车启动与制动时间4、不计公交车在站台的停留时间5、节点之间均为直线距离4符号说明5模型的建立与求解5.1 问题一模型的建立与求解公交车速度是恒定的，要使坐车时间最短，故使两点之间的路程最短。

根据题目，要去7个地点，且均乘坐公交车。

5.1.1 最短路径基本概念用于计算一个节点到其他所有节点的最短路径。

主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

算法具体的形式包括：确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。

确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。

在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。

全局最短路径问题 - 求图中所有的最短路径5.1.2 Dijkstra算法描述构造赋权图G=(V,E,W)。

其中，定点集V={v1,...,vn}，这里v1，...，vn表示各个地点；E 为边的集合，邻接矩阵 ()ij n n W w ⨯=，这里ij w 表示顶点i v 和j v之间直通的距离，若顶点i v 和j v之间无连接，ij w =∞。

问题就是求赋权图G 中指定的两个顶点0u ，0v 间的具有最小权的路。

这条路叫做0u ，0v 间的最短路，它的权叫做0u ，0v 间的距离，亦记作00(,)d u v 。

迪克斯特拉算法的基本思想是按距0u从近到远为顺序，依次求得0u 到G 的各项点的最短路和距离，直至0v(或直至G 的所有顶点)，算法结束。

为避免重复并保留每一步的计算信息，采用了标号算法。

下面是该算法。

（1）0000()0,(),{},0l u v u l v S u i =≠=∞==对，令。

（2）(\),i i i v S S V S --∈=对每个用min{(),()()}iu S l v l u w uv ∈+代替()l v ，这里()w uv 表示顶点u 和v 之间边的权值。

计算min{()}iu S l v ∈，把达到这个最小值的一个顶点记为1i u +，令11{}i i i S S u ++=⋃。

（3）若||1i V =-，则停止；若||1i V <-，则用i+1代替i ，转（2）。

5.1.3 有向赋权图的定义 （1）邻接矩阵的建立将该道路视为一个有向权图，其领接矩阵可定义为：11121919119229191()A x x x B G x x x ⎛⎫ ⎪= ⎪⎪⎝⎭ 其中，A G表示该有向权图，其领接矩阵元素为0-1决策变量，定义为：1,1,2, (91)0,ij i j x i j i j ⎧==⎨⎩，、节点路口连通（、节点路口连通（2）权值（时间）矩阵的建立同样，根据题目时间最短的要求，本文将时间(,1,2, (91)ij t i j =作为该有向赋权图中第i 各节点和第j 个节点之间弧ij e的权值，即：11121919119229191()A t t t T G t t t ⎛⎫ ⎪= ⎪⎪⎝⎭ 其中，时间矩阵元素ij t是路口i 和j 连接道路长度与公交车行驶速度的比值， 即：,(,1,2, (91)ijij l t i j v ==其中，0v--公交车行驶速度，规定为40km/h ，ij l --i 路口与j 路口间道路长度，通过两个路口坐标(,)i i x y 和(,)j j x y 确定，即：ij l =当i 、j 路口不连通时，规定ij l等于+∞。

5.1.4 基于最短理论的模型建立 1、目标分析根据5.1.3中建立的有向赋权图，其中0-1决策变量ij x表示弧（i,j ）是否在起点与终点的路上，在定义了ij t为边i 到j 的权的有向网络图后，可看出从出发点到终点有多条线路选择，但必有一条为时间最少的，因而可将这条时间最短的路径找出。

因而，根据所建立的网络领接矩阵和时间权值矩阵可以得到到达某一路口的时间的数学模型为：919111ij iji j T x t ===⨯∑∑从时间考虑，既要满足单个路径时间最短，所以目标函数应为：911min (,1,2, (91)ij ij i T x t i j ==⨯=∑2、约束分析（1）最短路起点约束由于G 为有向图，则其中顶点分为“起点”、“中间点”、“终点”三类，对于起点只有出的边而无入的边，对于中间点既有入的边也有出的边，对于中只有入的边而无出的边。

对有向图而言，若求顶点r 1到r 2的最短路径，以 表示进第j 顶点的边，以 表示出第j 顶点的边，则r 1到r 2的三类约束可表示为：19191211121,()1,2,...,91;1,(),1,2,...,7;21,22,...,910,(ij ji i i i r i x x i r r r i ====⎧⎛⎫⎪ ⎪-=-==⎨ ⎪⎪ ⎪==⎝⎭⎩∑∑其它） （2）0-1决策变量约束由于0-1决策变量 为有向道路网路图的领接矩阵元素，即表示i 、j 两路口是否连通，所以对其作下列约束：1,1,2, (91)0,ij i j x i j i j ⎧==⎨⎩，、节点路口连通（、节点路口连通3、模型确定综上目标和约束分析，可得从起始点到目的地的优化模型如下：911min (,1,2, (91)ij ij i T x t i j ==⨯=∑1919121112121,()1,2,...,91;1,(),1,2,...,7;21,22,...,910,(1,1,2,...,91)0,1,2,...,721,22,...,91ij ji i i ij i r i x x i r r r i i j x i j i j r r ==⎧==⎧⎛⎫⎪⎪ ⎪-=-==⎨⎪ ⎪⎪ ⎪⎪==⎝⎭⎩⎪⎪⎧⎨==⎨⎪⎩⎪⎪=⎪=⎪⎩∑∑其它），、节点路口连通（、节点路口连通5.1.5 基于Dijkstra 算法的“搜索算法”求解 该模型求解得到的是从起始点新校区（节点22）到目的地TASHIWODE 电影院（节点54）的乘坐公交车的最短时间。

所以将这7个最短时间相加即得整个过程的最短时间。

对于这个单目标规划模型，由于数据量较大且计算步骤繁琐，利用Lingo 优化软件求解困难，因此本文结合Dijkstra 算法通过Mtalab 编程进行遍历搜索求解。

算大步骤如下：Step1：取一路口节点j ；Step2：利用Dijkstra 算法求解最短时间；Step3：将 Step2中7个最短时间相加，并记录对应的路径和两端点； Step4：若求解未通过，转Step1，否则，转Step5； Step5：输出Step3的记录，根据断点确定最短时间。

根据以上算法，利用Matalb 软件编程（见附录I ）求解得到两个指定顶点间的最短距离，具体的线路安排如下： 22（新校区）、21、14、10、15、16、38、40、43、72（大川博物院）、73、18、91（郫郫公园）、90、83、80、79、78、76（林湾步行街）、62、57、50（老校区财务处）、51、8、34（新东方）、46、55、63（开心面馆）、54（TASHIWODE 电影院）。

5.2 问题二模型的建立与求解路口越密，越容易发生拥堵情况，因而公交车的行驶速度越慢。

因此要建立在不同路段公交车行驶速度与路口密度的模型，从而找出最佳路线使全程乘车时间最短。

5.2.1 蚁群算法（1）蚁群算法的基本原理与其它模拟进化算法一样，蚁群算法通过多个可行解组成的种群不断进化， 并以最大概率逼近甚至达到问题的最优解。