障碍物存在的最短路径算法及其在车载导航中的应用

车载导航系统中的动态路线选择是其必备功能之一,文中分析了经典Dijkstra算法存在的不足,并在此基础上,采用优化的邻接矩阵存储结构,讨论了有障碍物存在情况下的最短路径问题。同时用Vc＋＋与Mapx实现了有障碍物存在的动态最短路径算法。实验结果表明,该算法能有效求出有障碍物存在时的最短路径。     

An oriented spanning tree based genetic algorithm for multi-criteria shortest path problems

This paper investigates an oriented spanning tree (OST) based genetic algorithm (GA) for the multi-criteria shortest path problem (MSPP) as well as the multi-criteria constrained shortest path problem (MCSPP). By encoding a path as an OST, in contrast with the existing evolutionary algorithms (EA) for shortest path problem (SPP), the designed GA provides a “search from a paths set to another paths set” mutation mechanism such that both of its local search and global search capabilities are greatly improved. Because the possibility to find a feasible path in a paths set is usually larger than that of only one path is feasible, the designed GA has more predominance for solving MCSPPs. Some computational tests are presented and the test results are compared with those obtained by a recent EA of which the encoding approach and the ideas of evolution operators such as mutation and crossover are adopted in most of the existing EAs for shortest path problems. The test results indicate that the new algorithm is available for both of MSPP and MCSPP.     

Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment

A common algorithm to solve the shortest path problem (SPP) is the Dijkstra algorithm. In this paper, a generalized Dijkstra algorithm is proposed to handle SPP in an uncertain environment. Two key issues need to be addressed in SPP with fuzzy parameters. One is how to determine the addition of two edges. The other is how to compare the distance between two different paths with their edge lengths represented by fuzzy numbers. To solve these problems, the graded mean integration representation of fuzzy numbers is adopted to improve the classical Dijkstra algorithm. A numerical example of a transportation network is used to illustrate the efficiency of the proposed method.     

An efficient fault-containing self-stabilizing algorithm for the shortest path problem

Shortest path finding has a variety of applications in transportation and communication. In this paper, we propose a fault-containing self-stabilizing algorithm for the shortest path problem in a distributed system. The improvement made by the proposed algorithm in stabilization times for single-fault situations can demonstrate the desirability of an efficient fault-containing self-stabilizing algorithm. For single-fault situations, the worst-case stabilization time of the proposed algorithm is O(Δ), where Δ is the maximum node degree in the system, and the contamination number of the proposed algorithm is 1.     

Heuristic shortest path algorithms for transportation applications: State of the art

There are a number of transportation applications that require the use of a heuristic shortest path algorithm rather than one of the standard, optimal algorithms. This is primarily due to the requirements of some transportation applications where shortest paths need to be quickly identified either because an immediate response is required (e.g., in-vehicle route guidance systems) or because the shortest paths need to be recalculated repeatedly (e.g., vehicle routing and scheduling). For this reason a number of heuristic approaches have been advocated for decreasing the computation time of the shortest path algorithm. This paper presents a survey review of various heuristic shortest path algorithms that have been developed in the past. The goal is to identify the main features of different heuristic strategies, develop a unifying classification framework, and summarize relevant computational experience.     

A hill-jump algorithm of Hopfield neural network for shortest path problem in communication network

In this paper, we present a hill-jump algorithm of the Hopfield neural network for the shortest path problem in communication networks, where the goal is to find the shortest path from a starting node to an ending node. The method is intended to provide a near-optimum parallel algorithm for solving the shortest path problem. To do this, first the method uses the Hopfield neural network to get a path. Because the neural network always falls into a local minimum, the found path is usually not a shortest path. To search the shortest path, the method then helps the neural network jump from local minima of energy function by using another neural network built from a part of energy function of the problem. The method is tested through simulating some randomly generated communication networks, with the simulation results showing that the solution found by the proposed method is superior to that of the best existing neural network based algorithm.     

Stochastic shortest path with unlimited hops

