共查询到15条相似文献，搜索用时 109 毫秒
1.
越野环境下机动车辆的快速路径规划在野外搜救、应急抢险及军事作战等领域均具有重要意义,在以上场景中,随着空间维数的增加,传统路径搜索算法计算复杂性急剧增长,可能无法在既定时间内求解可靠路径。为解决上述不足,本文结合越野路径规划不受路网通行限制以及两点之间直线最短的特点,提出以方向指向作为搜索策略的启发式算法,该算法搜索效率大幅提升,却难以保证求解质量。为进一步提高求解质量,提出了带有方向指向的Dijkstra分段算法,该算法在较低精度环境模型下通过Dijkstra算法找到最优路径,并将该路径进行分段,各分段以方向指向作为搜索策略进行路径搜索,从而在长距离越野路径规划中快速规划通行方案。为验证该算法的有效性,本文利用山西省某市的数字高程模型数据进行实验,引入了窗口移动法对地形进行先期的坡度计算和通行性分析,构建越野环境模型,调用路径搜索算法进行规划。实验结果表明,本文所提算法相比Dijkstra算法计算效率得到了大幅提升,且规划路径的长度接近于最优解。 相似文献
2.
由于多层建筑空间相对于室外环境存在按楼层分层的三维空间特性,在室内路径分析中需考虑楼层空间位置信息对最优路径规划的影响,而传统基于节点之间的网络连通拓扑模型的最优路径规划方法并没有空间概念,不能很好地应用于室内路径分析。为此,针对室内最优路径规划问题,基于多层建筑空间的层次特性,采用分层结构化的方法,提出结构化动态网络分析模式,实现了室内分层最优路径算法。该算法将各楼层路网和楼层连接均视为独立结构,根据停靠点的楼层分布情况,逐楼层动态构建跨越2个楼层的结构化网络模型并以该网络模型进行跨楼层的路径分析,从而得到多层建筑空间中遍历所有停靠点的最优路径。试验结果表明：相比传统最优路径算法,该算法在路径规划结果更加合理的情况下,时间效率有明显提高;另外,结构化动态网络分析模式可根据需求定义不同的楼层转换规则,更具灵活性。该算法可应用于城市大型公共建筑中,让室内路径分析与室外路径分析进行对接,使路径分析更科学、全面、合理。 相似文献
3.
车辆路径问题:从时间地理学的视角 总被引：2，自引：0，他引：2
车辆路径问题具有典型的时空分布特征,受到众多时空约束条件的制约。在车辆路径规划中,综合考虑时间和空间因素是非常必要的。本文从时间地理学这一全新的视角来研究车辆路径问题,提出一套完整的时间地理学分析框架,阐述了时间地理学的基本概念,提出了车辆路径问题中的时空约束、时空路径、时空棱柱、时空可达性、时空距离等概念,并给出了图示或定量化的度量方法。论文提出的时空距离度量方法综合考虑了顾客在空间位置和时间窗口2个方面的特征,可更科学地判定顾客之间的"邻近性"。论文通过设计一种求解大规模软时间窗车辆路径问题的算法,证明了时空距离的价值,并展望了时间地理学在求解动态车辆路径规划问题、移动设施路径规划问题等方面的应用。本文的贡献在于,通过时间地理学所提供的一系列概念和方法,实现了在统一的框架下同时考虑车辆路径问题(VRP)的时间和空间特征的构想,挖掘了传统时间地理学理论在车辆路径领域中的应用潜力,这将有利于更快或者更好地求解VRP问题。 相似文献
4.
随着无人机监测、巡查和测绘等低空技术得到广泛应用,低空长距离空中路径规划成为低空航空器应用面临的一个挑战。而传统快速扩展随机树（Rapidly-Exploring Random Trees/RRT）及其改进算法在大范围长距离低空三维空间下面临计算效率慢的问题,对此,本文提出一种带有R树空间索引的双向启发式RRT*算法,该算法在双向RRT*算法基础上为随机采样过程设置了启发函数,使得在面对狭小城市障碍物之间空隙时,能够避免局部最小值情况的出现。在此基础上为城市障碍物建立R树空间索引,减少了海量障碍物情况下碰撞检测的时间,提高了低空长距离空中路径规划效率。此外,为了得到更加符合无人机运动规律的路径,提高算法的实用性,在采样过程中设置转弯阈值控制转弯角度,并且对规划结果路径使用3次B-spline函数进行路径平滑。最后在武汉市三维城市场景中,利用武汉市建筑物数据进行了实验,实验证明相比已有算法,本文提出的带有R树空间索引的双向启发式RRT*算法相比较RRT算法和双向RRT*算法在500 m、 2000 m、 10 000 m不同距离下规划时间均降低了90%以上;采样次数相比RRT算法在不同距离下分别降低了51.6%、75%、86.7%,相比双向RRT*算法在不同距离下分别降低了20%、24.7%、57.3%;转弯次数相比RRT算法在不同距离下分别降低了77.3%、73.5%、78.3%,相比双向RRT*算法在不同距离下分别降低了37.5%、30.8%、16.8%;同时带有R树空间索引的双向启发式RRT*算法得到的结果路径长度相比其他2种算法也有缩短。该算法应用于低空长距离空中路径规划能够有效提高计算效率,降低规划时间,减少采样次数,缩短结果路径,减少转弯次数,丰富无人机的应用场景。 相似文献
5.
一种基于SuperMap GIS的改进Dijkstra算法 总被引：1，自引：0，他引：1
为提高传统Dijkstra算法的搜索效率,满足车载导航中路径规划实时性的要求,本文利用SuperMapGIS平台的网络编辑功能,设计了一种基于SuperMap的改进Dijkstra算法。首先,结合道路网络的空间分布特性,在SuperMap中构建了道路网络;其次,设计算法,根据起止节点合理限制算法的搜索区域,并以经典Dijkstra为理论基础实现最短路径的求解;最后,结合需要设计了约束条件下的路径规划算法。在城市道路网络中的应用实例验证了算法的有效性。 相似文献
6.
景区游览线路是游客游览不同景点的有效选择路径。在导航系统中通常结合各景点POI(Point of Interest)和景区路网的路径规划而生成,但是,针对具有一定范围与多出入口的景点(如建筑物类景点),单一的POI坐标描述机制规划产生的游览路径,往往与智能导游应用中实际可行的最优游览路径存在明显差异。本文分析了景点大小、多出入口等特征对景区游览路径规划的影响,提出了顶点和边的权重均可动态选择的景区双加权图模型,突破了单一POI描述机制的限制。同时,讨论了景区双加权图模型的化简、构建方法,并以Dijkstra算法和Prim算法为基础,给出了其最优路径规划求解算法。实验表明,本文模型及其最优路径规划算法所得结果更为优化与合理,具有较少的游览规划距离和更为紧凑的游览过程安排。 相似文献
7.
路径规划问题是路网交通应用中的一个基础问题。A*算法是一个求解点到点最短路径问题的高效算法。但随着路网数据规模的增长,A*难以保证求解的实时性。利用并行计算进行加速是常用的算法性能提高手段,然而A*算法是由一系列前后依赖的迭代步骤组成,因此难以进行直接的并行化。本文提出一种分段化搜索的改进A*算法（SA*）。该算法在搜索路径前先选择若干可能在最短路径上的结点作为导航点,然后多线程并行地分别求出导航点之间的最短路径,并拼接这些路径作为原问题的一个近似解。分段搜索本身可以减少路径规划的搜索空间,借助多线程并行则可以进一步提高求解速度。实验结果表明,在真实路网数据上,利用16核的机器,SA*的性能可以达到A*算法的10-30倍。 相似文献
8.
人对所处客观世界的认识具有显著的空间层次特征,可指导出行路径规划过程。常用的层次空间推理的分层路径计算方法,虽顾及了路网的层次性特征,但道路规划等级与人对路网的层次性认知往往并不一致。而道路网络自身的拓扑结构可客观反映道路重要程度,以及出行者对道路的层次性认知经验。本文以拓扑结构指标表达道路的层次性特征,以此规划驾车出行路径,并通过与出租车行驶路径的匹配度及距离最短路径耗时比评价路径规划结果的合理性。研究结果表明,基于路网拓扑层次性表达的规划路径优于距离最短路径、动态时间最短路径、基于道路等级的静态时间最短路径及基于动态中介中心性分层的距离最短路径,与基于出租车经验建模的路径规划结果相当。但本文所提出的方法不需出租车经验建模所依赖的浮动车系统支持,更利于部署应用。 相似文献
9.
栅格数据模型是地理信息科学领域的主要数据模型,成本距离分析是其重要的应用方向之一。但当栅格数据量较大时,传统的Dijkstra求解效率较低,因此本文提出了一种用改进蚁群算法来求解栅格成本距离的方法。首先,构建了适合人工智能算法的栅格数据模型及编码方法;然后,在此基础上初始化蚁群,采用状态概率选择机制计算相邻栅格单元之间距离成本,以及距离成本路径方向选择,同时利用改进的信息素更新机制加强蚁群之间信息交流,加快算法收敛速度;最后,引入了遗传算法的选择、交叉和变异等算子优化生产的成本距离的解,增加解的全局性。本文以北极地区的海冰密集度栅格数据为基础,求解北极地区适合航行路线的成本距离。实验表明,结合了蚁群算法和遗传算法优势的改进蚁群算法,能够快速有效地求解出基于栅格数据的成本距离。 相似文献
10.
针对大区域路径规划问题,论述了道路层次划分模型和多尺度道路网数据库的建立,提出了构建多级道路网拓扑结构的方法,利用层次空间推理和改进的启发式A*算法进行最优路径的选取。 相似文献
11.
在利用卫星跟踪卫星资料解算重力场模型位系数时,其海量观测数据处理以及大型方程组解算过程存在计算效率低下、对平台硬件要求高等问题。针对以上问题,提出一种基于能量守恒方法的重力场反演快速异构并行算法,基于CUDA 在GPU端实现并行计算设计矩阵,结合MKL库与分区平差法、预处理共轭梯度法在CPU端完成低内存消耗下的法方程快速构建与求解,实现重力场模型反演的异构并行计算。运用该算法处理GRACE-FO卫星2020-01-01～06-30期间观测数据,反演获得120阶重力场模型GM-GraceFO2020h;与现有模型以及算法对比分析表明,该算法所得模型与现有GRACE重力场模型精度相当,且相较于传统的串行算法,反演耗时减少98.479%,内存消耗减小1个数量级。 相似文献
12.
随着空间数据库的建设和应用的发展,空间数据动态更新和数据分发成为确保数据现势性的主要研究课题,系统提出将地形地物要素数据的坐标数组通过MD5算法生成32位字符串的"要素对象空间信息指纹"作为判定要素数据变化的方法,结合Oracle数据库CDC技术,快速获取空间变化数据,再通过ETL数据同步机制流程化管理空间同步过程,多节点、多级联按需配置同步图层,实现不同Oracle数据库版本、不同Arc SDE版本间的空间数据断点续传同步功能。 相似文献
13.
The underground water qualitymodel with non-linear inversion problem is illposed, and boils down to solving the minimum of nonlinear function. Genetic algorithms are adopted in a number of individuals of groups by iterative search to find the optimal solution of the problem, the encoding strings as its operational objective, and achieving the iterative calculations by the genetic operators. It is an effective method of inverse problems of groundwater, with incomparable advantages and practical significances. 相似文献
14.
MA Ruijie LI Xin. College of Mathematics Jilin University Changchun China . College of Construction Engineering China 《东北亚地学研究》2009,(3):164-167
The underground water quality model with non-linear inversion problem is ill-posed, and boils down to solving the minimum of nonlinear function. Genetic algorithms are adopted in a number of individuals of groups by iterative search to find the optimal solution of the problem, the encoding strings as its operational objective, and achieving the iterative calculations by the genetic operators. It is an effective method of inverse problems of groundwater, with incomparable advantages and practical significances. 相似文献
15.
针对大规模GNSS网常规数据处理时效性差、效率低的问题,基于GAMIT/GLOBK软件,利用进程池技术从多时段与多子网2个维度分别设计共享内存模型数据并行算法,并融合实现大规模GNSS网在时间域和空间域上的时空一体化双层并行解决方案。该方案可突破软件传统串行处理GNSS数据时效性差、多核计算资源利用率低的限制,在测试环境下最大加速比高达19.39,可充分挖掘计算机算力,大幅提升大规模GNSS网数据处理的时效性。 相似文献