基于道路信息交互的最短路径算法研究

根据城市交通状况的实际,研究了描述城市交通网络图的城市道路信息集成数据库的组织结构.在此数据结构的基础上依靠GIS技术的支持,采集了大量具体道路信息,在不同的时段,根据城市的交通状况动态的对交通网络图的边值賦予不同的权值,通过计算过程中数据的动态调整,利用Dijkstra算法实现了动态最短路径搜寻.     

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

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

改进的Dijkstra算法在GIS路径规划中的应用

最短路径算法是计算机科学与地理信息科学等领域研究的热点。文章讨论了一种改进的Dijkstra算法，利用本算法根据用户给出的起始结点、必经点序列和目标结点在GIS的交通层网络图基础上进行路径规划，生成满足一定约束条件的最短路径。实际应用分析表明，改进的Dijkstra算法在提高网络系统空间分析效率方面是可行的。     

城市交通智能查询系统的研究与设计

本文介绍了一个利用自然语言处理技术进行城市交通查询的系统。该系统采用正向搜索反向匹配算法进行分词提取出起点和终点,综合采用最少换乘次数算法和最短路径算法,使城市交通查询更加人性化、智能化。     

基于蚁群算法的最短路径问题的研究和应用

求解交通路网中两点间的最短路径是智能交通系统中一个重要的功能,为了更为准确快速的找到最优解,本文尝试采用带有方向引导信息的蚁群算法来实现此功能。实验结果表明,该方法能较为准确的找到交通路网中两点间最短路径的最优解,搜索效率高、搜索最优解的能力强,对于智能交通系统中最短路径搜索的功能实现问题有一定的参考价值和实际意义。     

基于区域限定模型的最短路径算法研究

研究地理信息系统中最短路径问题,提高最短路径的搜索速率。针对地理信息系统GIS中最短路径是根据路径权值最小原则选取的,需要逐个遍历系统中所有路径,传统的Di jkstra算法逐个比较所有路径的权值计算量大,不能快速找出最短路径的问题。提出一种基于区域限定模型的算法选取最短路径,采用区域限定模型减少参与计算的路径信息数目,并在此基础上使用启发式搜索策略快速找到最短路径,这样就避免了对系统中所有路径信息遍历带来的计算量大、搜索速率不高的问题。实验证明,改进方法能够快速将最短路径搜索出来,满足地理信息系统实时性的要求,取得了满意的结果。     

改进Dijkstra算法在GIS导航应用中最短路径搜索研究

研究GIS在电子导航系统应用中的最短路径搜索效率问题。在电子导航系统中对最短路径的搜索效率要求很高。随着城市发展交通线路剧增,传统的基于Dijkstra算法的GIS导航系统不能适应日益复杂的交通线路,存在最短路径搜索效率过低的问题。考虑到GIS空间分布的特性,提出了改进的Dijkstra算法用以解决GIS导航中的最短路径搜索问题。改进算法不仅避免了传统Dijkstra算法逐个节点遍历搜索,而且根据方向优先特性缩小搜索范围,大大减少了搜索工作量,并通过改变搜索节点存储的数据结构提高了最短路径的搜索效率。实验表明,这种改进算法较之传统算法能够有效提高最短路径的搜索效率,满足了电子导航系统对最短路径搜索效率的要求,取得了满意的结果。     

交通网络限制搜索区域时间最短路径算法

在基于四叉堆优先级队列的改进型Ｄｉｊｋｓｔｒａ最短路径算法的基础上,进一步提出了利用交通网络的空间分布及方位特征构造限制区域的时间最短路径算法。在对城市交通网络空间分布特征进行统计分析的基础上,针对具体的起,终节点,设定合理的椭圆限制搜索区域,以减少算法的搜索规模。     

GIS-T中途经多地点后返回的最短路径搜索算法

在交通运输过程中，用户经常需要搜索经过多个无序地点后返回起点的最短路径。为此，首先在GIS-T中原有空间数据的基础上，动态地建立了一个两点间最短路径信息库；然后，给出了一个不依赖搜索图、结合路线特点的算法，实现了对所需的最短路径的搜索。     

