OGC® Routing Pilot ER

The client is a desktop based QGIS plugin to support network routing. The goal was to provide the ability to easily compute and display new routes, fetch existing routes and share routes with other clients in line with the sponsor requirements. These routes are converted to QGIS layers for display and to allow users to input them into native QGIS functions, the data exchange was performed using the Route Exchange Model and the exchange format was GeoPackage.

QGIS was also chosen due to its extensive plugin customization and by request of the sponsor. The majority of this plugin capability uses PyQT, a python module for developing interactive interfaces. Once the PyQT capabilities were evaluated it was clear that this combination of PyQT and QGIS would provide the necessary functionality to produce the desired interface.

The design of the UI is broken down into five QGIS windows. The initial window (see Figure 7) allows the user to choose an API landing page URL to utilize. In order to account for both Option 1 and Option 2 of the Routing API this window provides the ability to choose which option to use when requesting routes.

The initial window also allows the user to choose offline routing or to open the sharing window. The offline routing option supports the Offline Routing Scenario described in previous sections.

If Option 1 or Option 2 are chosen, then a corresponding window is displayed depending on the choice.

The Option 1 choice opens a comprehensive input window (see Figure 8) for the user to input route options and request a route.

The Option 2 choice opens a window displaying all processes exposed at the API’s processing endpoint (see Figure 9). The user then selects a process, sees the description and choose to continue with the chosen process.

The previous step opens a third window which is dynamically constructed to provide the input options and request options for the chosen process (see Figure 10).

Both the Opening window and the Option 1 Input window provide the ability to open the Sharing Window (see Figure 11). Once the sharing window is opened the user can select layers in the QGIS panel or GeoJSON files to share. The routes can be shared by sending them directly to other clients using the QGIS plugin or exported as a GeoPackage for offline sharing.

This design provides the core functionality to create and visualize routes. It is expected that any extensions could easily be added by including an additional window, for example to create/edit routes manually.

In addition, the design ensures the functionality for Option 1 and Option 2 are distinct from one another, meaning the two capabilities could be de-coupled in the future if required.

The following challenges were encountered during the development of the client. Some of these challenges are implementation specific whilst others relate directly to the Routing Exchange Model and Routing API.

The QGIS Plugin supports an assumed user workflow; initially the user opens the plugin initial window Figure 7 and decides whether they wish to interact with an API or conduct offline routing or sharing. The sharing button opens the sharing window, the Offline Routing button opens the Offline Routing window, which leverages the routing engines, including the Open Source Routing Machine and the Ecere Routing Engine. If the user wishes to use an online routing API then the landing page URL is specified in the text input box. Following these steps the user can either choose to use the Option 1 API and click the 'Get Routing options' button or the Option 2 API and click the Get WPS options.

Once the Option 1 Get Routing Options button is clicked the plugin conducts the following steps:

The user then chooses the start and endpoint of their desired route by clicking in the map view using the Start Point and End Point input check boxes. During the Pilot, no address geocoding was implemented as it was out of scope. From here the user can choose to accept the faults or they can alter the other inputs to reflect their requirements. In the case of the obstruction input, when the user clicks the Obstructions button the current selected layer in the QGIS layer list is validated and chosen for input.

The method by which a route is requested is available in the drop-down list adjacent to the FIND ROUTE icon. This lists the supported options, based on the APIs conformance classes, which the user can choose to request a route. The default is polling Figure 4, other optional inputs include the API supported sync Figure 3 and callback Figure 5, as well as an additional method SSE (Server Send Events) Figure 6.

Once the user is content with their inputs they can click 'FIND ROUTE' to request the route via the proposed OGC Routing API. The plugin then conducts the following steps:

When received, the plugin converts the route from a GeoJSON Feature Collection to QGIS Vector Layers (see QGIS and Heterogeneous Feature Collections), adds the Vector layers in a group to the layer list and displays them on the map.

If the user instead chooses to click the Option 2 Get WPS options button the plugin conducts the following steps:

The user then chooses the 'Compute routes' process and clicks 'Choose Process'. The plugin then conducts the following steps:

The user then chooses the start and endpoint of their desired route by clicking in the map view using the way points checkbox. If the API supports other inputs the corresponding input elements can be changed by the user in the GUI to reflect their requirements.

