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

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

基于改进蚁群算法的最短路径问题研究

最短路径问题是智能交通：交通网络分析中的一个重要问题。文章分析了基本蚁群算法在求解交通网络两点之间最短路径时所出现的问题,并针对这些问题,在方向引导及信息素更新等方面对算法进行了改进。实验证明,改进后的方法较基本蚁群算法能准确快速地找到交通路网中两点间的最短路径,是切实可行的。     

公交车网络的最短路径算法及实现

最短路径问题是图论研究中的一个经典算法问题,旨在寻找图中任意两结点之间的最短路径.一般在交通道路网络中最短路径问题就是单纯地求解两点间的最短路径.为了保证实用性,公交车网络的最短路径算法以转车次数最少为首要目的.文中借鉴广度优先搜索的思路来求解最短路径,即逐个找出经过起点站和终点站的车次以及这些车次沿途可转的车次.首先说明了算法的计算机实现方法,再举例详细说明其过程,最后指出此算法的扩充用途.     

基于规则的最短路径查询算法

最短路径查询是图数据管理中非常重要的一类问题.研究了基于规则的最短路径查询,它是一类特殊的最短路径查询问题.给定起点和终点,基于规则的最短路径查询是指找到一条从起点到终点的最短路径,使得此路径经过用户指定点集中的所有点,并且某些点的访问顺序满足一定的偏序规则.该问题被证明是一个NP-hard问题.目前已有的工作侧重于空间数据集（两点之间的最短距离用欧氏距离表示）上基于规则的最短路径问题,它采用穷举的方式列出所有满足规则的路径,然后选择长度最小的路径作为问题的解.然而在实际的道路交通网中,两点之间的距离等于两点之间的最短路径的长度,它往往大于两点之间的欧氏距离;此外,采用穷举的方式会造成大量重复的计算.因此,设计了一种前向搜索算法以及一些优化技术来求解该问题.最后,在不同的真实数据集上设计了大量的实验来验证算法的有效性.实验结果表明,该算法可以快速给出问题的解,而且算法的效率在很大程度上超过了现有的算法.     

基于Dijkstra算法的范围规划问题

Dijkstra(迪杰斯特拉)算法是典型的最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。该算法能得出最短路径的最优解,在实际选择路径方案中起重要作用。本文是Dijkstra算法在范围规划问题中的应用。     

基于蚁群算法的拥堵交通最短路径研究

针对当前交通网络在路径选择研究中,存在只考虑静态交通网络的路径选择的问题,提出了利用蚁群算法的拥堵交通网络的最短路径算法,建立了采用Petri网的交通网络模型,运用蚁群算法对静态交通网络进行了最短路径求解,并加入天气状况、道路容量等动量建立动态交通网络.运用层次分析法并结合Petri网对交通拓扑图进行了最短路径的探索并进行了对比分析.研究结果表明在道路拥挤的情况下,动态交通网络下的路径算法可以为出行者找到更快捷方便的路线.     

基于社区分析的最短路径计算

具有城市规模的大规模交通网络作为大规模网络的一个应用领域,由于不断升级的交通紧张问题,近年来也成为一个热点研究领域.智能交通领域中,在进行动态交通分配时,需要快速计算当前路况状态下的最短路径,因此大规模网络中最短路径的算法研究具有相当重要的现实意义,但由于网络规模因素,最短路径计算非常耗费资源.在社区分析的基础上,对大规模网络进行分割及简约,并提出了一个切实可行的最短路径的并行算法,并对该算法的正确性和时间复杂度进行了分析,理论分析及实验结果均表明:本算法在大规模网络应用中明显优于单纯应用迪杰斯特拉算法以及LC-2q并行算法,具有良好的实用性.     

交通道路网中任意两点之间最短路径的快速算法

寻找交通道路网中任意两点之间最短路径的算法已有许多 ,其中Dijkstra算法是最有效的算法之一 ,其时间复杂性为O(n2 )。本文提出的算法与Dijkstra算法不同 ,其主要思想是依据从始点至终点的直线段方向选择边产生二叉树 ,并采取有效方法降低二叉树的规模及缩短路径长度 ,然后由二叉树节点的标记计算出近似最短路径及其长度。反复执行常数次该算法可以求得最短路径及其长度。     

