基于路网拓扑层次性表达的驾车路径规划方法

人对所处客观世界的认识具有显著的空间层次特征,可指导出行路径规划过程。常用的层次空间推理的分层路径计算方法,虽顾及了路网的层次性特征,但道路规划等级与人对路网的层次性认知往往并不一致。而道路网络自身的拓扑结构可客观反映道路重要程度,以及出行者对道路的层次性认知经验。本文以拓扑结构指标表达道路的层次性特征,以此规划驾车出行路径,并通过与出租车行驶路径的匹配度及距离最短路径耗时比评价路径规划结果的合理性。研究结果表明,基于路网拓扑层次性表达的规划路径优于距离最短路径、动态时间最短路径、基于道路等级的静态时间最短路径及基于动态中介中心性分层的距离最短路径,与基于出租车经验建模的路径规划结果相当。但本文所提出的方法不需出租车经验建模所依赖的浮动车系统支持,更利于部署应用。     

一种基于路网等级启发式策略的路径搜索算法

本文提出了一种基于路网等级启发式策略的路径搜索算法。通过引入考虑路网等级因素的代价评估函数,有目的地引导搜索过程考虑路网道路等级特征,限制路径搜索规模,在精度可控的前提下,大幅度提高时间最短路径算法的效率,并使得搜索路径结果更符合心理认知过程。其与经典的层次空间推理算法相比,本文提出的算法实现过程简单,效率和精度相似。理论分析和实验过程验证了本文所提出算法的有效性。     

图划分对Arc-flags算法的影响

最短路径计算作为导航的常用算法在移动互联网中扮演了重要角色,由于路网规模的增大和终端的不停移动,传统的串行最短路径算法已经无法满足实时性要求,因此预处理技术得到了广泛使用。Arc-flags是一个经典的基于预处理技术的最短路径算法,可以提供高效的在线最短路径查询服务。现有Arc-flags算法的研究主要集中在提升预处理时空效率和比较不同路网划分方式的优劣上,尚未见图划分对Arc-flags算法影响的深入研究。本文在真实路网上测试了不同的图划分数量和边界点数量等因素对Arc-flags算法的影响,主要包括预处理时间和空间的消耗、在线查询时间和搜索范围等方面,并根据实验结果和分析提出了合理的图划分建议（如选用好的图划分方法减少边界点数量等）,为改进和使用Arc-flags算法提供指导。     

SA*：一种多线程路径规划算法

路径规划问题是路网交通应用中的一个基础问题。A*算法是一个求解点到点最短路径问题的高效算法。但随着路网数据规模的增长,A*难以保证求解的实时性。利用并行计算进行加速是常用的算法性能提高手段,然而A*算法是由一系列前后依赖的迭代步骤组成,因此难以进行直接的并行化。本文提出一种分段化搜索的改进A*算法（SA*）。该算法在搜索路径前先选择若干可能在最短路径上的结点作为导航点,然后多线程并行地分别求出导航点之间的最短路径,并拼接这些路径作为原问题的一个近似解。分段搜索本身可以减少路径规划的搜索空间,借助多线程并行则可以进一步提高求解速度。实验结果表明,在真实路网数据上,利用16核的机器,SA*的性能可以达到A*算法的10-30倍。     

基于粒子滤波的行车轨迹路网匹配方法

行车轨迹是一种时间序列的地理空间位置采样数据,而传统的轨迹—路网匹配方法主要以全局或局部寻优的方式建立轨迹—路网匹配关系,影响了时空场景中数据的匹配计算过程的相对独立性。针对这个问题,本文基于粒子滤波（Particle Filter,PF）原理建立行车轨迹与道路网络之间的匹配关系。首先,沿轨迹中车辆运动方向在道路网络中搜索邻近道路节点,在与道路节点拓扑邻接的道路弧段上初始化随机生成粒子,根据轨迹中车辆运动模型将粒子沿所在道路弧段移动;然后,基于PF原理计算各时刻粒子运动状态及与行车轨迹采样点之间的距离误差,根据高斯概率密度函数计算粒子权重并利用随机重采样方法进行粒子重采样,迭代更新粒子运动状态;最后,计算与搜索到的道路节点拓扑邻接的每条道路弧段中累计粒子权重,通过各道路弧段累计权重计算轨迹—路网匹配关系。以行车轨迹进行实验表明,利用本文方法可以通过粒子时空变化反映采样点的移动,行车轨迹—路网匹配结果的正确率大于85%,能够实现行车轨迹和路网的准确匹配。     

基于中轴变换算法的室内外一体化导航路网自动生成方法