Once the user is content with their inputs they can click 'POST to Process' to request the route from the OGC Routing API. The plugin then conducts the following steps:

When received, the plugin converts the route from a GeoJSON Feature Collection to QGIS Vector Layers (see QGIS and Heterogeneous Feature Collections), adds the Vector layers in a group to the layer list and displays them on the map.

The display of routes is customizable. At present the route and node features reference two styles on disk which the user can choose to update or change. Below in Figure 12 can be seen the full QGIS application, with the plugin loaded. In this image the route used as part of the TIE tests can be seen between the National Cathedral and the Washington Monument.

The corresponding inputs used to create the route can be seen in the plugin input box on the right hand side. The Nodes are represented by red points and the edges by red lines.

When using either the HERE routing Engine or the Offline OSRM engine, routes can be made outside of the District of Columbia as they are not constrained by the pilot test data. See Figure 13

The QGIS client plugin provides the functionality to interact with OGC APIs which support the proposed Routing API definition (both Option 1 and 2). The interface for Option 1 is detailed, allowing the user to tweak inputs, import obstructions from the native Layer List and retrieve existing routes from the Routing API. This is in contrast to the Option 2 interface, which is paired back and contains no cosmetic alteration. The Option 2 interface is built purely from an OGC WPS input list exposed by the Option 2 API.

In the case a connection cannot be established with the OGC API - Processes interface. The user also has the option to choose Offline Routing from the initial window. Once that option is selected a simple window opens allowing the user to choose between either OSRM (Open Source Routing Machine) engine or the Ecere routing engine. In addition, the user chooses their way points and a name for the route. Once the 'FIND ROUTE' button is clicked the route is calculated on the local machine and returned to the client that then adds the route to the map.

Future improvements include:

In addition to the QGIS client, a basic Cesium client was created. The QGIS client is designed to support most input types, handle all APIs and Engines and provide the required functionality for a route manager or dissemination function. In contrast the Cesium viewer supports only the bare minimum functionality and is intended to allow users to view routes that conform to the Routing Exchange Model, alongside 3D data. In this fashion the Cesium client compliments the QGIS client which cannot be used to visualize the routes in a 3D environment. The Cesium client uses the Cesium-provided Manhattan 3D Tiles Sample to demonstrate the route visualization through the center of Manhattan using the OSRM engine. 3D Tiles, based on the gITF transmission format, is an OGC Community Standard.

This client is designed as a web GUI to prove the concepts of the proposed Routing API and the underlying proposed Routing Exchange Model. This web client is also implemented as an embedded desktop application to ensure the ability to demonstrate offline routing scenario.

The main challenges encountered and their solutions discussed here were describing the conformance class and the dynamic GUI generation:

The Routing API provides the endpoint of the "/conformance" path to support discovery of the capabilities of the endpoint. The descriptions of the conformance classes reflect the parameter settings on the client GUI. To make this automatic generation work, the parser of the conformance classes on the client is required.

The Routing API provides different approaches of endpoint implementations. The client must also provide two different workflows and parsers to invoke the endpoints and digest the results. The Routes option is a more intuitive modern web design for resource access while the WPS option requires more basic and in advance knowledge about understanding the WPS to deal with the input, output and process elements. The WPS option supports the asynchronous execution (async) mechanism natively in the WPS implementation while the Routes option requires a developer implement an asynchronous mechanism like callback in advance. Both the Routes and WPS options use Routing Exchange Model, and the client can reuse this model parser.

The Routing API supports synchronous and asynchronous execution. The client must design different workflow to handle job waiting (WPS option) or callback (Routes option) of the async approach.

To provide the offline scenario, the client was also designed to run offline. The approach of this client was to use a C# WebBrowser component to embed the client as a desktop application.

When the client runs as a desktop application, the base map switches to the local OSM tiled vector data for better performance.

When losing the internet connection, the client relies on the local routing engine to compute the routes. The local routing engine is an OS dependent library or command line program.

The technical details are described in the following section.

Ecere built a cross-platform mapping and routing client application featuring a 3D view. This was done leveraging the Ecere GNOSIS geospatial software technology.

