基于NNlists的路网k路径近邻查询

为满足k路径近邻查询的实时性要求,运用预计算思想提出了基于NNlists的BNNL算法,通过在用户当前位置和目的地结点进行双向Dijkstra扩展得到两点间的最短路径,再通过对最短路径上的路网结点预计算的m近邻进行优化处理,最终得到正确的k路径近邻。该方法提高了k路径近邻查询的查询速度,尤其适用于兴趣点密度较大、k值较大的情况。     

智能交通在数字化社区服务平台中的研究与实现

通过对常见的最短路径及其算法的分析,指出以往的最短路径算法不能实现公交路线的查询,提出更适合公交查询的最短路径算法以及在数字化社区服务平台中智能公交系统的实现。     

道路网络中k路径最近邻居针对两种目标点的应用

提出一种道路网络中针对两种不同类型目标点的k组路径最近邻居查询,这是一种新的查询:给出用户希望到达的终点位置以及两组目标点集合,这种查询返回连接用户当前位置和终点位置的最短路径,以及相对于这条最短路径的k组路径最近邻居,每组包含两个不同类型的目标点,将这种查询命名为k-PNNT.提出了一种典型的过滤-精炼算法得到k-PNNT及对应的最短路径,并且在实际道路网络中进行了实验.实验证明,算法可行,有效.     

多维代价图模型上最优路径查询问题的研究

近年来,图数据模型被广泛地用于刻画现实世界中各种各样的实体间的复杂关系.最短路径查询是图研究领域中一类非常重要的查询并有着广泛的应用.然而,目前大多数关于最短路径的查询都是定义在单代价(权重)图模型下的.现实世界中,基于单一代价所选择的最短路径并不明智,比如路程最短的路径需要花费极高的费用.该文中,作者介绍了多维代价图模型的概念,并给出了多维代价图模型下基于函数的最优路径的定义.现有的计算最短路径的方法都利用了最短路径的子路径最优的性质:最短路径上的任意两点间的子路径是这两点的最短路径.因此,在计算最短路径的过程中,对访问过的每个顶点,只需保留起点到该点的最短路径即可.不幸的是,多维代价图模型下,当评分函数是非线性的时候,子路径最优的性质并不成立.因此,目前的方法均不能应用于多维代价图模型下基于函数的最优路径查询问题.该文给出了一个best-first search分支界限法并给出3种优化策略.进一步,给出了一个顶点过滤算法,该算法能从图中过滤掉大部分不属于最优路径的顶点.最后,用真实数据集上的实验验证了算法的有效性.     

基于非线性有约束最优化的路径规划研究

研究采用智能的方法来进行路径规划,通常作为一类优化组合问题来解决.因此,提出一种非线性有约束最优化问题的路径规划新方法.在静态环境中,把障碍物图形化处理后,应用线性规划思想,每个搜索点以目标点为导向寻找最优路径.仿真结果表明,改进方法能够快速准确的找到一条可行的最短路径.     

移动机器人路径规划的仿真研究

研究移动机器人路径优化问题,由于移动机器人寻优中存在定位稳定性和避障准确性问题,机器人路径规划不仅找到一条无碰撞、安全的移动机器人路径,而且要求路径尽可能最短。传统单一栅格法和遗传算法搜索最优路径效率低,难以全局最优路径。为了获得机器人全局最优路径,提出一种栅格法和混沌遗传算法相融合的移动机器人路径规划方法。首先采用栅格法对移动路径进行规划,作为遗传算法的初始种群,采用遗传算法进一步寻找最优路径。最后对移动机器人路径规划进行仿真,结果表明,混合算法可以很好地避免障碍物,快速找到一条机器人最优移动路径,十分适合于复杂环境路径规划。     

基于路由机制的时变路网k近邻算法

针对现实生活中动态路网的地理信息查询问题,提出了一种基于路由机制的动态路网中k近邻查询的算法。其主导思想是利用空间换时间,用路由表保存历史查询结果,用查询路由表的方法代替传统的最短路径计算,通过历史数据减少系统重复计算并对车辆行驶路径进行规划,用更新路由表的方法适应路况的变化。围绕路由表这一核心,改进相应的k近邻算法的过滤、精炼过程。通过路由表对动态路网进行少量的预处理,减少系统在k近邻搜索中的候选点数量,缩小查询范围,提高搜索效率。     

