图论在城市规划和交通运输中的数学模型

《图论在城市规划和交通运输中的数学模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、湖北大学硕士学位论文图论在城市规划和交通运输中的数学模型姓名：黄健申请学位级别：硕士专业：基础数学指导教师：刘慧清20100501摘要二十世纪中后期，随着计算机的出现和发展，图论的研究得到广泛重视，最短路径问题和旅行售货员问题已经是图论中的典型问题，本文通过两个实际例子说明最短路问题在山区修建公路和旅行售货员问题灾区巡视路线中的应用。在山区修路中采用将地形图转化为网络图的方法对网络的边的公路、隧道、桥梁分别赋予不同的值，最后求最小成本路线问题就转化为求网络中最短路径的问题。在灾区巡视路线的数璺模型属

2、于旅行售货员问题，应用多推销员回路等近似解法制订了三种行驶路线。在本文中根据实际问题的需要选择恰当的算法合理的解决实际需要。关键词：最短路问题；旅行售货员问题；数学模型AbstractThelatetwentiethcent,、析tIltheemergenceanddevelopmentofcomputers．graphtheoryresearchiswidelyrecognized，theshortestpathproblemandthetravelingsalesmanproblemisatyp

3、icalproblemingraphtheory,thispapertwopracticalexamplesoftheshortestpathprobleminthemountainsbuildingroadsandtravelingsalesmanproblemisofcoursevisitedthestrickenarea．Theuseofroadsinmountainousterrainmapintoar’etworkdiagramapproachonthenetworksideofthehi

4、ghway,tunnel，bridgeandgivendifferentvalues，。thefinalrouteofseekingtheminimumcostoftransformationforthesakeofthenetworkonthe，shortestpathproblem．Inspectionroutesintheaffectedareasaretravelingsalesmanproblemmodel，applicationssuchasmulti-loopapproximateso

5、lutionsalesmanhasdevelopedthreetypesoftravelroutes．Inthispaper,basedontheactualissuesneedtoselecttheappropriatealgorithmforareasonablesolutiontotheactualneeds．Keywords：Theshortestpathproblem，travelingsalesmanproblem，mathematicalmodelII第一章绪论1．1概述弟一早三百T匕

6、二十世纪中后期，随着计算机的出现和发展，图论的研究得到广泛重视，最短路径问题和旅行售货员问题已经是图论中的经典问题，它已经被应用于众多领域．最短路径问题最直接的应用在地理信息领域，如：GIS网络分析、城市规划、电子导航等．特别是改革开放带来了中国经济的腾飞，社会财富的积累，综合国力的提升，使中国的城市化进程加快，不论从速度还是规模上，都是人类历史上前所未有的，而城市的建设往往大都具有盲目性，大规模城市都不能合理妥善的建设，甚至出现资源的浪费，所以合理的利用有限的资源，达到最佳的预期效果就成为城市建设

7、和交通运输中的首要问题。本文通过两个实际例子说明最短路问题和旅行售货员问题在地理科学中(城市规划)的应用。首先以模拟山区修建公路为载体，根据山区山脉的高低起伏，河流的宽度和走向为前提，以图论中最短路思想为依据，通过建立数学模型的方式建造一条两点问的公路，从而解决网络中最短路问题。其次在另一个实际应用例子中以模拟灾区巡视路线为载体，根据路线的实际情况，运用最短路和旅行售货员问题的思想制定确实可行的路线，因此两个例子在日常生活中具有较为实际的作用。1．2相关的研究综述最短路算法本质上是应用动态规划的理论

8、，通过递归的方法在图上进行搜索从起点到终点(或从终点到起点)的最短路。其综合起来最短路问题算法的实现技术，可将其分为精确算法和启发式算法两大类。Dijkstra算法、A木算法Bellman—Ford算法、SPFA算法、Floyd—warshall算法、Johnson算法、Bi-OirectionBFS算法、分支定界法、改良圈算法、“便宜”算法、贪心算法、修改最小树生成法等等。本文旨在此基础上比较各种算法以寻找出适合本模型的算法以解决实际问题。在模型的建立过程当中根据实