A simple graphical user interface was developed allowing the selection of the routing points, the components, the algorithms and the parameters to use for the route calculation.

The client was used in multiple Technology Integration Experiments (TIEs), including both online and offline scenarios. This was done to support connecting to multiple open routing API services to perform route calculations, using the proposed Route Exchange Model.

The resulting routes were visualized in the client, and situated in a geospatial context with a number of available data layers. This included 3D content such as digital terrain elevation models and 3D buildings, background imagery, as well as styled and dynamically labeled OpenStreetMap vector data.

The experiments involved components from different participants, combining the client capabilities with a variety of processing services endpoints implementing the Open Routing API (Ecere, Skymantics, Helyx, 52° North and GIS-FCU), three different routing engines used for computing the routes (Ecere, Skymantics and HERE), and different source data for the roads network used by those calculations (OpenStreetMap, HERE and NSG).

The large number of combinations tested, together with the new and evolving nature of both the Open Routing API and the components implementation, as well as the compact schedule of the pilot, posed many challenges. This however, resulted in improvements to both the API description and the components implementation.

The simplest scenario is the fully disconnected use case, where the client application embeds the Ecere routing engine and OpenStreetMap roads network data and makes use of them internally. As the client can also visualize compact optimized maps offline, this approach works in all DDIL environments, as both the roads network and maps to display was preloaded.

The client can also connect to online Open Routing API endpoints which will perform the route calculation. The communication mechanism between the routing client and the routing endpoint is defined by the Open Routing API specifications designed during the pilot. The client sends out an HTTP POST request embedding a JSON object with the parameters of the route calculation to perform.

The data visualized in the client came from multiple sources and formats:

While conformance classes are useful for communicating the capabilities of services, their expressiveness is not enough to convey the information needed in the use cases described in this Pilot. The architecture of a distinct service per engine (see Final Component Description) was ultimately chosen to compensate for the difference in supported inputs and parameter values across engine implementations.

For Example, the HERE engine does not support the selection of the source dataset but is fixed to the usage of the HERE data, while the Skymantics engine is able to operate on the NSG, HERE and OSM datasets. If a service offers both engines via the 'engine' parameter it has to decide if the 'http://www.opengis.net/orapip/routing/1.0/conf/source-dataset' conformance class should be listed or not. If the client decides to conform, the route calculation will fail, either silently or with an error message, if a client selects the HERE engine and the OSM dataset. If it chooses to only list conformance classes that are valid for all engines, a client cannot assume that the parameter is supported by any of the engines without out-of-band information.

By having one API endpoint for each engine, and by such one conformance class declaration for each engine, clients can refrain from using out-of-band information or issuing possibly invalid requests, but can solely rely on the information the service offers.

For the most part, this only concerns the simplified Routing API and not the OGC API - Processes option, as the conformance classes are solely created from the process descriptions. As these only list the supported inputs and allowed parameter values, clients have all the information they need. One exception is the 'http://www.opengis.net/orapip/routing/1.0/conf/intermediate-waypoints' conformance class, which cannot be expressed using the standardized process description, as there is no way to describe how many points are required or allowed inside a GeoJSON 'MultiPoint'. One solution to overcome this would be to split the 'waypoints' parameter into three distinct parameters as it is done for the internal processes.

All routing engines support the 'core', 'callback', 'delete-route' and 'sync-mode' conformance classes as these are not engine specific but implemented within the proxy.

The Conformance classes of the HERE routing engine additionally list the optional 'max-height', 'max-weight', 'obstacles', 'time' and 'intermediate-waypoints' conformance classes as these are supported by the HERE engine.

The Conformance classes of the Skymantics routing engine additionally lists the optional 'routing-algorithm' and 'source-dataset' conformance classes as these are supported by the Skymantics engine. The supported values of these parameters are generated from the input description of the process.

If all three engines were combined in a single API instance (see Potential conformance classes of a single API instance), the service would have to list the conformance classes of all engines. With this approach the client has no way to determine if a parameter is really supported by the chosen engine. According to the conformance classes, the client is allowed to issue a request using the HERE engine and the OSM source dataset. As this specific combination is not supported the API would have to return an error or fail silently.

During the pilot the following shortcomings in the current draft of the OGC API - Processes were identified.