基于VB.NET实现任意两点间最短路径算法

实际生活中的许多问题都可归结为图论中的求最短路径问题,Dijkstra算法是求最短路径算法中最有效的算法之一。在VB.NET编程环境下,实现了Dijkstra算法,根据指定的起始点和终点,得到了两点之间的最短路径长度和经过的节点。     

交通路网最优路径的搜索仿真研究

在道路状况日趋复杂的今天,交通路网中两点之间的最短路径已经不再是人们驾驶所需要的最优路径。传统路径规划方法存在考虑路径规划影响因素过于单一以及搜索效率过低的问题。在路径规划问题中缺少一种在多约束条件下的具体方法来实现交通路网中最优路径的高效搜索。针对上述问题,提出一种基于AHP层次分析法的改进Dijkstra算法。该算法在保有经典Dijkstra算法准确性的基础上,考虑了多种约束条件并大大提升了搜索效率。仿真结果表明,这种基于AHP层次分析法的改进Dijkstra算法具有良好的性能,能够满足当前路径规划问题的要求。     

Parallel Algorithms for Dynamic Shortest Path Problems

The development of intelligent transportation systems (ITS) and the resulting need for the solution of a variety of dynamic traffic network models and management problems require faster‐than‐real‐time computation of shortest path problems in dynamic networks. Recently, a sequential algorithm was developed to compute shortest paths in discrete time dynamic networks from all nodes and all departure times to one destination node. The algorithm is known as algorithm DOT and has an optimal worst‐case running‐time complexity. This implies that no algorithm with a better worst‐case computational complexity can be discovered. Consequently, in order to derive algorithms to solve all‐to‐one shortest path problems in dynamic networks, one would need to explore avenues other than the design of sequential solution algorithms only. The use of commercially‐available high‐performance computing platforms to develop parallel implementations of sequential algorithms is an example of such avenue. This paper reports on the design, implementation, and computational testing of parallel dynamic shortest path algorithms. We develop two shared‐memory and two message‐passing dynamic shortest path algorithm implementations, which are derived from algorithm DOT using the following parallelization strategies: decomposition by destination and decomposition by transportation network topology. The algorithms are coded using two types of parallel computing environments: a message‐passing environment based on the parallel virtual machine (PVM) library and a multi‐threading environment based on the SUN Microsystems Multi‐Threads (MT) library. We also develop a time‐based parallel version of algorithm DOT for the case of minimum time paths in FIFO networks, and a theoretical parallelization of algorithm DOT on an ‘ideal’ theoretical parallel machine. Performances of the implementations are analyzed and evaluated using large transportation networks, and two types of parallel computing platforms: a distributed network of Unix workstations and a SUN shared‐memory machine containing eight processors. Satisfactory speed‐ups in the running time of sequential algorithms are achieved, in particular for shared‐memory machines. Numerical results indicate that shared‐memory computers constitute the most appropriate type of parallel computing platforms for the computation of dynamic shortest paths for real‐time ITS applications.     

A dynamic fault-tolerant message routing algorithm for double-loop networks

Message routing is a fundamental function of a network, and fault-tolerance is an important tool to ensure the quality of service of a network. Assume that the network contains at most one faulty element and the algorithm does not know the faulty element in advance. We present an optimal fault-tolerant message routing algorithm for double-loop networks. We show that sending at most two messages with different routing strategies can ensure that one of the messages will be sent through a shortest path that avoids the faulty element. At each vertex, for any destination, the algorithm needs only constant time and space to determine the next vertex to which the message is to be sent.     

求图中顶点之间所有最短路径的一种算法

提出求一个顶点到另一个顶点的所有最短路径的一个算法.该算法利用图中每个顶点的出度的变化,来动态修改每个顶点到目的结点的最短路径长度,用C+ +编制了相应程序验证该算法的正确性和高效性,该算法容易理解,降低了时间复杂度.     

Dynamic Shortest Path Monitoring in Spatial Networks

