In the water delivery project, we have a task to automate the distribution of orders between a fixed number of cars. The criterion for the effectiveness of the solution was not only the minimum total distance but the uniformity of vehicle loading. An additional limitation was the speed of the algorithm since it influenced some business processes. It was also necessary to scale – the ability to distribute orders not only for one city but for several.
The most accurate way to get the optimal solution is a complete enumeration of all possible solutions. But the time required for this will be dramatically long. To reduce the running time of the algorithm, one has to make certain assumptions, which in turn affects the accuracy of the resulting solution. As a result, it is necessary to find some balance between the speed of the algorithm and its accuracy.
First of all, we solved the problem with filling in the matrix of distances between orders. It’s all about data amounts. For 150 orders, this is 150 * 149 = 22,350 distances between orders and another 150 distances from the warehouse to each order – 22 500 distances in total. It would be possible to use the distance between the coordinates, but obviously, it is impossible to travel in a straight line from point A to point B. (The option with distances between geographic coordinates is used in case of failures when filling in the distance matrix). Each free geo service has limitations of no more than 10,000 – 15,000 free queries per day. In services of the Yandex level, you need to pay for requests. We chose to deploy our OpenStreetMap server. It is less accurate than, for example, Yandex, but there are always limitations, including financial ones.
After calculating the matrix of distances, all orders are divided into clusters (orders that are close to each other) using the clustering algorithm. The number of clusters is equal to the number of cars for which there is a distribution. Then for each cluster we assigned a car. After that, we get a set of cars to which the nearest orders are tied. Next, we must count the filling of cars, as well as the requirement for equal filling.
Some cars have underloading, we called them “hungry”. Some cars have overloading – “overfed.”
At the last stage, the “overfed” begin to transfer orders to other cars. It is important that before moving the order, a direction is drawn to the “hungry” car itself, so that, as a result, “overfed” cars begin to move unnecessary orders in favor of the “hungry” ones. These unnecessary orders are moved to the closest cars. The number of such transfer orders is limited to speed up the algorithm.
Below is an example of the result of the algorithm. The calculation was made for 163 orders and 8 cars.
The time spent is 8 seconds, excluding the generation of the distance matrix. Matrix filling time depends on the number of points, for 180 delivery points (orders) an average of 5 minutes.
