《毕业论文-交通线路选择软件的设计与实现【最终稿】 .doc》由会员分享，可在线阅读，更多相关《毕业论文-交通线路选择软件的设计与实现【最终稿】 .doc（30页珍藏版）》请在三一文库上搜索。
1、 武汉纺织大学 毕业设计(论文) 交通线路选择软件的设计与实现 姓 名： 学 号： 学 院：电子与电气工程学院 指 导 老 师： 2015年 5 月 30 日摘 要随着社会经济的飞速发展，出行方式的多样选择，设计和研究一套简单交通线路选择软件，成为利民便民和增强市场竞争力的重要举措。这其中设计最主要的核心问题是最优路径选择问题。本文分析了交通道路网络的具体特点，主要包括线性分布特点、网络分布特点、分段分布特点、动态性特点和车辆行驶的自主性特点等。将交通网络抽象成一个由边和节点组成的图，并根据图论的相关理论和知识构建起交通网络模型，包括交通道路节点模型，交叉口和道路模型，并对上述道路模型信息进行
2、存储，以构建好的交通道路模型为基础研究智能交通系统中的最优路径问题。考虑到实际道路中存在一定的交通阻抗，为使算法更具有应用价值，本项目在Dijkstra算法的基础上进行了改进，缩短了道路搜索时间，提高了最优路径选择的效率。数据库的选择与设计是系统实现中不可或缺的重要组成部分，优秀的数据库选择和设计方案能够提高最优路径选择的效率、也提高了整个智能交通系统的工作效率。本文使用了GIS数据模型与数据库的管理设计，主要包括GIS数据的简介、选择Oracle的理由、GIS数据向Oracle中的导入和存储、Oracle中GIS数据的访问和维护。对道路交通系统的建模、最优路径选择算法的研究以及数据库的开发设
3、计目的是建立一套接近实际情况的最优路径选择系统。本文将经典的Dijkstra算法和改进的Dijkstra算法进行编码实现，使之在最优路径选择系统中正确运行。关键词：智能交通线路选择; 最优路径; GIS数据; 系统设计; Dijkstra算法IABSTRACTAlong with the rapid development of social economy, diverse selection of travel mode, research and design a simple traffic routes to choose software become convenience an
4、d to enhance the market competitiveness of the important initiatives. The design of the main core of the problem is the optimal routing problem.This paper analyzes the specific characteristics of the traffic and road network,including linear distribution characteristics of network distribution chara
5、cteristics，segmented distribution characteristics，dynamic characteristics of vehicles autonomous featuresAbstract transportation network as a graph of edges and nodes，and build a transportation network model based on graph theory theory and knowledge，including traffic road node model, intersections
6、and road model,and storage of the road model information to build good traffic road model for basic research in intelligent transportation systems，the optimal path. Considering the actual road traffic impedance，is the algorithm more application improved value on the basis of the Dijkstra algorithm,s
7、hortening the path search time，and to improve the efficiency of the selection of the optimal path The database is an important part of an integral system design and implementation, database selection and design of a direct impact on the efficiency of the path planning systemThis article uses the des
8、ign of a GIS data model and database management，mainly including the introduction of GIS data,select Oracle reason imported and stored in the Oracle，GIS data, the Oracle GIS data access and maintenance. Modeling of road traffic system,the optimal path selection algorithm well as the development of t
9、he database is designed to establish the optimal route selection system set close to the actual situationClassical Dijkstra algorithm and improved Dijkstra algorithm were implementedThe optimal path selection system is proved correctlyKey Words：Intelligent traffic line selection ; Optimal path; GIS
10、data; System design; Dijkstra algorithm II目 录1 绪论12 基础知识321 路径优化算法概述3211 Floyd算法3212 Dijkstra算法4213 GPSR算法422 图论简介52. 2. 1 图的概念6222 图的表示6223 图的存储723 本章小结73 最优路径831 建立城市交通模型8311 道路节点模型9312 交叉口和道路模型932 交通模型数据存储9321 数据预处理9322 交通路径模型建立与数据存储1033 最优路径选择11331 最优路径的求解过程11332 经典Dijkstra算法分析11333 Dijkstra算法改进
11、1233. 4 交通阻抗分析133. 4 本章小结144 GlS数据模型和数据库设计1441 GIS数据模型建立14411 空间数据模型15412 属性数据模型154. 2 GlS数据的管理与组织164. 3 SpatiaI简介1644 空间数据向Oracle中的导入1745 GIS数据在OracIe中的存储1746 Oracle中GIS数据的访问184. 7 Oracle中GlS数据的维护1848 本章小结195 路径优化算法系统实现1951 电子地图制作1952 仿真结果与分析1953 本章小结216 结论21参考文献22致 谢23IV1武汉纺织大学2015届毕业设计论文1 绪论随着改革开
12、放经济的发展，人口数量的不断增多，城市的数量和规模不断增大和增多，城市化程度和趋势十分明显，城市交通问题成为目前影响和制约我国经济发展和社会进步的主要因素。不论是上海北京等特大城市还是其他省会城市或地级市，普遍存在交通问题，城市车辆不断增多，人口越发密集，道路环境不断恶化等原因都是导致城市交通问题的主要方面。这就要求我们拥有的便利交通系统，随着计算机技术和电子技术的不断发展，以及电子地图测绘技术的不断进步，这使得地理信息系统也得到了长足的进步，这些技术的发展都给智能交通系统的发展奠定了良好的基础。通过中西交通道路系统的比较，我国城市交通系统的主要问题包括交通管理技术落后，为从根本上解决问题上述
13、交通拥堵问题，并保持大中城市交通可持续发展带动城市的可持续反战，除了合理地进行交通道路等基础设施建设外，另一个切实可行的办法就是进西方先进的高科技管理技术改进我们的交通系统，并使其符合我国国情，建立高性能高效率的智能城市交通系统(ITS)。智能交通系统(ITS)通过充分发挥现有交通资源潜力和系统内部协同作用产生的效力，能够为城市交通提供更安全、更舒适、更高效率和更高品质的新型城市交通系统嘲。智能交通系统的目标是利用现金的计算机技术和先进的网络管理来减少交通拥堵、交通事故和环境污染，与此同时，交通系统能够有效的正常的运行。在交通、计算机、电子通信、信息技术和系统科学与工程应用领域中，智能交通系统
14、是日前许多国内外学者和研究机构集中、深入的研究领域之一，具有非常好的发展前景。在我国，随着交通运输业的不断发展，交通环境日益恶化的今天，研究出一套能够适应我国国情的现代智能交通系统和车辆导航系统，使之能够为人们出行提供重要的交通信息，避免交通拥堵，减少交通事故，为驾驶者提供最佳的驾驶路径，达到交通的路网畅通已经迫在眉睫。如果能够对车辆导航系统提供行之有效的最佳路径选择算法，就能为人们出行提供有效、合理有效的出行路径，从而提高交通系统运行的效率。最佳路径选择问题是智能交通系统中的重要组成部分，也是交通地理信息系统研究中的一个热点问题之一，是出行路径设计与优化、现有有限资源重新利用和分配等问题的基
15、础。因此最优路径选择与优化问题是实时的动态交通系统中具有具有重要现实意义的研究课题。最佳路劲的算法研究不仅可以应用在交通网络系统中，而且对出行决策、校车路径查询、快递物流、资源分配等方面也有很好的应用价值。道路交通系统中最佳路径选择的研究能够为综合信息管理和只能决策提供先进、科学和行之有效的判决依据；为人们出行提供便利的交通运输条件；为车辆的运行提供安全保障：提高了现代交通道路的利用效率；帮助车辆减少尾气排放和燃油等资源的消耗：对于建设资源节约型社会具有划时代的意义。目前我国对有许多与最优路径求解相关的学科在侧面对这个问题做过研究，如运筹学、计算机科学、图论、数论、交通工程学理论、地理信息科学
16、研究等。日前网络发展十分迅速，而网络的构成类似交通道路系统，可以利用最优路径算法来解决很多网络方面的问题。经典学科中的图论、数论与计算机科学以及数据结构与算法的有效结合使得对最优路径算法的研究有了很大进展。国内外大量研究机构和相关学者对最优路径问题的解决进行过深入研究与探讨。数学家EWDijkstra在1959年就提出了标号设定法用于解决路径问题，形成了目前仍被视为经典的Dijkstra算法。自从Dijkstra算法面世以后，又历经了很多学者对该算法的改进与发展，因此有关最优路径选择问题的研究成果不断涌现，使其求解速度和求解效率不断提高。最优路径选择算法在不同的应用条件下可以按照不同的方法进行
17、分类。如按照时间顺序来分类，分为动态最优路径选择问题和静态最优路径选择问题；如果按照确定性和非确定性来划分，分为确定型和随机型最优路径选择问题；如果按照网络规模大小划分，可分为小规模网络和大规模网络最优路径选择问题：如果按照计算方式来划分，可分为串行和并行最优路径选择算法。各种不同类别的最优路径选择算法相互组合可以成为解决不同问题的各种各样算法。最优路径问题按照是否是单源问题还可以分为单源最优路径选择问题及全源最优路径选择问题。其中单源最优路径选择问题更具有实际应用的意义，而且良好的单源路劲问题的算法可为全源最优路径问题提供良好的研究基础，因此本文在研究最优路径选择问题的过程中只考虑单源最优路
18、径选择问题。2基础知识21 路径优化算法概述国内外的研究机构和学者对不同的路径优化算法进行了研究、分析、比较和论证，比较经典的路径优化算法有Floyd算法、Dijkstra算法、GPSR算法、遗传算法、蚁群算法等。实际的交通网络是一个复杂的动态网络系统结构，它包括各种道路的限制信息以及交通流量的实时信息，然而现有的所有路径优化算法均是对某种抽象的具体网络结构进行优化计算各种，这就需要对实际的交通网络建立模型。路径优化的效率和速度室友所建立模型的准确程度来决定的。目前，国内外学者己经有许多传统的经典算法用来解决路径优化问题，但这些算法具有共同的点就是并没考虑实际出行的具体特点特点，如路况信息、道
19、路质量、道路上的车流量等。最短路径算法求出的仅仅是在空间距离最短的路径，但在实际应用中人们需要的是最优路径，最优路径不一定是距离最短，还要考虑交通阻抗的问题，比如想要求得从A地到B地的最优路径，这个问题是指在所有从A地到B地的所有路线当中选择最优的一条，包括最节省时问，最节省资源，是驾驶者最舒适，对交通工具的各项消耗最小等。最优路径问题并不是普通意义上的距离最短路径选择问题。实际情况下最优路径选择问题包括两层含义：首先最优路径是一条可以从A地到达B地的畅通的路径；其次这条路径在所有路径当中是最佳的。从A地到B地想要找一条最优路径，应是一条的所用时间最短、驾驶者最舒适、道路上的车辆数量较少，或对
20、交通车辆的损耗最少。211 Floyd算法Floyd算法是由Floyd在1962年提出的。将图的节点和边的信息计算利用矩阵计算来完成，通过一个图的权值矩阵中求出交通网络中任意两点之间的最短路径。基本思想：比如求图中两节点Vi到Vj的之问的最短路径问题。Floyd算法是一种动态规划算法，由于是穷举法进行计算，因此对于稠密图效果较好。此算法思路简单，该算法对于稠密图来说，效率要高于经典的Dijkstra算法。但缺点是时间复杂度较高，不适合大规模数据的计算，耗时较长。212 Dijkstra算法Dijkstra算法由荷兰数学家Edsger Wybe Dijkstra在1959年提出来的，是一种单源最
21、短路算法适用于非负权值网络的计算，是目前在求解最短路径问题较为完备且应用广泛的算法之一，可以计算出图中从指定结点到图中其他任意节点之问的最短路径。在一个图G中，Dijkstra算法不但可以给出两指定结点之间的一条具有权值最下送的路径，且还可找出从指定点到图G中所有结点的最短路径。Dijkstra算法的缺点就是当网络中结点数量较大时，就会增加算法的复杂度，降低了效率。该算法通过图中的每个节点v建立额外的信息数组，存储从其他任意节点S到v的最短路径。在初始状态下，原始节点S的路径长度值被赋为0即dis的值为0， 同时假设其他所有节点到该节点的路径长度为无穷大，用无穷大长度的路径表示任何其他节点到该
22、结点的路径是未知的。如果存在从S到v的路径，那么当苏算法结束时储存的信息是S到v的距离最短路径；如果从S到v的路径不存在，则dV中储存信息是无穷大。Dijkstra算法的操作对边进行了拓展：如果从U到v的路径是存在的，将边(u，v)添加到(s，v)尾部，则这条新的路径的长度为dM+w(u，v)。如果这条路径的长度比已知的路径长度dv的值小，我们可以用新的路径来代替原有路径。这种拓展边的迭代运算一直进行，一直运行到所有的dM都代表从S到v最短路径为止。算法需要维护两个结点集Q和P，集合P保留了我们通过迭代运算所得的所有dM的最短路径的值结点，而集合Q则保留其他剩下的所有结点。集合P初始状态为空，
23、而后每一步都有一个结点从集合Q中转移到集合P中，并相应的在Q中删除该节点信息。213 GPSR算法GPSR路由算法的思路是利用地理位置信息进行最优路径选择，该算法需要通过贪婪转发算法来建立与其他信息之间的关联和路由。当节点s向D转发数据分组时，他首先找到与相邻节点中距离最小的那个节点，然后将数据分组转发给那个节点，将距离最小的那个节点称为跳点，然后将S的数据传送给这个跳点，该过程需要一直迭代计算，直到分组数据全部到达节点D。利用欧氏距离计算距离方法计算距离该节点最近的相邻节点，但如果数据传输的某一节点是发现没有找到下一个距离最小的节点使得数据传送的目标节点时，导致了数据传输的失败。在发生生无法
24、传送数据时，节点能够探测到周围的空洞，并利用右手法则沿着空洞周围的节点传输数据来解决这类问题。该方法的优点在于米面了在节点信息中存储建立和维护路由表信息，只需要利用相邻节点进行路径选取即可进行，几乎是不需要任何协议辅助；并且利用欧氏距离最小的方法进行路由，数据传输的延时最小；并能够保证只要网络路径不被破坏，数据一定能到传送到目标节点中去。但该算法存在这一定的缺点，当网络中的某节点与源点集中在两个区域时，由于通信的不平衡能够导致部分节点无效，从而是网络的连通性遭到破坏；另一方面是该方法需要GPS定位系统的辅助来计算几点的位置信息。GPSR中贪婪转发算法能够正常转发数据的前提是：目的结点的位置都包
25、含于每个数据分组中，每个结点都有邻居结点列表信息以及邻居结点和本结点的位置信息。在实际的路线选取过程中，我们将路口与上述的结点对用。在电子地图中，每个路口都有坐标位置和列表信息，那么在算法程序中我们首先要做的是让每个结点都包含一条邻居结点链表，并将结点号与位置信息关联起来。22 图论简介图论(Graph Theory)是组合数学的一个分支，它源于瑞士数学家欧(Euler)1736年对于著名的哥尼斯堡七桥问题的解决，从而使欧拉成为了图论的创始人。图论是数学学科当中比较年轻的一个分支。在图论被提出后的两百年中，图论的发展相对缓慢，但自从图论与大量的实际问题相结合，在物理学、化学、信息论、运筹学、计
26、算机科学、控制论、社会科学，经济管理等各种学科中找到了更广泛的应用，使图论在近几十年来得到了快速的的发展。目前在图论领域中形成了两个不同的方向：抽象图论和最优化图论。前者主要研究图的性质，后者主要讨论与图有关的优化问题。最优化图论既可以算作图论中的一个研究方向，也可以看作运筹学中最优化理论的组成部分。图论中的图是由若干节点以及两节点之间的连线所构成的图形，图论的研究对象是图，这种图形不考虑点的大小、形状和边的形状、长度、大小以及边与边的角度等几何问题，而主要表达的是点点之间通过线的连通关系，通常可以用来描述某些事物之间的相互关系，即用点来代表事件发生，用连接两点的边表示两个事件之间的关系。因此
27、图论中的图能够代表多种含义，因此图论在诸多领域都有着非常广泛的应用。2. 2. 1 图的概念无向图是指有序三元组(V，E,F)中边没有方向，其中集合y被称为结点集，y中的元素称为结点：集合E被称为边集，E中的元素被称为边；而函数是边集E到无序结点对儿所构成的集合的一个映射关系，称之为关联函数。如果P是一条边“，两个结点，且满足F(E)=uv，那么就可称为e连接：并且称，y为E的端点。每条边与边两端的节点是相互关联的因此称为相互关联，与同一条边相关联的节点或者与同一个节点相互关联的边称为相邻的节点或者相邻的边，具有相同两个节点的边称为重合边或者是平行边，两个节点相同的边组成环，简单图就是没有环和
28、重边的图。每个结点度数相同的简单图称为正则图，最大度与最小度恰好相差1的简单图被称为几乎正则图。图的结点的个数称为图的阶。222 图的表示由点集合V和点与点之间的连线的集合E所组成的集合对(V，E)可以构成图，用G(V,E)来表示。图G(V，E)由其结点与边之间的关系确定，且是唯一的。也由它的结点对儿之间的邻接关系唯一确定。V中的元素为结点，E中的元素为边。节点集合V与边集合E均为有限的图称为有限图。 图2-1 图的结构 223 图的存储(1) 邻接表邻接表结构： adfvexnextarc info datafirstarc 图2-2 邻接表结构表节点和头结点邻接表以一种以链式存储结构所构成
29、的图。在邻接表中，图中的每个节点都会有一个单链表与之对应，第i个单链表中的结点数据表示依附于结点v。三个域构成了每个节点，其中结点的邻接点域的数值表示与结点-相邻节点在图中的具体位置，结点的链域将指示下一条边的结点，结点数据域存储的是图中边的信息，如权值、方向等。每个链表都会有一个表头结点与之对应，在表头结点中，设有存储结点q的各个域及与该信息有关的相关数据域。这些表头结点存储数据的形式通常是顺序存储的，这样存储方式便于随即访问任何一个节点的链表信息。(2)十字链表十字链表针对有向图的另一种存储结构。可以看成是一种新的链表，该链表将有向图的邻接表和逆邻接表结合在一起。在十字链表中，每一条边都有
30、一个节点与之对应，每一个节点也有一个节点与之对应。23 本章小结本章对最优路径算法和图论的相关理论知识进行了简单概述。对几个经典的最优路径选择算法进行了介绍，如Floyd算法、Dijkstra算法、GPSR算法，并分析了他们的优点和不足。图论在近几十年来得到了飞速的发展，尤其是与物理学、化学理论、信息理论、运筹学、计算机理论、控制论、社会科学等不同领域和学科的结合方面。3 最优路径最优路径选择和交通系统优化的目的就是是交通流均衡化，合理的在交通系统中分配，提高交通运输效率。因此，应当首先考虑交通流的特征。一般地，交通网络有如下特点：(1)线性分布，交通网络结构在空问分布中一般呈现线性特征，因此
31、交通网络建模可以依靠图论的相关理论和知识；(2)网络分布，交通网络是一个负载的网络拓扑结构，连通性好，结构复杂：(3)分段分布，交通系统中不同路段的特征一般不同，表现为空间的差异性，且同一路段的不同时间的交通网络特征也可能不同，表现为时间差异性；(4)动态性特点，交通网络上交通状况不是一层不变的，随时间的变化而变化，失意是时变系统：(5)车辆行驶的主观性，交通网络不同于其它网络，交通网络的主体可以自主的选择交通路径，行驶时间和行驶路线等是他的一个最显著特征。以图的理论为研究基础研究交通道路模型，采用改进的方法使得道路的车道信息加入到节点和边的信息中。以完整的交通道路作为建模的基本单元，但在交通
32、应用当中，交通特征的变化在交通系统的具体应用当中经常和车道关联密切。在同一一条道路上不同方向的车道具有不同的交通特性，如交通规则变化、交通量变化等。31 建立城市交通模型利用图论的相关理论和知识，对图中的节点和边设法加入车道信息用于模拟就哀痛系统。以完整的交通道路网络作为模型建立对象，只需要对道路中的相关数据和参数进行显示和计算，但在实际的交通道路当中，交通特征是实时变化的，这与交通道路模型密不可分。首先，在同一条道路上不同的车道在不同的行驶方向的交通特征可能不同，如交通量变化和交通规则等。例如：在早晚的上下班的高峰区段，进出同一区域的同一条道路在不同方向表现的车流量是明显不同的，交通拥堵现象
33、大多数情况下是发生在某条车道的单向车道上。其次，不同方向的车道由于具有不同的拓扑关系，因此交通规则有可能不同。由于在节点图层和路段图层中分别存储的点、线图元是分别独立的，两个图层问不想关联。为建立点线各个元素之间的空间拓扑关系，使他们构成有机整体，需要分别在存储点线信息的两张表文件中扩展一定长度的字段，用对象的属性字段之问的相互联系来建立交通网络图的拓扑关系，这样就建立了交通网络系统的有机整体即他们的拓扑关系结构图。311 道路节点模型可以将交通网络抽象成一个有向图，图中的边带有一定的权值，但这个抽象的有向图如何建立起来需要视具体的应用环境而定。在实际情况中人民出行是从一个地方到另一个地方，这
34、种不能简单的归结在图中从一个节点到另一个节点的转移，实际情况的交通网络运行是非常复杂的，所以不能简单的把某一个具体的地方当成是图中的某个节点，把道路信息抽象成图中带有权值的边，而是要将具体的地址信息抽象为节点以及其附属信息并加入到交通网络系统中。交通地址的交叉口所抽象的节点和将具体地址被抽象成图中的节点是不相等价的，需要考虑实际情况，因此交通节点的阻抗值应该视具体情况而定，而表示地名的节点的阻抗值可以视为零。 312 交叉口和道路模型将道路的数据模型抽象为一条线，因此选择道路中问的中心线表示道路数据模型，这种建模方法不能很好的描述交通道路的属性信息，丢失很多信息量。实际生活中的道路不能简单的抽
35、象为一条直线，因为有些道路存在很多车道，每个车道的属性信息不尽相同，多车道的交通道路属性信息较为复杂。在GPS进行导航式，需要考虑到的交通网络信息往往与车道信息密切相关。32 交通模型数据存储321 数据预处理在实际应用中，一般将交通网络模型用矢量化的数据地图表示，为了建立交通网络可使用的数据模型，需要对原始道路构成的交通网络矢量图进行优化和预处理，建立相应的拓扑关系图谱。矢量图形的预处理的一般包括：(1)对原始道路图像进行拓扑关系检查并进行剪断处理，保证地图中不存在两条道路相交的情况，将原来的道路拆分成多条道路的集合：(2)为每一条剪断后的道路建立拓扑关系，并定义其属性特征，如道路名称、道路
36、长度、交通流等特征；(3)将地图经过上述处理之后生成拓扑文件。322 交通路径模型建立与数据存储（1）交通路径模型的建立最短路径选择的前提是对交通系统创建合适的模型。按照上述方法对原始的交通道路进行预处理之后就可以确定道路之间的拓扑关系，进而可以建立以道路拓扑关系为基准的交通系统模型，拓扑关系中包括线性实体之间的模型，线性实体与节点之问的模型，节点与节点之间的模型，以及他们的连通性等。使用图中的节点表示交通系统的的较差路径，道路交叉即是图中的节点，两个节点之间的道路在图中用弧表示，就是图的边，路段的长度以及消耗时问等信息则为边带有的权值。在本文中，交通路径系统的模型由两部分图层所构成，一部分是
37、节点图层，一部分是交通道路图层。节点图层表示交通交叉口或者道路的起始点或终止点，用点对象来表示，路段图层存储这连接各个节点的交通路径以及他们的属性信息，用线对象表示。在两图层中分别存储的节点信息和路段信息分别是独立的，下一步就是建立两个图层之问的拓扑联系，使得两个图层构成有机整体，形成交通路径系统的完整性，需要用两个图层所对应的两张表中的文件扩展出一定的字段，用对象的属性信息来代表两个图层之间的拓扑关系，这样就构成了交通路径模型的整体拓扑关系结构图。交通路径的限制信息是交通导航中需要终点考虑的因素，比如由于施工、交通事故、速度限制、恶劣天气造成的交通限制等，实际的道路中交通限制信息十分复杂，而
38、且随时发生变化。本文考虑的交通限制信息只考虑了禁止通行的信息。如果某条道路出现禁止通行的限制信息，用节点的交通限制信息来表示。（2）数据存储一般地，在计算机中大多采用利用邻接表和邻接矩阵的方法存储有向图。顺序表V0，V1，Vm-1。的形式在邻接局长呢中存储图中所有的结点，以mm大小的矩阵存储图的边。使用邻接矩阵来表示图的存储浅显易懂，也可以通过邻接矩阵来存储边的权值信息和节点信息以及他们之间的连同情况等等，因此在本文中也利用邻接表和邻接矩阵方法。33 最优路径选择331 最优路径的求解过程在交通网络中，求解最优路径的一般思路是：把最优路径选择问题转化成优化问题来解决，应用优化理论的相关思想和思
39、路解决最优路径优化问题。求解过程包括以下四个步骤酬：(1)交通网络模型建立；(2)交通道路权重的计算；(3)利用最短路径计算方法求解交通网络中的最短路径问题；(4)将交通网络图中的最短路径问题转化为现实交通网络中的路段集合。其中，建立交通网络模型是最优路径选择的基础，交通网络模型中道路权值的计算以及利用权值信息求解最短路径是关键。道路的权值是计算现实问题中最短路径的基础，最优路径选择的准确与否在很大程度上取决于道路权值的设计和计算。 332 经典Dijkstra算法分析在1959年荷兰数学家EWDijkstra首先提出的Dijkstra算法，该算法是一种单源最短路径的搜索算法，他适用于非负权值
40、网络的，是目前求解最短路问题的理论上最完备、应用范围最广的算法，可以计算出从图中的某一节点到其他任意节点的最短路径搜索结果.Dijkstra是一种迭代的贪心策略的路径搜索算法，他根据路径的长短逐渐增长来搜索点数，构造了一颗路径树，从而得到路径树中的根部节点到其他任意节点的最短路径结果。假设带权值的有向图为G=(V，E)，其中V是数量为n的结点集，E是数量为m的边集，w为权值向量。具体算法步骤如下：(1) 对d和x进行初始化；(2)s集合初始为空，S=； （3）为当前图中的所有结点赋值给集合Q，Q=VG：(4)循环条件：while Q；(5)提取出集合Q中最小d值的结点，并赋给甜，U=Point
41、Min(Q)：(6)将提取出的结点加入S集合，S=Su；(7)对于每个结点vAdju，计算并修改v的d和，；(8)结束。最初Dijkstra算法开发的目的是计算网络图中两节点之间的最短路径问题，当该算法应用到交通网络的最短路径搜索时，由于起始点和终止点都是已知的，因此只需要从起始点开始搜索，按照其搜索原则寻找最短路径，一直搜索的终止点为止，需要对该算法进行优化和改进，才能使用到交通网络的最优路径选择系统当中。从算法的原理可以发现，当交通网络十分庞大时，该算法的计算量是十分巨大的，如果将该算法直接用于交通网络的最优路径选择算法当中，不能达到应用的实时性要求，因此需要对该算法的性能进行提升式改进。
42、另外，该算法只是路径搜索，对于交通网络中的路径权值问题没有任何解决办法，因此该算法可以作为最优路径选择的主要路径搜索算法，而对于权值的提取和计算，需要额外增加辅助算法来完成，能够反映交通网络系统在实时状态下权值的变化情况。 333 Dijkstra算法改进由于动态路径所具有的特点，需要在搜索过程中实时导入交通系统中的更新的信息，而Dijkstra算法不能适用与大规模交通网络的路径搜索问题，因此需要对Dijkstra算法进行改进，改进的Dijkstra算法的具体计算步骤如下：(1)初始化：设S仅包含原节点，原节点为当前节点(m)，令d=0，=，其他各节点的d=，=：(2)如果S中包含全部节点，转
43、入(6)；否则转入(3)；(3)根据当前节点历后面连接的路段自动生成节点m的后继结点，对每一个后继节点n，计算如下：a计算车辆到达节点历时对应的Sk值；计算车辆在节点m与节点n之问的时问花费；b如果d(n)d(m)+time(m，n)，则将d(n)=d(m)+time(m，n)，(n)=m：否则转入(4)；(4)排除与节点m相邻的节点的限制信息并读取m的限制信息。搜索d值最小的结点并将当前节点设为(m)，将结点m加入到集合S中，转入步骤(2)；否则程序终止，这时，对每个属于S的节点，其d值就是原节点到达此节点的最短路径需要花费的时间；(5)根据s中节点的属性信息开始回溯，一直回溯到起始的源节点
44、，最后报告结果路径;(6)算法结束。当算法结束时，集合S中的每个节点，其d值表示的就是原始节点到达该节点利用最短路径所耗费的市静安。若s表示交通路径中路段数，Z表示交通路径中的节点的个数，则改进算法的时间复杂度最大值为O(z2+s)+O(z2） 33. 4 交通阻抗分析交通阻抗是车辆运行在交通道路上时，根据运行的距离、时间、舒适度、拥堵情况、交通费用和人的舒适度等综合因素，需要考虑到即人、车、路、环境相互影响，对交通出行的阻力作用值。针对不同的交通网络系统，阻抗值的计算方法不同，需要考虑到的阻碍因素也不同。城市交通系统的交通阻抗可分为两类，节点交通阻抗和道路交通阻抗，节点交通阻抗表示的是交叉口
45、的交通阻抗。交通阻抗的计算指标主要表现在阻抗函数的确定，为了将交通阻抗使用语一般性的公路系统，将路径诱导算法中采用广义上的交通阻抗。所谓广义交通阻抗，是指出行者从起始点开始驾驶机动车到达终点而付出的代价以及对交通道路系统带来的负面效应的综合。它的要素应该包括出行时间、出行方式、出行费用、使用资源、车辆磨损、环境污染程度等。因此交通阻抗的最小值为以上各个元素最小值的总和，而最大值为以上各个元素最大值的总和。在路径选择中，有出行时间长度、行驶距离长度、拥挤程度、道路质量和出行费用等评价指标，以提供不同的应用环境进行选择使用。当交通网络中交通流量分布比较均匀，没有出现交通意外事故等特殊情况时，这五种
46、评价方法不会互相矛盾的，当交通道路中出现交通拥堵，交通事故等特殊情况时，这五种评价方法所得到的结果可能不同，有存在矛盾的地方，但一般来说，实际情况下考虑出行的交通阻抗，一般采用一时问为评价标准来作为交通那个阻抗的评价指标。3. 4 本章小结本章利用图论的相关理论和方法对交通道路进行分析。分析了经典的最优路径选择Dijkstra算法并对其进行改进，考虑到在实际情况中由道路质量、拥堵情况等导致交通道路存在一定的交通阻抗，并将交通阻抗的计算加入到改进的Dijkstra算法当中，使之更具有应用价值。改进的路径选择算法在原有算法基础上，减少了时间复杂度，提高了路径搜索的效率。4 GlS数据模型和数据库设
47、计路径选择系统的工作原理是输入交通系统中的起点和终点，能给出一条已规划的路径结果。在路径选择系统的设计与实现过程中需要使用合适的数据库来管理地理数据信息(GIS数据)能够提高GIS数据的计算速度，进一步提高路径选择的效率，使能够大道实时效果。本章的内容主要是介绍了GIS数据的一些相关内容和数据库管理设计内容，主要内容包括GIS数据的相关概念和内容知识、Oracle数据库选择的原因、GIS数据导入、GIS数据在数据库中的管理和维护等内容。41 GIS数据模型建立数据模型是能够描述数据内在特征的工具，也是一门描述语言，是现实世界中对某种或某类特征的模拟、抽象、提取和组织。地理信息数据模型是模拟地理信息的形式化表示的工具。地理信息数据模型的建立为地理信息的表达和操作方法提供了具体的形式构架。GIS数据所描述的对象主要包括与地理位置有关的空间数据信息和非空间依赖性的属性方面的信息数据。 411 空间数据模型G1S空间数据与要描述的对象空间位置信息是相关的。目前，在GIS数据研究领域中学者们提出的空问数据模型主要有矢量数据模型、栅格数据模