毕业论文交通线路选择软件的设计与实现【最终稿】

武汉纺织大学交通线路选择软件的设计与实现姓名：学号：学院：电子与电气工程学院指导老师：2015年5月30日摘要随着社会经济的飞速发展，出行方式的多样选择，设计和研究一套简单交通线路选择软件，成为利民便民和增强市场竞争力的重要举措。这其中设计最主要的核心问题是最优路径选择问题。本文分析了交通道路网络的具体特点，主要包括线性分布特点、网络分布特点、分段分布特点、动态性特点和车辆行驶的自主性特点等。将交通网络抽象成一个由边和节点组成的图，并根据图论的相关理论和知识构建起交通网络模型，包括交通道路节点模型，交叉口和道路模型，并对上述道路模型信息进行存储，以构建好的交通道路模型为基础研究智能交通系统中的最优路径问题。考虑到实际道路中存在一定的交通阻抗，为使算法更具有应用价值，本项目在Dijkstra算法的基础上进行了改进，缩短了道路搜索时间，提高了最优路径选择的效率。数据库的选择与设计是系统实现中不可或缺的重要组成部分，优秀的数据库选择和设计方案能够提高最优路径选择的效率、也提高了整个智能交通系统的工作效率。本文使用了GIS数据模型与数据库的管理设计，主要包括GIS数据的简介、选择Oracle的理由、GIS数据向Oracle中的导入和存储、Oracle中GIS数据的访问和维护。对道路交通系统的建模、最优路径选择算法的研究以及数据库的开发设计目的是建立一套接近实际情况的最优路径选择系统。本文将经典的Dijkstra算法和改进的Dijkstra算法进行编码实现，使之在最优路径选择系统中正确运行。关键词：智能交通线路选择;最优路径;GIS数据;系统设计;Dijkstra算法ABSTRACTAlongwiththerapiddevelopmentofsocialeconomy,diverseselectionoftravelmode,researchanddesignasimpletrafficroutestochoosesoftwarebecomeconvenienceandtoenhancethemarketcompetitivenessoftheimportantinitiatives.Thedesignofthemaincoreoftheproblemistheoptimalroutingproblem.Thispaperanalyzesthespecificcharacteristicsofthetrafficandroadnetwork,includinglineardistributioncharacteristicsofnetworkdistributioncharacteristics，segmenteddistributioncharacteristics，dynamiccharacteristicsofvehiclesautonomousfeatures．Abstracttransportationnetworkasagraphofedgesandnodes，andbuildatransportationnetworkmodelbasedongraphtheorytheoryandknowledge，includingtrafficroadnodemodel,intersectionsandroadmodel,andstorageoftheroadmodelinformationtobuildgoodtrafficroadmodelforbasicresearchinintelligenttransportationsystems，theoptimalpath.Consideringtheactualroadtrafficimpedance，isthealgorithmmoreapplicationimprovedvalueonthebasisoftheDijkstraalgorithm,shorteningthepathsearchtime，andtoimprovetheefficiencyoftheselectionoftheoptimalpath．Thedatabaseisanimportantpartofanintegralsystemdesignandimplementation,databaseselectionanddesignofadirectimpactontheefficiencyofthepathplanningsystem．ThisarticleusesthedesignofaGISdatamodelanddatabasemanagement，mainlyincludingtheintroductionofGISdata,selectOraclereasonimportedandstoredintheOracle，GISdata,theOracleGISdataaccessandmaintenance.Modelingofroadtrafficsystem,theoptimalpathselectionalgorithmwellasthedevelopmentofthedatabaseisdesignedtoestablishtheoptimalrouteselectionsystemsetclosetotheactualsituation．ClassicalDijkstraalgorithmandimprovedDijkstraalgorithmwereimplemented．Theoptimalpathselectionsystemisprovedcorrectly．KeyWords：Intelligenttrafficlineselection;Optimalpath;GISdata;Systemdesign;Dijkstraalgorithm目录TOC\o"1-3"\h\u1绪论12基础知识32．1路径优化算法概述32．1．1Floyd算法32．1．2Dijkstra算法42．1．3GPSR算法42．2图论简介52.2.1图的概念62．2．2图的表示62．2．3图的存储72．3本章小结73最优路径83．1建立城市交通模型83．1．1道路节点模型93．1．2交叉口和道路模型93．2交通模型数据存储93．2．1数据预处理93．2．2交通路径模型建立与数据存储103．3最优路径选择113．3．1最优路径的求解过程113．3．2经典Dijkstra算法分析113．3．3Dijkstra算法改进123．3.4交通阻抗分析133.4本章小结144GlS数据模型和数据库设计144．1GIS数据模型建立144．1．1空间数据模型154．1．2属性数据模型154.2GlS数据的管理与组织164.3SpatiaI简介164．4空间数据向Oracle中的导入174．5GIS数据在OracIe中的存储174．6Oracle中GIS数据的访问184.7Oracle中GlS数据的维护184．8本章小结195路径优化算法系统实现195．1电子地图制作195．2仿真结果与分析195．3本章小结216结论21参考文献22致谢231绪论随着改革开放经济的发展，人口数量的不断增多，城市的数量和规模不断增大和增多，城市化程度和趋势十分明显，城市交通问题成为目前影响和制约我国经济发展和社会进步的主要因素。不论是上海北京等特大城市还是其他省会城市或地级市，普遍存在交通问题，城市车辆不断增多，人口越发密集，道路环境不断恶化等原因都是导致城市交通问题的主要方面。这就要求我们拥有的便利交通系统，随着计算机技术和电子技术的不断发展，以及电子地图测绘技术的不断进步，这使得地理信息系统也得到了长足的进步，这些技术的发展都给智能交通系统的发展奠定了良好的基础。通过中西交通道路系统的比较，我国城市交通系统的主要问题包括交通管理技术落后，为从根本上解决问题上述交通拥堵问题，并保持大中城市交通可持续发展带动城市的可持续反战，除了合理地进行交通道路等基础设施建设外，另一个切实可行的办法就是进西方先进的高科技管理技术改进我们的交通系统，并使其符合我国国情，建立高性能高效率的智能城市交通系统(ITS)。智能交通系统(ITS)通过充分发挥现有交通资源潜力和系统内部协同作用产生的效力，能够为城市交通提供更安全、更舒适、更高效率和更高品质的新型城市交通系统嘲。智能交通系统的目标是利用现金的计算机技术和先进的网络管理来减少交通拥堵、交通事故和环境污染，与此同时，交通系统能够有效的正常的运行。在交通、计算机、电子通信、信息技术和系统科学与工程应用领域中，智能交通系统是日前许多国内外学者和研究机构集中、深入的研究领域之一，具有非常好的发展前景。在我国，随着交通运输业的不断发展，交通环境日益恶化的今天，研究出一套能够适应我国国情的现代智能交通系统和车辆导航系统，使之能够为人们出行提供重要的交通信息，避免交通拥堵，减少交通事故，为驾驶者提供最佳的驾驶路径，达到交通的路网畅通已经迫在眉睫。如果能够对车辆导航系统提供行之有效的最佳路径选择算法，就能为人们出行提供有效、合理有效的出行路径，从而提高交通系统运行的效率。最佳路径选择问题是智能交通系统中的重要组成部分，也是交通地理信息系统研究中的一个热点问题之一，是出行路径设计与优化、现有有限资源重新利用和分配等问题的基础。因此最优路径选择与优化问题是实时的动态交通系统中具有具有重要现实意义的研究课题。最佳路劲的算法研究不仅可以应用在交通网络系统中，而且对出行决策、校车路径查询、快递物流、资源分配等方面也有很好的应用价值。道路交通系统中最佳路径选择的研究能够为综合信息管理和只能决策提供先进、科学和行之有效的判决依据；为人们出行提供便利的交通运输条件；为车辆的运行提供安全保障：提高了现代交通道路的利用效率；帮助车辆减少尾气排放和燃油等资源的消耗：对于建设资源节约型社会具有划时代的意义。目前我国对有许多与最优路径求解相关的学科在侧面对这个问题做过研究，如运筹学、计算机科学、图论、数论、交通工程学理论、地理信息科学研究等。日前网络发展十分迅速，而网络的构成类似交通道路系统，可以利用最优路径算法来解决很多网络方面的问题。经典学科中的图论、数论与计算机科学以及数据结构与算法的有效结合使得对最优路径算法的研究有了很大进展。国内外大量研究机构和相关学者对最优路径问题的解决进行过深入研究与探讨。数学家E．W．Dijkstra在1959年就提出了标号设定法用于解决路径问题，形成了目前仍被视为经典的Dijkstra算法。自从Dijkstra算法面世以后，又历经了很多学者对该算法的改进与发展，因此有关最优路径选择问题的研究成果不断涌现，使其求解速度和求解效率不断提高。最优路径选择算法在不同的应用条件下可以按照不同的方法进行分类。如按照时间顺序来分类，分为动态最优路径选择问题和静态最优路径选择问题；如果按照确定性和非确定性来划分，分为确定型和随机型最优路径选择问题；如果按照网络规模大小划分，可分为小规模网络和大规模网络最优路径选择问题：如果按照计算方式来划分，可分为串行和并行最优路径选择算法。各种不同类别的最优路径选择算法相互组合可以成为解决不同问题的各种各样算法。最优路径问题按照是否是单源问题还可以分为单源最优路径选择问题及全源最优路径选择问题。其中单源最优路径选择问题更具有实际应用的意义，而且良好的单源路劲问题的算法可为全源最优路径问题提供良好的研究基础，因此本文在研究最优路径选择问题的过程中只考虑单源最优路径选择问题。2基础知识2．1路径优化算法概述国内外的研究机构和学者对不同的路径优化算法进行了研究、分析、比较和论证，比较经典的路径优化算法有Floyd算法、Dijkstra算法、GPSR算法、遗传算法、蚁群算法等。实际的交通网络是一个复杂的动态网络系统结构，它包括各种道路的限制信息以及交通流量的实时信息，然而现有的所有路径优化算法均是对某种抽象的具体网络结构进行优化计算各种，这就需要对实际的交通网络建立模型。路径优化的效率和速度室友所建立模型的准确程度来决定的。目前，国内外学者己经有许多传统的经典算法用来解决路径优化问题，但这些算法具有共同的点就是并没考虑实际出行的具体特点特点，如路况信息、道路质量、道路上的车流量等。最短路径算法求出的仅仅是在空间距离最短的路径，但在实际应用中人们需要的是最优路径，最优路径不一定是距离最短，还要考虑交通阻抗的问题，比如想要求得从A地到B地的最优路径，这个问题是指在所有从A地到B地的所有路线当中选择最优的一条，包括最节省时问，最节省资源，是驾驶者最舒适，对交通工具的各项消耗最小等。最优路径问题并不是普通意义上的距离最短路径选择问题。实际情况下最优路径选择问题包括两层含义：首先最优路径是一条可以从A地到达B地的畅通的路径；其次这条路径在所有路径当中是最佳的。从A地到B地想要找一条最优路径，应是一条的所用时间最短、驾驶者最舒适、道路上的车辆数量较少，或对交通车辆的损耗最少。2．1．1Floyd算法Floyd算法是由Floyd在1962年提出的。将图的节点和边的信息计算利用矩阵计算来完成，通过一个图的权值矩阵中求出交通网络中任意两点之间的最短路径。基本思想：比如求图中两节点Vi到Vj的之问的最短路径问题。Floyd算法是一种动态规划算法，由于是穷举法进行计算，因此对于稠密图效果较好。此算法思路简单，该算法对于稠密图来说，效率要高于经典的Dijkstra算法。但缺点是时间复杂度较高，不适合大规模数据的计算，耗时较长。2．1．2Dijkstra算法Dijkstra算法由荷兰数学家EdsgerWybeDijkstra在1959年提出来的，是一种单源最短路算法适用于非负权值网络的计算，是目前在求解最短路径问题较为完备且应用广泛的算法之一，可以计算出图中从指定结点到图中其他任意节点之问的最短路径。在一个图G中，Dijkstra算法不但可以给出两指定结点之间的一条具有权值最下送的路径，且还可找出从指定点到图G中所有结点的最短路径。Dijkstra算法的缺点就是当网络中结点数量较大时，就会增加算法的复杂度，降低了效率。该算法通过图中的每个节点v建立额外的信息数组，存储从其他任意节点S到v的最短路径。在初始状态下，原始节点S的路径长度值被赋为0即dis的值为0，同时假设其他所有节点到该节点的路径长度为无穷大，用无穷大长度的路径表示任何其他节点到该结点的路径是未知的。如果存在从S到v的路径，那么当苏算法结束时储存的信息是S到v的距离最短路径；如果从S到v的路径不存在，则d[V]中储存信息是无穷大。Dijkstra算法的操作对边进行了拓展：如果从U到v的路径是存在的，将边(u，v)添加到(s，v)尾部，则这条新的路径的长度为dM+w(u，v)。如果这条路径的长度比已知的路径长度d[v]的值小，我们可以用新的路径来代替原有路径。这种拓展边的迭代运算一直进行，一直运行到所有的dM都代表从S到v最短路径为止。算法需要维护两个结点集Q和P，集合P保留了我们通过迭代运算所得的所有dM的最短路径的值结点，而集合Q则保留其他剩下的所有结点。集合P初始状态为空，而后每一步都有一个结点从集合Q中转移到集合P中，并相应的在Q中删除该节点信息。2．1．3GPSR算法GPSR路由算法的思路是利用地理位置信息进行最优路径选择，该算法需要通过贪婪转发算法来建立与其他信息之间的关联和路由。当节点s向D转发数据分组时，他首先找到与相邻节点中距离最小的那个节点，然后将数据分组转发给那个节点，将距离最小的那个节点称为跳点，然后将S的数据传送给这个跳点，该过程需要一直迭代计算，直到分组数据全部到达节点D。利用欧氏距离计算距离方法计算距离该节点最近的相邻节点，但如果数据传输的某一节点是发现没有找到下一个距离最小的节点使得数据传送的目标节点时，导致了数据传输的失败。在发生生无法传送数据时，节点能够探测到周围的空洞，并利用右手法则沿着空洞周围的节点传输数据来解决这类问题。该方法的优点在于米面了在节点信息中存储建立和维护路由表信息，只需要利用相邻节点进行路径选取即可进行，几乎是不需要任何协议辅助；并且利用欧氏距离最小的方法进行路由，数据传输的延时最小；并能够保证只要网络路径不被破坏，数据一定能到传送到目标节点中去。但该算法存在这一定的缺点，当网络中的某节点与源点集中在两个区域时，由于通信的不平衡能够导致部分节点无效，从而是网络的连通性遭到破坏；另一方面是该方法需要GPS定位系统的辅助来计算几点的位置信息。GPSR中贪婪转发算法能够正常转发数据的前提是：目的结点的位置都包含于每个数据分组中，每个结点都有邻居结点列表信息以及邻居结点和本结点的位置信息。在实际的路线选取过程中，我们将路口与上述的结点对用。在电子地图中，每个路口都有坐标位置和列表信息，那么在算法程序中我们首先要做的是让每个结点都包含一条邻居结点链表，并将结点号与位置信息关联起来。2．2图论简介图论(GraphTheory)是组合数学的一个分支，它源于瑞士数学家欧(Euler)1736年对于著名的哥尼斯堡七桥问题的解决，从而使欧拉成为了图论的创始人。图论是数学学科当中比较年轻的一个分支。在图论被提出后的两百年中，图论的发展相对缓慢，但自从图论与大量的实际问题相结合，在物理学、化学、信息论、运筹学、计算机科学、控制论、社会科学，经济管理等各种学科中找到了更广泛的应用，使图论在近几十年来得到了快速的的发展。目前在图论领域中形成了两个不同的方向：抽象图论和最优化图论。前者主要研究图的性质，后者主要讨论与图有关的优化问题。最优化图论既可以算作图论中的一个研究方向，也可以看作运筹学中最优化理论的组成部分。图论中的图是由若干节点以及两节点之间的连线所构成的图形，图论的研究对象是图，这种图形不考虑点的大小、形状和边的形状、长度、大小以及边与边的角度等几何问题，而主要表达的是点点之间通过线的连通关系，通常可以用来描述某些事物之间的相互关系，即用点来代表事件发生，用连接两点的边表示两个事件之间的关系。因此图论中的图能够代表多种含义，因此图论在诸多领域都有着非常广泛的应用。2.2.1图的概念无向图是指有序三元组(V，E,F)中边没有方向，其中集合y被称为结点集，y中的元素称为结点：集合E被称为边集，E中的元素被称为边；而函数是边集E到无序结点对儿所构成的集合的一个映射关系，称之为关联函数。如果P是一条边“，'，两个结点，且满足F(E)=uv，，那么就可称为e连接：并且称Ⅳ，y为E的端点。每条边与边两端的节点是相互关联的因此称为相互关联，与同一条边相关联的节点或者与同一个节点相互关联的边称为相邻的节点或者相邻的边，具有相同两个节点的边称为重合边或者是平行边，两个节点相同的边组成环，简单图就是没有环和重边的图。每个结点度数相同的简单图称为正则图，最大度与最小度恰好相差1的简单图被称为几乎正则图。图的结点的个数称为图的阶。2．2．2图的表示由点集合V和点与点之间的连线的集合E所组成的集合对(V，E)可以构成图，用G(V,E)来表示。图G(V，E)由其结点与边之间的关系确定，且是唯一的。也由它的结点对儿之间的邻接关系唯一确定。V中的元素为结点，E中的元素为边。节点集合V与边集合E均为有限的图称为有限图。图2-1图的结构2．2．3图的存储邻接表邻接表结构：adfvexnextarcinfodatafirstarc图2-2邻接表结构表节点和头结点邻接表以一种以链式存储结构所构成的图。在邻接表中，图中的每个节点都会有一个单链表与之对应，第i个单链表中的结点数据表示依附于结点v。三个域构成了每个节点，，其中结点的邻接点域的数值表示与结点-相邻节点在图中的具体位置，结点的链域将指示下一条边的结点，结点数据域存储的是图中边的信息，如权值、方向等。每个链表都会有一个表头结点与之对应，在表头结点中，设有存储结点q的各个域及与该信息有关的相关数据域。这些表头结点存储数据的形式通常是顺序存储的，这样存储方式便于随即访问任何一个节点的链表信息。(2)十字链表十字链表针对有向图的另一种存储结构。可以看成是一种新的链表，该链表将有向图的邻接表和逆邻接表结合在一起。在十字链表中，每一条边都有一个节点与之对应，每一个节点也有一个节点与之对应。2．3本章小结本章对最优路径算法和图论的相关理论知识进行了简单概述。对几个经典的最优路径选择算法进行了介绍，如Floyd算法、Dijkstra算法、GPSR算法，并分析了他们的优点和不足。图论在近几十年来得到了飞速的发展，尤其是与物理学、化学理论、信息理论、运筹学、计算机理论、控制论、社会科学等不同领域和学科的结合方面。3最优路径最优路径选择和交通系统优化的目的就是是交通流均衡化，合理的在交通系统中分配，提高交通运输效率。因此，应当首先考虑交通流的特征。一般地，交通网络有如下特点：(1)线性分布，交通网络结构在空问分布中一般呈现线性特征，因此交通网络建模可以依靠图论的相关理论和知识；(2)网络分布，交通网络是一个负载的网络拓扑结构，连通性好，结构复杂：(3)分段分布，交通系统中不同路段的特征一般不同，表现为空间的差异性，且同一路段的不同时间的交通网络特征也可能不同，表现为时间差异性；(4)动态性特点，交通网络上交通状况不是一层不变的，随时间的变化而变化，失意是时变系统：(5)车辆行驶的主观性，交通网络不同于其它网络，交通网络的主体可以自主的选择交通路径，行驶时间和行驶路线等是他的一个最显著特征。以图的理论为研究基础研究交通道路模型，采用改进的方法使得道路的车道信息加入到节点和边的信息中。以完整的交通道路作为建模的基本单元，但在交通应用当中，交通特征的变化在交通系统的具体应用当中经常和车道关联密切。在同一一条道路上不同方向的车道具有不同的交通特性，如交通规则变化、交通量变化等。3．1建立城市交通模型利用图论的相关理论和知识，对图中的节点和边设法加入车道信息用于模拟就哀痛系统。以完整的交通道路网络作为模型建立对象，只需要对道路中的相关数据和参数进行显示和计算，但在实际的交通道路当中，交通特征是实时变化的，这与交通道路模型密不可分。首先，在同一条道路上不同的车道在不同的行驶方向的交通特征可能不同，如交通量变化和交通规则等。例如：在早晚的上下班的高峰区段，进出同一区域的同一条道路在不同方向表现的车流量是明显不同的，交通拥堵现象大多数情况下是发生在某条车道的单向车道上。其次，不同方向的车道由于具有不同的拓扑关系，因此交通规则有可能不同。由于在节点图层和路段图层中分别存储的点、线图元是分别独立的，两个图层问不想关联。为建立点线各个元素之间的空间拓扑关系，使他们构成有机整体，需要分别在存储点线信息的两张表文件中扩展一定长度的字段，用对象的属性字段之问的相互联系来建立交通网络图的拓扑关系，这样就建立了交通网络系统的有机整体即他们的拓扑关系结构图。3．1．1道路节点模型可以将交通网络抽象成一个有向图，图中的边带有一定的权值，但这个抽象的有向图如何建立起来需要视具体的应用环境而定。在实际情况中人民出行是从一个地方到另一个地方，这种不能简单的归结在图中从一个节点到另一个节点的转移，实际情况的交通网络运行是非常复杂的，所以不能简单的把某一个具体的地方当成是图中的某个节点，把道路信息抽象成图中带有权值的边，而是要将具体的地址信息抽象为节点以及其附属信息并加入到交通网络系统中。交通地址的交叉口所抽象的节点和将具体地址被抽象成图中的节点是不相等价的，需要考虑实际情况，因此交通节点的阻抗值应该视具体情况而定，而表示地名的节点的阻抗值可以视为零。3．1．2交叉口和道路模型将道路的数据模型抽象为一条线，因此选择道路中问的中心线表示道路数据模型，这种建模方法不能很好的描述交通道路的属性信息，丢失很多信息量。实际生活中的道路不能简单的抽象为一条直线，因为有些道路存在很多车道，每个车道的属性信息不尽相同，多车道的交通道路属性信息较为复杂。在GPS进行导航式，需要考虑到的交通网络信息往往与车道信息密切相关。3．2交通模型数据存储3．2．1数据预处理在实际应用中，一般将交通网络模型用矢量化的数据地图表示，为了建立交通网络可使用的数据模型，需要对原始道路构成的交通网络矢量图进行优化和预处理，建立相应的拓扑关系图谱。矢量图形的预处理的一般包括：(1)对原始道路图像进行拓扑关系检查并进行剪断处理，保证地图中不存在两条道路相交的情况，将原来的道路拆分成多条道路的集合：(2)为每一条剪断后的道路建立拓扑关系，并定义其属性特征，如道路名称、道路长度、交通流等特征；(3)将地图经过上述处理之后生成拓扑文件。3．2．2交通路径模型建立与数据存储（1）交通路径模型的建立最短路径选择的前提是对交通系统创建合适的模型。按照上述方法对原始的交通道路进行预处理之后就可以确定道路之间的拓扑关系，进而可以建立以道路拓扑关系为基准的交通系统模型，拓扑关系中包括线性实体之间的模型，线性实体与节点之问的模型，节点与节点之间的模型，以及他们的连通性等。使用图中的节点表示交通系统的的较差路径，道路交叉即是图中的节点，两个节点之间的道路在图中用弧表示，就是图的边，路段的长度以及消耗时问等信息则为边带有的权值。在本文中，交通路径系统的模型由两部分图层所构成，一部分是节点图层，一部分是交通道路图层。节点图层表示交通交叉口或者道路的起始点或终止点，用点对象来表示，路段图层存储这连接各个节点的交通路径以及他们的属性信息，用线对象表示。在两图层中分别存储的节点信息和路段信息分别是独立的，下一步就是建立两个图层之问的拓扑联系，使得两个图层构成有机整体，形成交通路径系统的完整性，需要用两个图层所对应的两张表中的文件扩展出一定的字段，用对象的属性信息来代表两个图层之间的拓扑关系，这样就构成了交通路径模型的整体拓扑关系结构图。交通路径的限制信息是交通导航中需要终点考虑的因素，比如由于施工、交通事故、速度限制、恶劣天气造成的交通限制等，实际的道路中交通限制信息十分复杂，而且随时发生变化。本文考虑的交通限制信息只考虑了禁止通行的信息。如果某条道路出现禁止通行的限制信息，用节点的交通限制信息来表示。（2）数据存储一般地，在计算机中大多采用利用邻接表和邻接矩阵的方法存储有向图。顺序表V0，V1，⋯Vm-1。的形式在邻接局长呢中存储图中所有的结点，以m×m大小的矩阵存储图的边。使用邻接矩阵来表示图的存储浅显易懂，也可以通过邻接矩阵来存储边的权值信息和节点信息以及他们之间的连同情况等等，因此在本文中也利用邻接表和邻接矩阵方法。3．3最优路径选择3．3．1最优路径的求解过程在交通网络中，求解最优路径的一般思路是：把最优路径选择问题转化成优化问题来解决，应用优化理论的相关思想和思路解决最优路径优化问题。求解过程包括以下四个步骤酬：(1)交通网络模型建立；(2)交通道路权重的计算；(3)利用最短路径计算方法求解交通网络中的最短路径问题；(4)将交通网络图中的最短路径问题转化为现实交通网络中的路段集合。其中，建立交通网络模型是最优路径选择的基础，交通网络模型中道路权值的计算以及利用权值信息求解最短路径是关键。道路的权值是计算现实问题中最短路径的基础，最优路径选择的准确与否在很大程度上取决于道路权值的设计和计算。3．3．2经典Dijkstra算法分析在1959年荷兰数学家EW．Dijkstra首先提出的Dijkstra算法，该算法是一种单源最短路径的搜索算法，他适用于非负权值网络的，是目前求解最短路问题的理论上最完备、应用范围最广的算法，可以计算出从图中的某一节点到其他任意节点的最短路径搜索结果.Dijkstra是一种迭代的贪心策略的路径搜索算法，他根据路径的长短逐渐增长来搜索点数，构造了一颗路径树，从而得到路径树中的根部节点到其他任意节点的最短路径结果。假设带权值的有向图为G=(V，E)，其中V是数量为n的结点集，E是数量为m的边集，w为权值向量。具体算法步骤如下：(1)对d和x进行初始化；(2)s集合初始为空，S=Φ；（3）为当前图中的所有结点赋值给集合Q，Q=V[G]：(4)循环条件：whileQ≠Φ；(5)提取出集合Q中最小d值的结点，并赋给甜，U=PointMin(Q)：(6)将提取出的结点加入S集合，S=S∪{u}；(7)对于每个结点v€Adj[u]，计算并修改v的d和，π；(8)结束。最初Dijkstra算法开发的目的是计算网络图中两节点之间的最短路径问题，当该算法应用到交通网络的最短路径搜索时，由于起始点和终止点都是已知的，因此只需要从起始点开始搜索，按照其搜索原则寻找最短路径，一直搜索的终止点为止，需要对该算法进行优化和改进，才能使用到交通网络的最优路径选择系统当中。从算法的原理可以发现，当交通网络十分庞大时，该算法的计算量是十分巨大的，如果将该算法直接用于交通网络的最优路径选择算法当中，不能达到应用的实时性要求，因此需要对该算法的性能进行提升式改进。另外，该算法只是路径搜索，对于交通网络中的路径权值问题没有任何解决办法，因此该算法可以作为最优路径选择的主要路径搜索算法，而对于权值的提取和计算，需要额外增加辅助算法来完成，能够反映交通网络系统在实时状态下权值的变化情况。3．3．3Dijkstra算法改进由于动态路径所具有的特点，需要在搜索过程中实时导入交通系统中的更新的信息，而Dijkstra算法不能适用与大规模交通网络的路径搜索问题，因此需要对Dijkstra算法进行改进，改进的Dijkstra算法的具体计算步骤如下：(1)初始化：设S仅包含原节点，原节点为当前节点(m)，令d=0，π=φ，其他各节点的d=∞，π=φ：(2)如果S中包含全部节点，转入(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中节点的属性信息开始回溯，一直回溯到起始的源节点，最后报告结果路径;(6)算法结束。当算法结束时，集合S中的每个节点，其d值表示的就是原始节点到达该节点利用最短路径所耗费的市静安。若s表示交通路径中路段数，Z表示交通路径中的节点的个数，则改进算法的时间复杂度最大值为O(z^2+s)+O(z^2）3．3.4交通阻抗分析交通阻抗是车辆运行在交通道路上时，根据运行的距离、时间、舒适度、拥堵情况、交通费用和人的舒适度等综合因素，需要考虑到即人、车、路、环境相互影响，对交通出行的阻力作用值。针对不同的交通网络系统，阻抗值的计算方法不同，需要考虑到的阻碍因素也不同。城市交通系统的交通阻抗可分为两类，节点交通阻抗和道路交通阻抗，节点交通阻抗表示的是交叉口的交通阻抗。交通阻抗的计算指标主要表现在阻抗函数的确定，为了将交通阻抗使用语一般性的公路系统，将路径诱导算法中采用广义上的交通阻抗。所谓广义交通阻抗，是指出行者从起始点开始驾驶机动车到达终点而付出的代价以及对交通道路系统带来的负面效应的综合。它的要素应该包括出行时间、出行方式、出行费用、使用资源、车辆磨损、环境污染程度等。因此交通阻抗的最小值为以上各个元素最小值的总和，而最大值为以上各个元素最大值的总和。在路径选择中，有出行时间长度、行驶距离长度、拥挤程度、道路质量和出行费用等评价指标，以提供不同的应用环境进行选择使用。当交通网络中交通流量分布比较均匀，没有出现交通意外事故等特殊情况时，这五种评价方法不会互相矛盾的，当交通道路中出现交通拥堵，交通事故等特殊情况时，这五种评价方法所得到的结果可能不同，有存在矛盾的地方，但一般来说，实际情况下考虑出行的交通阻抗，一般采用一时问为评价标准来作为交通那个阻抗的评价指标。3.4本章小结本章利用图论的相关理论和方法对交通道路进行分析。分析了经典的最优路径选择Dijkstra算法并对其进行改进，考虑到在实际情况中由道路质量、拥堵情况等导致交通道路存在一定的交通阻抗，并将交通阻抗的计算加入到改进的Dijkstra算法当中，使之更具有应用价值。改进的路径选择算法在原有算法基础上，减少了时间复杂度，提高了路径搜索的效率。4GlS数据模型和数据库设计路径选择系统的工作原理是输入交通系统中的起点和终点，能给出一条已规划的路径结果。在路径选择系统的设计与实现过程中需要使用合适的数据库来管理地理数据信息(GIS数据)能够提高GIS数据的计算速度，进一步提高路径选择的效率，使能够大道实时效果。本章的内容主要是介绍了GIS数据的一些相关内容和数据库管理设计内容，主要内容包括GIS数据的相关概念和内容知识、Oracle数据库选择的原因、GIS数据导入、GIS数据在数据库中的管理和维护等内容。4．1GIS数据模型建立数据模型是能够描述数据内在特征的工具，也是一门描述语言，是现实世界中对某种或某类特征的模拟、抽象、提取和组织。地理信息数据模型是模拟地理信息的形式化表示的工具。地理信息数据模型的建立为地理信息的表达和操作方法提供了具体的形式构架。GIS数据所描述的对象主要包括与地理位置有关的空间数据信息和非空间依赖性的属性方面的信息数据。4．1．1空间数据模型G1S空间数据与要描述的对象空间位置信息是相关的。目前，在GIS数据研究领域中学者们提出的空问数据模型主要有矢量数据模型、栅格数据模型、矢量．栅格一体化数据模型以及面向对象的数据模型等。现实空间世界外模式外模式外模式概念数据模型逻辑数据模型物理数据模型图4-1空间数据模型三个层次之间的相互关系4．1．2属性数据模型属性数据与要描述的对象的空间位置关系无关，他是GIS数据中空问数据的重要组成部分。例如，一条公路可以用实线或连续像素点或矢量表示的曲线实体，并可以用一定的颜色符号把GIS数据中要表达的内容完整的表达出来，这样道路的类型就可以用相应的符号表达出来。而道路的属性数据就由于道路的宽度、路面结构、修缮日期、水管电缆走向和位置、特殊交通规则标记以及某一时间的车流量等。这鞋数据都与道路实体的数据无关，是道路的附加数据，这些属性数据可以通过添加一个公共标识的符号与空问实体对应起来。当空间实体的空间数据模型与其对应的属性数据联系起来以后，就可以对其GIS数据进行操作和运算了。当然，根据实际情况，GIS数据应该提供灵活的数据查询和连接方法，以便经常增加、删除或修改其中属性数据的操作。4.2GlS数据的管理与组织为了对GIS数据方便操作，一般将GIS数据存储与数据库的使用结合在一起，这涉及到数据库和计算机的相关知识。注意GIS数据库管理主要原则:通用性原则、独立性原则、共享性原则、最小冗余度原则。OracleGIS数据将不同功能的机构或场所放在不同的图层当中，每个专题图层在数据库中都可以找到一一对应的数据库表，将与这个图层有关的空间及属性信息存储在数据库表中。4.3SpatiaI简介随着Oracle8i的推出，SpatialCartridge将升级为OracleSpatial。在新的数据库工具中，新的表示数据空间类型的抽系那个数据类型被提出，用(ADT)一SDOGEOMETRY来表示，(ADT)一SDOGEOMETRY可以将数据存储在一列中，OracleSpatial发展了新型的数据库管理方式，也对索引机制进行了一体化管理进行了优化，增加了缓冲区生成、二级过滤和叠加分析等新的数据处理过程。空间数据信息的存储都在SDO_GEOMETRY之中，对SDO_GEOMETRY的理解和帐户是使用OracleSpatial接口程序的关键步骤。SDO_GEOMETRY是按照openGIS的规则定义的一个对象，程序原始的创建方式如下表示:CREATETYPEsdo_geometryASOBJECT(SDO_GTYPENUMBER，SDO_SRIDNUMBER，SDO_POINTSDO_POINT_TYPE，SDO_ELEM_INFOMDSYS．SDO_ELEM_INFO_ARRAY，SDO_ORDINATESMDSYS．SDO_ORDINATE_ARRAY)；4．4空间数据向Oracle中的导入有两种不同的方法可以将MapInfo格式的空间数据信息导入到Oracle中：利用控件文件成批量的加载控件数据和利用MapInfo自带工具EasyLoader直接导入数据信息。下面介绍这两种方法怎样实现的数据自动导入。(1)利用工具EasyLoader直接将空问数据导入利用EasyLoader工具将MapInfo数据信息直接导入到数据库中是比较简单的导入方法。EasyLoader是MapInfo公司专门编写用于将MapInfo格式的数据导入到各种数库中的工具。(2)利用控制文件对数据批量加载导入每个0racle数据库都附带一个控制文件。该控制为二进制文件，能够记录数据的物理结构，主要内容包括：数据库的名称和属性、数据库的创建时间点、当前日志的序号、检验点信息等等，．ctl表示控制文件的扩展名。4．5GIS数据在OracIe中的存储在数据库中可以存储多种空问数据，根据实验的需要，本文只介绍与我们实验和研究内容相关的空间数据，包括道路数据，道路节点数据，分层路段数据，和多比例尺道路数据等。这些数据起初是MapInfo格式的数据，为了充分发挥OracleSpatial数据库的优势、提高计算效率、减少存储空问，我们将数据都储存在Oracle中。图4-2道路线型与节点在MapInfoProfessional中的显示结果4．6Oracle中GIS数据的访问0040(OracleObjectsforOLE)是Oracle公司提供快捷访问接口，这个程序接口是发基于Oracle数据库应用程序的底层的开发的，它的优点是速度快、支持Mirosoft编程语言、对Oracle数据库进行较强控制等。但同时也存在着一定缺点，如通用新不好，与其他数据库不兼容，但用它来访问Oracle数据库比用其它方法访问速度快很多。4.7Oracle中GlS数据的维护通过Oracle的EnterpriseManagerConsole打开数据库表road，即可进行数据库记录的添据库表road的删除。通过Oracle创建数据库表road；在Oracle数据库的SQLPlusWorksheet平台上输入代码：droptableroad；则数据库表被删除。通过Oracle的EnterpriseManagerConsole打开数据库表road，即可进行数据库记录的添加删除和修改。4．8本章小结本章介绍的是关于GIS数据模型与Oracle数据库管理设计的相关内容，主要包括以下几个方面：GIS数据模型的建立；GIS数据的管理与组织；数据管理设计基础知识；OracleSpatial简介；GIS数据向Oracle中的导入；GIS数据在Oracle中的存储；oracle中GIS数据的访问；Oracle中GIS数据的维护。数据库在整个程序系统设计与实现中起到非常重要的，可以说数据库选择和设计的好坏直接影响到系统的性能，和系统工作的效率，影响到路径选择的最优效率。5路径优化算法系统实现5．1电子地图制作从宏观来说，制作以路径优化为目的的专用电子地图时要遵循的原则是：以诱导为中心，以为路径优化算法服务为目的，忽略与路径选择无关的路网要素，重点描述对路径选择相关的内容，以最小的代价来表达及存储路网。具体说来，路径优化问题对电子地图信息的需求有以下几点：每条道路的准确位置与坐标；道路的静态属性：道路名称、道路等级、道路宽度、车道数、道路长度、路面状况；道路与交通相关的静态信息：速度限制信息、转弯限制信息、单行线信息；特殊道路特征的抽象与表示：主要指各种形式交叉口、立交桥等等；道路周围重要建筑物的信息。5．2仿真结果与分析本文的电子地图图层数据来源于南昌市的电子地图，截取了其中的一部分，其结点图层由九个结点组成且每个结点都具有结点权重。分别利用Dijkstra，分层A*算法，基于速度模式的动态分层A*算法计算出最优路径并绘制计算出的路径，其仿真效果展示如下。图5-1基于Dijkstra算法的最优路径图5-2基于分层A*算法最优路径图5-1的起始点是“中国移动”，目的地是“人民公园”，依据Dijkstra算法进行的路径优化，从图中可以看出，只考虑距离最短这一个因素，没有考虑道路等级、交通拥堵等复杂因素。图5-2的出发地点和目标地点一样，是按照分层A*算法进行路径优化的，道路被分成一级、二级、三级以及高架几种层次，图中可以