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

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

城市交通最优路径规划仿真研究

研究城市交通最优路径规划问题,由于城市交通网复杂,增加了规划的难度,传统的最优路径规划算法没有考虑城市道路网络中的交通限制问题,更忽略了车辆在道路交叉口转向延误的时间,不符合城市交通的实际情况.为了解决上述问题.首先建立了一个城市路网交通模璎.然后运用线性规划方法建立最优路径规划问题的线性规划模型.最后采用桶排序算法对狄杰斯特拉算法进行优化,得到一个新的最优路径规划算法,对线性规划模型进行求解.仿真结果证明,利用算法搜索得到的最优路径更加符合实际的路网情况,为设计提供了理论依据.     

一种适合移动导航系统的路网数据描述与分析方法

针对移动导航系统的特点,以及移动导航系统对道路网络描述与分析的新要求,提出了一种面向移动导航系统道路网络的网络分析模型和数据描述模型。在网络分析模型中,将路段通行方向和节点转弯限制很好地融合到有向图中。在数据描述模型中,对信息量较大的节点转弯限制,探讨了一种二进制编码方案,提高了数据传输和处理的效率。该模型在上海市交通信息网格及移动导航系统中取得了良好的实施效果。     

基于Dijkstra算法的动态交通诱导技术及仿真

研究车辆行驶过程中的路径动态诱导问题,针对目前交通导航系统不能实时动态规划行驶路线的不足,结合自主研发的车载终端装置,通过对Dijkstra算法的改进及优化,提出了一个可应用于交通诱导过程的动态实时最优路径算法;基于该路径优化算法,车载终端装置可以通过接受交通控制中心的实时道路信息,不断调整车辆的行驶路线,最终实现行驶路线的全程动态优化;仿真实例证明:在实时交通信息的引导下,动态交通诱导技术保证了行驶路线的全程优化.     

基于GIS的最优路径自适应规划算法

基于GIS的最优路径自适应规划算法是公交交通的核心技术。该文研究公共交通网络的特性和路径自适应规划算法的需求特点，构建了公共交通网络的几何模型和数据模型，设计了最优路径自适应规划算法且分析了复杂度，完成了基于GIS的客户端图形化显示，并结合实际公交网络进行了算法的验证，实现了算法的实际应用。     

一种博弈竞争选择的异构无线网络最优接入策略

为了提高异构无线网络的信息传输速率和网络利用率,减少网络的系统开销,提出一种博弈竞争选择的异构无线网络最优接入策略算法,该算法在考虑了实际带宽的情况下引入了代价因子,并得到最大化的网络信息传输速率.在接入网络的选择上,通过采用基于博弈模型和最优接入策略的博弈模型,通过多项服务质量指标来计算综合竞争值,从而通过竞争值大小来选择最优的接入网络.实验仿真及数据结果表明,相比另外两种异构接入网络的选择算法,该算法具有带宽资源利用率和网络信息传输速率更高的优势.     

无线Ad Hoc网络中增强安全性的多路径路由算法

针对无线ad hoc网络的数据安全性问题,提出了一种增强安全性的多路径路由算法．该算法通过目标节点发送检测数据包的机制,动态维护多路径路由信息的有效性．源节点则根据收到检测包的信息自适应地更新当前的最优传输路径,充分利用路由寻找及维护过程中的信息建立多条可用路径,提供最优的路由方案,并增强了无线ad hoc网络数据传输的安全性．仿真结果表明此算法的数据传输安全性达到了合理的水平．     

一种基于道路网络层次拓扑结构的分层路径规划算法

鉴于平面最短路径算法应用于大规模网络规划中的效率不高,而分层算法引入"分而治之"策略,则能有效解决此难题。为了利用分层算法进行路径规划,首先研究了分层算法的数据基础——道路网络层次拓扑结构,其涉及基于道路等级的路网分层抽象、道路数据分区组织、以区域为单位的路网层次拓扑关系模型;接着提出了一种适用于LBS(基于位置的服务)的分层路径规划算法。该算法先通过距离值判断是否切换到上一层;然后利用启发式A*算法搜索入口和出口;最后使用双向策略搜索层内两点之间的最短路径。利用现实道路网络进行的实验分析结果表明,该算法能从本质上提高大规模网络中路径规划的效率。     

基于道路网络的约束聚类

聚类法是最重要的空间数据分析方法之一。在大多数真实的应用中,对受限于网络空间的数据访问和分析更有意义（如道路网络上对象的分析）。目前已有一些道路网络聚类方法,但都是基于理想的抽象空间,没有考虑现实存在的约束条件（如交通限制信息）,因此不能直接应用到现实环境中。本文提出了带约束条件的道路网络模型,扩展了已有的聚类算法。算法的实验结果表明,算法对真实的道路网络中的对象聚类是高效的。     

基于分层的改进A＊算法在路径规划中的应用

智能交通中的路径诱导系统能够极大地提高人们的出行效率与出行体验。经典A＊算法只注重搜索精度而忽略了搜索效率,在城市道路网络分层的基础上,对高层道路使用的A＊算法进行了改进,对于道路网络中的不同节点,设置估价函数具有不同的权值,同时给定权值的一个上下限阈值,以平衡算法的搜索效率与搜索精度。实验表明,得到的最短路径虽然不是常规的距离最短却是实际行驶时间最优的。     

