智能交通系统中最优路径的算法研究

运用图论中有向加权图的相关知识,综合道路交通的各种因素,对智能交通系统中最优路径实现提出一个距离模型,在此模型上利用邻接矩阵和迭代算法生成了一种通用的最优路径求解算法。并对实际应用中的问题,给出了在M apinfo环境下建立道路拓扑结构的方法,有效地解决了各种路况下的路径寻优问题。     

一种考虑交通限制信息的道路网络模型

随着城市交通网络的发展,实际道路中的交通限制信息使得道路网络中的最优路径规划变得更加复杂,针对这一问题,笔者讨论了一种考虑交通限制信息的道路网络模型,并详细阐述了该模型的存储方法及各种常见交通限制信息的解决方案,然后给出了利用此模型求解最优路径的改进的Diiktra算法描述。最后,笔者根据北京市道路数据建立道路网络,通过实际数据进行验证,实验结果表明,该模型及算法能满足实际道路网络的最优路径分析的需要,具有一定的应用价值。     

重庆市交通控制仿真系统的设计与实现

针对重庆市常见的交通控制措施,用VC设计和开发了一套可以模拟道路通断、道路通行方向、交叉口转向规则等交通控制措施并能分析它们对道路通畅状况影响的交通仿真系统。介绍了系统的需求分析、总体设计、消息平台搭建、道路和交叉口设计、车辆碰撞检测及处理、车辆在交叉口的路径决策算法、道路畅通状态评价指标算法等问题。     

隐马尔可夫模型的道路拥堵时间预测

道路车辆拥堵问题导致交通事故增加,降低了居民的出行效率,长时间的道路拥堵更是加重了环境污染,造成国家经济损失等诸多问题。为缓解城市道路交通的拥堵问题,提高出行效率,基于隐马尔可夫模型,针对已有道路拥堵时间数据进行采集与建模,并对该隐马尔可夫模型进行训练,通过算法计算与分析,预测未来一段时间的道路拥堵情况,为人们的出行提供拥堵时间预测,而后提出不同时段通过道路用时最短的最优路径。对韦尔奇算法进行改进,在原算法基础上增加考虑前[n]时刻状态。利用改进型韦尔奇算法,使得训练集参数更精确,达到预测精度更高的目的。实验结果表明,预测数据结果与真实数据相比,误差不超过3%,该模型预测结果具有较高准确性。     

限制搜索区域的分层路径规划算法

依据城市路网独特的空间分布特性及不同道路等级特性,提出一种限制搜索区域的分层路径规划算法．与文献[2]相比,文中算法新增了对路网空间分布特性的利用,引入了限制搜索区域的搜索机制．结合路径规划算法在实时车辆导航系统中的实际应用,给出该算法的一个应用实例,通过对实验结果的分析验证了其有效性．     

基于邻接点算法的Dijkstra优化研究

在将城市道路实体抽象为图论理论中的网络图,对道路和站点数据结构进行定义的基础上,利用邻接点算法对Dijkstra算法进行改进,通过构建邻接矩阵和初始判断矩阵,得出网络图中任意两点间的最短路径.当点数越多时改进算法的效率就显现出来,结果表明邻接点算法在一定程度上既节省了存储空间,又提高了运算效率.     

车辆行驶最优路径优化算法设计

针对实际交通路网的特点,对道路网络模型、路网数据库的结构建设、最优路径优化算法等问题进行了研究.建立了体现城市道路交通的方向性及交叉口延误和限制的新城市路网模型,该模型利用交叉口、路段等基本构成要素描述道路网络,利用节点--弧段联合结构描述路段特性,再用图论中的有向图思想将路网抽象成数学模型描述;基于经典高效的狄杰斯特拉(Dijkstra)算法,设计了一种可应用于实际道路网络中的最优路径算法--改进的狄杰斯特拉算法,采用该算法可求解带有转向延误和限制的最优路径问题.     

交通路径诱导系统中最优路径选取研究与仿真

