by Alex Sukholeyster, Vas Mylko
Ingeenee works together with the routing engine. This post digs into some details of our geo technology, initially described in the geo engine post. This post is a continuation, kind of part two.
Problem
We use geo engine for the following tasks:
- Get the nearest road by specific lat, lon coordinates.
- Calculate distance and drive time between given two points. Road-trip calculations are mostly based on drive-time, not distance, but some variables such as fuel cost are driven from direct mileage.
- Get driving directions (road details) and show the route on the map. We also use the pathway between points to get ‘en-route’ cities and attractions.
- Limit geo engine to specific region boundaries.
- Multi-modal routing. Get from A to B using a few means of transportations.
Open Source Map Data
Why not Google Maps, Mapbox or similar service? When we decided on what data source to use, there are two options: commercial or open source. Map services such as Mapbox or Google, have the most up-to-date maps, high quality, and excellent coverage but with high recurrent price, and limitations of usage.
The main reason why we pass on Google Maps and Mapbox routing services are terms of use that do not allow saving API call results. Pricing also needs to be considered wisely when planning for scale. We are using Mapbox for map tiles and our users are happy with a slightly customized light-grey map.
Mapbox uses OSM besides other data. OSM is community-driven high-quality map data, with somewhat limited coverage, and it is open source. We are glad to be story editors of THE BOOK OF OSM, check it out for the project history. Nowadays OSM node density is pretty high worldwide. Make sure you check out the beautiful interactive visualization of OSM. Below is a time-lapse video of making OSM for Japan for five years. The community effort is impressive.
Route-to-Routing Engine
For the routing engine, we started prototyping with pgRouting, geo library around PostGIS, which uses geo-enabled PostgreSQL. OSM data is loaded into PostgreSQL DB and converted into the relation road network. Then, to get directions or distance between two points, SQL query is used. It worked ok, but it was slow. Anita Graser’s blog is the main resource on pgRouting out there.
For better performance, we switched to OSRM. It’s open-source routing service, which powered OSM demo site, written in C++, high performance. OSRM provides tools to convert OSM data files into its own format, and OSRM server, accessible via web API. OSRM worked well for our needs, at least for the first 3 tasks. Limit of routing to the specific region and multi-modal routing became problematic. We started to look elsewhere for badass routing over OSM data, that could satisfy Touristportation 2020 needs.
Dynamic Routing
Imagine a user who forgets his passport and seeks a route from Detroit, MI to Buffalo, NY. The fastest route between these cities is via Canada. For a US citizen, it is required to use a passport when driving through Canada. There are many cases where visa requirements limit specific border crossing. Another case is a user intentionally seeking a road-trip within specific area.
When in doubt, use brute force.
— Ken Thompson
The brute-force solution is to create OSRM instance for each new region, but at some point, it does not fit server memory (memory footprint ranges between hundreds of MBytes to dozens of GBytes). After surpassing 200GB on single iron we decided to re-engineer the architecture (despite we could continue with 1TB memory).
When brute force doesn’t work, engineer new force.
— Ingeenee
Recently we have explored alternatives to OSRM, one of them is Valhalla. In early 2018 Tesla switched to Valhalla & Mapbox. Valhalla team is currently at Mapbox, but the Valhalla service, created by Mapzen company, is available as open source for anybody. You could check out Tesla’s fork of Valhalla. Valhalla provides similar functions to OSRM, with one benefit — Dynamic Costing. It allows us to implement routing within a custom region with a single instance of Valhalla service.
Latest version of our tech is available at https://ingeenee.ai
