共查询到20条相似文献，搜索用时 31 毫秒
1.
The problem of finding the K shortest paths (KSPs) between a pair of nodes in a road network is an important network optimization problem with broad applications. Yen's algorithm is a classical algorithm for exactly solving the KSP problem. However, it requires numerous shortest path searches, which can be computationally intensive for real large networks. This study proposes a fast algorithm by introducing a generalized spur path reuse technique. Using this technique, shortest paths calculated during the KSP finding process are stored. Accordingly, many shortest path searches can be avoided by reusing these stored paths. The results of computational experiments on several large‐scale road networks show that the introduced generalized spur path reuse technique can avoid more than 98% of shortest path searches in the KSP finding process. The proposed algorithm speeds up Yen's algorithm by up to 98.7 times in experimental networks. 相似文献
2.
主要针对当前嵌入式导航应用中路径规划计算存在的问题,设计了一种满足实时导航应用基于转换路网的分层搜索A*算法。该算法对于大区域的路径规划采用分层搜索策略,路径计算时采用能够处理交叉口转向限制和结点权重,并且占用存储空间小,搜索速度快的基于转换路网的二次搜索A*算法。通过实际的应用表明,算法在计算速度、路径合理性等方面可以满足实时导航应用的技术需求。 相似文献
3.
激光星间链路具有传输容量大和传输速率高等技术特点，具有激光星间链路功能的卫星节点可以在激光-微波混合星间链路网络中作为高速骨干网节点. 如何部署这些高速节点，使得构建的卫星网络拓扑达到最优目标，是星间链路由微波到激光过渡发展中的一个研究重点. 以包括24颗中圆地球轨道（MEO）、3颗地球同步轨道（GEO）和3颗倾斜地球同步轨道（IGSO）卫星的导航卫星星座为应用场景，在高速节点数量固定的条件下，综合几何可视性、星间距离和工程约束等约束条件， 以卫星网络接入节点到目的节点的平均端到端时延最小为优化目标，建立数学模型，提出一种基于多源最短路径策略的混合星间链路网络高速节点选取算法，求解局部激光高速节点骨干网络的最优拓扑结构. 仿真结果表明:本文算法得到的局部激光高速节点骨干网络拓扑结构能使整网传输时延更小，通信性能更佳. 相似文献
4.
节点重要性对大规模道路网下最短路径的计算有着重要影响。本文提出了顾及节点重要性的最短路径估计方法,该方法基于Critic方法与复杂网络理论评价节点的重要性,结合限制策略实现网络划分,通过层次结构网络的构建,实现大规模道路网数据的有效化简和最短路径的快速有效计算。试验结果表明,该方法能够使中心节点均衡地分布于网络,更好地均衡划分后子网络的规模;随着限制参数的增大,网络规模逐渐降低,查询精度最高达到1.026,相比于单一指标和无限制参数的方法,本文方法显著降低了网络的规模,在最短路径的近似计算上保持了较高的准确性,为大规模复杂网络的近似分析提供分析思路。 相似文献
5.
李妍妍 《测绘与空间地理信息》2014,(5):172-173
最短路径问题是地理信息系统的关键问题,传统Dijkstra算法在求解节点间最短路径时,对已标识节点以外的大量节点进行了计算,从而影响了算法的速度。因而对其算法进行优化是很有必要。本文在对传统Dijkstra算法分析的基础上,对其进行了优化,优化算法只对最短路径上节点的邻居做了处理,而不涉及其他节点,并利用Visual C++6.0开发平台编程进行了实验。实验表明,该算法是行之有效的。 相似文献
6.
Human beings’ intellection is the characteristic of a distinct hierarchy and can be taken to construct a heuristic in the shortest path algorithms. It is detailed in this paper how to utilize the hierarchical reasoning on the basis of greedy and directional strategy to establish a spatial heuristic, so as to improve running efficiency and suitability of shortest path algorithm for traffic network. The authors divide urban traffic network into three hierarchies and set forward a new node hierarchy division rule to avoid the unreliable solution of shortest path. It is argued that the shortest path, no matter distance shortest or time shortest, is usually not the favorite of drivers in practice. Some factors difficult to expect or quantify influence the drivers’ choice greatly. It makes the drivers prefer choosing a less shortest, but more reliable or flexible path to travel on. The presented optimum path algorithm, in addition to the improvement of the running efficiency of shortest path algorithms up to several times, reduces the emergence of those factors, conforms to the intellection characteristic of human beings, and is more easily accepted by drivers. Moreover, it does not require the completeness of networks in the lowest hierachy and the applicability and fault tolerance of the algorithm have improved. The experiment result shows the advantages of the presented algorithm. The authors argued that the algorithm has great potential application for navigation systems of large-scale traffic networks. 相似文献
7.
车载导航系统中顾及道路转向限制的弧段Dijkstra算法 总被引：15，自引：1，他引：14
路径规划作为组成车载导航系统的核心模块,其效率对整个系统有着至关重要的影响,传统路径规划常用的Dijkstra算法是根据道路“有向图”中的节点进行计算,相关的交通属性附加在道路节点上,事实上,道路转向限制不仅与节点（交叉口）有关,而且与相连的2条道路弧段有关,若要用节点表达道路转向限制,需要把2条弧段间的转向关系转换为相邻的3个节点之间的关系。这种转换增大存储空间和转换时间的开销,还增加了搜索的复杂度。为了解决这一问题,提出将原来附属于节点上的转向关系转移到相应的弧段上,用节点-弧段关系表达网络的连通性,用弧段-弧段转向关系表达交叉路口的转向限制,在此基础上,提出了一种顾及导航转向限制的弧段Dijkstra算法,试验表明,该算法能够有效地进行顾及道路转向限制的路径规划。 相似文献
8.
This research proposed a parallelized approach to scaling up the calculation of inundation height, the minimum sea‐level rise required to inundate a cell on a digital elevation model, which is based on Dijkstra's algorithm for shortest‐path calculations on a graph. Our approach is based on the concepts of spatial decomposition, calculate‐and‐correct, and a master/worker parallelization paradigm. The approach was tested using the U.S. Coastal Relief Model (CRM) dataset from the National Geophysical Data Center on a multicore desktop computer and various supercomputing resources through the U.S. Extreme Science and Engineering Discovery Environment (XSEDE) program. Our parallel implementation not only enables computations that were larger than previously possible, but also significantly outperforms serial implementations with respect to running time and memory footprint as the number of processing cores increases. The efficiency of the scalability seemed to be tied to tile size and flattened out at a certain number of workers. 相似文献
9.
Virtual globes enable the combination of heterogeneous datasets for optimal routing analyses in transportation, environmental ecology, and construction engineering. In this study, considering the advantages of the hierarchical tiling structure and topography of virtual globes, we propose a tile‐based optimal routing method for large‐scale road networks in a virtual globe. This method designs a topographically preserved road‐network tile model by partitioning roads into tiles and constructs the road‐network pyramid from the bottom to the top. During construction, a TileArc is calculated and flagged as the shortest path in a tile. Based on the built road‐network pyramid carrying hierarchical TileArcs, a multi‐level and flexible shortest path query can be executed efficiently. The proposed method is implemented with large road networks with different road grades in a virtual globe. Experimental results verify its validity, efficiency, and exactness. Moreover, the length of the shortest path with surface distance is approximately 1.3 times longer than that with Euclidean distance. 相似文献
10.
This article presents an approach to hierarchical matching of nodes in heterogeneous road networks in the same urban area. Heterogeneous road networks not only exist at different levels of detail (LoD), but also have different coordinate systems, leading to difficulties in matching and integrating them. To overcome these difficulties, a pattern‐based method was implemented. Based on the authors' previous work on detecting patterns of divided highways, complex road junctions, and strokes to eliminate the LoD effect of road networks, the proposed method extracts the local networks around each node in a road network and uses them as the matching units for the nodes. Second, the degree of shape similarity between the matching units is measured using a Minimum Road Edit Distance based on a transformation. Finally, the proposed method hierarchically matches the nodes in a road network using the Minimum Road Edit Distance and eliminates false matching nodes using M‐estimators. An experiment involving matching heterogeneous road networks with different LoDs and coordinate systems was carried out to verify the validity of the proposed method. The method achieves good and effective matching regardless of differences in LoDs and road‐network coordinate systems. 相似文献
11.
最短路径是现代物流配送研究中热点问题之一,在分析传统启发式搜索算法的基础上,针对算法在路径优化中存在的不足,提出基于二叉树优化启发式搜索算法（A＊）实现所需结点之间最短路径查询,在引入已知的全局信息条件下选择下一个被检查的结点,并根据用户给出的起始顶点与目标顶点以及搜索的角度查找最短路径,从而搜索可能性较大的结点,提高搜索过程的效率.实验表明,基于二叉树的A＊比A＊效率提高11％～26％. 相似文献
12.
An optimum vehicular path algorithm for traffic network based on hierarchical spatial reasoning 总被引：5，自引：0，他引：5
Human beings' intellection is the characteristic of a distinct hierarchy and can be taken to construct a heuristic in the shortest path algorithms.It is detailed in this paper how to utilize the hierarchical reasoning on the basis of greedy and directional strategy to establish a spatial heuristic,so as to improve running efficiency and suitability of shortest path algorithm for traffic network.The authors divide urban traffic network into three hierarchies and set forward a new node hierarchy division rule to avoid the unreliable solution of shortest path.It is argued that the shortest path,no matter distance shortest or time shortest,is usually not the favorite of drivers in practice.Some factors difficult to expect or quantify influence the drivers' choice greatly.It makes the drivers prefer choosing a less shortest,but more reliable or flexible path to travel on.The presented optimum path algorithm,in addition to the improvement of the running efficiency of shortest path algorithms up to several times,reduces the emergence of those factors,conforms to the intellection characteristic of human beings,and is more easily accepted by drivers.Moreover,it does not require the completeness of networks in the lowest hierarchy and the applicability and fault tolerance of the algorithm have improved.The experiment result shows the advantages of the presented algorithm.The authors argued that the algorithm has great potential application for navigation systems of large-scale traffic networks. 相似文献
13.
14.
现有的动态路径规划算法通常只考虑当前时刻交通信息,而忽略了路段行程时间依赖于进入该路段的时刻这一现实。而且,转向延误的存在使得传统的基于节点标号的最短路径算法不再有效。本文建立了基于路段的时间依赖网络模型,将转向延误时间引入到FIFO（先进先出）条件的定义中,并给出了满足FIFO条件的路段到达时间和转向延误时间计算式。以此模型为基础,并通过将时间因子引入到启发式评价函数中,发展了基于路段标号的时间依赖A*最短路径算法。实验表明,所提出的算法能预测并回避即将发生的交通拥堵,有效节省用户的出行时间。而其平均计算时间仅比传统算法增加了10%左右。此外,由于不再需要进行频繁的路径重优化,该算法能大幅提高路径规划的整体效率。 相似文献
15.
针对现有算法在计算道路网节点重要度时忽略节点间的相互影响以及道路密度引起的重要度异常等问题,提出了一种基于加权网页排序算法的道路网自动提取方法。首先将道路连接成路段,以路段为网络节点,道路交叉作为节点连线,路段长度作为边的权重,将道路网抽象成有向有权图;然后利用加权网页排序算法计算有向有权图节点的重要度,并利用链接作弊检测的方法修正由道路密度引起的节点重要度异常,得到道路节点的最终重要度排序,从而完成道路网的提取。通过真实路网数据进行实验分析,结果表明,相对基于网络中心性的方法,该算法的提取结果能够更好地保留原始路网的密度差异和整体结构。 相似文献
16.
将行人的生理因素与GIS路径分析有机结合起来,根据生理学研究进展,建立了步行体能消耗计算模型,并提出了基于坡度转换的等效水平距离计算原则,从而将三维空间距离转换为等体能消耗平面距离,实现了顾及地形起伏的最优路径算法。实验结果表明,该算法具有兼顾坡度与距离关系的优势,提高了路径分析方法的有效性。 相似文献
17.
提出一种基于路段连接图的格网模式识别方法.该方法以路段连接对作为研究的基本单元,以节点路段为点,路段的连接为边用路段连接图表达道路网.将在道路网中识别格网转化为在路段连接图中搜索格网回路.提出了描述路段连接对几何与连接关系的5个参量,用于筛选图中符合格网特点的节点和边.设计了图搜索的约束条件,使用广度优先遍历搜索连接关... 相似文献
18.
19.
20.
一种基于时空拥挤度的应急疏散路径优化方法 总被引：3，自引：1，他引：2
提出时空拥挤度的概念来描述时间与空间维上的移动对象的拥挤程度,并以此提出一种基于拥挤度的应急疏散路径优化方法,该方法能够为大型公共场所的人员疏散提供从建筑物内部经由路网离开危险区域的一个完整疏散路径方案。分析在疏散路径分配的过程中以最短路径为基础的疏散路径分配方案的拥堵情形,然后以缓解拥堵、减少疏散总时间为目标,设计疏散路径分配方案的优化方法。试验结果表明优化后的方案能够减轻整个疏散方案的拥堵程度,同时能够为每个疏散个体提供一条相对合理的疏散路径。 相似文献