一种改进蚁群算法的移动机器人快速路径规划算法研究

以Dijkstra算法求解移动机器人路径规划(mobile robot path planning,MRPP)问题已得到广泛的应用,但在复杂工况下无法保证求解的正确性和全局最优性.而基于蚁群算法的移动机器人路径规划模型,在一定条件下能可靠地获得全局最优解,但存在求解时间过长的问题.因此,提出一种结合Dijkstra算法和蚁群算法模型两者优势求解MRPP问题的融合优化方法,以实现在短时间内获得全局最优解的目标.首先,应用Dijkstra快速算法在机器人工作环境中粗略寻迹得到最短路径次优解,然后,在次优解路径附近进行工作环境的精确划分;最后,利用蚁群算法在次优解附近精确寻迹,使最终的寻迹结果无限逼近最短路径.仿真结果表明,该融合优化方法既克服了经典蚁群算法求解时间过长的缺点,又能无限逼近全局最优解,寻迹时间较蚁群算法可缩短90%以上.     

人工蜂群算法在移动机器人路径规划中的应用

研究机器人路径规划优化问题,机器人工作环境复杂,运动路径上存在许多障碍物.针对提高机器人安全导航性能问题,传统群智能算法存在早熟、搜索效率低等难题,难以获得全局最优路径.为了获得最优机器人运动路径,避免碰撞的发生,提出了一种人工蜂群算法的机器人路径规划方法.首先采用栅格法对机器人工作环境进行建模,然后机器人路径规划目标点作为蜜源,最后蜂群之间信息交换、协作搜索最优机器人运动路径.结果表明,人工蜂群算法解决了传统群智能算法存在的难题,加快了机器人路径规划求解速度,以较短时间找到最短机器人运动路径.     

时态图最短路径查询方法

最短路径查询问题已被研究多年,然而,目前已有大部分工作主要集中在普通图上,针对时态图最短路径查询的研究工作相对较少.时态图中,2个顶点之间有多条边,每条边附带有时态区间,记录着边上代表事件的发生时间和结束时间.时态图最短路径查询在城市交通路径规划、社交网络分析、通信网络挖掘等领域有着广泛的应用.由于最短时态路径的子路径...     

An efficient path computation model for hierarchically structured topographical road maps

In this paper, we have developed a HiTi (Hierarchical MulTi) graph model for structuring large topographical road maps to speed up the minimum cost route computation. The HiTi graph model provides a novel approach to abstracting and structuring a topographical road map in a hierarchical fashion. We propose a new shortest path algorithm named SPAH, which utilizes HiTi graph model of a topographical road map for its computation. We give the proof for the optimality of SPAH. Our performance analysis of SPAH on grid graphs showed that it significantly reduces the search space over existing methods. We also present an in-depth experimental analysis of HiTi graph method by comparing it with other similar works on grid graphs. Within the HiTi graph framework, we also propose a parallel shortest path algorithm named ISPAH. Experimental results show that inter query shortest path problem provides more opportunity for scalable parallelism than the intra query shortest path problem.     

A shortest path routing algorithm using Hopfield neural network with an improved energy function

A shortest path routing algorithm using the Hopfield neural network with a modified Lyapunov function is proposed. The modified version of the Lyapunov energy function for an optimal routing problem is proposed for determining routing order for a source and multiple destinations. The proposed energy function mainly prevents the solution path from having loops and partitions. Experiments are performed on 3000 networks of up to 50 nodes with randomly selected link costs. The performance of the proposed algorithm is compared with several conventional algorithms including Ali and Kamoun's, Park and Choi's, and Ahn and Ramakrishna's algorithms in terms of the route optimality and convergence rate. The results show that the proposed algorithm outperforms conventional methods in all cases of experiments. The proposed algorithm particularly shows significant improvements on the route optimality and convergence rate over conventional algorithms when the size of the network approaches 50 nodes.     

A Shortest Path Based Path Planning Algorithm for Nonholonomic Mobile Robots