There are two ways of defining an allowed range for a literal input of a process. The range can be defined using the 'allowedRanges' or using the 'allowedValues' in the 'valueDefinition' of a 'literalDataDomain'. While the former approach supports only ranges, the latter also supports the definition of values (see Redundancy in the OGC API for Processes description language. Both, 'allowedRanges' and 'allowedValues' allows the definition of ranges). The Pilot participants recommend that the 'allowedRanges' approach be removed from the draft specification.

There is a risk of redundancy when specifying an input that can occur an unlimited number of times. Table 16 of the WPS 2.0.2 standard (14-065r2) indicates that the default value for both the minOccurs and the maxOccurs attributes is 1. In contrast, the draft OGC API – Processes specification does not explicitly state the default values of these attributes. This means that there could be a risk of omission of the 'maxOccurs' property being interpreted as 'maxOccurs' set to unbounded (see Incorrect interpretation of 'maxOccurs' omission and 'maxOccurs=unbounded' as meaning semantic equivalence). The former approach has the benefit of using just one type for the 'maxOccurs' key instead of allowing a 'string' or an 'integer, and is therefore recommended. It is recommended that the editors of the OGC API – Processes specification clarify that the default value for both the minOccurs and the maxOccurs attributes is 1.

Many JSON libraries are able to automatically parse JSON objects into language specific structures or objects. One example of this is the popular Jackson library for Java, which can convert between JSON and annotated Java classes. The current draft version of the OGC API - Processes specification makes extensive usage of the 'oneOf' keyword of JSON Schema. This allows for the definition of multiple alternative schemas for the same property or object. While there is support for this kind of approach, libraries most often rely on discriminator values to determine the actual type of the object.

For example, the 'input' property of an inputs element can contain three different objects (see Different input types of the OGC API for processes).

The concrete type can only be determined by the existence of distinct property names (i.e. 'literalDataDomains', 'supportedFormats' and 'supportedCRS'). This approach is unsupported for most of the popular frameworks and requires manual type conversion or custom parsers. The same applies to the 'valueDefinition' of 'literalDataDomains' where the concrete type is determined by the JSON type (i.e. a JSON array denotes an 'allowedValues', a JSON object with the 'allowedRanges' property denotes an 'allowedRanges', any other JSON object denotes an 'anyValue' and a JSON string denotes a 'valuesReference').

Further, the semantic meaning of specifying '"valueDefinition": { "any": "false" }' is unclear.

Thus, adding discriminator values to the relevant entities of the specification is highly recommended to add discriminator values to the relevant entities of the specification (see Different input types of the OGC API for processes with type discriminators for an example).

The current draft of the OGC API - Processes specification only supports the retrieval of all results of a process in a single document via '/processes/{processId}/jobs/{jobId}/result' (see below). This approach does not support sharing the result of a route computation without additional logic on the recipient side. A possible solution to this would be the definition of an additional endpoint (like '/processes/{processId}/jobs/{jobId}/result/{outputId}') to directly retrieve the result.

Each routing engine implementation is encapsulated in a single WPS process. Their process descriptions only specify the inputs and parameter values that are supported and enable clients to execute the processes without any prior knowledge of the underlying engine. While the processes are very similar to the specified routing process, they differ in some key points from the routing engine capabilities:

To achieve compliance with the routing specification, a Spring Boot application was developed that can proxy the process. The application implements both specified options, the OGC API for Processes with a single routing process and the simplified Routing API. The actual route computation is delegated to the WPS process, while the proxy is responsible for the persistence of routes and route definitions, the conversion between route definitions and execute documents, handling of synchronous computations and callback handling. Besides this, the proxy splits the supplied 'waypoints' parameter into its internal representation as three distinct parameters.

The WPS supporting the Routing API is divided into two options - a WPS option and a Routes option. In order to reduce the implementation overhead and duplication, this implementation was created based on a WPS kernel, and reused this kernel as the other option - Routes.

The draft Routing API provides two sets of interfaces but similar data structures (Routing Exchange Model). In order to reduce the implementation overhead, the API was designed using the following structure.

The Routes option shares the same functions as the WPS option, but uses a different RESTful Profile to fulfill the definitions of the Routing API.