With the increasing availability of real-time traffic information, dynamic spatial networks are pervasive nowadays and path planning in dynamic spatial networks becomes an important issue. In this light, we propose and investigate a novel problem of dynamically monitoring shortest paths in spatial networks (DSPM query). When a traveler aims to a destination, his/her shortest path to the destination may change due to two reasons: 1) the travel costs of some edges have been updated and 2) the traveler deviates from the pre-planned path. Our target is to accelerate the shortest path computing in dynamic spatial networks, and we believe that this study may be useful in many mobile applications, such as route planning and recommendation, car navigation and tracking, and location-based services in general. This problem is challenging due to two reasons: 1) how to maintain and reuse the existing computation results to accelerate the following computations, and 2) how to prune the search space effectively. To overcome these challenges, filter-and-refinement paradigm is adopted. We maintain an expansion tree and define a pair of upper and lower bounds to prune the search space. A series of optimization techniques are developed to accelerate the shortest path computing. The performance of the developed methods is studied in extensive experiments based on real spatial data.     

带杂交算子的蚁群算法求解动态网络中的最短路径问题

动态网络与传统的网络模型相比更具有现实意义，具有广泛的应用领域。本文对动态网络模型进行了描述，用实例证明了著名的Dijkstra算法在动态网络中不能有效地求解最短路径问题，提出了一种用带杂交算子的蚁群算法来求解动态网络最短路径问题的新算法。此算法不仅能够以较大的概率找到最优解而且对网络没有任何约束条件，即对离散
散和连续的动态网络模型都有效，而且用实例证明了算法的稳定性。     

A Routing Algorithm with Candidate Shortest Path

An improved algorithm based on the next node routing principle is proposed in this paper.In this algorithm there is a column added to the classical routing table, in which the candidateshortest distance to the destination node is the entry. When a link fails, the new shortest path inthe nodes connected directly with the failure link can be found immediately (it is just thecandidate shortest path before failure). For all other nodes in which routing tables should bechanged, the required number of control messages and time for convergence are also less thanTajibnapis' algorithm and Predecessor algorithm. The message looping problem does not existin duplex loop networks and is radically improved in mesh networks. These statements areproved by the analysis and simulation in this paper. From the simulation results of a 30-nodemesh network, when one link goes down, the total number of control messages generatedduring convergence with this algorithm on the average is about 30% of Tajibnapis' algorithm.The iterations required is 50% of Tajibnapis' algorithm. The memory space required andcomputation complexity in nodes are almost the same as the two algorithms mentioned aboveand the algorithm implementation is as easy as well.     

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

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

卫星时变拓扑网络最短路径算法研究

在提出卫星时变拓扑网络模型的基础上，首先证明了传统网络中的最短路径算法（如Dijkstra算法）在卫星时变拓扑网络中使用存在局限性，给出了一种可适用于卫星时变拓扑网络的最短路径算法并利用卫星节点间邻居关系的相对规律性，对算法进行了优化．相关仿真表明该算法比目前常用的卫星网络路由算法（如DVTR）更适合于切换频繁的卫星网络．     

Dynamic Task Assignment and Path Planning for Multi-AUV System in Variable Ocean Current Environment

An integrated multiple autonomous underwater vehicle (multi-AUV) dynamic task assignment and path planning algorithm is proposed by combing the improved self-organizing map (SOM) neural network and a novel velocity synthesis approach. Each target is to be visited by one and only one AUV, and a shortest path between a starting point and the destination is found in the presence of the variable current environment and dynamic targets. Firstly, the SOM neuron network is developed to assign a team of AUVs to achieve multiple target locations in dynamic ocean environment. The working process involves special definition of the rule to select the winner, the computation of the neighborhood function, and the method to update weights. Then, the velocity synthesis approach is applied to plan a shortest path for each AUV to visit the corresponding target in dynamic environment subject to the ocean current being variable and targets being movable. Lastly, to demonstrate the effectiveness of the proposed approach, simulation results are given in this paper.     

Multicasting in the hypercube, chord and binomial graphs

We discuss multicasting for the n-cube network and its close variants, the Chord and the Binomial Graph (BNG) Network. We present simple transformations and proofs that establish that the sp-multicast (shortest path) and Steiner tree problems for the n-cube, Chord and the BNG network are NP-Complete, even when every destination vertex is at a distance two from the source vertex.