A Shortest Path Algorithm for Multi-stage Network with Linear Parameter

In this paper, we give the shortest path algorithm for multi-stage network with a linear parameter, and study its complexity.

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.

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.

A Constrained Time-Dependent K Shortest Paths Algorithm Addressing Overlap and Travel Time Deviation

Theoretical research often assumes all users arc homogeneous in their route choice decision and will always pick the route with the shortest travel cost,which is not necessarily the case in reality.This paper documents the research effort in developing a Constrained Time-Dependent K Shortest Paths Algorithm inorder to find K Shortest Paths between two given locations.The goal of this research is to provide sound route options to travelers in order to assist their route choice decision process,during which the overlap and travel time deviation issues between the K paths will be considered.The proposed algorithm balancing overlap and travel time deviation is developed in this research.A numerical analysis is conducted on the Tucson 1-10 network,the outcome of the case study shows that our proposed algorithm is able to find different shortest paths with a reasonable degree of similarity and close travel time,which indicates that the result of the proposed algorithm is satisfactory.

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

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.

A~*算法在Shortest-Path方面的优化研究

在游戏和地理信息系统开发等领域中,专门针对最短路径搜索方面的优化研究较多,尤其是最短路径中启发式搜索算法中的A*算法的效率优化研究.本文将针对在人工智能或算法研究中的使用的地图大多数是基于任意图而不是网格图的状况,通过任意图与网格图及方向的相结合,提出了三种优化A*算法的启发式函数搜索策略,较好地减小了算法搜索的范围和规模,有效地提高了A*算法的运行效率.最后的实验结果显示,与传统的A*算法相比较,优化启发搜索策略后的A*算法寻径更快速,更准确,计算效率更高.

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.

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.

A routing algorithm for industrial wireless network based on ISA100.11a

ISA100.11 a industrial wireless network standard is based on a deterministic scheduling mechanism.For the timeslot delay caused by deterministic scheduling,a routing algorithm is presented for industrial environments.According to timeslot,superframe,links,channel and data retransmission of deterministic scheduling mechanisms that affect the design of the routing algorithm,the algorithm selects the link quality,timeslot delay and retransmission delay as the routing criteria and finds the optimum communication path by k shortest paths algorithm.Theoretical analysis and experimental verification show that the optimal paths selected by the algorithm not only have high link quality and low retransmission delay,but also meet the requirements of the deterministic scheduling.The algorithm can effectively solve the problem of packet loss and transmission delay during data transmission,and provide a valuable solution for efficient data transmission based on determinacy.

A Disk Scheduling Algorithm:SPFF

We put forward an optimal disk schedule with n disk requests and prove its optimality mathematically.Generalizing the idea of an optimal disk schedule, we remove the limit of n requests and, at the same time, consider the dynamically arrival model of disk requests to obtain an algorithm, shortest path first-fit first （SPFF）. This algorithm is based on the shortest path of disk head motion constructed by all the pendent requests. From view of the head moving distance, it has the stronger glohality than SSTF. From view of the head-moving direction, it has the better flexibility than SCAN. Therefore, SPFF keeps the advantage of SCAN and, at the same time, absorbs the strength of SSTF. The algorithm SPFF not only shows the more superiority than other scheduling polices, but also have higher adjustability to meet the computer system＇s different demands.

Constructing Multicast Routing Tree for Inter-cloud Data Transmission：An Approximation Algorithmic Perspective

Networking plays a crucial role in cloud computing especially in an inter-cloud environment, where data communications among data centers located at different geographical sites form the foundation of inter-cloud federation. Data transmissions required for inter-cloud federation in the complex inter-cloud networking system are often point-to-multi points, which calls for a more effective and efficient multicast routing algorithm in complex networking systems. In this paper, we investigate the multicast routing problem in the inter-cloud context with K constraints where K ≥ 2. Unlike most of existing algorithms that are too complex to be applied in practical scenarios, a novel and fast algorithm for establishing multicast routing tree for interclouds is proposed. The proposed algorithm leverages an entropybased process to aggregate all weights into a comprehensive metric, and then uses it to search a multicast tree(MT) on the basis of the shortest path tree(SPT). We conduct complexity analysis and extensive simulations for the proposed algorithm from the approximation perspective. Both analytical and experimental results demonstrate that the algorithm is more efficient than a representative multi-constrained multicast routing algorithm in terms of both speed and accuracy, and thus we believe that the proposed algorithm is applicable to the inter-cloud environment.

Application of Dijkstra Algorithm to Proposed Tramway of a Potential World Class University

Nowadays, the development of “smart cities” with a high level of quality of life is becoming a prior challenge to be addressed. In this paper, promoting the model shift in railway transportation using tram network towards more reliable, greener and in general more sustainable transportation modes in a potential world class university is proposed. “Smart mobility” in a smart city will significantly contribute to achieving the goal of a university becoming a world class university. In order to have a regular and reliable rail system on campus, we optimize the route among major stations on campus, using shortest path problem Dijkstra algorithm in conjunction with a computer software called LINDO to arrive at the optimal route. In particular, it is observed that the shortest path from the main entrance gate (Canaan land entrance gate) to the Electrical Engineering Department is of distance 0.805 km.

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.

考虑鲁棒成本与绝对后悔的最短路径问题研究

为克服鲁棒偏差方法在处理区间路网时所求鲁棒最短路径的保守性问题,通过分析鲁棒成本的定义以及鲁棒最短路径过于保守的原因,结合算例分析提出了绝对后悔值的概念,并以鲁棒成本和绝对后悔值为目标函数建立了区间路网的多目标最短路径模型;根据最短路径模型的特点设计了分离路径决策变量与连续变量的Benders分解算法,同时基于传统有效路径的判断依据重新定义了符合该最短路径模型的有效路径,并在分解后的主问题模型中引入了有效路径约束以加快算法收敛速度;利用MATLAB生成了一个包含29个节点、70条双向通行路段的区间路网对模型与算法进行仿真测试。结果表明:考虑鲁棒成本和绝对后悔值的最短路径模型能在区间路网中找到不保守,且同时兼具鲁棒性的最短路径,能够有效克服鲁棒偏差方法的缺陷。