城市交通系统最优路径算法研究

针对目前交通拥挤现象提出了城市交通诱导系统,最短路径寻求是其主要问题之一。通过对最短路径实现算法的分析和研究,本文对传统的Dijk—stra算法和启发式搜索算法As算法进行了详细的探讨。基于GIS特性对最短路径算法进行优化,改进了Dijkstra算法。     

基于MapX和Floyd算法的最短路径搜索系统设计与实现

以MapX地图在VC环境下的开发为基础,通过构建道路网络拓扑关系数据库和应用Floyd算法,实现最短路径搜索系统的设计.主要研究了拓扑系数据库的建立和Floyd算法的改进应用,在完成GIS基本功能的条件下,实现了最短路径的搜索.     

基于分块路径缓存的在线路径搜索算法

为建立一个高效的互联网在线地图服务路径搜索引擎,提出一种基于分块路径缓存的最短路径算法。对路网重采样得到路网密集度图像,提出路网分块算法ISODATA。根据路网子块构建路径缓存设计缓存路径索引算法,提出基于子块缓存路径与节点间动态路径结合的双向路径搜索算法。实验结果表明,该算法可将城市级在线路径搜索时间控制在0.2 s以内,降低网络地图服务路径计算服务器负荷。     

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

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

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

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

基于OpenStreetMap最短路径算法的分析与实现

随着计算机网络技术和地理信息科学的发展,最短路径问题无论是在交通运输,还是在城市规划、物流管理、网络通讯等方面,都发挥了重要的作用。文中旨在阐述如何基于OSM运用Dijkstra算法计算两联通节点之间的最短路径。首先介绍了开放式OSM的特点以及地图数据文件中道路图像元素的数据结构;然后运用正则表达式算法从OSM数据中提取出交通道路信息,并选择合适的结构进行存储;最后通过将道路信息抽象成路径拓扑图,并以道路的地理距离作为路径权值,运用Dijkstra最短路径算法求解出两连通节点之间的最短路径。     

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

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

改进的基于元胞自动机扩展模型的图的最短路径算法

在基于元胞自动机单源点到单节点图的最短路算法的基础之上,通过改进控制演化的终止条件和记录演化过程中的路径信息,提出了单源点到多节点的元胞自动机扩展模型求解图的最短路算法模型，将该算法应用于城市道路交通网的实证研究之中,可以得到路段上任意两端点之间的最短路径及路权。     

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

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

     

A Hierarchical Path View Model for Path Finding in Intelligent Transportation Systems

Effective path finding has been identified as an important requirement for dynamic route guidance in Intelligent Transportation Systems (ITS). Path finding is most efficient if the all-pair (shortest) paths are precomputed because path search requires only simple lookups of the precomputed path views. Such an approach however incurs path view maintenance (computation and update) and storage costs which can be unrealistically high for large ITS networks. To lower these costs, we propose a Hierarchical Path View Model (HPVM) that partitions an ITS road map, and then creates a hierarchical structure based on the road type classification. HPVM includes a map partition algorithm for creating the hierarchy, path view maintenance algorithms, and a heuristic hierarchical path finding algorithm that searches paths by traversing the hierarchy. HPVM captures the dynamicity of traffic change patterns better than the ITS path finding systems that use the hierarchicalA * approach because: (1) during path search, HPVM traverses the hierarchy by dynamically selecting the connection points between two levels based on up-to-date traffic, and (2) HPVM can reroute the high-speed road traffic through local streets if needed. In this paper, we also present experimental results used to benchmark HPVM and to compare HPVM with alternative ITS path finding approaches, using both synthetic and real ITS maps that include a large Detroit map (> 28,000 nodes). The results show that the HPVM incurs much lower costs in path view maintenance and storage than the non-hierarchical path precomputation approach, and is more efficient in path search than the traditional ITS path finding using A* or hierarchical A* algorithms.