室内外一体化导航路网的快速生成与更新对面向行人的跨场景导航具有重要意义。当前研究主要关注单一场景下的导航路网构建,对于跨室内外场景的导航路网自动生成研究较少。本文基于对偶图思想与二维平面多边形中轴变换（Medial Axis Transform）算法,提出一种室内外一体化导航路网自动生成方法,并以某建筑CAD平面图及周边路网环境为基础数据进行了实例研究。结果表明：该方法能够根据原始数据的几何、拓扑、语义信息自动构建导航路网,并支持室内外跨场景的最短路径查询,在最短路径查询效率上较传统分场景寻路模型整体提升10.18%;相较单一场景下的导航路网,一体化导航路网可结合语义信息将室内及室外导航路网有机统一起来,解决跨场景寻求最优路径的问题,为最优路径规划的相关研究提供了新的思路。     

一种基于SuperMap GIS的改进Dijkstra算法

为提高传统Dijkstra算法的搜索效率,满足车载导航中路径规划实时性的要求,本文利用SuperMapGIS平台的网络编辑功能,设计了一种基于SuperMap的改进Dijkstra算法。首先,结合道路网络的空间分布特性,在SuperMap中构建了道路网络;其次,设计算法,根据起止节点合理限制算法的搜索区域,并以经典Dijkstra为理论基础实现最短路径的求解;最后,结合需要设计了约束条件下的路径规划算法。在城市道路网络中的应用实例验证了算法的有效性。     

一种面向海量浮动车数据的地图匹配方法

浮动车数据已广泛应用于交通监管、智能出行、城市规划等领域,地图匹配是浮动车数据关键技术之一,保障匹配算法精度的同时提高匹配效率,是面向海量浮动车数据地图匹配方法的难点。本文提出一种基于HMM（Hidden Markov Model）的地图匹配模型,相对传统模型尝试了多个方面的改进：在发射概率计算中引入航向角变量,并探讨了该变量对模型精度的影响;以格网对路网进行划分,构建哈希索引,实现候选路段快速查找;采用路径无权距离替代路径实际距离,并对路网进行预处理,根据浮动车有限时间内的活动范围构建路段转移矩阵,实现路段转移概率快速计算,以减小路径匹配算法时间复杂度。将模型应用于北京出租车轨迹数据匹配结果表明,对于采样时间间隔在1~120 s的浮动车数据模型切实可行。在满足匹配精度应用需求的前提下,模型效率有了较大幅度提升,能有效应用于海量浮动车数据地图匹配。     

基于土地利用强度的城市道路增长模拟模型与案例分析

城市交通与土地利用相互作用、相互影响。传统的城市空间模拟研究多关注交通对土地利用变化影响,缺少土地利用对路网空间形态影响的模拟。已有研究通常使用静态路网,不能表达土地利用与交通间的动态相互作用关系。本文以城市土地利用强度与城市道路网络空间分布间的正向关系,提出了基于城市土地利用强度的城市路网增长模拟模型。以唐山市为例,对其城市环路内的道路增长进行了模拟。结果表明,该模型能以城市土地利用强度的空间分布特征快速生成路网,反映城市土地利用对道路网络扩张的影响。模拟结果与实际路网具有高度的空间分布相似性。该模型可进一步与土地利用模拟模型结合,模拟城市土地利用与交通的动态相互作用。     

基于改进RRT*算法的城市低空路径规划方法研究

随着无人机监测、巡查和测绘等低空技术得到广泛应用,低空长距离空中路径规划成为低空航空器应用面临的一个挑战。而传统快速扩展随机树（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种算法也有缩短。该算法应用于低空长距离空中路径规划能够有效提高计算效率,降低规划时间,减少采样次数,缩短结果路径,减少转弯次数,丰富无人机的应用场景。     

一种建立公交网络的最短路径改进算法

目前,对最短路径问题的研究很多,基本都是关注算法的计算效率问题,而其应用到具体领域时会遇到一些算法本身无法解决的细节问题。如将邻接结点算法用于公交网络的最短路径计算时,会遇到诸如缺少网络拓扑信息、属性数据复杂等问题。本文针对这些问题给出了解决方法:在计算最短路径之前,利用算法将站点和线路数据进行自动匹配,建立公交网络的拓扑关系。同时在数据存储方式上进行了改进,运用数据库存储复杂的公交属性数据和中间过程中产生的公交网络数据,节约了运算时的内存占用率,提高了数据的利用率,使算法更具实际意义。     

基于效用值的模糊最短路问题的研究

模糊数学是研究和处理模糊现象的一种数学方法,而最短路径问题一直是运筹学、地理信息科学、计算机科学等学科的一个研究热点,被广泛地应用于交通运输、通讯工程、计算机网络和供应链管理等领域．模糊最短路问题的求解,实质就是比较模糊数的序关系,对模糊数进行排序,从而得出模糊最短路问题的结果．在基于对效用值的研究基础上,综合考虑了模糊数隶属函数的分布情况,得到一种新的三角模糊数和梯形模糊数的排序．并应用于求解模糊最短路问题,获得了求解模糊最短路问题的新算法．通过几个实例,验证了方法的有效性和实用性．     

一种公交换乘优化算法设计

