Building an Interoperable Routing Engine (Part 1)

Contributed by: 
Ignacio "Nacho" Correas, Chief Technology Innovation Officer at Skymantics

Standardizing APIs for Route Calculation


OGC is currently in the process of creating a Routing Standards Working Group (SWG). If you use routing in any shape or form as part of your business, or are interested by the below blog post, please consider joining this new Standards Working Group!  For more information on the group see the News Item: OGC Members propose new Routing Standards Working Group; public comment sought on draft charter.  
More information on the Routing Pilot, including video demonstrations of the outcomes, is available on the OGC Open Routing API Pilot page.


 

Skymantics has a long record of researching and developing new routing algorithms and technologies, but it was during the OGC Open Routing API Pilot when the team built its own routing engine. This is the first of a series of short articles that summarize Skymantics’ experiences and findings in building an interoperable routing engine using OGC standards.

About the OGC Open Routing API

The goal of the Open Routing API Pilot was to develop an API that allowed requests for routes from different users in an interoperable and standardized way via Web protocols. OpenLS is an older existing standard for Location Services. OpenLS was developed 20 years ago, which is aeons in terms of technology evolution. It was developed with carriers and second-generation mobile phones in mind, quite far from the emerging next generation of OGC Web Service interface definitions. Just to get an idea how old OpenLS is, consider that by the time it started development, Excite and Yahoo! were the most popular search engines on the Internet and the Wireless Application Protocol (WAP) was considered the future in mobility.

As hard as it is to believe, there is no standard for routing or navigation. There are many services for consumers but they all offer non-standard interfaces with different query models and parameter options. Routing is an important-enough topic to have a standard of its own!

The main focus of the Open Routing API Pilot was to define a JSON-based route model, called Route Exchange Model, for route exchange, comparison, and integration and demonstrate its interoperability in a variety of situations: online/offline routing; desktop clients, browser-based apps, and mobile apps; online services and/or local routing engines that work with GeoPackages.

The figure below shows the various participants in the Open Routing API Pilot who sought to develop routing engines using OGC Web Processing Service (WPS) for improved interoperability and the Route Exchange Model for modeling standard routes.

The various participants in the Open Routing API Pilot
The various participants in the Open Routing API Pilot (click for larger version)

There were four main requirements for the definition of the Route Exchange Model:

  1. It must be consistent with current OGC API implementations
  2. It should use GeoJSON, to benefit from existing tooling
  3. It must provide support for fetching parts of a route in environments with low bandwidth or intermittent connectivity
  4. It must be modular and extensible

An example of a JSON route using the Route Exchange Model
An example of a JSON route following the above requirements displayed on a map (click for larger version)

A very important piece of the puzzle was the interface for the routing services, a WPS 3.0 based on OpenAPI, should be able to connect with any of the pilot’s routing engines. As these are a new generation of web service interface definitions, two different approaches were implemented in parallel in order to compare them and start a discussion: (1) Routing API (more specific to routing) (see Table A) vs (2) WPS Profile API (more generic, similar to other non-routing interfaces) (see Table B). Both approaches worked well, but the Routing API was simpler and more intuitive, whereas the WPS Profile worked particularly well for those familiar with the WPS standard.

Routing API overview
Table A. Routing API overview (click for larger version)

WPS Profile API Overview
Table B. WPS Profile API Overview (click for larger version)

The pilot was successful in developing a proof of concept in record time (approximately three months). It defined a Route Exchange Model and a new API for routing that allowed several newly developed clients (desktop, web, or mobile) to make calls to any of the four different newly developed web interfaces which could in turn use any of three different routing engines – Truly Interoperable! Some routing engines also offered several possibilities in terms of routing algorithms or source datasets. In our next article, we will go explore the architecture of Skymantics routing engine developed during the Open Routing API Pilot.

Skymantics Universal Routing Engine (SURE)

Skymantics routing engine was designed following the Model-View-Controller (MVC) architectural pattern, combining three different main blocks, as shown in the following diagram:

  1. Model: The mapping data
  2. View: The web interface
  3. Controller: The routing algorithms, engine core and tools


Skymantics Universal Routing Engine (SURE) (click for larger version)

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.

Coming soon to the OGC Blog: Building an Interoperable Routing Engine (Part 2: Tips and Tricks).

OGC is currently in the process of creating a Routing Standards Working Group (SWG). For more information on the group see the News Item: OGC Members propose new Routing Standards Working Group; public comment sought on draft charter.  More information on the Routing Pilot, including video demonstrations of the outcomes, is available on the OGC Open Routing API Pilot page.

The Open Routing API was sponsored and led by the US Army Geospatial Center (AGC).

Note: images provided by Clemens Portele (Interactive Instruments)