Optimizing Connections:Applied Shortest Path Algorithms for MANETs

This study is trying to address the critical need for efficient routing in Mobile Ad Hoc Networks(MANETs)from dynamic topologies that pose great challenges because of the mobility of nodes.Themain objective was to delve into and refine the application of the Dijkstra’s algorithm in this context,a method conventionally esteemed for its efficiency in static networks.Thus,this paper has carried out a comparative theoretical analysis with the Bellman-Ford algorithm,considering adaptation to the dynamic network conditions that are typical for MANETs.This paper has shown through detailed algorithmic analysis that Dijkstra’s algorithm,when adapted for dynamic updates,yields a very workable solution to the problem of real-time routing in MANETs.The results indicate that with these changes,Dijkstra’s algorithm performs much better computationally and 30%better in routing optimization than Bellman-Ford when working with configurations of sparse networks.The theoretical framework adapted,with the adaptation of the Dijkstra’s algorithm for dynamically changing network topologies,is novel in this work and quite different from any traditional application.The adaptation should offer more efficient routing and less computational overhead,most apt in the limited resource environment of MANETs.Thus,from these findings,one may derive a conclusion that the proposed version of Dijkstra’s algorithm is the best and most feasible choice of the routing protocol for MANETs given all pertinent key performance and resource consumption indicators and further that the proposed method offers a marked improvement over traditional methods.This paper,therefore,operationalizes the theoretical model into practical scenarios and also further research with empirical simulations to understand more about its operational effectiveness.

A genetic algorithm for the pareto optimal solution set of multi-objective shortest path problem

Unlike the shortest path problem that has only one optimal solution and can be solved in polynomial time, the muhi-objective shortest path problem （ MSPP ） has a set of pareto optimal solutions and cannot be solved in polynomial time. The present algorithms focused mainly on how to obtain a precisely pareto optimal solution for MSPP resulting in a long time to obtain multiple pareto optimal solutions with them. In order to obtain a set of satisfied solutions for MSPP in reasonable time to meet the demand of a decision maker, a genetic algo- rithm MSPP-GA is presented to solve the MSPP with typically competing objectives, cost and time, in this pa- per. The encoding of the solution and the operators such as crossover, mutation and selection are developed. The algorithm introduced pareto domination tournament and sharing based selection operator, which can not only directly search the pareto optimal frontier but also maintain the diversity of populations in the process of evolutionary computation. Experimental results show that MSPP-GA can obtain most efficient solutions distributed all along the pareto frontier in less time than an exact algorithm. The algorithm proposed in this paper provides a new and effective method of how to obtain the set of pareto optimal solutions for other multiple objective optimization problems in a short time.

The Algorithm of the Time-Dependent Shortest Path Problem with Time Windows

In this paper, we present a new algorithm of the time-dependent shortest path problem with time windows. Give a directed graph , where V is a set of nodes, E is a set of edges with a non-negative transit-time function . For each node , a time window ?within which the node may be visited and ?, is non-negative of the service and leaving time of the node. A source node s, a destination node d and a departure time?t0, the time-dependent shortest path problem with time windows asks to find an s, d-path that leaves a source node s at a departure time t0;and minimizes the total arrival time at a destination node d. This formulation generalizes the classical shortest path problem in which ce are constants. Our algorithm of the time windows gave the generalization of the ALT algorithm and A* algorithm for the classical problem according to Goldberg and Harrelson [1], Dreyfus [2] and Hart et al. [3].

An Investigation on the Effect of Migration Strategy on Parallel GA-Based Shortest Path Routing Algorithm

Genetic algorithm (GA) is one of the alternative approaches for solving the shortest path routing problem. In previous work, we have developed a coarse-grained parallel GA-based shortest path routing algorithm. With parallel GA, there is a GA operator called migration, where a chromosome is taken from one sub-population to replace a chromosome in another sub-population. Which chromosome to be taken and replaced is subjected to the migration strategy used. There are four different migration strategies that can be employed: best replace worst, best replace random, random replace worst, and random replace random. In this paper, we are going to evaluate the effect of different migration strategies on the parallel GA-based routing algorithm that has been developed in the previous work. Theoretically, the migration strategy best replace worst should perform better than the other strategies. However, result from simulation shows that even though the migration strategy best replace worst performs better most of the time, there are situations when one of the other strategies can perform just as well, or sometimes better.

An Evolutionary Algorithm Coupled to an Outranking Method for the Multicriteria Shortest Paths Problem

In this article, we are interested in solving a combinatorial optimization problem, the shortest path problem in a multi-attribute graph, by the out-ranking methods. A multi-attribute graph has simultaneously qualitative and quantitative criteria. This situation gives rise to incomparable paths thus forming the Pareto front. Outranking methods in Multi-criteria Decision Making (MCDM) are the only methods that can take into account this situation (incomparability of actions). After presenting the categories of Multi-criteria Decision Making (MCDM) and the difficulties related to the problems of the shortest paths, we propose an evolutionary algorithm based on the outranking methods to solve the problem of finding “best” paths in a multi-attribute graph with non-additive criteria. Our approach is based on the exploration of induced subgraphs of the outranking graph. Properties have been established to serve as algorithmic basis. Numerical experiments have been carried out and the results presented in this article.

