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.
Snow plow route optimization: A constraint programming approach
Published in IISE Transactions, 2020
Joris Kinable, Willem-Jan van Hoeve, Stephen F. Smith
The routing and plowing graphs are implemented using the graph library JGraphT 1.3.0 (Michail et al., 2020). To reduce memory utilization, lanes in the same direction belonging to the same road segment are represented as a single arc in the graph (as opposed to individual arcs for every lane). The number of lanes in each direction is stored as an attribute on each arc. Shortest path computations are performed using an efficient implementation of Dijkstra’s shortest path algorithm; additional performance improvements could be obtained by implementing Highway and Contraction Hierarchies.
Smart Mobility in Smart Cities: Emerging challenges, recent advances and future directions
Published in Journal of Intelligent Transportation Systems, 2023
Soumia Goumiri, Saïd Yahiaoui, Soufiene Djahel
This class includes the oldest algorithms proposed for routing such as Dijkstra Dijkstra (1959), A* Hart et al. (1972) and Contraction Hierarchies (CH) Geisberger et al. (2008). CH is a fast technique that consists of contracting a node, meaning that changing this node by shortcuts representing the shortest paths passing by it.