动态交通网络中最优路径查找算法*

在真实交通网络中,可能出现某高速公路在某一时刻内通过的车辆过多,从而改变了该时刻道路的即时速度,这就需要对道路的交通流量进行监控。针对这一问题,通过建立交通网络的速度模式库,根据道路可达速度的变化更新速度模式。基于A*算法与速度模式库,提出针对动态交通网络的最短路径查询算法。采用真实数据集对算法进行测试,结果表明,应用该方法能够有效地解决在速度模式发生变化的情况下最优路径的查找,使交通网络中的最优路径查询更为准确有效。     

一种面向城市复杂路网最短路径提取的定向收敛算法*

为提高城市复杂路网最短路径提取的效率,针对路网数据量大、结构密集等特点,研究了路网节点之间最短路径的分布特征,通过引入收敛点方式,设计并实现了一种面向复杂路网最短路径快速提取的定向收敛算法。为检验该算法的有效性,利用某城市道路交通网络进行了实验和分析,并与Dijsktra算法、A*算法等比较,证实了该算法能够提高路径搜索效率,且随着城市路网规模的扩大定向收敛算法的高效性将愈加明显。     

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

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

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

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

     

基于数据库的城市道路中最短路径搜索

根据城市交通路网建设的实际 ,研究了描述城市交通网络图的城市道路数据库的组织结构 ,在此数据结构的基础上依靠 GIS技术的支持 ,采集了大量具体道路信息 ,采用 Dijkstra算法实现了快速最短路径搜索。根据城市的交通状况对交通网络图的边值赋予不同的权值可实现最优路径搜寻 ,给出了一个搜索实例——一个包含 6 1个交通路口的最短路径搜索结果的搜索时间约为 1.1s     

基于道路风险评估的城市路网实时路径选择

为了缓解城市交通拥堵、避免交通事故的发生,城市路网的路径选择一直以来是一个热门的研究课题.随着边缘计算和车辆智能终端技术的发展,城市路网中的行驶车辆从自组织网络朝着车联网(Internet of vehicles,IoV)范式过渡,这使得车辆路径选择问题从基于静态历史交通数据的计算向实时交通信息计算转变.在城市路网路径选择问题上,众多学者的研究主要聚焦如何提高出行效率,减少出行时间等.然而这些研究并没有考虑所选路径是否存在风险等问题.基于以上问题,首次构造了一个基于边缘计算技术的道路风险实时评估模型(real-time road risk assessment model based on edge computing, R³A-EC),并提出基于该模型的城市路网实时路径选择方法(real-time route selection method based on risk assessment, R²S-RA). R3A-EC模型利用边缘计算技术的低延迟,高可靠性等特点对城市道路进行实时风险评估,并利用最小风险贝叶斯决策验证道路是否存在风险问...     

基于组件的电子地图显示软件设计

设计了基于组件的电子地图显示软件,实现了电子地图基本操作功能及路径规划功能。可以在软件中实现地图放大、缩小、漫游、测距、图层控制、鹰眼视图、全图显示、坐标显示等功能,作为电子导航显示软件,利用DOkstra算法可以在地图中求解任意两点之间最短距离,利用蚁群算法对道路进行了路径规划,在有结点约束的条件下求解一条较优路径。因蚁群算法求解路径规划问题存在求解速度慢问题,利用Cilk＋＋并行模型对蚁群算法进行了并行化。     

超限车辆的最短路径在MAPGIS中的实现

最短路问题是图论中的基本问题,也是交通网络分析中的一个重要问题.改进了经典的Dijkstra算法,使之适合于有车辆负载约束的最短路问题,并讨论了如何利用MAPGIS实现超限车辆的最短路径分析,将图论的算法和地理图形信息有机结合,从而为公路管理的可视化决策提供了一个参考.     

"GPS最短路径"搜索研究与实施

“最短路径”是网络分析中的重要问题,也是许多应用领域中最优选择的基础.“车载GPS（Global PositioningSystem）最短路径分析”在汽车导航系统及城市应急系统中有着广泛的应用前景.针对城市道路网的特点,对基于城市道路网的最短路径分析的关键技术进行了研究和验证.提出了一种实用、高效的最短路径分析解决方案,并在此基础上实现了一个最短路径分析、最短路径算法的高效实现关键技术.测试结果表明,该系统的响应速度和分析效率能够满足车载GPS系统的应用需求.     

A Hybrid Genetic and Ant Colony Algorithm for Finding the Shortest Path in Dynamic Traffic Networks

Solving the dynamic shortest path problem has become important in the development of intelligent transportation systems due to the increasing use of this technology in supplying accurate traffic information. This paper focuses on the problem of finding the dynamic shortest path from a single source to a destination in a given traffic network. The goal of our studies is to develop an algorithm to optimize the journey time for the traveler when traffic conditions are in a state of dynamic change. In this paper, the models of the dynamic traffic network and the dynamic shortest path were investigated. A novel dynamic shortest path algorithm based on hybridizing genetic and ant colony algorithms was developed, and some improvements in the algorithm were made according to the nature of the dynamic traffic network. The performance of the hybrid algorithm was demonstrated through an experiment on a real traffic network. The experimental results proved that the algorithm proposed in this paper could effectively find the optimum path in a dynamic traffic network. This algorithm may be useful for vehicle navigation in intelligent transportation systems.