How we reduced the cost of the Google Maps API by 94%

Striving to be a reliable partner for our customers, we at Cityflo We want to guarantee the high accuracy and predictability of our vehicle tracking system. Displaying the exact time of arrival is the great experience our users expect from us.

Problem
We use Google Advanced Directions API to calculate the travel time between two points. Google is the default choice, given the accuracy of real-time traffic data. We used this API to calculate the ETA (Estimated Time of Arrival) separately for each vehicle at each of its stops, individually calling the API each time the stop was registered. A couple of months ago, this API could be used for free.
After changing their pricing, working in the previous mode would cost us about $ 960 a day.
We assumed that there are 150 buses with 8 average stops, the average waiting time of which is about 20 minutes. This gives approximately 96,000 API calls. The Google Directions API costs $ 10 for 1,000 calls.
It was clearly an unrealistic option for us, since we are a young startup. We could slightly reduce the cost by reducing the frequency of updating traffic data, but this would affect the accuracy of calculating the arrival time. A sudden surge in traffic would affect our system too late, which was unacceptable.
We explored some open source alternatives such as Open street mapbut couldn’t get what Google does. Instead, we decided to stay on the Google Maps platform and rethink our approach.

Decision
Unlike taxis, our buses follow fixed routes, and all stops in the region are covered by several buses in the park. We determined the pattern of movement of vehicles. The developed scheme allowed us to calculate the travel time between the nearest stops, regardless of which bus was traveling. It was our architecture that significantly helped us separate the bus location updates from the calculation of the travel time for each bus, thereby reducing any redundant calculations.

If the bus connects the two nearest stops, we call them adjacent.
For example, suppose there is a network of stops shown in the following figure.

Here the pairs of adjacent stops are (A, B), (B, C), (D, C), (C, F) and (E, F). By calculating the travel time between neighboring stops, we can apply the same data to all vehicles. If the bus is at stop A and goes to stop F, then the arrival time at F can be calculated by summing the travel times (A, B), (B, C) and (C, F).
t (A, F) = t (A, B) + t (B, C) + t (C, F)
It goes without saying that there is no silver bullet here.
The catch is what happens when the bus is somewhere between stop A and stop B, how do we calculate its arrival time at stop F?

We decided to solve this problem using linear interpolation.

If we can determine the relative position of the bus between two stops, we can estimate the arrival time. For example, if a bus covered half the distance between two stops, it can be assumed that it would take another half time between these two stops to reach the other end.

The Directions API provides a broken line — a set of coordinates in a specific order — between adjacent stops, which helps us pinpoint the location of the bus. To increase accuracy during interpolation, these lines are adjusted to make them more uniform. For example, lines on straight roads are more sparse and vice versa. Thus, we provide a maximum of 20 meters between the two coordinates of the location to improve the accuracy of information.
Locating a bus on a broken line can be a difficult problem if the network of stops and the movement of the car are a bit confused. For example, if a bus registers a location at a bus stop while driving on the opposite side of the road, the system will fail. However, this story is for a separate post.

Result
This approach made API calls independent of the number of vehicles and dependent only on our stops, which helped us expand our tracked fleet at no extra cost. However, the cost here depends on the number of network stops. After several iterations of customization and adaptation for our use case, we observed a decrease in the cost of the Google Directions API by at least 94%.

What’s next?
We were able to make a workable system, but there is still a lot of work ahead. We can further optimize it by changing the refresh rate of various pairs of stops, observing the trends in movement between them. If the change in travel time between two stops is small, we can reduce the refresh rate and vice versa.
This was a very interesting issue for our team of developers and engineers. But we solved it and this helped us maintain a high quality experience at Cityflo, while at the same time providing continuous innovation.