We present new results for the Stochastic Shortest Path problem when an unlimited number of hops may be used. Nodes and links in the network may be congested or uncongested, and their states change over time. The goal is to adaptively choose the next node to visit such that the expected cost to the destination is minimized. Since the state of a node may change, having the option to revisit a node can improve the expected cost. Therefore, the option to use an unbounded number of hops may be required to achieve the minimum expected cost. We show that when revisits are prohibited, the optimal routing problem is np-hard. We also prove properties about networks for which continual improvement may occur.We study the related routing problem which asks whether it is possible to determine the optimal next node based on the current node and state, when an unlimited number of hops is allowed. We show that as the number of hops increases, this problem may not converge to a solution.     

一种求受顶点数限制的最短路径的新算法

提出了一种基于逆邻接表求受顶点数限制的最短路径的新算法,其时间复杂度为O(m-2)^*w)(m是受限制的顶点数,w是有向图中弧的条数),优于同类算法。采用逆邻接表作为图的存储结构,该算法很容易实现。     

求解最短路径的遗传算法中若干问题的讨论

针对道路交通网络中的最短路径问题,讨论了遗传算法中遗传算子的设计及运行参数的选择,提出一种新的交叉算子,提高了种群多样性.通过计算机仿真实验,比较了多种遗传算子设计方案的优劣及不同运行参数对算法效果的影响,为实际应用提供了参考.采用VC语言实现该遗传算法,并应用于实际的电子地图中,结果表明了算法的有效性和实用性.     

A linear-time algorithm for finding approximate shortest common superstrings

Approximate shortest common superstrings for a given setR of strings can be constructed by applying the greedy heuristics for finding a longest Hamiltonian path in the weighted graph that represents the pairwise overlaps between the strings inR. We develop an efficient implementation of this idea using a modified Aho-Corasick string-matching automaton. The resulting common superstring algorithm runs in timeO(n) or in timeO(n min(logm, log¦¦)) depending on whether or not the goto transitions of the Aho-Corasick automaton can be implemented by direct indexing over the alphabet . Heren is the total length of the strings inR andm is the number of such strings. The best previously known method requires timeO(n logm) orO(n logn) depending on the availability of direct indexing.This work was supported by the Academy of Finland.     

基于GA的网络最短路径多目标优化算法研究

针对现有基于遗传算法(GA)优化的网络最短路径算法存在优化目标单一、遗传编码质量低、搜索策略间平衡性差、适应度分配效率与灵活性较低等问题,建立一种多目标优化最短路径自适应GA模型,提出了优先级编码和优先级索引交叉算子,引入了遗传算子参数的模糊控制机制和基于自适应加权的适应度分配方法.实验结果表明,该算法的准确性和稳定性高、复杂度合理,实现了对网络设计优化中多目标最短路径问题的高质量求解.     

On an exact method for the constrained shortest path problem

The constrained shortest path (CSP) is a well known NP-Hard problem. Besides from its straightforward application as a network problem, the CSP is also used as a building block under column-generation solution methods for crew scheduling and crew rostering problems. We propose an exact solution method for the CSP capable of handling large-scale networks in a reasonable amount of time. We compared our approach with three different state-of-the-art algorithms for the CSP and found optimal solutions on networks with up to 40,000 nodes and 800,000 arcs. We extended the algorithm to effectively solve the auxiliary problems of a multi-activity shift scheduling problem and a bus rapid transit route design problem tackled with column generation. We obtained significant speedups against alternative column generation schemes that solve the auxiliary problem with state-of-the-art commercial (linear) optimizers. We also present a first parallel version of our algorithm that shows promising results.     

Improved algorithm for all pairs shortest paths

We present an improved algorithm for all pairs shortest paths. For a graph of n vertices our algorithm runs in O(n³(loglogn/logn)^5/7) time. This improves the best previous result which runs in O(n³(loglogn/logn)^1/2) time.     

Parallel algorithms for shortest path problems in polygons

Given ann-vertex simple polygon we address the following problems: (i) find the shortest path between two pointss andd insideP, and (ii) compute the shortestpath tree between a single points and each vertex ofP (which implicitly represents all the shortest paths). We show how to solve the first problem inO(logn) time usingO(n) processors, and the more general second problem inO(log² n) time usingO(n) processors, and the more general second problem inO(log² n) time usingO(n) processors for any simple polygonP. We assume the CREW RAM shared memory model of computation in which concurrent reads are allowed, but no two processors should attempt to simultaneously write in the same memory location. The algorithms are based on the divide-and-conquer paradigm and are quite different from the known sequential algorithmsResearch supported by the Faculty of Graduate Studies and Research (McGill University) grant 276-07     