A greedy path planning algorithm based on pre-path-planning and real-time-conflict for multiple automated guided vehicles in large-scale outdoor scenarios

With the wide application of automated guided vehicles(AGVs) in large scale outdoor scenarios with complex terrain,the collaborative work of a large number of AGVs becomes the main trend.The effective multi-agent path finding(MAPF) algorithm is urgently needed to ensure the efficiency and realizability of the whole system. The complex terrain of outdoor scenarios is fully considered by using different values of passage cost to quantify different terrain types. The objective of the MAPF problem is to minimize the cost of passage while the Manhattan distance of paths and the time of passage are also evaluated for a comprehensive comparison. The pre-path-planning and real-time-conflict based greedy(PRG) algorithm is proposed as the solution. Simulation is conducted and the proposed PRG algorithm is compared with waiting-stop A^(*) and conflict based search(CBS) algorithms. Results show that the PRG algorithm outperforms the waiting-stop A^(*) algorithm in all three performance indicators,and it is more applicable than the CBS algorithm when a large number of AGVs are working collaboratively with frequent collisions.

A Practical Parallel Algorithm for All-Pair Shortest Path Based on Pipelining

On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP pipelining algorithm makes full use of overlapping technique between computation and communication. Compared with broadcast operation, the parallel algorithm reduces communication cost. This algorithm has been implemented on MPI on PC-cluster. The theoretical analysis and experimental results show that the parallel algorithm is an efficient and scalable algorithm.

An efficient parallel algorithm for shortest pathsin planar layered digraphs

This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log^3n) time with n processors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way separator, which has the property that any directed path can be crossed only once.

The Shortest Path Analysis Based on Road Network

Rational planning of agricultural product transport route from initial node to destination node can effectively reduce the cost price of agricultural products,and the calculation of shortest path between any two points also affects people’s daily travel.Taking Heze Railway Station to Heze College for example,with remote sensing image data as the base map,we conduct vectorization and topological analysis on roads in the target area.With Dijkstra as theoretical basis of shortest path algorithm,we use ArcG IS network analysis method to build road network,and calculate the planning program of the shortest distance path,the shortest path by driving and the shortest path by walking.

An Algorithm to Find K Shortest Path

In this figure, it finds a vertex to another vertex k shortest path algorithm. Provided there are n vertices and edges in the diagram. If the path loops, the time complexity of the algorithm is allowed O（w ＋ n log 2 n ＋ kw log 2 k）. If the request path does not contain the loop, the time complexity of the algorithm O（kn（w ＋ n log2 n）＋ kw log2 k）. The algorithm utilizes a simple extension of the Dijkstra algorithm determined the end of the length of the shortest path to the other vertices, and then, based on these data, branch and bound method to identify the required path. Experimental results show that the actual running time has relations with the structure of FIG.

Using Link Analysis Technique with a Modified Shortest-Path Algorithm to Fight Money Laundering

Effective link analysis techniques are needed to help law enforcement and intelligence agencies fight money laundering. This paper presents a link analysis technique that uses a modified shortest-path algorithms to identify the strongest association paths between entities in a money laundering network. Based on two-tree Dijkstra and Priority＇First-Search （PFS） algorithm, a modified algorithm is presented. To apply the algorithm, a network representation transformation is made first.

Grid-Based Path Planner Using Multivariant Optimization Algorithm

To solve the shortest path planning problems on grid-based map efficiently,a novel heuristic path planning approach based on an intelligent swarm optimization method called Multivariant Optimization Algorithm( MOA) and a modified indirect encoding scheme are proposed. In MOA,the solution space is iteratively searched through global exploration and local exploitation by intelligent searching individuals,who are named as atoms. MOA is employed to locate the shortest path through iterations of global path planning and local path refinements in the proposed path planning approach. In each iteration,a group of global atoms are employed to perform the global path planning aiming at finding some candidate paths rapidly and then a group of local atoms are allotted to each candidate path for refinement. Further,the traditional indirect encoding scheme is modified to reduce the possibility of constructing an infeasible path from an array. Comparative experiments against two other frequently use intelligent optimization approaches: Genetic Algorithm( GA) and Particle Swarm Optimization( PSO) are conducted on benchmark test problems of varying complexity to evaluate the performance of MOA. The results demonstrate that MOA outperforms GA and PSO in terms of optimality indicated by the length of the located path.

Path Planning Method Based on D^(*) lite Algorithm for Unmanned Surface Vehicles in Complex Environments