研究交通路径诱导系统优化问题。复杂路况高峰时多条道路车辆同时汇聚造成交通拥塞,但是拥塞信息的实时变化存在高度的非线性和突变性。传统的交通路径诱导系统,仅仅是针对最短距离进行路径选取,非线性和突变性拥堵信息不能在模型中得到反应,一旦拥堵发生,会降低交通路径诱导的效率。提出了一种基于自适应t分布变异人工鱼群算法的交通路径诱导系统。引入t分布变异算子将高斯变异和柯西变异的优点结合起来,提取交通路径拥塞参数,并将其反馈到控制端,使用AFSA方式进行迭代处理,将迭代次数作为t分布的自由度参数,从而提高了交通诱导的效率。实验证明,鱼群算法提高了交通路径诱导的性能,避免了交通拥塞的缺陷。     

一类标准矩形网络节点间最短路径的求解方法

针对常见的交通道路最短路径问题, 提出标准矩形网络的概念, 分析其节点间最短路径的性质, 并在此基础上给出一种新颖的最短路径求解算法. 该算法利用标准矩形网络的几何性质, 简化了搜索方向和步长的判断, 同时指出常见的交通道路网络一般均可以整体或部分化为标准矩形网络. 与常见的求取最短路径的Dijkstra、Floyd、ACO、A* 等算法进行仿真实验比较, 实验结果表明, 对于大规模标准矩形道路网络, 所提出算法具有更好的寻优精度、稳定性和寻优速度.

     

基于LCC的测试程序控制流路径子集生成算法

针对路径覆盖测试技术中如何计算被测试程序的有效控制流路径子集的关键性问题,提出一种利用LCC编译器的前端结果来生成基于一次循环策略的测试程序控制流路径子集的算法。该算法通过引入邻接矩阵并借助自定义的堆栈数据结构来完成控制流路径子集的生成。通过实验程序对算法进行检验,结果表明,该方法能高效准确地计算出待测源程序片的控制流路径子集。     

Dijkstra算法在停车诱导系统中的应用

路径诱导是停车诱导系统中需要解决的关键问题,而路径诱导的本质就是求最短路径,Dijkstra算法可以很好地求解最短路径.传统Dijkstra算法采用邻接矩阵作为存储结构,算法的时间复杂度为O（n2）,存在搜索速度慢和浪费空间的缺点.为此,对传统Dijkstra算法进行了改进,采用邻接多重表作为存储结构,采用堆排序法的思想来寻找权值最小的顶点,算法的时间复杂度为O（nlog2n）.用改进后的算法在实际地图中进行仿真实验,结果表明,改进后的算法能更快、更有效率地找到两点间的最短路径.     

障碍物存在的最短路径算法及其在车载导航中的应用

车载导航系统中的动态路线选择是其必备功能之一,文中分析了经典Dijkstra算法存在的不足,并在此基础上,采用优化的邻接矩阵存储结构,讨论了有障碍物存在情况下的最短路径问题。同时用Vc＋＋与Mapx实现了有障碍物存在的动态最短路径算法。实验结果表明,该算法能有效求出有障碍物存在时的最短路径。     

最短路径算法在配电网抢修中的应用

现有的最短路径搜索算法如Dijkstra算法或椭圆限制的Dijkstra算法等计算效率较低,有待进一步改进.在分析已有Dijkstra算法的基础上,提出了快速最短路径优化算法.根据城市的交通状况对交通网络图的边值赋予不同的权值可实现最优路径搜寻,以逆邻接表结构为基础,采用矩形限制搜索范围来优化Dijkstra算法.通过对算法的运行结果进行对比,证明了本算法的灵活性和可靠性.     

联锁进路敌对信号的搜索算法设计

分析了铁路信号计算机联锁系统中进路敌对信号的定义及处理生成问题,借助联锁进路表阐述了敌对信号与进路搜索之间的约束关系;结合站场有向图和邻接矩阵,利用数学图论知识,提出了一种进路敌信号搜索算法和k步进路扩散生成算法,给出了算法步骤流程并通过类C语言实现算法全过程.算法在实际工程项目中进行了应用,并对实际的站场实例进行了算法仿真模拟,提供了部分铁路站场进路和敌对信号实例数据.     

