交通线路选择软件的设计与实现毕业设计(编辑修改稿)

交通线路选择软件的设计与实现毕业设计(编辑修改稿)内容摘要：

探测到周围的空洞，并利用右手法则沿着空洞周围的节点传输数据来解决这类问题。 该方法的优点在于米面了在节点信息中存储建立和维护路由表信息，只需要利用相邻节点进行路径选取即可进行，几乎是不需要任何协议辅助；并且利用欧氏距离最小的方法进行路由，数据传输的延时最小；并能够保证只要网络路径不被破坏，数据一定能到传送到目标节点中去。 但该算法存在这一定的缺点，当网络中的某节点与源点集中在两个区域时，由于通信的不平衡能够导致部分节点无效，从而是网络的连通性遭到破坏；另一方面是该方法需要 GPS 定位系统的辅助来计算几点的位置信息。 GPSR 中贪婪转发算法能够正常转发数据的前提是：目的结点的位置都包含于每个数据分组中，每个结点都有邻居结点列表信息以及邻居结点和本结点的位置信息。 在实际的路线选取过程中，我们将路口与上述的结点对用。 在电子地图中，每个路口都有坐标位置和列表信息，那么在算法程序中我们首先要做的是让每个结点都包含一条邻居结点链表，并将结点号与位置信息关联起来。 2． 2 图论简介 图论 (Graph Theory)是组合数学的一个分支，它源于瑞士数学家欧(Euler)1736 年对于著名的哥尼斯堡七桥问题的解决，从而使欧拉成为了图论 的创始人。 图论是数学学科当中比较年轻的一个分支。 在图论被提出后的两百年中，图论的发展相对缓慢，但自从图论与大量的实际问题相结合，在物理学、化学、信息论、运筹学、计算机科学、控制论、社会科学，经济管理等各种学科中找到了更广泛的应用，使图论在近几十年来得到了快速的的发展。 目前在图论领域中形成了两个不同的方向：抽象图论和最优化图论。 前者主要研究图的性质，后者主要讨论与图有关的优化问题。 最优化图论既可以算作图论中的一个研究方向，也可以看作运筹学中最优化理论的组成部分。 图论中的图是由若干节点以及两节点之间的连线所构成 的图形，图论的研究对象是图，这种图形不考虑点的大小、形状和边的形状、长度、大小以及边与边的角度等几何问武汉纺织大学 20xx 届毕业设计论文 6 题，而主要表达的是点点之间通过线的连通关系，通常可以用来描述某些事物之间的相互关系，即用点来代表事件发生，用连接两点的边表示两个事件之间的关系。 因此图论中的图能够代表多种含义，因此图论在诸多领域都有着非常广泛的应用。 2. 2. 1 图的概念 无向图是指有序三元组 (V， E,F)中边没有方向，其中集合 y 被称为结点集，y中的元素称为结点：集合 E被称为边集， E中的元素被称为边；而函数是边集E到无序结点对儿所构成的 集合的一个映射关系，称之为关联函数。 如果 P是一条边“， 39。 ，两个结点，且满足 F(E)=uv，那么就可称为 e连接：并且称Ⅳ， y为 E 的端点。 每条边与边两端的节点是相互关联的因此称为相互关联，与同一条边相关联的节点或者与同一个节点相互关联的边称为相邻的节点或者相邻的边，具有相同两个节点的边称为重合边或者是平行边，两个节点相同的边组成环，简单图就是没有环和重边的图。 每个结点度数相同的简单图称为正则图，最大度与最小度恰好相差 1 的简单图被称为几乎正则图。 图的结点的个数称为图的阶。 2． 2． 2 图的表示 由点集合 V 和点与 点之间的连线的集合 E 所组成的集合对 (V， E)可以构成图，用 G(V,E)来表示。 图 G(V， E)由其结点与边之间的关系确定，且是唯一的。 也由它的结点对儿之间的邻接关系唯一确定。 V中的元素为结点， E中的元素为边。 节点集合 V 与边集合 E 均为有限的图称为有限图。 图 21 图的结构 武汉纺织大学 20xx 届毕业设计论文 7 2． 2． 3 图的存储 (1)邻接表 邻接表结构： 图 22 邻接表结构表节点和头结点 邻接表以一种以链式存储结构所构成的图。 在邻接表中，图中的每个节点都会有一个单链表与之对应，第 i 个单链表中的结点数据表示依附于结点 v。 三个域构成了每个节点，其中结点的邻接点域的数值表示与结点 相邻节点在图中的具体位置，结点的链域将指示下一条边的结点，结点数据域存储的是图中边的信息，如权值、方向等。 每个链表都会有一个表头结点与之对应，在表头结点中，设有存储结点 q 的各个域及与该信息有关的相关数据域。 这些表头结点存储数据的形式通常是顺序存储的，这样存储方式便于随即访问任何一个节点的 链表信息。 (2)十字链表 十字链表针对有向图的另一种存储结构。 可以看成是一种新的链表，该链表将有向图的邻接表和逆邻接表结合在一起。 在十字链表中，每一条边都有一个节点与之对应，每一个节点也有一个节点与之对应。 2． 3 本章小结 本章对最优路径算法和图论的相关理论知识进行了简单概述。 对几个经典的最优路径选择算法进行了介绍，如 Floyd 算法、 Dijkstra 算法、 GPSR 算法，并分析了他们的优点和不足。 图论在近几十年来得到了飞速的发展，尤其是与物理学、化学理论、信息理论、运筹学、计算机理论、控制论、社会科学等 不同领域和学科的结合方面。 adfvex nextarc info data firstarc 武汉纺织大学 20xx 届毕业设计论文 8 3 最优路径 最优路径选择和交通系统优化的目的就是是交通流均衡化，合理的在交通系统中分配，提高交通运输效率。 因此，应当首先考虑交通流的特征。 一般地，交通网络有如下特点： (1)线性分布，交通网络结构在空问分布中一般呈现线性特征，因此交通网络建模可以依靠图论的相关理论和知识； (2)网络分布，交通网络是一个负载的网络拓扑结构，连通性好，结构复杂： (3)分段分布，交通系统中不同路段的特征一般不同，表现为空间的差异性，且同一路段的不同时间的交通网络特征也可能不同，表现为时间差异性； (4)动态性特点，交通网络上交通状况不是一层不变的，随时间的变化而变化，失意 是 时变系统： (5)车辆行驶的主观性，交通网络不同于其它网络，交通网络的主体可以自主的选择交通路径，行驶时间和行驶路线等是他的一个最显著特征。 以图的理论为研究基础研究交通道路模型，采用改进的方法使得道路的车道信息加入到节点和边的信息中。 以完整的交通道路作为建模的基本单元，但在交通应用当中，交通特征的变化在交通系统的具体应用当中经常和车道关联密切。 在同一一条道路上不同方向的车道具有不同的交通特性，如交通规则变化、交通量变化等。 3． 1 建立城市交通模型 利用图论 的相关理论和知识，对图中的节点和边设法加入车道信息用于模拟就哀痛系统。 以完整的交通道路网络作为模型建立对象，只需要对道路中的相关数据和参数进行显示和计算，但在实际的交通道路当中，交通特征是实时变化的，这与交通道路模型密不可分。 首先，在同一条道路上不同的车道在不同的行驶方向的交通特征可能不同，如交通量变化和交通规则等。 例如：在早晚的上下班的高峰区段，进出同一区域的同一条道路在不同方向表现的车流量是明显不同的，交通拥堵现象大多数情况下是发生在某条车道的单向车道上。 其次， 不同方向的 车道由于具有不同的拓扑关系，因此交通规则有可能不同。 武汉纺织大学 20xx 届毕业设计论文 9 由于在节点图层和路段图层中分别存储的点、线图元是分别独立的，两个图层问不想关联。 为建立点线各个元素之间的空间拓扑关系，使他们构成有机整体，需要分别在存储点线信息的两张表文件中扩展一定长度的字段，用对象的属性字段之问的相互联系来建立交通网络图的拓扑关系，这样就建立了交通网络系统的有机整体即他们的拓扑关系结构图。 3． 1． 1 道路节点模型 可以将交通网络抽象成一个有向图，图中的边带有一定的权值，但这个抽象的有向图如何建立起来需要视具体的应用环境而定。 在实际情 况中人民出行是从一个地方到另一个地方，这种不能简单的归结在图中从一个节点到另一个节点的转移，实际情况的交通网络运行是非常复杂的，所以不能简单的把某一个具体的地方当成是图中的某个节点，把道路信息抽象成图中带有权值的边，而是要将具体的地址信息抽象为节点以及其附属信息并加入到交通网络系统中。 交通地址的交叉口所抽象的节点和将具体地址被抽象成图中的节点是不相等价的，需要考虑实际情况，因此交通节点的阻抗值应该视具体情况而定，而表示地名的节点的阻抗值可以视为零。 3． 1． 2 交叉口和道路模型 将道路的数据模型抽象为一条 线，因此选择道路中问的中心线表示道路数据模型，这种建模方法不能很好的描述交通道路的属性信息，丢失很多信息量。 实际生活中的道路不能简单的抽象为一条直线，因为有些道路存在很多车道，每个车道的属性信息不尽相同，多车道的交通道路属性信息较为复杂。 在 GPS进行导航式，需要考虑到的交通网络信息往往与车道信息密切相关。 3． 2 交通模型数据存储 3． 2． 1 数据预处理 在实际应用中，一般将交通网络模型用矢量化的数据地图表示，为了建立交通网络可使用的数据模型，需要对原始道路构成的交通网络矢量图进行优化武汉纺织大学 20xx 届毕业设计论文 10 和预处理，建立相应的拓 扑关系图谱。 矢量图形的预处理的一般包括： (1)对原始道路图像进行拓扑关系检查并进行剪断处理，保证地图中不存在两条道路相交的情况，将原来的道路拆分成多条道路的集合： (2)为每一条剪断后的道路建立拓扑关系，并定义其属性特征，如道路名称、道路长度、交通流等特征； (3)将地图经过上述处理之后生成拓扑文件。 3． 2． 2 交通路径模型建立与数据存储 （ 1）交通路径模型的建立 最短路径选择的前提是对交通系统创建合适的模型。 按照上述方法对原始的交通道路进行预处理之后就可以确定道路之间的拓扑关系，进而可以建立以道路拓扑 关系为基准的交通系统模型，拓扑关系中包括线性实体之间的模型，线性实体与节点之问的模型，节点与节点之间的模型，以及他们的连通性等。 使用图中的节点表示交通系统的的较差路径，道路交叉即是图中的节点，两个节点之间的道路在图中用弧表示，就是图的边，路段的长度以及消耗时问等信息则为边带有的权值。 在本文中，交通路径系统的模型由两部分图层所构成，一部分是节点图层，一部分是交通道路图层。 节点图层表示交通交叉口或者道路的起始点或终止点，用点对象来表示，路段图层存储这连接各个节点的交通路径以及他们的属性信息，用线对象表示。 在两图 层中分别存储的节点信息和路段信息分别是独立的，下一步就是建立两个图层之问的拓扑联系，使得两个图层构成有机整体，形成交通路径系统的完整性，需要用两个图层所对应的两张表中的文件扩展出一定的字段，用对象的属性信息来代表两个图层之间的拓扑关系，这样就构成了交通路径模型的整体拓扑关系结构图。 交通路径的限制信息是交通导航中需要终点考虑的因素，比如由于施工、交通事故、速度限制、恶劣天气造成的交通限制等，实际的道路中交通限制信息十分复杂，而且随时发生变化。 本文考虑的交通限制信息只考虑了禁止通行的信息。 如果某条道路出现禁止 通行的限制信息，用节点的交通限制信息来表示。 武汉纺织大学 20xx 届毕业设计论文 11 （ 2）数据存储 一般地，在计算机中大多采用利。