August 26, 2020 • 6 min read

Elevation Aware Routing

The routing problem focuses on how to get to a specific destination and how long it will take. rideOS’ Routing Engine solves this problem by computing routes and ETAs both for autonomous and human-driven vehicles and managing the data needed for that.

 

But are there not other services that provide routing solutions?

At rideOS, we are focused on building an engine that is flexible to meet the needs of our customers. We bracket our customers’ needs into two major buckets:

  • Increasing the accuracy of ETAs to make better dispatch decisions.

  • Easily customizing your routes to increase ETA and path accuracy.

In this blog, we focus on improving the latter by enriching the engine with elevation data of the whole world.

 

Customization of Routes

The heart of our routing engine lies in computing the correct cost function for our customers’ needs. These cost functions are designed based on the underlying map, traffic data and user-defined constraints.

 

So, how does a customer customize their route planning?

The routing engine offers a variety of customization options:

  • Constraints Data API (Eg: allow/exclude certain streets and areas, avoid specific vehicle maneuvers)

  • Tunable knobs for path selection (Eg: shortest path, fastest path, turn cost)

  • Tailored ETAs for specific use cases.

In the existing setup, the engine can answer these customized routing queries while it treats the world as a flat surface.

 

The Elevation Problem

As we move from a flat topology of the earth to an elevation-based one, it opens a whole new set of problems for us to solve.

A few examples are:

  • Scooters exerting higher pressure on their engine to power through an incline

  • Restricted roads for trucks based on the inclination of the road

  • Charge-efficient paths for electric vehicles

Until now, our routing engine was not aware of the elevation, thereby limiting the customization capabilities of the system. My internship project at rideOS was focused on enhancing the routing engine with this knowledge.

 

Elevation data to the rescue

The routing engine was made elevation-aware by leveraging NASA’s Shuttle Radar Topography Mission (SRTM) data which provides a high resolution (1 arc-second, or around 25 meters) and has near-global coverage (from 56°S to 60°N).

We massage and store this data into our global data store (Planet) using an independent pipeline to make it source agnostic for the Planet’s clients. It provides us the flexibility to change the elevation data source to a more accurate one in the future. The elevation data from Planet is used to enrich the graphical representation of our underlying maps which serves as the source for routing decisions.

For a visual reference, we compared the global topographic (elevation) map produced by a third-party app with the elevation data from Planet and found it to be pretty similar.

(1) : Global topographic map from Planet, (2) : Global topographic map from third party app

 

My Learnings

As someone new to the maps and routing domain, there was a good learning curve involved in the process.

  1. The SRTM data was available in the big-endian encoding as opposed to the common little-endian encoding.

  2. The data resolution was 1 arc second (25 m). We used bilinear interpolation as an interpolation technique to fill in the gaps.

  3. The SRTM tile size was large for processing and using it as such was not so efficient. Hence we decided to split the data into smaller tiles. Finding the optimal size considering the factors of compression, data duplication and making efficient spatial queries piqued my interest.

  4. Using the idea of S2 cells (based on Hilbert curve) for range queries.

  5. We leveraged parallel processing to improve the speed of the elevation data ingestion process considerably.

After having the elevation data available in our routing engine, we conducted a couple of experiments to demonstrate how the elevation information can be useful.

 

Case study 1 : The Wiggle in San Francisco

The famous Wiggle in San Francisco is “one-mile, zig-zagging bicycle route from Market Street to Golden Gate Park, that minimizes hilly inclines for bicycle riders”, as shown in this below map:

The Wiggle route

 

First, let’s see what our routing engine returns without elevation enabled, just using shortest distance routing. It finds the shortest route, which is up the very steep Duboce Ave as shown:

Route between Market Street and Golden Gate Park and its elevation profile using the shortest route.

 

Now let’s use a cost function that minimizes the elevation gain. The below images shows the path returned and the corresponding elevation profile.

Route between Market Street and Golden Gate Park and its elevation profile minimizing elevation gain.

 

As you can see, the routing engine now returns the wiggle which has minimum elevation.

Yes!! We could reproduce the wiggle.

 

Case study 2: Travel across US (Los Angeles to New York)

For something a bit more challenging, we tried finding the route from Los Angeles to New York using different cost functions:

 

(a) Minimize total elevation gain

The same cost function(to minimize the elevation gain) from the wiggle case study was used. The result is a 5,205 km route with a maximum elevation of 2,090 meters.

(1),(2) : Route from LA to NY minimizing total elevation gain, (3) : Elevation profile for this route

 

The topograph shows the route crossing the mountainous Continental Divide (colored in brown).

The route still reaches a peak elevation of 2,090 meters, since it needs to traverse the mountainous Continental Divide. What if we want to find the route from LA to NY that minimizes the maximum elevation reached?

 

(b) Minimize maximum elevation reached

We then modified the cost function to minimize the maximum elevation attained in the path. Since there is an almost continuous sequence of mountain ranges from Alaska in the north to the southern tip of South America, the solution is non-trivial:

(1), (2) : Route from LA to NY minimizing maximum elevation, (3) : Elevation profile for this route

 

As seen the route now avoids the mountainous Continental Divide. The total route length is 8,460 km, with a maximum elevation of 798 meters.

As seen in the 2 case studies, we can modify the cost function based on use case to return routes that take into account the elevation information of the earth, thus solving the elevation problem.

 

Towards a happier future

Woohoo!!! The routing engine now knows about elevation. Once we have customer inputs on their requirements with elevation data (Eg: if a customer sends a fuel level or charge level with the routing request, based on that fuel/charge level, we adjust the route taking into account the elevation of the path), we can design cost functions accordingly. This will help us in offering greater flexibility to our customers who can further customize their routing solutions. They can improve their ETAs, calculate and optimize for fuel efficiency, and optimize routes for bikes, scooters or pedestrians.

If you are interested in using the rideOS platform to power your vehicle fleet, please follow us on Twitter and reach out to contact@rideos.ai if you have any questions!