Routino Router Algorithm

    2 Votes

Routino application is used to find the route between two points using topographical information collected by Open Street Map. Fundamental part of the algorithm is to find all the possible routes from start to end point. Router uses The router uses speed limits,barriers,gates,highway restrictions in their algorithm to produce accurate results. While this method does work, it is not a fast Improved Algorithm. It describes the simplest way to do this is to follow all possible segments from the starting node to the next nearest node (an intermediate node in the complete journey). For each node that is reached store the shortest route from the starting node and the length of that route. The list of intermediate nodes needs to be maintained in order of shortest overall route on the assumption that there is a straight line route from here to the end node. At each point the intermediate node that has the shortest potential overall journey time is processed before any other node. From the first node in the list follow all possible segments and place the newly discovered nodes into the same list ordered in the same way.

This will tend to constrain the list of nodes examined to be the ones that are between the start and end nodes. If at any point you reach a node that has already been reached by a longer route then you can discard that route since the newly discovered route is shorter The final algorithm that is implemented in the router is basically the one above but with an important difference. Since the time taken to find a route is proportional to the number of nodes the main route takes 1/10th of the time and the very short routes take almost no time at all. The solution to making the algorithm fast is therefore to discard most of the nodes and only keep the interesting ones. In this case a node is deemed to be interesting if it is the junction of three or more segments or the junction of two segments with different properties. In the algorithm these are classed as super-nodes. Between each super-node and a neighboring super-node a super-segment is generated that contains the shortest path along segments with identical properties. This decision making process can be repeated until the only the most important and interesting nodes remain.

The hardest part of implementing this router is the data organisation. The arrangement of the data to minimize the number of operations required to follow a route from one node to another is much harder than designing the algorithm itself. The final implementation uses a separate table for nodes, segments and ways. Each table individually is implemented as a C-language data structure that is written to disk by a program which parses the Open Street Map XML data file. In the router these data structures are memory mapped so that the operating system handles the problems of loading the needed data blocks from disk. Each node contains a latitude and longitude and they are sorted geographically so that converting a latitude and longitude coordinate to a node is fast as well as looking up the coordinate of a node. The node also contains the location in the array of segments for the first segment that uses that node. 

Each segment contains the location of the two nodes as well as the way that the segment came from. The location of the next segment that uses one of the two nodes is also stored; the next segment for the other node is the following one in the array. The length of the segment is also pre-computed and stored. Each way has a name, a highway type, a list of allowed types of traffic, a speed limit, any weight, height, width or length restrictions and the highway properties. The super-nodes are mixed in with the nodes and the super-segments are mixed in with the segments. For the nodes they are the same as the normal nodes, so just a flag is needed to indicate that they are super. The super-segments are in addition to the normal segments so they increase the database size (by about 10%) and are also marked with a flag. Some segments are therefore flagged as both normal segments and super-segments if they both have the same end nodes.

The relations are stored separately from the nodes, segments and ways. For the turn restriction relations the initial and final segments are stored along with the restricted node itself. Each node that has a turn restriction is marked in the main node storage with a flag to indicate this information.

References

http://www.grade.de/route/routino/documentation/algorithm.html

Popular Videos

How to speak to people

How to speak so that people want to listen.

Got a tip or Question?
Let us know

Related Articles

Travel Planner using Genetic Algorithm
Data Recovery and Undeletion using RecoverE2
PC CONTROLLED ROBOTIC CAR
Data Leakage Detection
Scene Animation System Project
Data Structures and Algorithms Visualization Tool
Paint Program in C
Solving 0-1 Knapsack Problem using Genetic Algorithm
Software Watermarking Project
Android Gesture Recognition
Internet working between OSI and TCP/IP Network Managements with Security Features Requirements
Web Image Searching Engine Using SIFT Algorithm
Remote Wireless Sensor Networks for Water Quality Monitoring Requirements
Ranking Spatial Data by Quality Preferences
Scalable Learning Of Collective Behaviour
Computational Metaphor Extraction And Interpretation
Designing a domain independent Rules Engine For Business Intelligence
Graph Colouring Algorithm
Gesture Based Computing
Facial Expression Detection