A path planning algorithm for a mobile robot subject to nonholonomic constraints is presented. The algorithmemploys a global- local strategy, and solves the problem in the 2D workspace of the robot, without generating the complexconfiguration space. Firstly, a visibility graph is constructed for finding a collision-free shortest path for a point. Secondly,the path for a point is evaluated to find whether it can be used as a reference to build up a feasible path for the mobile robot.If not, this path is discarded and the next shortest path is selected and evaluated until a right reference path is found. Thirdly,robot configurations are placed along the selected path in the way that the robot can move from one configuration to the nextavoiding obstacles. Lemmas are introduced to ensure that the robot travels using direct, indirect or reversal manoeuvres. Thealgorithm is computationally efficient and runs in time O(nk + n log n) for k obstacles andn vertices. The path found is near optimal in terms of distance travelled. The algorithm is tested in computersimulations and test results are presented to demonstrate its versatility in complex environments.     

A near-exact method for solving the log-truck scheduling problem

We propose a solution method for the log‐truck scheduling problem, which is a generalisation of the pick‐up and delivery problem with time windows. Our approach is based on column generation and pseudo branch and price. Each column in the proposed mathematical model represents one feasible route for one truck. We start by designing a priori an initial set of routes. Then, the subproblem, which is a constrained shortest path problem, is solved by applying a k‐shortest path algorithm. Numerical results from a case study are presented.     

Algorithms for a special class of state-dependent shortest path problems with an application to the train routing problem

We study the state-dependent shortest path problem and focus on its application to the Single Train Routing Problem consisting of a rail network with only double-track segments, where the objective is to route one train through an empty network as fast as possible. We show that the Single Train Routing Problem is NP-hard. We investigate the solution properties and present sufficient conditions for optimality. Different conditions on the parameters are given to guarantee that certain local route selection is optimal. Then, a dynamic programming heuristic is introduced and conditions when the proposed heuristic can obtain the optimal solution in polynomial time are also discussed. Experimental results show the efficiency of the proposed heuristics for general problem settings.     

煤矿紧急救援实时最短路径的研究

煤矿事故紧急救援是一个艰难的任务,救援的关键是探明事故的发生地点、事故的影响范围和救援的最短路径.论文采用GIS独特的空间分析功能,构造了煤矿项目的关系模型和巷道数据库,建立了基于Dijsktra优化算法的实时最短路径搜索算法,为紧急救援指明了最短救援路径,给出了分析过程和可行性证明.     

应用于地质调查的最短路径寻路算法

地质调查往往需要大量的野外勘测活动,如何最小化其成本开销是地质调查统筹工作研究的热点之一。本文提出一种用于地质调查勘测的最优野外路线选择算法,旨在使用现代计算机技术和地理信息技术提高地质调查统筹工作的效率。首先对地物地貌对人员运动的影响建立数学模型,建立抽象化分析基础,然后采用最短路径算法计算起始点与终点之间成本最低的最优路径。设计并实现算法对应的最优路线求解系统。实验结果表明,设计的最短路径寻路算法正确,具有较好的扩展性。     

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

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

时间依赖的网络中最小时间路径算法

时间依赖的网络与传统网络模型相比更具有现实意义，具有广泛的应用领域，交通网络和通信网络可以抽象为时间依赖的网络模型，当模型中弧的工度是时间依赖的变量，最短路径问题的求解变得非常困难，早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的，因此给出限制性条件使得传统最短路径算法是有效的。该文从最短路径算法的理论基础入手，从理论上证明了传统最短路径算法，如Dijkstra算法和标号设置算法，在时间依赖的网络上不能有效地求解最短路径问题，并且，在没有任何限制性条件下，给出了时间依赖的网络模型，理论基础，求解最小时间路径的优化条件和SPTDN算法，从理论上证明了SPTDN算法的正确性，算法的实验结果是正确的，最后给出了时间依赖的网络应用实例。     

K(≤3)条渐次短路径搜索算法的研究

Dijkstra算法是经典的最短路径搜索算法。该文在Dijkstra算法的基础上,提出了在单限制多权值的条件下k(≤3)条渐次短路径的搜索算法。算法的实例表明,该算法切实有效。