交通中最优线路问题的数学模型

《交通中最优线路问题的数学模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.武汉工业学院毕业论文论文题目：交通中最优线路问题的数学模型姓名吴惠平学号061201222院（系）数理科学系专业信息与计算科学指导教师同小军2010年6月15日-..目录摘要IAbstractII1.引言11.1课题来源11.2课题简介11.3交通中最优线路问题的研究现状11.4论文章节安排2本章小结22.最优线路及最优线路的评价标准22.1最优线路的定义及评价指标22.2最优线路评价指标的量化32.2.1最短出行线路的量化32.2.2最少换乘次数的量化32.2.3最低票价的量化4本章小结43.Floyd

2、算法43.1Floyd算法的基本原理43.2Floyd算法构造距离矩阵的原理53.2.1Floyd算法步骤53.2.2回溯法求最短路径53.3Floyd算法改进63.3.1改进Floyd算法原理63.3.2改进Floyd算法的计算步骤6本章小结64.多维Floyd算法74.1算法的基本思想74.1.1建立赋权有向图D74.1.2构造路由矩阵T74.1.3构造统计矩阵S84.1.4迭代过程9-..4.2算法的基本步骤10本章小结115.Dijkstra算法介绍115．1Dijkstra算法原理115.2Dij

3、kstra算法的基本步骤125.3Dijkstra算法与基本Floyd算法时间复杂度的比较12本章小结136.Floyd算法实例应用136.1问题的提出136.2问题分析146．2.1问题一的分析146．2.2问题二的分析156．2.3问题三的分析166.3问题求解166.3.1问题一的求解166.3.2问题二的求解176.3.3问题三的求解186.4问题的结果196.4.1问题一的汽车最优路线196.4.2问题二的汽车和地铁最优路线226.4.3问题三的最优线路22本章小结22谢辞23参考文献24附录26

4、-..摘要交通问题与城市经济和居民生活息息相关，建立以交通网络为基础的交通优化模型就显得尤为重要。本文以城市交通优化问题为例，研究了网络交通优化问题的数学模型。在已有Floyd算法的基础上提出了多维Floyd算法。目前关于最佳出行线路的算法有很多，具有代表性的有Dijkstra算法、Floyd算法、Bellman算法等。但是现有的这些算法都只能解决单权最短路问题，对于多权最短路问题则无法解决，而实际交通优化问题均是多权网络交通优化问题。本文首先构造了向量矩阵，并定义了向量矩阵的运算方法，由此得到多维Floy

5、d算法，该算法能够有效得解决多权网络交通优化问题。本文最后以北京市公交为例，建立了多权交通网，根据所采用的不同交通工具，分别讨论了从出发点A站到目的地B站的最优路线查询问题。运用向量Floyd算法建立该问题的数学模型，最后用C语言实现对该算法的求解。通过实例应用，进一步证明了该算法和模型的可行性和合理性。关键词：最优线路赋权有向图Floyd算法多维Floyd算法-..AbstractTransportionproblemisrelevanttourbaneconomyandresidents’life.So

6、itisveryimportanttoestablishthemathematicalmodelofoptimizationoftrafficbasedontranspatationnetwork.Inthispaper,wetaketheurbantransportationforanexample,makearesearchabouttheoptimizationoftrafficnetworkproblemsofmathematicalmodel.Weproposedthemultidimension

7、alFloydalgorithmbasedontheexistingFloydalgorithm.Atpresenttherearemanyalgorithmsonthebesttravelroute，therepresentativealgorithmistheDijkstraalgorithm,Floydalgorithm,Bellmanalgorithmandsoon.However,theseexistingalgorithmscanonlysolveasingleweightofshortestp

8、athproblem,forthemoreweighttheshortestpathproblemitcannotsolve.Buttheactualtrafficoptimizationproblemsaremulti-weightnetworktrafficoptimization.Inthispaper,westructuredamulti-dimensionalmatrixfirst,thendefine