How to decrease costs for google route service

In this rapidly developing world, there are more and more services that require calculating travel time. Often we order something at home, be it a massage, a workout with a personal trainer, a hairdresser or make-up artist, or even a meal, and we would like it to be done at an agreed time. But the company that provides us with these services must also take into account the time that will be spent on their employees’ transportation to work as efficiently as possible.

During the development of one of our projects, we were faced with a requirement of the customer to have such an opportunity, but without the daily costs of using third-party services, so we came to this solution.

Business case description

In the existing system of delivering “services from a specialist to a client’s door”, it became necessary to add an approximate calculation of the time required for a specialist to travel from one client to another. The system has a calendar in which each hour is divided into 15-minute segments, which allows you to order service for a specific time. When choosing a specific service, the system should calculate the time of the specialist’s journey to the client and display the specialist’s availability information to the client. It is also necessary to take into account that in the system, there may be pre-orders of a specialist.

Ideas with pros and cons

There are 2 main ways to solve the problem:

• Use offline maps.
• Use APIs of various third-party services.

The first method involves connecting an offline city map, which should include data about the direction of traffic on the streets, the travel speed trend of traffic on the streets, and the length of each street. Then, with the help of this amazing article, we have to calculate on the fly a path for every route, between points A and B, for many specialists and also take into account existing pre-orders. So we excluded this option for several reasons:

• Availability of the offline maps with the required information;
• Simple service activation for a new city;
• The time cost of a request;
• Duration of implementation of this solution into the system.

The second option is to create a request to one of the existing services for calculating the time, to receive a response. We reviewed several options, among which were the:

• Google Distance Matrix,
• Mapquest Route Matrix,
• Microsoft Bing Route API,

and decided to choose the service from Google because our system already uses other services from the Google Cloud Platform. Better to control everything in one place, right? At the same time, it is necessary to take into account that every time a customer requests a service, the system will produce a request for all specialists in the entire city each time, even if the service is not eventually ordered but “just to see”. We used the Google Distance Matrix, which can calculate the travel time between 25 elements i.e. an address or a coordinate in a single request.

But the cost of this service’s usage exponentially increases with the number of clients and it becomes too costly. So what was the solution to this we came up with?

Our choice

Inspired by the idea of distance matrices, we decided to create a so-called transport grid with similar functionality. In our work, we used PostgreSQL + PostGIS + PG Routing. We show the logic on the example of Zurich:

First, we need to determine the boundaries of the city in which the calculation will be made, as well as the “density” of our transport grid. The higher the density is – the higher the accuracy, so, taking into account business requirements, there is a choice for everyone. For example, we decided to create a grid in 1 km increments (in the production version, we used 500m).

The red dots in the picture are ‘transport nodes’, the geographic coordinates equidistant from each other, which are represented by real addresses in the city border area. Also, around each transport node, we built a polygon with sides of 1km x 1km for further calculations. In the picture, these polygons look rectangular because they are displayed in the WGS 84 coordinate system.

Using the capabilities of the Google Distance Matrix, we can calculate the distance and travel time between adjacent transport nodes. Let’s create connectors between the nodes that will store the received data. We received such results:

• Travel_time – path time value returned from a third-party service
• Travel_distance – the value of the actual path length returned from a third-party service
• Linear_distance – the value of the length of the path “directly”

As you can see, for some Linear_distance values, the Travel_distance value varies from 1300 to 3200, a significant difference, isn’t it? Let’s try and do something about it.

As can be seen from the figure, the red lines divide the polygons of the transport nodes into small triangles with sides of 500 * 500 * 707 (for the production version, it’s already 250 * 250 * 353). Let’s create polygons with vertices at the intersection points.

Suppose that the trend of the road does not change significantly – it means you can receive the values of Travel_time and Travel_distance (both for the newly created triangle) simply by dividing the corresponding value by half (note that we have a bi-directional calculation for horizontal and vertical connectors). By calculating the speed and the ratio between linear distance and distance from the real world, we obtain the “Road density ratio”, which will be our connection between our transport network and the real world.

It’s time to make some calculations. How exactly are they performed?

Our Client places a service order to his house, the system finds all specialists and tries to calculate the time of the journey from the client to each of the specialists. So basically, we know the length (linear_distance) of the segment created by an intersection with each triangle, we know the average ‘Road_density_ratio’ and the average ‘Travel_speed’ for this triangle, easy maths and voilà!

All further actions are performed by PostGIS. For higher clarity, there is an animation:

And what should we do if the connector goes over the area where there are no triangular polygons? For such a case, there is still the same magnificent tutorial on the capabilities of PGR. In our case, instead of specifying a table with roads, we simply specify a table with connectors between transport nodes.

Our solution vs Google Maps output

Here are some result comparisons between our output and Google Maps:

Result 1:

Result 2:

Result 3:

Conclusion

To jump-start the system in Zurich, we created requests using 724 elements, which cost us less than 4 USD. Just as an example, in the production version ~60 clients make requests in our system with 10-20 specialists daily. This way, direct API requests generate about 900 element requests daily, which is more than was required for the system set up in the city. So our solution turned out to be more cost-efficient, than creating requests to existing APIs.

Contact us if you have questions or ideas, and follow our blog updates.