How to improve couriers routing by 3.7 times. AI can help.

Part 1. The Challenge

GIS (geographic information system) services have always been essential for strategic planning.

With the increasing share of remote work and the growth of delivery services, the task of coordinating couriers has become critical.

In services like Uber optimal logistics is one of the most important components for success.

In April 2020, a large Moscow company had the urgent task of delivering electronic devices with certain software to thousands of citizens.

The number of citizens who required the device delivered was growing day by day, and the number of couriers were not at all permanent with about 20 volunteers.

The task of routing their movements around the city at some point became absolutely crucial.

At the same time, there was clearly no time to develop any sophisticated system.

In general, the organisation of the client’s processes was rather poor and sometimes even chaotic.

Part 2. The Solution

As primary data we had the delivery addresses, the number of couriers assigned for the upcoming day and the information about their delivery way — by car or by foot.

As a result, we had to give optimal clusters of two types: for cars and for couriers on foot according to their number.

The task was solved in several stages.

First, we converted the addresses into geo-coordinates.

Then addresses were filtered out to find those included by mistake — not related to Moscow.

Then, using the machine learning algorithm, the points were combined into no more than 40 groups, so that the distance between the points in each group was the shortest.

These groups were then combined together or re-formed based on the number of couriers and quantity of cars available. Severely scattered points that were marked with a separate cluster were attached to the closest group to them. Clusters scattered around were assigned to drivers, local clusters went to couriers on foot.

After all this, there were still certain problems if, for example, the points are close by but across the river with no bridge nearby. Since we were pressed with time, this was not the target problem we had to solve.

Practice showed there were less than 1% of such cases of the total number and this was an acceptable exception.

After forming the cluster, we were supposed to build routing within the cluster.

The simplest solution was to arrange the points according to decreasing longitude if the cluster was more horizontal and latitude if vertical. Despite this solution might be considered pretty much basic or even primitive, the comparison showed that the delivery speed was not particularly different from the speed if complex routing services were applied.

However, we didn’t take traffic jams into account as the planning had to be done right before the delivery day and the calculations would be inaccurate. Also, the traffic jams were not considerable within the area.

Part 3. The result.

As a result, we managed to increase the number of addresses the couriers were able to attend in a day by 3.7 times.

The report was generated within half an hour in automatic mode (in contrast to manual compilation of non-optimised lists which took several hours).

We will describe other geo-analytics tasks we solved in Moscow this year in the next articles!