On Part 1: about OGC Open Routing API we covered the context where Skymantic’s Universal Routing Engine was conceived, that is, the OGC Open Routing Pilot, the requirements and the API overview. In this part we are going to describe the architecture of the routing engine.
Skymantics routing engine was designed following the Model-View-Controller (MVC) architectural pattern, combining three different main blocks, as shown in the following diagram:
- Model: The mapping data
- View: The web interface
- Controller: The routing algorithms, engine core and tools
The model
Map data are downloaded from different providers for Washington DC and stored locally in Geopackage format. For this pilot, we had access to three different data providers: Open Street Maps (OSM), U.S. National System for Geospatial Intelligence (NSG) and HERE.
Map data had to be preprocessed before being fed into the routing engine. The first step was to transform the information coded in the different formats into a Skymantics Universal GrAph structuRe (SUGAR), that could handle mapping information independently from the original format. It is important to define the goal of the routing engine in order to facilitate optimization starting from the generation of the SUGAR. For example, if the routing engine will only calculate vehicle routes, then all pedestrian and cycling routes can be ignored and simplify the resulting graph.
The next step consists of optimizing the graph, that is, removing unnecessary nodes, merging edges and creating shortcuts. All this graph cleansing can reduce the size of the graph by half or even more and improve performance by x5. Shortcuts can improve performance by an additional x10. Finally, the graph needs to be preloaded into memory in order to further improve performance by an additional x10. The result is a sufficiently fine-grained map that can be explored at high speed.
The view
The web interface was built based on Web Processing Service 3.0, the OGC standard that defines how a client can request the execution of a process and how the output from the process is handled. It implemented the definition of the newly drafted Routing API, in which routes were generated by querying with the POST method. Several routing parameters or constraints could be sent in the query, such as waypoints in the route, obstacles, maximum height and load, or even specify the routing algorithm to use. The response was sent in the newly defined Route Exchange Model, a GeoJson object consisting of a route overview (specifying the geometry of the complete route path, ready to display in a map) and the description of each route segment.
The controller
Two different families of routing algorithms were coded from scratch: Dijkstra and A*. Each of these implemented three different flavors: unidirectional, bidirectional or Contraction Hierarchies. Besides, each algorithm and flavor could calculate the fastest or the shortest route between two points. Moreover, it was possible to specify the data source to use for the route calculation (OSM, NSG or HERE). So, for the same two points, the routing engine could basically generate 36 different routes
All the execution is orchestrated by a core that receives and interprets the requests from the interface, selects the data source, and triggers the appropriate routing algorithm to generate the route.
Would you like to learn more?
Feel free to Contact Us, we’ll be happy to help!