基于CSR存储的三维网格最短路径算法

论文针对数据组织结构导致Dijkstra算法的存储空间、邻接关系检索效率等关键问题,介绍了相关研究工作。并针对三维网格模型的邻接关系为稀疏图这一要点,基于三维网格模型的CSR存储结构,给出了记录Dijkstra最短路径的算法。该文算法返回了最短路径长度,记录最短路径上点集,充分利用了中间计算结果。     

业务量矩阵估算算法的设计与实现

随着互联网的飞速发展和网络业务的日趋丰富，网络规模和业务量急速增长，而目前的Internet不能完全满足网络各方面的应用要求，因此实施流量工程显得十分重要。主要研究流量工程中业务量矩阵的估算算法。实验系统以Network Simulator 2作为网络拓扑结构和数据的生成环境及后期算法验证环境，根据现有的理论和实验依据搭建实验框架，运用Java语言实现离线的业务量矩阵的估算算法，最后通过大量的仿真实验验证、比较、改进算法的有效性，为进一步的研究提供实验数据支持。     

基于等效网络的车辆导航系统路线规划算法

在实际交通行为中,不可避免地存在着交叉口时间延迟,而且交通管制信息如交叉口转向限制也普遍存在,这些交通特征使得常规的最短路算法难以满足车辆导航系统路线规划的要求。提出基于“节点-弧段-特征”的数据结构存储方案,能够完整描述路网的平面拓扑和交通特征属性;针对具有交叉口转向限制和交叉口延迟等特征的交通网络,首先采用对偶图方法构造等效网络,在等效网络中采用常规的最短路算法计算最优路线,然后将它转化为原道路网中的行车路线。试验证明这种方法能够有效解决包含交通特征的车辆导航系统路线规划问题.     

Design of multi-path data routing algorithm based on network reliability

Data routing through an interconnected network is important and this paper addresses the design of a multi-path data routing algorithm based on network reliability. Generally, multiple routes for a given source–terminal pair exist in a data network and the best possible route based on network metrics like hop-count, delay, traffic, queue, etc. is selected by a routing algorithm. Since network reliability incorporates all these metrics, the routing decision based on reliability seems to be the best possible option and a distributed routing algorithm based on the source–terminal (s–t) path reliability has been proposed in this work. Each node in the proposed routing generates an adjacency matrix of a network graph by periodically exchanging connection information with the adjacent nodes and selects multiple routes based on reliability of the paths. We propose an implementation of a two-path routing algorithm that instead of one includes two next-hop nodes in each node’s routing table. An example is given for further illustration of the proposed algorithm.     

遗传算法在路径规划上的应用

为了满足出行者能高效快捷地到达目的地, 需要找到一条综合权值最优的出行路径, 再在其上设置指路标志对目的地进行指引. 基于此, 本文首先根据路网的特点, 对交通路网模型进行表述; 接着阐述了遗传算法的基本概念和算法思想, 并以行驶路程和交叉口个数作为出行者路径选择的因素, 定义了行驶路程和交叉口个数综合指标最小的路径为最优路径; 最后, 以广州大学城中山大学为例, 在明确起终点的情况下, 利用遗传算法的方法找到了去往中山大学的最优路径, 验证了遗传算法在路径规划上的有效性.     

公交线路查询算法

公共交通不仅是衡量城市现代化程度的重要标志也是解决交通拥堵问题的途径. 而公交线路查询系统的关键技术是公交线路查询算法, 它对提高公交资源的利用率有着重要的意义. 总结了国内外城市公交最优路径算法并在此基础上分析了高效运行城市公交系统的条件和影响因素. 介绍了最短路径问题及Dijkstra算法及其在查询系统应用中的弊端. 然后提出了基于换乘最小的广度优先算法的数学模型, 给出了算法的实现, 并以银川市公共交通公司的公交部分数据为基础, 完成了公交信息查询系统的设计与开发.