目前,在智能交通系统应用中,公交查询亟待解决其算法效率和换乘两大问题。对此,本文首先在分析乘客出行因素和公交网络特性的基础上,提出了关键站点的公交网络通达矩阵,分析了直达矩阵的计算原理;其次,阐述了城市道路网络最短路径算法,引入直达矩阵和公交网络通达矩阵,设计了一种公交换乘优化算法。该算法的基本原理:利用公交网络通达矩阵来确定哪些临时标记节点是潜在的永久标记结点,并始终优先考虑直达节点作为最短路径上的节点,从而实现对经典最短路径算法--Dijkstra算法的改进;最后,通过一个案例对该算法进行验证。实验表明,该算法不仅能够获得优于Dijkstra算法的性能,而且换乘次数更加合理。该算法能够适用于一般公交网络,对于换乘代价较高的公交网络更有优势。     

基于地形数据的长距离越野路径快速规划方法研究

越野环境下机动车辆的快速路径规划在野外搜救、应急抢险及军事作战等领域均具有重要意义,在以上场景中,随着空间维数的增加,传统路径搜索算法计算复杂性急剧增长,可能无法在既定时间内求解可靠路径。为解决上述不足,本文结合越野路径规划不受路网通行限制以及两点之间直线最短的特点,提出以方向指向作为搜索策略的启发式算法,该算法搜索效率大幅提升,却难以保证求解质量。为进一步提高求解质量,提出了带有方向指向的Dijkstra分段算法,该算法在较低精度环境模型下通过Dijkstra算法找到最优路径,并将该路径进行分段,各分段以方向指向作为搜索策略进行路径搜索,从而在长距离越野路径规划中快速规划通行方案。为验证该算法的有效性,本文利用山西省某市的数字高程模型数据进行实验,引入了窗口移动法对地形进行先期的坡度计算和通行性分析,构建越野环境模型,调用路径搜索算法进行规划。实验结果表明,本文所提算法相比Dijkstra算法计算效率得到了大幅提升,且规划路径的长度接近于最优解。     

多层建筑空间的分层最优路径算法实现

由于多层建筑空间相对于室外环境存在按楼层分层的三维空间特性,在室内路径分析中需考虑楼层空间位置信息对最优路径规划的影响,而传统基于节点之间的网络连通拓扑模型的最优路径规划方法并没有空间概念,不能很好地应用于室内路径分析。为此,针对室内最优路径规划问题,基于多层建筑空间的层次特性,采用分层结构化的方法,提出结构化动态网络分析模式,实现了室内分层最优路径算法。该算法将各楼层路网和楼层连接均视为独立结构,根据停靠点的楼层分布情况,逐楼层动态构建跨越2个楼层的结构化网络模型并以该网络模型进行跨楼层的路径分析,从而得到多层建筑空间中遍历所有停靠点的最优路径。试验结果表明：相比传统最优路径算法,该算法在路径规划结果更加合理的情况下,时间效率有明显提高;另外,结构化动态网络分析模式可根据需求定义不同的楼层转换规则,更具灵活性。该算法可应用于城市大型公共建筑中,让室内路径分析与室外路径分析进行对接,使路径分析更科学、全面、合理。     

基于MapReduce的多机并行DP算法与实验分析

随着网络地图不断发展,个性化网络地图也得到快速发展。个性化网络地图需要以矢量数据为数据基础,以满足人们对地图色彩、符号等个性化要求,所以需要实时、快速进行大量数据化简。本文以经典Douglas-Peucker算法作为曲线化简算法,利用开源云计算平台Hadoop建立多机协作的曲线并行化简服务框架,设计和实现了多机并行Douglas-Peucker算法,并在集群上进行实验分析,验证算法的效率和适用性。算法核心是设计数据的逻辑分片,利用MapReduce计算原理,将分片分配到集群中,实现并行运算。实验分别分为两个方面:(1)比较在固定阈值不同数据量情况下,传统DP算法与多机并行DP算法效率;(2)比较在相同数据量不同阈值情况下,传统DP算法与多机并行DP算法效率。实验表明,在大数据量和高复杂度情况下,多机并行DP算法的效率更高。     

海洋运输网络研究进展与趋势探讨

随着经济全球一体化快速发展,国际海运贸易的规模不断扩大,全球海运网络研究成为当前的研究热点领域。该研究是海洋运输、地理信息科学、数学物理、统计科学、复杂网络科学、大数据科学、计算机科学等多学科交叉领域共同关注的研究主题,对国家宏观战略与政策制定具有重要作用。本文总结了海运网络研究数据基础、理论模型和研究方法,包括数学物理统计理论方法,基于复杂网络的分析方法、数据挖掘理论方法等,然后从海运网络运输模式设计与优化,网络结构静动态特征,网络结构和交通流演化机制等角度总结海运网络的研究进展、分析所存在的问题,提出海运网络研究在跨学科跨领域研究方法的交叉、多源异构数据融合分析、理论与实际应用结合等方面的未来研究趋势。