新建道路最优化选择方案.docx

分类号： 密 级： 毕业论文（设计） 题 目: 新建道路最优化选择方案 系 别: 数学系 专业年级: 数学与应用数学2009级 姓 名: 学 号: 指导教师: 2013年05月27日原 创 性 声 明本人郑重声明：本人所呈交的毕业论文,是在指导老师的指导下独立进行研究所取得的成果.毕业论文中凡引用他人已经发表或未发表的成果、数据、观点等,均已明确注明出处.除文中已经注明引用的内容外,不包含任何其他个人或集体已经发表或撰写过的科研成果.对本文的研究成果做出重要贡献的个人和集体,均已在文中以明确方式标明.本声明的法律责任由本人承担.论文作者签名： 日 期： 关于毕业论文使用授权的声明资料（包括图纸、试验记录、原始数据、实物照片、图片、录音带、设计手稿等）本人完全了解有关保存、使用毕业论文的规定,同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版,允许论文被查阅和借阅；本人授权可以将本毕业论文的全部或部分内容编入有关数据库进行检索,可以采用任何复制手段保存和汇编本毕业论文.如果发表相关成果,一定征得指导教师同意,且论文作者签名： 日 期： 指导老师签名： 日 期： 新建道路最优化选择的一个方案摘 要从整体上来研究城市道路网络的结构,从道路网络结构来分析城市道路的交通功能,是对城市路网进行评价和改善行之有效的一种方法.通过改善路网的内在结构来提高道路网的外延功能可以从根本上来缓解城市交通供需矛盾.本文在分析城市道路网结构与功能的基础上,将路网的整体结构的优化作为确定新建道路方案的一个标准.给出了确定新建道路被选的一个方法.写出了具体的选取算法及相应的C程序.同事通过对吕梁市道路网络的实际问题研究,应用提出的最优化选取方案选出了两种新建道路中较为合理的一个方案.关键字： 道路网络；Dijkstra算法；最短路径；wiener指数New roads selected a program optimizationAbstractCome from the overall structure of urban road network,road network structure from the analysis of urban road traffic function is to evaluate the urban road network and improving effective method by improving the internal structure of the road network to improve the road network extension function can fundamentally come ease urban traffic supply and demand.This paper analyzes the structure and function of the urban road network on the basis that the road network based on the overall structure in order to improve the road network functions.Taking into account previous studies on the road network and based on the dynamic,static,and comprehensive evaluation of the road network in combination with graph theory,reliability theory and road network expansion constrains,proposed road network optimization model in order to validate the model and applies or not correct,select the Lvliang City simplifying the route network as object of study papers in the model validation process.In the model validation process ,taking into account the characteristics of the optimization,select the Dijkstra algorithm to compute this model satisfactory solution,from which select most appropriate way to plan a city.Keywords : road networks; Dijkstras labeled algorithm; Shortest path; wiener index目 录第一章 绪 论- 1 -1.1 道路建设背景- 1 -1.2 图的基本概念- 1 -1.3 图的矩阵表示- 2 -第二章 新建道路网络的优化选取- 3 -2.1系统模型- 3 -2.2Dijkstra算法分析- 3 -2.2.1 Dijkstra算法的描述- 3 -2.2.3 Dijkstra算法的流程图- 4 -第三章 新建道路的优化选取- 5 -3.1离市区的道路网络模型- 5 -3.2 离石区现有交通网络- 5 -3.3 离石区新建道路选取方案- 6 -谢 辞- 20 -第一章 绪 论1.1 道路建设背景随着社会经济发展不断扩张、城市化进程的不断加速使得许多老旧城市的道路系统严重的超荷,道路拥堵现象越来越严重,直接影响到地方经济和环境的状况.同时,“十二五”期间低碳、环保的观念逐步深入人心,使得人们对城市生活质量的要求也越来越高.所以,很多城市在不断地进行道路的改建或新建以减少汽车尾气排放和增加绿化.广义的道路指公路、城市道路以及广场、公共停车场等设施,本文中的道路主要指连接城市或城乡作用的公路和主要城市道路.在所有的运输方式中,道路运输以其机动、灵活、快速、便捷、门到门服务的特点,成为交通运输体系中的重要组成部分.随着近年来国民经济结构的调整,我国进入全面建设道路网络的新时期,大规模的道路(尤其是公路)建设使得道路运输优势作用日益发挥且逐步占据了市场的主导地位.当前我国正处于大力发展道路基础设施建设的大背景之下,由于道路建设项目规模大.投资多,同时牵涉到社会经济的各个方面,因此如何科学合理地建设道路,如何以最小的代价来缓解道路运输的供需矛盾,使资金得到合理使用,并发挥最大的经济社会效益一直是人们致力研究的热点,也是我国今后道路建设的关键之一.道路的合理建设始于规划,做好道路网络规划的理论研究工作进而指导建设实践,是发展我国道路交通的前提和基础.在我国特定的国情下,如何合理利用建设资源和资金,使道路网络的布局结构达到最优,使得最少的投入能够获得最大的效益,是道路网络优化理论面临的一个挑战和急需解决的关键课题.本论文选择以道路网络优化为切入点,充分把握在新建的几种道路方案基础上,研究并运用Dijkstra 标记算法,选择出其中的一条道路,使得整体的道路网路更为紧凑合理.同时,利用吕梁市区道路网络规划的实例研究,在空间结构发展以及产业布局合理的情况下,开辟一条新的道路以解决我市出现的拥堵状况.因此,论文选题具有较重大的理论和实践意义.1.2 图的基本概念无向网络图的基本图之一,广泛用于描述最短路问题,使该问题直观化,便于理解.最短路问题是运筹学的经典问题,也是促使图论成为一门学科的奠基问题之一,特别是无向网络中的最短路问题1.定义131 一个图定义为一个三元组,记作.其中是个非空有限集合,它的元素成为结点；也是个有限集合,其元素称为边,而是：或定义的.由定义可知,图中的每条边都与图中的无序结点对相联系的.若边与无序结点对相联系,则,这时边称为无向边,有时简称为边.若结点与由一条边（或弧）所联结,则称结点和是边（或弧）的端点；同时也称结点和是邻接结点,记作 ；否则为非邻接结点,记作 ；也说边（或弧）关联与或说结点和关联边（或弧）.如果把图中的弧或边总是看做联结两个节点,则图可简记为,其中是非空结点集,是联结结点的边集或弧集.若,则称为阶图.定义2 在图中,如果每条边都是弧,该图称为有向图；若每条边都是无向边,该图称为无向图.定义3 给每条边或弧都赋予权的图,称为加权图,记为,其中表示各边之权的集合.加权图在实际中有许多应用,如在输油管系统图中,权表示单位时间流经管中的石油数量；在城市街道中,权表示通行车辆密度；在航空交通图中,权表示两城市的距离等等.本论文用权来表示道路的长度.1.3 图的矩阵表示定义131 给定简单图,中的结点按下标由小到大编序,则阶方阵称为图的邻接矩阵.其中定义2 已知加权简单图,定义一个矩阵,其中第二章 新建道路网络的优化选取2.1系统模型城市交通系统主要由众多的道路相交、相连而成,并组成纵横交错、错综复杂的城市交通网络.系统模型以交叉路口为分割点,对道路进行分割,把整个交通网络看作由交叉路口和路段组成,进而定义交叉路口为交通网络的顶点,路段为交通网络的边.建立模型的过程就是把现实中的城市交通网络抽象为一个图.每条边上定义不同的权值,权值表示路径长度,即：定义个交叉口和交叉口间的路段组成交通网络.表示路口到路口的实距离.其中表示路口集；表示与路口相关的路段集,表示存在一条从路口到路口的路段.2.2Dijkstra算法分析在实际问题中为了解决距离问题,我们往往会新建一些道路.并且会提出几个方案.那么哪个方案比较好呢？我们将从新建的这些道路后,对整体道路网的影响方面出发来考虑,即新建道路后,整体道路上的任意两个道路路口的距离之和能够比较小,较小说明新增道路使整个道路网比较紧凑.自然比较优,也就是使得图中的最小.而这一问题的关键是要求出图中两个结点之间的距离.我们可以改进Dijkstra算法来实现这一结果,具体算法如下：2.2.1 Dijkstra算法的描述 步骤1 用带权的邻接矩阵来表示带权无向图,表示边上的权值.若不存在,则置为0,表示当前所找到的从始点到每个终点的最短路径的长度.为所有顶点的集合,为已找到从出发的最短路径的终点的集合,它的初始状态为空集.那么,从出发到图上其余顶点（终点）可能达到的最短路径长度的初值为 步骤2 选择使得 就是当前求得的一条从出发的最短路径的终点.令 步骤3 修改从出发到集合上任一顶点可达的最短路径长度.如果 则修改为为 步骤4 重复操作步骤2、步骤3共次.由此求得从到图上其余各顶点的最短路径是以路径长度递增的序列.步骤5 每次以一个顶点为源点,重复执行Dijkstra算法次,这样,便可求得每一对顶点之间的最短路径.2.2.3 Dijkstra算法的流程图程序的算法详见附录2第三章 新建道路的优化选取3.1离市区的道路网络模型离石区目前多中心的空间结构还没有形成,城市的发展主要依托老城区,单中心的空间结构使得人口密度大,现状用地混杂,分区不明确,城市外围建设了大量的新开发的住宅区,而就业还集中在市区,不可避免的出现了大量长途单向通勤人员.从家里到上班距离越拉越长,靠步行或骑车上班不现实了,所以对机动交通就会更加依赖,这在一定程度上鼓励了私家车的购买,导致城市道路愈发拥挤.某些中心区超强度开发,超过了区级道路承载能力,人流车流不能得到有效疏散,这也是城市道路拥堵的原因之一9.3.2 离石区现有交通网络下面是离石区城市的卫星云图. 根据上图以黄色道路为主,删去其中的一些不必要的小路,并结合人口聚集的密集程度以及道路每天的承载能力,将它简化为简单的无向连通图,以每个路口为结点,每条路为边,每条边上有固定的权值.如图4所示 ：3.3 离石区新建道路选取方案针对吕梁市区的道路拥堵问题,根据自己亲自调查发现在上下班高峰期,吕梁市人民医院的路和龙凤大街最为拥堵.在考虑到车流量和道路承载能力的基础上从新铺设两条道路,从整个道路网络出发以缓解道路网的整体压力.本论文在进行其他条件（如车流量、人口密度,环境卫生等）最有合理化的情况下,根据Dijkstra算法计算出每一个路口到其他路口的最短路并计算出所有最短路之和,根据下面给出的两种方案并且与现有道路作比较,选择出其中和数最小,最为紧凑,合理的一种方案.方案一：在石州桥（桥三）与永宁桥（桥五）之间在架设一条道路（即连接与）,根据仪器测量这两点之间的道路预计长为90米；从龙凤大桥到龙山路与建设路的交叉路口铺设一条道路（即连接与）预设出这两点间的长度为170米.表中黑色加粗的字体表示为两条新建的道路,其他的道路没有发生任何的改动,距离不变（见表4）：表4在C语言程序中其他语言不变的情况,根据上表新的数据写出程序中所需要的权矩阵,运行新的程序把得到的各个顶点到其他顶点的最短路距离之和填写在下表中.到各顶点的距离之和83608075624089156100482051205980到各顶点的距离之和59204705460059305660572043754935到各顶点的距离之和63155850543057304685510053955775到各顶点的距离之和558066556215616061705615表5编写的c程序见附录3. 最短路之和为方案二：在滨河南路与建设路的交叉路口（）铺设一条路到达滨河北路与长治路的交叉路口（）,通过测量这两路口的长度约为190米；从龙凤大桥（）到晋绥路与209国道的交叉路口（）,估计这两点间的距离为95米. 表中黑色加粗字体表示为原有道路不变的情况下,预计新规划的两条新建的道路（见表6）：表6在其他条件不变的情况下,改变权矩阵再次运用C语言程序,从新统计的各个顶点到其他顶点的最短路距离之和(见下表).到各顶点的距离之和84558100633589356125492051856000到各顶点的距离之和59504805470059655695576044654975到各顶点的距离之和59405735589557054675509053855640到各顶点的距离之和550066456195543552155490表7编写的c程序见附录4. 第三次将所得到的数据,应用Wiener指数求出方案二的最短路.最短路之和为 综合上述两种方案,并与现有道路进行比较.发现在其他条件最优化的基础上,两种方案在道路路段距离设计上都比现有的道路的最短路之和小,但是我们发现在这两种方案中,方案一是我们最为可选的一种方案.附 录附录1Dijkstra算法的C语言程序/* Note:Your choice is C IDE */#include #define INFINITE 1000 /定义无穷大数#define N 7 /定义图的阶 main()int weightNN; /权矩阵 int i,j,k,sum=0; /变量 int distanceN; /各顶点到出发点的距离 int predecessorN; /先驱结点 int start; /每一步搜索出发点 int min; int lableN=0; int vertexN;printf(请输入搜索点);scanf(%d,&start);distancestart-1=0;predecessor0=start;lablestart-1=1;for(i=0;iN;i+) if(i!=(start-1) distancei=INFINITE; for(i=0;iN;i+)for(j=0;jN;j+)printf(%d ,weightij);printf(n); /权矩阵printf(n); for(i=1;iN;i+) for(j=0;jN;j+) if(lablej=0 & weightstart-1j!=0 & distancestart-1+weightstart-1jdistancej) distancej=distancestart-1+weightstart-1j; min=INFINITE; for(j=0;jN;j+) if(lablej=0&distancejmin) min=distancej; start=vertexj; k=j; distancek=min; predecessori=start; lablestart-1=1; printf(n);for(i=0;iN;i+) printf(%d ,distancei); printf(n); for(i=0;iN;i+) printf(%d ,predecessori); for(i=0;iN;i+) sum=sum+distancei; printf(出发点到其它所有顶点的距离和为 %d,sum);/* Note:Your choice is C IDE */#include #define INFINITE 1000#define N 30 main()int weightNN=0,105,80,0,0,0,0,0,0,0,0,0,105,0,0,200,75,0,0,80,0,0,0,70,75,0,0,200,0,0,0,0,0,105,0,75,70,0,0,0,70,25,0,0,75,0,0,0,30,0,0,0,40,0,0,0,0,70,30,0,75,55,0,0,0,105,25,0,75,0,35,0,0,0,0,0,0,0,35,0,140,0,30,0,0,0,0,0,0,55,0,140,0,20,0,0,70,0,0,0,0,0,40,0,0,0,20,0,0,0,0,65,0,0,0,0,0,0,0,0,30,0,0,0,45,0,0,0,0,0,0,0,0,0,0,0,45,0,105,0,0,0,0,0,0,0,0,0,80,0,0,0,0,0,0,0,0,0,0,0,0,105,0,100,0,0,0,0,0,0,0,80,0,0,0,0,0,0,0,0,0,0,65,0,0,100,0,30,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,110,0,80,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,110,0,30,0,0,0,0,0,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,30,0,0,0,0,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,80,0,30,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,80,0,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,0,0,0,80,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,30,0,0,80,0,0,0,0,0,0,0,0,0,0,0,0,0,80,0,0,0,0,0,0,0,30,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,80,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,0,30,0,0,0,75,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,80,0,0,0,0,80,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,0,0,0,0,80,0,0,80,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,30,0,0,0,0,0,0,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,80,30,0,80,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,75,0,0,0,80,0; int i,j,k,sum=0; int distanceN; int predecessorN; int start; int min; int lableN=0; int vertexN=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30;printf(请输入搜索点);scanf(%d,&start);distancestart-1=0;predecessor0=start;lablestart-1=1;for(i=0;iN;i+) if(i!=(start-1) distancei=INFINITE; for(i=0;iN;i+)for(j=0;jN;j+)printf(%d ,weightij);printf(n); /权矩阵printf(n); for(i=1;iN;i+) for(j=0;jN;j+) if(lablej=0 & weightstart-1j!=0 & min=distancej; start=vertexj; k=j; distancek=min; predecessori=start; lablestart-1=1; printf(n);for(i=0;iN;i+) printf(%d ,distancei); printf(n); for(i=0;iN;i+) printf(%d ,predecessori); for(i=0;iN;i+) sum=sum+distancei; printf(出发点到其它所有顶点的距离和为 %d,sum);/* Note:Your choice is C IDE */#include #define INFINITE 1000#define N 30 main()int weightNN=0,105,80,0,0,0,0,0,0,0,0,0,105,0,0,200,75,0,0,80,0,0,0,70,75,0,0,200,0,0,0,0,0,105,0,75,70,0,0,0,70,25,0,0,75,0,0,0,30,0,0,0,40,0,0,0,0,70,30,0,75,55,0,0,0,105,25,0,75,0,35,0,0,0,0,0,0,0,35,0,140,0,30,0,0,0,0,0,0,55,0,140,0,20,0,0,70,0,0,0,0,0,40,0,0,0,20,0,0,0,0,65,0,0,0,0,0,0,0,0,30,0,0,0,45,0,0,0,0,0,0,0,0,0,0,0,45,0,105,0,0,0,0,0,0,0,0,0,80,0,0,0,0,0,0,0,0,0,0,0,0,105,0,100,0,0,0,0,0,0,0,80,0,0,0,0,0,0,0,0,0,0,65,0,0,100,0,30,0,0,90,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,110,0,80,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,110,0,30,0,0,0,0,0,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,30,0,0,0,0,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,90,80,0,30,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,80,0,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,0,0,0,80,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,30,0,0,80,0,0,0,0,0,0,0,0,0,0,0,0,0,80,0,0,0,0,0,0,0,30,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,80,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,0,30,0,0,170,75,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,80,0,0,0,0,80,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,0,0,0,0,80,0,0,80,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,30,0,0,0,0,0,0,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,170,0,80,30,0,80,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,75,0,0,0,80,0; int i,j,k,sum=0; int distanceN; int predecessorN; int start; int min; int lableN=0; int vertexN=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30;printf(请输入搜索点);scanf(%d,&start);distancestart-1=0;predecessor0=start;lablestart-1=1;for(i=0;iN;i+) if(i!=(start-1) distancei=INFINITE; for(i=0;iN;i+)for(j=0;jN;j+)printf(%d ,weightij);printf(n); /权矩阵printf(n); for(i=1;iN;i+) for(j=0;jN;j+) if(lablej=0 & weightstart-1j!=0 & min=INFINITE; for(j=0;jN;j+) if(lablej=0&distancejmin) min=distancej; start=vertexj; k=j; distancek=min; predecessori=start; lablestart-1=1; printf(n);for(i=0;iN;i+) printf(%d ,distancei); printf(n); for(i=0;iN;i+) printf(%d ,predecessori); for(i=0;iN;i+) sum=sum+distancei; printf(出发点到其它所有顶点的距离和为 %d,sum);/* Note:Your choice is C IDE */#include #define INFINITE 1000#define N 30 main()int weightNN=0,105,80,0,0,0,0,0,0,0,0,0,105,0,0,200,75,0,0,80,0,0,0,70,75,0,0,200,0,0,0,0,0,105,0,75,70,0,0,0,70,25,0,0,75,0,0,0,30,0,0,0,40,0,0,0,0,70,30,0,75,55,0,0,0,105,25,0,75,0,35,0,0,0,0,0,0,0,35,0,140,0,30,0,0,0,0,0,0,55,0,140,0,20,0,0,70,0,0,0,0,0,40,0,0,0,20,0,0,0,0,65,0,0,0,0,0,0,0,0,30,0,0,0,45,0,0,0,0,0,0,0,0,0,0,0,45,0,105,0,0,0,0,0,0,0,0,0,80,0,0,0,0,0,0,0,0,0,0,0,0,105,0,100,0,0,0,0,190,0,0,80,0,0,0,0,0,0,0,0,0,0,65,0,0,100,0,30,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,110,0,80,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,110,0,30,0,0,0,0,0,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,30,0,0,0,0,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,80,0,30,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,190,0,0,0,0,30,0,80,0,0,0,0,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,0,0,0,80,0,30,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30,0,30,0,0,80,0