基于云计算的混合并行遗传算法求解最短路径

为提高最短路径求解问题的效率,提出一种基于云计算的细粒度混合并行遗传算法求解最短路径的方法。方法采用云计算中H adoop的Map Reduce并行编程模型,提高编码效率,同时将细粒度并行遗传算法和禁忌搜索算法结合,提高了寻优算法的计算速度和局部寻优能力,进而提高最短路径的求解效率。仿真结果表明,该方法在计算速度和性能上优于经典遗传算法和并行遗传算法,是一种有效的最短路径求解方法。     

Optimally fast shortest path algorithms for some classes of graphs

Two algorithms for shortest path problems are presented. One is to find the all-pairs shortest paths (APSP) that runs in O(n ²logn + nm) time for n-vertex m-edge directed graphs consisting of strongly connected components with O(logn) edges among them. The other is to find the single-source shortest paths (SSSP) that runs in O(n) time for graphs reducible to the trivial graph by some simple transformations. These algorithms are optimally fast for some special classes of graphs in the sense that the former achieves O(n ²) which is a lower bound of the time necessary to find APSP, and that the latter achieves O(n) which is a lower bound of the time necessary to find SSSP. The latter can be used to find APSP, also achieving the running time O(n ²).     

Solving shortest path problem using particle swarm optimization

This paper presents the investigations on the application of particle swarm optimization (PSO) to solve shortest path (SP) routing problems. A modified priority-based encoding incorporating a heuristic operator for reducing the possibility of loop-formation in the path construction process is proposed for particle representation in PSO. Simulation experiments have been carried out on different network topologies for networks consisting of 15–70 nodes. It is noted that the proposed PSO-based approach can find the optimal path with good success rates and also can find closer sub-optimal paths with high certainty for all the tested networks. It is observed that the performance of the proposed algorithm surpasses those of recently reported genetic algorithm based approaches for this problem.     

Reduction approaches for robust shortest path problems

We investigate the uncertain versions of two classical combinatorial optimization problems, namely the Single-Pair Shortest Path Problem (SP-SPP) and the Single-Source Shortest Path Problem (SS-SPP). The former consists of finding a path of minimum length connecting two specific nodes in a finite directed graph G; the latter consists of finding the shortest paths from a fixed node to the remaining nodes of G. When considering the uncertain versions of both problems we assume that cycles may occur in G and that arc lengths are (possibly degenerating) nonnegative intervals. We provide sufficient conditions for a node and an arc to be always or never in an optimal solution of the Minimax regret Single-Pair Shortest Path Problem (MSP-SPP). Similarly, we provide sufficient conditions for an arc to be always or never in an optimal solution of the Minimax regret Single-Source Shortest Path Problem (MSS-SPP). We exploit such results to develop pegging tests useful to reduce the overall running time necessary to exactly solve both problems.     

闭合螺线阵列的最短路径算法

介绍了闭合螺线阵列的概念;利用动态规划法中的Floyd算法思想对求解闭合螺线阵列最短路径的问题进行了描述,并给出了具体算法;给出了利用二维数组算法求解闭合螺线阵列最短路径的过程.对于以上两种算法的优缺点进行了比较.这两种算法可以用于解决大多数路径问题.     

The shortest path in a simply-connected domain having a curved boundary

Given two distinct points S and E on a closed parametric curve forming the boundary of a simply-connected domain (without holes), this paper provides an algorithm to find the shortest interior path (SIP) between the two points in the domain. The SIP consists of portions of curves along with straight line segments that are tangential to the curve. The algorithm initially computes point-curve tangents and bitangents using their respective constraints. They are then analyzed further to identify potential tangents. A region check is performed to determine the tangent that will form part of the SIP. Portions of the curve that belong to the SIP are also identified during the process. The SIP is identified without explicitly computing the length of the curves/tangents. The curve is represented using non-uniform rational B-splines (NURBS). Results of the implementation are provided.