In recent decades,path planning for unmanned surface vehicles(USVs)in complex environments,such as harbours and coastlines,has become an important concern.The existing algorithms for real-time path planning for USVs are either too slow at replanning or unreliable in changing environments with multiple dynamic obstacles.In this study,we developed a novel path planning method based on the D^(*) lite algorithm for real-time path planning of USVs in complex environments.The proposed method has the following advantages:(1)the computational time for replanning is reduced significantly owing to the use of an incremental algorithm and a new method for modelling dynamic obstacles;(2)a constrained artificial potential field method is employed to enhance the safety of the planned paths;and(3)the method is practical in terms of vehicle performance.The performance of the proposed method was evaluated through simulations and compared with those of existing algorithms.The simulation results confirmed the efficiency of the method for real-time path planning of USVs in complex environments.

An Improved Genetic Algorithm for Flight Path Re-Routes with Reduced Passenger Impact

Adverse weather has serious implications for flight timeliness, as well as passenger and aircraft safety. This often implies that alternative flight paths have to be used by aircraft to avoid adverse weather. To reduce the impact of such path re-routes, exact techniques such as artificial potential field model and Dijkstra’s algorithms have been proposed. However, such approaches are often unsuitable for real time scenarios involving large number of waypoints and constraints. This has led to the use of metaheuristic techniques that give sub-optimal solutions in good time. In this work, an improved genetic algorithm-based technique has been proposed. The algorithm used an improved mutation operator, reduced passenger inconvenience and considered the schedules of aircraft.

Java Computer Animation for Effective Learning of the Cholesky Algorithm with Transportation Engineering Applications

In this paper, the well-known Cholesky Algorithm (for solving simultaneous linear equations, or SLE) is re-visited, with the ultimate goal of developing a simple, user-friendly, attractive, and useful Java Visualization and Animation Graphical User Inter-face (GUI) software as an additional teaching tool for students to learn the Cholesky factorization in a step-by-step fashion with computer voice and animation. A demo video of the Cholesky Decomposition (or factorization) animation and result can be viewed online from the website: http://www.lions.odu.edu/~imako001/cholesky/demo/index.html. The software tool developed from this work can be used for both students and their instructors not only to master this technical subject, but also to provide a dynamic/valuable tool for obtaining the solutions for homework assignments, class examinations, self-assessment studies, and other coursework related activities. Various transportation engineering applications of SLE are cited. Engineering educators who have adopted “flipped classroom instruction” can also utilize this Java Visualization and Animation software for students to “self-learning” these algorithms at their own time (and at their preferable locations), and use valuable class-meeting time for more challenging (real-life) problems’ discussions. Statistical data for comparisons of students’ performance with and without using the developed Java computer animation are also included.

Floyd-Warshall Algorithm Based on Picture Fuzzy Information

The Floyd-Warshall algorithm is frequently used to determine the shortest path between any pair of nodes.It works well for crisp weights,but the problem arises when weights are vague and uncertain.Let us take an example of computer networks,where the chosen path might no longer be appropriate due to rapid changes in network conditions.The optimal path from among all possible courses is chosen in computer networks based on a variety of parameters.In this paper,we design a new variant of the Floyd-Warshall algorithm that identifies an All-Pair Shortest Path(APSP)in an uncertain situation of a network.In the proposed methodology,multiple criteria and theirmutual associationmay involve the selection of any suitable path between any two node points,and the values of these criteria may change due to an uncertain environment.We use trapezoidal picture fuzzy addition,score,and accuracy functions to find APSP.We compute the time complexity of this algorithm and contrast it with the traditional Floyd-Warshall algorithm and fuzzy Floyd-Warshall algorithm.

Design and Implementation of Bidirectional Dijkstra Algorithm

Bidirectional Dijkstra algorithm whose time complexity is 8O(n~2) is proposed. The theory foundation is that the classical Dijkstra algorithm has not any directional feature during searching the shortest path. The algorithm takes advantage of the adjacent link and the mechanism of bidirectional search, that is, the algorithm processes the positive search from start point to destination point and the negative search from destination point to start point at the same time. Finally, combining with the practical application of route-planning algorithm in embedded real-time vehicle navigation system (ERTVNS), one example of its practical applications is given, analysis in theory and the experimental results show that compared with the Dijkstra algorithm, the new algorithm can reduce time complexity, and guarantee the searching precision, it satisfies the needs of ERTVNS.

Implementation and comparative testing of turn-based algorithm for logit network loading

In order to evaluate the practicality and effectiveness of the turn-based algorithm for logit loading （TALL）, the TALL is implemented using C＋＋, and it is compared with a combination of the network-expanding method and the Dial algorithm based on the analysis of algorithm procedures. The TALL uses the arc-labeling shortest path searching, bidirectional star and the deque structure to directly assign the traffic flow, while the Dial algorithm should be used in an expanded network. The test results over realistic networks of eight cities show the superior performance of the TALL algorithm over the combination of the network-expanding method and the Dial algorithm, and the average processing time is reduced by 55. 4%. Furthermore, it is found that the operational efficiency of the TALL relates to the original densities of the cities. The average processing time is reduced by 65. 1% when the original density is about 14%, but the advantage of the TALL is not obvious with the increase in the original density.