This paper presents project duration assessment model based on modification of shortest path algorithms and superposition. One of the shortest path algorithms, Dijkstra algorithm, is modified in order to find the long...
详细信息
ISBN:
(纸本)9780769546308
This paper presents project duration assessment model based on modification of shortest path algorithms and superposition. One of the shortest path algorithms, Dijkstra algorithm, is modified in order to find the longest path. This is used for critical path calculation, i.e. for resolving project duration assessment problem. Another modification of algorithm calculates subcritical path as the second longest one. These paths are used for superposition, because of stochastic nature of many research and development projects which can cause that at some point in time subcritical becomes critical path. Thus, subcritical path influence on project duration should be taken into account, and, in this case, superposition is used for that. Superposition used in the model is based on analytical method - Clark's formulas. Presented model can be used for business process improvement and project management support.
For the first time, this paper proposes the Network-Tree Model (NTM), route optimization theory and wholly new, high performance algorithm for shortestpath calculation in large-scale network. We first decompose the n...
详细信息
ISBN:
(纸本)3540401962
For the first time, this paper proposes the Network-Tree Model (NTM), route optimization theory and wholly new, high performance algorithm for shortestpath calculation in large-scale network. We first decompose the network into a set of sub-networks by adopting the idea of multi-hierarchy partition and anomalistic regional partition, and then construct the NTM and the Expanded NTM. The Network-Tree shortestpath (NTSP) algorithm presented in this paper narrows the searching space of the route optimization within a few sub-networks, so it greatly reduces the requirements for main memory and improves the computational efficiency compared to traditional algorithms. Experiment results based on grid network show that NTSP algorithm achieves much higher computational performance than Dijkstra algorithm and other hierarchical shortest path algorithms.
In recent years, the employment of mobile chargerson energy supplementation of mobile charger (MC) has received increasing attention. This paper focuses on the online scheduling and charging strategies of robots in wa...
详细信息
In recent years, the employment of mobile chargerson energy supplementation of mobile charger (MC) has received increasing attention. This paper focuses on the online scheduling and charging strategies of robots in warehouses with unknown moving paths. First, the storage scenario is abstracted to a grid model in this article. Secondly, a shortest path algorithm based on coordinate difference under the premise of giving priority to the robot task is proposed. Then, the minimum service quantity of MC is determined through random simulation. Last but not least, the model of M/M/n/infinity/m/FCFS is used to calculate the average charging delay of the robot. Through simulation analysis, it can be found that the average service rate of MC is inversely proportional to the average charging delay of the robot. As time increases, the number of charging requests received by the MC also rises linearly. However, in a fixed length of time of Delta t, the number of charging requests is approximately a fixed value. Moreover, there is a linear positive correlation between the number of charging requests received by the MC and the total number of robots. When the total number of robots stays unchanged, the more MCs in the warehouse, the smaller the average charging delay of the robot will be yet with lower bound. The robot online scheduling and charging strategy proposed in this paper is applicable for most storage scenarios. Further, it contributes a new idea for further research on robot mobile charging scheduling strategy.
K-shortest path algorithm is generalization of the shortest path algorithm. K-shortestpath is used in various fields like sequence alignment problem in molecular bioinformatics, robot motion planning, path finding in...
详细信息
K-shortest path algorithm is generalization of the shortest path algorithm. K-shortestpath is used in various fields like sequence alignment problem in molecular bioinformatics, robot motion planning, path finding in gene network where speed to calculate paths plays a vital role. Parallel implementation is one of the best ways to fulfill the requirement of these applications. A GPU based parallel algorithm is developed to find k number of shortestpath in a positive edge-weighted directed large graph. In calculated shortestpath repetition of the vertices is not allowed. Implemented algorithm calculates a k-shortestpath between two pair of vertices of a graph with n nodes and m vertices. This approach is based on Yen's algorithm to find k-shortest loopless path. We implemented our algorithms in Nvidia's GPU using Compute Unified Device Architecture (CUDA). This paper presents comparative analysis between CPU and GPU based implementation of Yen's algorithm. Our approach achieves the 6 time speed up in comparison of serial algorithm.
Nowadays, the four-rotor aircraft path planning is an important research subject. To control the single four-rotor aircraft, we propose a path pre-planning algorithm and integrate the shortest path algorithm and the s...
详细信息
ISBN:
(纸本)9781467352512
Nowadays, the four-rotor aircraft path planning is an important research subject. To control the single four-rotor aircraft, we propose a path pre-planning algorithm and integrate the shortest path algorithm and the statistical analysis method into the algorithm. According to the certainty of path planning, we set the pre-planned paths in the electronic map for 3-d coordinate as trajectories. The aircraft gets the valid data from the three-dimensional coordinate. Then it adjusts the attitude and position in real-time to complete the path planning by using the data. In this paper, the algorithm improves the aircraft control accuracy and stability. We apply the path pre-planning algorithm to the four-rotor aircraft and verify the algorithm with simulations. The results of simulations show the accuracy and feasibility of the algorithm.
the vast majority of researches about the shortest path algorithm, nowadays, focus just on the case starting from the beginning point and ending at the ending point. If additional condition that the shortestpath must...
详细信息
the vast majority of researches about the shortest path algorithm, nowadays, focus just on the case starting from the beginning point and ending at the ending point. If additional condition that the shortestpath must go through some given nodes of which number is uncertain must be met, then most of the existing classic algorithms are not applicable. A general method based on the Virus Co-Evolutionary Genetic algorithm and greedy algorithm is presented to solve this kind of problem. The time complexity of the algorithm is given by theoretical analysis and the effectiveness of the algorithm is verified by programming calculation. Furthermore, this algorithm in HUAWEI Code Craft 2016 makes 17 th score in preliminary to the semi-finals.
shortest path algorithms can be utilized to find the shortest distance between one vertex to another in a graph for logistics applications. In IKEA warehouses, the efficiency is reduced when customers squander time re...
详细信息
shortest path algorithms can be utilized to find the shortest distance between one vertex to another in a graph for logistics applications. In IKEA warehouses, the efficiency is reduced when customers squander time repeating routes in picking up their desired furniture. The shortest path algorithm implemented in this paper is to be a proper means of demonstrating the most efficient route with restricted intermediate nodes for customers. Since the traditional shortest path algorithm presents random intermediate nodes along the shortestpath from entrance to exit. We proposed a shortest path algorithm that is suited to this circumstance as we used Greedy algorithm to divide the original problems into three, as well as Dijkstra algorithm for calculating the shortest distance between two nodes. The data required in the Dijkstra algorithm is stored in IKEA warehousing relational database which is designed in this paper for simulation.
In Current, physical distribution allocation has the problem that efficiency is not high, But this article mainly through analyzes the most short-path's two algorithms in the WebGIS technology: The classic Dijkstr...
详细信息
ISBN:
(纸本)9781457714146
In Current, physical distribution allocation has the problem that efficiency is not high, But this article mainly through analyzes the most short-path's two algorithms in the WebGIS technology: The classic Dijkstra algorithm and Ant Colony algorithm, And improvement through its to establish a more reasonable based on WebGIS logistics distribution system, And then through the analysis of the algorithm, Investigate Application in the Logistics and distribution system.
This paper presents a shortest path algorithm for FPGA based robot which can assist in industrial environment for various tasks. When a desired task is assigned to the robot, it chooses a shortestpath from the source...
详细信息
ISBN:
(纸本)9781479935420
This paper presents a shortest path algorithm for FPGA based robot which can assist in industrial environment for various tasks. When a desired task is assigned to the robot, it chooses a shortestpath from the source to the destination. path planning is an important issue for an autonomous robot to fulfill any desired task. Today many robots implement the path planning depending on the track, but practically track doesn't exists. So path planning with track is not a right choice. This paper overcomes tracking path issues, estimates the exact position, and improves effective localization and accuracy using land mark determination (RFID). With the help of ultrasonic sensors, the robot overcomes all the obstacles in its path. By using obstacle avoidance approach, a robot can perform a desired task using optimal resources. When a navigation task is assigned to the robot, it starts from there evaluating shortest distance to reach the destination. The proposed Robot is incorporated with Xilinx board XC3S500E (FPGA Spartan 3E) and RFID reader which checks the signal from RFID tags to localize the robot with respect to global position. The destination location is received from the remote location and the shortestpath is computed by algorithm. The Implementation results have been shown and estimation of shortestpath is done successfully.
This work presents a unique SDN-based Dijkstra shortestpath routing algorithm for QoS improvisation in UAV Networks. It discusses the various problems pertaining to the networking of unmanned aerial vehicles in disas...
详细信息
ISBN:
(纸本)9798350316469
This work presents a unique SDN-based Dijkstra shortestpath routing algorithm for QoS improvisation in UAV Networks. It discusses the various problems pertaining to the networking of unmanned aerial vehicles in disaster rescue operations and unique networking algorithmic solutions to the problems. Involving the SDN technology in networks provides faster service delivery than the traditional technology, as it isolates the control plane and data plane. This SDN technology has the centralised governing management service on the distributed network that affords improved security. But, SDN with Wireless Sensor Network (WSN) does not provide enhanced Quality of Services (QoS) in sophisticated cloud computing (CC) applications. Across the research community, end-users seek to attain a QoS while accessing the cloud-based services depending on their knowledge in using today's technology. Therefore, this research study is aimed to prioritize the cloud application data without any delay from the normal data and also to provide the fastest communication using the SDN framework applying shortestpath routing. The traditional networking infrastructure's speed, scalability, and agility are increased by the key functionality of SDN, which is used to intellectual the network information from the applications. Moreover, massive size data are managed and customized by using OpenContrail, which is a more responsive and scalable network. The QoS provided by the SDN with cloud-based services using shortestpath, stimulates this research to apply the integrated technology in UAV. UAV can transfer the data through cloud service using SDN, in order to maintain a communication with remote experts. The proposed shortestpath (SP) direction-finding algorithm provides appropriate deployment & connectivity to the modules of group of UAVs, also decreases time delay within the network. The simulation results reveal that the proposed technique is suitable and more effective to set up an emergency
暂无评论