The Middle Path for ETA Prediction — OSRM
In logistics domain, the ability to compute the shortest distance and time between two different points is a very basic need. We need it to build any sort of optimisation model or any conditional routing algorithm. However, complexities arise in fetching this information in an accurate, time-bound and a cost effective manner.
The most commonly method used here is the Haversine Distance Calculation Formula. To the ones unaware of this, it is a mathematical formula to compute the aerial distance between two geo-coordinates. ETA is calculated via this method by assuming a given speed and dividing distance by it. This method gives quick results at zero monetary cost however, it is inaccurate and unreliable in most of the scenarios. Following are the reasons
- It doesn’t take road network into account — No twists and turns, just the straight line distance
- It doesn’t take route traffic into account — It’ll give the same distance/ETA whatever time of the day it is
- Speed factor needs to be modelled to match ground reality
Having said that, it’s a good method to approximate ETAs when distance is in the orders of ~200–300m and is widely used in such use cases like fetching nearby cabs etc.
Next up is Google Maps Distance Matrix API . In most of the cases it gives the most accurate ETA between a given matrix of geo-coordinates. It takes into account the routing network, traffic and travel mode as well. However when we start building routing algorithms using this, following concerns come to fore
- Response Time — Since it is a call made to the Google server from our application servers, it takes somewhere around 100–150 ms for response. When computing large datasets and doing real-time operations, this is a pain point
- It’s Expensive! — In our use case, doing computation even for 10k orders/day, would cost us ~$3000 monthly. (Check out its pricing here).
Let’s now talk about OSRM — An open source routing engine which computes the shortest path between points in a given map (it does for any given graph). Written in C++, it is designed to run well with map data from the OpenStreetMap Project. Following are its salient features
- Incorporates Routing Data and Travel modes — It takes into account the major and minor roads, one-ways, driving or cycling routes etc while finding the best path. This map data is again open source and is widely enhanced by the community
- Response Time — This could be installed on your own private servers. While that allows you to manage its performance, it also results in a response time of ~5–10 ms
- Significantly Cheaper — All it takes is a server to host it. If you take a t2.medium from AWS EC2, it’ll cost you around ~$40 monthly (around 1% of what Google APIs would cost) and this is irrespective of the number of calls you make
- Incorporate Traffic Data — We can incorporate our own traffic data for a given geographical zone to customise and model the system better. Check this link to find out how to configure this via a CSV file.
In conclusion, OSRM is a good choice when you’re working with routing problems on a decent enough dataset . Its traffic data might not be accurate as that of Google Maps’s but the tradeoff w.r.to cost and response time does make a case towards usage of OSRM.
Do comment if you would like to add other better methods or have differing views from the ones shared above.
Update: Mar 7, 2018
We have had fantastic success with our routing engine to improve the efficiency of deliveries; asingle delivery partner carrying up to 6 different orders at a time.