This WPS implementation successfully connects to three different engines - HERE, Ecere, and Skymantics. Further, three different datasets - HERE, OSM, and NSG were available.

The conformance classes are the place to harmonize the client and the service without fully understanding the entire specification in advance. The format of the conformance class must be simple and clear. This WPS used the "one endpoint for all engines" approach to offer the routing services. For example, see the following listing.

The client can very easily parse the conformance class and generate the routing parameters on the client side. The downside of this approach is that the engine might not support specific algorithms or datasets, and the client would as a result receive an HTTP 404 error response which might lead the client to be confused by the error handling.

Java was the language of choice for the Skymantics server development, utilizing the Spring Framework (https://spring.io) for RESTful API design. The Framework’s large community of support and simple implementation allows for quicker development time with an operational standard. An additional use of Spring is its capability to rapidly test new implementations required in this pilot, including both internal to the WPS and from external members due to its embedded servlet. Maven was also chosen as the build tool of choice, due to both developer familiarity and its robust plugin options. The WPS implementation was deployed on an Azure Container instance. A Docker image of a Tomcat 9 Linux server was used as a baseline, with the application Web Archive (WAR) file and the relevant production libraries included. This containerized image was then deployed on Microsoft Azure’s Container Instances. This allows for ease of deployment in a production environment, and also could allow for other providers to implement their own container on separate hardware.

The WPS needed to be able to take a variety of conformant JSON, including GeoJSON, and respond in the appropriate manner. As such, request Model classes needed to be made in order to perform request validation and any additional processing.

In addition, two API Options were proposed during the Pilot kickoff - the more codified WPS Option, and a less verbose Routes Option. This meant that any request to the WPS could be different, but must be handled in the same fashion regardless of input. To facilitate this, Skymantics implemented two different endpoints a client could submit requests to:

Initially, some increased development time was required. This was due to the requirement for both a simplified Route option and a more complex WPS option, as some properties of a more enriched WPS option may not exist on a simplified option (such as Units of Measurement). However, different implementation methods have yielded important insights into OGC API development. A complex Routing Model requirement such as Option WPS led to increased code complexity and therefore development time; However, this complexity reduces the amount of out-of-band information required by the client application to appropriately communicate with the various routing engines implemented in the pilot.

Two forms of endpoints to this WPS were postulated, conforming to a less stringent Routes form (AKA Option 1) and a heavier, more generic form WPS (AKA Option 2). Both forms of requests and their accompanying markup are accepted by the WPS. Internally, the input received by the WPS is serialized via Jackson JSON library into a Route object. This representation inherits from a generic ProcessInput abstract class specifying properties not exclusive to routing, such as MimeType of the request, a name, etc, as per the WPS standard. If the Route conforms to the input specified by the WPS process offering, a Job is then generated by the server, with an accompanying JobId. This job is then passed to a JobHandler singleton, which orchestrates all HTTP requests to a routing engine. Apache’s HTTP Commons library was used to facilitate communications between the WPS and the relevant Routing Engines. This includes a multithreaded, non-blocking input-output offering in which requests may be made synchronously and returned to the end client, or alternatively returned asynchronously.

The asynchronous communications approach utilized Apache’s HTTP Commons library to achieve asynchronous callback functionality of web request / responses and Google’s Guava library to provide a cache of currently running route operations. When a Job is created and the Asynchronous option is indicated, a callback method on the HTTP communication classes insert the response of a particular routing engine into the value of the Cache for a given job key. Consequently, a user may access this result up to 20 minutes after a result has been inserted into the cache. After this time period, the record is expunged from the data structure to reduce memory footprint on the server. These implementations are the same regardless of which markup Option is indicated by the user- there is no delineation between Routes. As the Route Object is a subset of Jobs, and the Route Model is of a Job Result subclass, both response to the end client are of the same type, and therefore agnostic to both the WPS Cache and the End user- The WPS handles Option 1 requests the same way it would handle an Option 2 request, and responses to the client are the same Route Model response regardless.

The Jackson Java library was utilized to validate and transform the received Route Model request to a strongly-typed Route object. Validation of parameters and GeoJSON structures are conducted, and any missing parameters are defaulted to predefined values (such as using A* as a default algorithm, or using Skymantics Routing Engine if none is specified). This Object is then deserialized back to JSON and sent to the specified Routing Engine, with additional requirements if it is a bespoke API non-conformant with the Route Model.

The WPS also has HATEOAS capability, where route requests in an asynchronous manner return their respective API options, such as result endpoint and status endpoint.

The goal was to implement a scalable, robust and performant WPS with a rapid startup time. To enable this, Helyx used a microservice approach and chose Option 1 to build the server against. Option 1 suited a microservice approach better than Option 2 as Option 2 is monolithic in nature due to the required amount of inputs. However Option 2 could be treated as a gateway with intelligent routing, filtering and service discovery. In which case, the WPS acts as a gateway to broker with the processes deployed as separate microservices. However, in doing so we would lose the benefit of OpenAPI definitions which Option 1 provided.

For the Option 1 implementation Helyx used Kotlin, a Java Virtual Machine language by Jetbrains which has proven to be useful in building robust solutions. Given one of the goals for the implementation was performance, Kotlin has a number of benefits. The conciseness and performance of Kotlin allows for a non-blocking approach to development, improving performance and robustness.

The Kotlin microservice was built on top of a native web server and placed in an Uber JAR, that is, a JAR file that contains all of the dependencies. This Jar file was placed in a Docker container with environment variables to allow for scalability, which enabled exploitation of a relatively small memory footprint and fast startup time. This was achieved using a configuration management tool called Ansible.

A number of serialization utilities were used in the implementation including Jackson and Moshi. Moshi was used to satisfy a requirement for polymorphic data objects to mirror the polymorphic nature of option 2. An additional requirement was a lightweight Publish-Subscribe pattern embedded into the API, this design pattern provides a subscriber URI for a client to POST the data to when the route is ready to be consumed.

In the final representation of the API, the landing page conforms to the draft OGC API - Common specification in most aspects except the routes URI which has POST, GET and DELETE capabilities to modify a resource. At this point the OGC API - Common specification does not yet consider POST and DELETE capabilities.

Another method of execution was implemented named Server Sent Events (SSE). As mentioned previously, Server Sent Events are a hybrid approach much like a websocket where a consumer subscribes to a connection with the API after initializing a request and following the link in the location header. The API then forwards the resulting route through this tunnel-like connection to the client. This implementation is useful as another method of execution to provide streaming functionality to consumers without websocket capabilities.

As this service is open to the web, the service would need a secure authentication option. The current implementation of the Helyx WPS provides a basic internal Access Management via request headers. With the current implementation, a client application can provide a user id when making requests and the service will authenticate based on those credentials. A future improvement on the basic implementation is to implement authentication using a token-based(Jwt) approach for Access Management.

The application was briefly load-tested using the HERE routing engine and had interesting results. With 10,000 concurrent requests over a minute the service handled well with only 300mb of RAM usage. The bottleneck is listing the resources in the '/routes' URI, due to this being a large array. A large array only allowed a browser to display ~12000 elements and when submitting the request with Postman the response was never received, even with GZIP compression in place. This testing demonstrates that while the routing API is robust, the significant quantity of resources proves to be a limitation for consumer applications. Potential solutions could include:

Any solution would have to be accounted for in the specification.

Future improvements to the draft Routing API could include:

The scope of the Skymantics routing engine was relatively broad; extracting data from two different datasets (OSM and NSG) and trying several flavors of the Dijkstra (well known shortest path) algorithm. The scope was later extended to additionally cope with HERE data and the A* algorithm family. The A* algorithm is a routing process based upon nodes, its significance is that it routes by finding the vertices that are closest to the destination, rather than the start point. In order to be able to stretch the scope as much as possible within the project timeframe, the top priority for the design of the routing engine was rapid prototyping. Performance was considered secondary and was only addressed at the last stages of the implementation.

Python3 was chosen as the language to implement the routing engine. This allowed use of as many available off-the-shelf libraries as possible, such as Fiona (to extract data from the GeoPackages) https://pypi.org/project/Fiona/, Vincenty (to calculate distances) https://pypi.org/project/vincenty/, or json (to create the geojson output based on the Routing Exchange model defined in the pilot) https://docs.python.org/3/library/json.html , among others. The data extraction process was designed to store the data on roads and junctions in separate MySQL databases using a common, pre-processed data structure. This structure describes the road mesh in terms of a graph and it includes nodes, edges, shortcuts, and additional information to process route restrictions or to generate the draft Route Exchange Model. By using this common data structure, a route could be calculated in the same way, independently from the dataset it originated from, whether OSM, NSG or HERE. This facilitated the comparison of routes from different sources.

In order to have full control of the implementation, the routing algorithms were built from scratch, without the use of external libraries. Three different options were considered from the start for each algorithm family:

The route engine works in four different stages:

Ecere built a routing engine for calculating routes using the OpenStreetMap dataset. This engine is named OSMERE for OpenStreetMap Ecere Routing Engine.

Ecere decided that it would implement the A* algorithm, and work with a road network constructed from OpenStreetMap data.

The engine was to be used in Technology Integration Experiments with components from other participants including both online and offline scenarios. To do so it produced a GeoJSON object according to the Route Exchange Model, including an overview of the whole route and a description of the road segments with properties indicating the name of the road, the distance (in meters), the duration (in seconds) and the speed limit (including a unit specifier).

Consideration of the acceleration/deceleration time, stop signs and traffic lights as contributing to the route duration was deferred for a future version.

Parameters specifying a preference for fastest or shortest route, additional waypoints, as well as weight or height restrictions were also supported, while the ability to specify obstacles to avoid was planned for future improvements.

The engine was also designed to take into account restrictions such as one-way streets and roads not accessible to motor vehicles.

In order to achieve optimal performance and complement Ecere’s GNOSIS geospatial software technology, the Ecere Routing Engine was written using the eC programming language and compiled natively. The engine was also designed with scalability considerations in mind, such as the ability to distribute the computation of roads to parallel threads running on different CPU cores.

The roads network was assembled from original OpenStreetMap data sourced from the .osm.pbf format. First, the Protocol Buffer encoding was decoded into multiple vector data layers, stored in a GNOSIS data store consisting of a series of tile pyramids (each containing multiple GNOSIS Map Tiles encoding of the features), as well as associated attributes stored in SQLite databases. This data store was also used by the Ecere client for visualizing the OpenStreetMap overlays.

One of these resulting layers contains (Multi)LineStrings vector features representing all roads. A network graph is then constructed from these roads, with nodes at the end of each segments, in effect more closely resembling the original OpenStreetMap data model consisting of Nodes and Ways than the Simple Features representation. This network construction required a very minimal amount of preprocessing and can be done quickly on-the-fly, but a much more optimized version of the engine may later be a little more involved.

GeoPackages of the roads network sourced from the OpenStreetMap dataset were produced by Ecere. However, the pilot participants decided that the definition of a standard GeoPackage layout for use by routing engines was out of scope given the compact schedule. As a standardized format was not yet defined, and since GeoPackage was neither the source data format used by our engine, nor the representation that the routing engine directly works with, the functionality to build the road network graph from GeoPackage was not prioritized. Considerations for such a format however are included in the recommendations section, and once a consensus is reached, support for implementing that import process will be added to the engine.

As OpenStreetMap data is crowd-sourced by a very diverse global community. As such there sometimes is a lack of consistency in how features are tagged. In order to properly implement road access restriction, an analysis of the tags available for the source data had to be conducted, in conjunction with consulting the OpenStreetMap wiki entries describing how the tagging should be done and how to interpret it.

In addition to the tags considered while selecting the nodes and ways to include as part of the roads network data (e.g. the presence of the 'highway' tag), other OpenStreetMap tags were also taken into account for returning the name of roads, the speed limit, height and weight restrictions, as well as access restrictions such as one-ways roads and usage type. Although all routing experiments so far were only done for motor vehicles, road access was categorized based on whether pedestrians, bicycles and/or motor vehicles could use any given way. The following summarizes the OpenStreetMap tags taken into consideration and their interpretation by the Ecere Routing Engine. It is to be noted that this is still at a very early experimental stage, and may be partially incomplete or wrongly interpreted.

highway

The presence of the highway tag is used to identify an OpenStreetMap Way as being part of the roads network graph. Default usage access and speed limits are also associated to the different values for this key, but could be overridden by other tags.

oneway

If specified and the value is anything other than 'no', the road is understood to be traversable in a single direction. Separate one-way restrictions for different road usage types (pedestrian, cycling, motor vehicles) were not yet implemented. Note that value of '-1' and 'reversible' were encountered in the dataset, but not dealt with specifically.

maxspeed

If provided, the value replaces the default speed unit. This element is currently being interpreted as miles/hour unless it contains the letters 'km'. Ideally, the default would be based upon the country in which routing occurs.

maxheight

Interpreted as the maximum height for a vehicle to be allowed access to a road. If this element contains the letter 'm', height is interpreted as meters; otherwise the height is specified in feet, and numbers following a single quote are interpreted as inches.

maxweight

Interpreted as the maximum weight for a vehicle to be allowed access to a road. If the element contains the letters 'lbs', it is interpreted as pounds; if the element contains the letters 'kg' it is interpreted as kilograms; otherwise the element is interpreted as US tons.

cycle, bicycle, cycleway

If the values for any of these is 'yes' or empty, cycling access is enabled. If the value is 'no' or 'private', it is disabled. If the value is 'designated', cycling access is enabled, while pedestrian and motor vehicle access is disabled.

steps

The presence of this tag disables cycling and motor vehicle access, and enables pedestrian access.

foot, footway

If the values for any of these is 'yes' or empty, pedestrian access is enabled. If the value is 'no' or 'private', this capability is disabled. If it is 'designated', pedestrian access is enabled, while cycling and motor vehicle access is disabled.

vehicle, motor_vehicle, motorcar

If the values for any of these is 'yes' or empty, motor vehicle access is enabled. If the value is 'no' or 'private', this capability is disabled. If the value is 'designated', motor vehicle access is enabled, while cycling and pedestrian access is disabled.

bus, taxi

If the values for any of these is empty, 'yes', or 'designated', motor vehicle, cycling and pedestrian access is disabled.

railway

If the values for any of these is 'yes', or empty, motor vehicle, cycling and pedestrian access is disabled.

access

If the value is 'no', 'private', or 'restricted', motor vehicle, cycling and pedestrian access is disabled.

Consideration of more specific restrictions (e.g. "no left turn"), as described by the "restriction" type of OpenStreetMap relations, have not yet been implemented. Where properly mapped in the data set, this offers full detailed description of different types of restrictions, including time-dependent (hourly and daily) restrictions. Some restrictions are described as 'from' and 'to' ways, while others are 'via' a node or a way.

OpenStreetMap describes the Relation:restriction.

Ecere provided a "bare-bones" online routing API which processes routing requests using the Ecere Routing Engine. Other participants also deployed Open Routing APIs implementations which passed routing requests to the Ecere Routing Engine through this endpoint.

In addition to the online endpoint, the Ecere Routing Engine was also made available to other participants as a Command Line Interface executable for Linux and Windows platforms. This enabled its use in offline scenarios by other client applications, but could also have avoided an extra server roundtrip in other routing endpoints, resulting in a faster response time. A library version of the engine was also proposed, which would be optimal in a server-side integration for loading the road network only once, then issuing multiple routing requests to the engine.

An important current limitation is that when identifying start, end and intermediate waypoints nodes, the engine snaps to nodes in the graph as opposed to being able to use a point on the road in-between two nodes. This can result in snapping to a street closer to the requested point, and not an intersection further away, while the ideal approach would be supporting calculations to that exact position on the road as requested.

In addition to the main test area of Washington D.C., experiments were also done with larger amounts of data from OpenStreetMap, including the entire state of North Carolina, as well as large regions in Japan. These larger datasets allowed to put the routing engine’s performance to a more stringent test and really showcase potential. Despite the early stage of development, the performance has proved to be quite satisfactory.

The limited availability of computing resources in mobile and embedded environments, as well as under heavy volume of requests in processing servers, is mitigated by the fact that the Ecere Routing Engine was designed with high performance in mind.

A further optimized version of the engine should be able to achieve even better performance and leverage multiple CPU cores, with an end goal of calculating continent-wide routes from a worldwide OpenStreetMap dataset in just a few milliseconds.

An improvement planned to be achieved in future activities is taking elevation from a Digital Elevation Model into account for calculating energy efficient routes.