China
Africa
Explore chapters and articles related to this topic
Architecture
Published in Hanky Sjafrie, Introduction to Self-Driving Vehicle Technology, 2019
Route planning typically uses special algorithms for solving a common graph theory problem called the shortest path problem. The problem can be defined as finding the shortest path between two nodes in a graph. One of the best-known shortest path algorithms is Dijkstra’s algorithm [6] as shown in Figure 4.1. The algorithm starts by initializing the distance value of all nodes to infinity. For all directly reachable nodes from the starting node a new distance value or cost is calculated, and the value is updated if the distance is shorter. This process iterates through the entire graph until all nodes have been traversed. The shortest path to any destination can now be determined by summing the cost of the node and the set of registered edges to reach that node. Faster algorithms, such as Contraction Hierarchies [9], perform some precomputation steps to speed up the process.
Multiobjective Routing in a Metropolitan City with Deterministic and Dynamic Travel and Waiting Times, and One-Way Traffic Regulation
Published in Ramakrishnan Ramanathan, Muthu Mathirajan, A. Ravi Ravindran, Big Data Analytics Using Multiple Criteria Decision-Making Models, 2017
Swaminathan Vignesh Raja, Chandrasekharan Rajendran, Ramaswamy Sivanandan, Rainer Leisten
A transportation network is a network of roads and streets, which permits vehicles to move from one place to another. A directed or undirected graph can be used to represent a transportation network, where edges of the graph have a capacity and receive a flow. The vertices of the graph are called nodes and the edges of the graph are called arcs. In any transportation network, the vehicle starts from the source node and moves toward the sink node. There are several types of network problems/models available in literature, for example, transportation problem, shortest path problem, minimum spanning tree problem, maximum flow problem, and minimum flow problem. The shortest path problem has tremendous importance in network flow models because it is applicable to any type of transportation network seen in real life. One of the most important issues affecting the performance of a transportation network is routing. The goal of routing between two points in a network is to reach the destination as quickly as possible (shortest time path problem) or as cheaply as possible (minimum cost or distance path problem).
Introduction
Published in Randall L. Eubank, Ana Kupresanin, Statistical Computing in C++ and R, 2011
Randall L. Eubank, Ana Kupresanin
Situations where priority queues are useful are frequent in practice. For example, the way a business distributes products to dealerships may be prioritized in terms of past sales performance. The scheduling of jobs on a computer cluster is likely to be managed with a priority queue. The future event queues that arise in a discrete event simulation are often handled using priority queues as implemented through a heap (discussed in the next section) or one of its variants (e.g., Mansharamani 1997). The problem of finding the shortest travel route between two locations is an example of the shortest path problem from graph theory. In that setting, Dijkstra’s algorithm for finding the optimal path benefits greatly from an efficient priority queue implementation (Exercise 9.32).
A graph algorithm for the time constrained shortest path
Published in Connection Science, 2022
Dijkstra’s algorithm presented by E. Dijkstra (Barbehenn, 1998) is a graph search algorithm to solve the single source shortest path problem in a graph with nonnegative edge weights. Compared with FILO-based and FIFO-based algorithms, Dijkstra’s algorithm does not give rise to the state explosion problem because it traverses all edges of the graph only once. The variant of Dijkstra’s algorithm for solving TCSPPs is to take time constraint as a restrictive condition to limit the choice of the path. If a path in the graph violates the time constraint, the second path must be constructed. Kjerrstrom (2001) put forward the concept of the Dijkstra-based algorithm but did not provide a specific realisation. To realise the variant of Dijkstra’s algorithm, we used the stack to store the intermediate processes such that the variant can backtrack to the previous step and find the second-shortest path. However, the backtracking process may traverse many repeated paths, resulting in lower time efficiency of the variant in practical implementation.
Exploring public bicycle network structure based on complex network theory and shortest path analysis: the public bicycle system in Yixing, China
Published in Transportation Planning and Technology, 2019
Sheng Wei, Jiangang Xu, Haitao Ma
The shortest path problem is a classical algorithm problem in graph theory, which aims to find the shortest path between two nodes in a graph (composed of nodes and paths). Many shortest path algorithms have been proposed in the literature, such as the Dijkstra search algorithm (cf. Ramalingam and Reps 1996). In this paper, in order to improve accuracy, the shortest path analysis of the two stations is carried out using Applications Programming Interfaces (APIs) of the Highmoralmap map, which provides accurate road data and an algorithm for computing the shortest path. The processes are as follows. First, convert the topographic map coordinates of the public bicycle stations to the Highmoralmap map projection coordinates and then calculate the shortest path between two public bicycle stations using the APIs of the Highmoralmap map.
An optimal and a heuristic algorithm for the single-item retrieval problem in puzzle-based storage systems with multiple escorts
Published in International Journal of Production Research, 2019
Altan Yalcin, Achim Koberstein, Kai-Oliver Schocke
Two classical search problems are the shortest path problem and n-puzzles (Edelkamp and Schrödl 2012). The shortest path problem is the problem of finding a path between two nodes in a graph that minimises the sum of weights of its constituent edges (e.g. the shortest path between two locations in a map). In the shortest path problem, a state can be described with a single node (location). In n-puzzles, the problem is to find a sequence of escort moves that transforms an initial configuration into a desired configuration with minimum number of actions. In n-puzzles, a state can described with the positions of the numbered tiles in the grid. The SRPME possesses the characteristics of both of these problems. As in the shortest path problem, we need to search for a path between two locations. As in n-puzzles, we need to consider tiles that are moved in a grid. In our algorithm, we define a state by the position of the retrieved item R and the positions of the escort locations (i.e. unoccupied locations) in the grid. An action consists of a movement of item R to an adjacent location and, in case this location is occupied, of the movement of an escort location to the adjacent location along a clearance path.