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.     

An adaptive amoeba algorithm for constrained shortest paths

The constrained shortest path problem (CSP) is one of the basic network optimization problems, which plays an important part in real applications. In this paper, an adaptive amoeba algorithm is combined with the Lagrangian relaxation algorithm to solve the CSP problem. The proposed method is divided into two steps: (1) the adaptive amoeba algorithm is modified to solve the shortest path problem (SPP) in a directed network; (2) the modified adaptive amoeba algorithm is combined with the Lagrangian relaxation method to solve the CSP problem. In addition, the evolving processes of the adaptive amoeba model have been detailed in the paper. Two examples are used to illustrate the efficiency of the proposed method. The results show that the proposed method can deal with the CSP problem effectively.     

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.     

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.     

Order relation between intervals and its application to shortest path problem

It is true that intervals are frequently partially ordered and cannot be compared. Nevertheless, varous definitions for ranking intervals have been proposed. In this paper, we propose a new definition for order relation between intervals by introducing a parameter called “a degree between partial and total order”, and apply it to the shortest path problem with arcs represented as intervals. In order to solve this problem, we modify the Dijkstra's algorithm, and propose a new algorithm obtaining some incomparable interval solutions. Finally, a numerical example is shown.     

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 ²).     

Modeling and solving the rooted distance-constrained minimum spanning tree problem

In this paper we discuss models and methods for solving the rooted distance constrained minimum spanning tree problem which is defined as follows: given a graph G=(V,E)$G=(V,E)$ with node set V={0,1,…,n}$V=\{0,1,\dots ,n\}$ and edge set E$E$, two integer weights, a cost _ce$c_e$ and a delay _we$w_e$ associated with each edge e$e$ of E$E$, and a natural (time limit) number H$H$, we wish to find a spanning tree T$T$ of the graph with minimum total cost and such that the unique path from a specified root node, node 0, to any other node has total delay not greater than H$H$. This problem generalizes the well known hop-constrained spanning tree problem and arises in the design of centralized networks with quality of service constraints and also in package shipment with service guarantee constraints. We present three theoretically equivalent modeling approaches, a column generation scheme, a Lagrangian relaxation combined with subgradient optimization procedure, both based on a path formulation of the problem, and a shortest path (compact) reformulation of the problem which views the underlying subproblem as defined in a layered extended graph. We present results for complete graph instances with up to 40 nodes. Our results indicate that the layered graph path reformulation model is still quite good when the arc weights are reasonably small. Lagrangian relaxation combined with subgradient optimization procedure appears to work much better than column generation and seems to be a quite reasonable approach to the problem for large weight, and even small weight, instances.     

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.     

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.     

Hybrid shortest path algorithm for vehicle navigation

Vehicle navigation is one of the important applications of the single-source single-target shortest path algorithm. This application frequently involves large scale networks with limited computing power and memory space. In this study, several heuristic concepts, including hierarchical, bidirectional, and A^*, are combined and used to develop hybrid algorithms that reduce searching space, improve searching speed, and provide the shortest path that closely resembles the behavior of most road users. The proposed algorithms are demonstrated on a real network consisting 374,520 nodes and 502,485 links. The network is preprocessed and separated into two connected subnetworks. The upper layer of network is constructed with high mobility links, while the lower layer comprises high accessibility links. The proposed hybrid algorithms are implemented on both PC and hand-held platforms. Experiments show a significant acceleration compared to the Dijkstra and A^* algorithm. Memory consumption of the hybrid algorithm is also considerably less than traditional algorithms. Results of this study showed the hybrid algorithms have an advantage over the traditional algorithm for vehicle navigation systems.     

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.     

Multi-objective and multi-constrained non-additive shortest path problems

Shortest path problems appear as subproblems in numerous optimization problems. In most papers concerning multiple objective shortest path problems, additivity of the objective is a de-facto assumption, but in many real-life situations objectives and criteria, can be non-additive. The purpose of this paper is to give a general framework for dominance tests for problems involving a number of non-additive criteria. These dominance tests can help to eliminate paths in a dynamic programming framework when using multiple objectives. Results on real-life multi-objective problems containing non-additive criteria are reported. We show that in many cases the framework can be used to efficiently reduce the number of generated paths.     

A novel neural network method for shortest path tree computation

Shortest path tree (SPT) computation is a critical issue in many real world problems, such as routing in networks. It is also a constrained optimization problem, which has been studied by many authors in recent years. Typically, it is solved by heuristic algorithms, such as the famous Dijkstra's algorithm, which can quickly provide a good solution in most instances. However, with the scale of problem increasing, these methods are inefficient and may consume a considerable amount of CPU time. Neural networks, which are massively parallel models, can solve this question easily. This paper presents an efficient modified continued pulse coupled neural network (MCPCNN) model for SPT computation in a large scale instance. The proposed model is topologically organized with only local lateral connections among neurons. The start neuron fires first, and then the firing event spreads out through the lateral connections among the neurons, like the propagation of a wave. Each neuron records its parent, that is, the neighbor which caused it to fire. It proves that the generated wave in the network spreads outward with travel times proportional to the connection weight between neurons. Thus, the generated path is always the global optimal shortest path from the source to all destinations. The proposed model is also applied to generate SPTs for a real given graph step by step. The effectiveness and efficiency of the proposed approach is demonstrated through simulation and comparison studies.     

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

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

Constructing the nearly shortest path in crossed cubes

A graph G is panconnected if each pair of distinct vertices u,v∈V(G) are joined by a path of length l for all d_G(u,v)?l?|V(G)|-1, where d_G(u,v) is the length of a shortest path joining u and v in G. Recently, Fan et. al. [J. Fan, X. Lin, X. Jia, Optimal path embedding in crossed cubes, IEEE Trans. Parall. Distrib. Syst. 16 (2) (2005) 1190-1200, J. Fan, X. Jia, X. Lin, Complete path embeddings in crossed cubes, Inform. Sci. 176 (22) (2006) 3332-3346] and Xu et. al. [J.M. Xu, M.J. Ma, M. Lu, Paths in Möbius cubes and crossed cubes, Inform. Proc. Lett. 97 (3) (2006) 94-97] both proved that n-dimensional crossed cube, CQ_n, is almost panconnected except the path of length d_CQn(u,v)+1 for any two distinct vertices u,v∈V(CQ_n). In this paper, we give a necessary and sufficient condition to check for the existence of paths of length d_CQn(u,v)+1, called the nearly shortest paths, for any two distinct vertices u,v in CQ_n. Moreover, we observe that only some pair of vertices have no nearly shortest path and we give a construction scheme for the nearly shortest path if it exists.     

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

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

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     

Output-threshold coupled neural network for solving the shortest path problems

This paper presents a coupled neural network, called output-threshold coupled neural network (OTCNN), which can mimic the autowaves in the present pulsed coupled neural networks (PCNNs), by the construction of mutual coupling between neuron outputs and the threshold of a neuron. Based on its autowaves, this paper presents a method for finding the shortest path in shortest time with OTCNNs. The method presented here features much fewer neurons needed, simplicity of the structure of the neurons and the networks, and large scale of parallel computation. It is shown that OTCNN is very effective in finding the shortest paths from a single start node to multiple destination nodes for asymmetric weighted graph, with a number of iterations proportional only to the length of the shortest paths, but independent of the complexity of the graph and the total number of existing paths in the graph. Finally, examples for finding the shortest path are presented.