Many companies whose profit depends on the servicing of points or customers in the field do not use any mathematical method of selecting the most optimal combinations of routes between them. The order of scheduled visits results from the experience, practice or intuition of the planner, and sometimes by coincidence. Hardly anyone wonders about the scale of possible solutions and thus how much such a coincidence could cost a company in a month, year or a few years.
10 points, millions of possibilities
Below is an estimate of the number of possible combinations of routes with 10, 25 and 50 points respectively to visit for 1 driver only.
When our task is to visit a small number, only 10 points, we choose from:
10! = 3628800
combinations of possible routes. Assuming that there is exactly one best solution for a 10-point route, by choosing the order of points randomly, we have a chance to hit them with the same probability as when buying 4 Lotto bets to hit the Jackpot.
Alternatively, by checking 8 solutions per second you can verify them all in a year.
In the case of 25 points the number increases to
25! = 155112100433330985984000000 = approx. 1.5 * (10 ^ 25)
combinations.
The age of the universe is approximately 4 * 10 ^ 17. Otherwise, by verifying 150 million solutions every second starting from the beginning of the Universe, we would be at the moment of checking them all about now.
For 50 points the number of possible routes is quite a lot, because:
50! = 155112100433330985984000000 = approx. 3 * (10 ^ 64)
Earth has about 10 ^ 50 atoms (1 and 50 zeros). In other words, for a 50 point problem, there are approximately 3 * 10^15 solutions for every atom on Earth.
Alternatively, we get this combination by choosing a slightly larger number – one solution for approximately 10 to 1000 atoms in our galaxy (our galaxy has almost 10 ^ 67 atoms).
20 seconds of Emapa algorithm operation
Emapa’s algorithm needs tens of seconds of calculation time to resolve such small problems. Two minutes is too much. There are many reasons for this, and the simplest one is that most of the possible solutions (routes) are completely pointless. For example, after passing 2 points, the algorithm knows that regardless of the third point on the route, the driver will not be able to return to his base on time.
When only one vehicle is available, it is relatively easy to calculate the number of possible route combinations. The combinations for many vehicles are more interesting and much more complicated. Emapa’s algorithm can also handle this without any problems.
Using 2 vehicles in the company, one should add to the above estimates all possible divisions of the set of points into 2 subsets and multiply it by the number of possible permutations of these sets, for 3 into 3 subsets, etc.
As you can see, it is not that difficult to make a mistake trying to calculate routes based on your own intuition. The costs of such a mistake are, above all, unnecessarily consumed fuel, too many employees to handle a certain number of orders or loss of potential customers who could not wait for our delivery. For a small company, unnecessary losses can reach several hundred PLN in just one day.
Records broken every day
The current work of Emapa programmers is based on continuous improvement of VRP algorithms, which are already at the top of the world rankings. The highest number of records that Emapa has broken in recent months is in the category of 1000 points. With one vehicle and 1000 customers to visit, we have around 4 * 10 ^ 2568 ways to arrange the route.
This is a number that has no comparison with anything that exists in the universe, in any unit. The highest number shown in the tables is 10^100, which is a number that is essentially indistinguishable from zero compared to 10 ^ 2568.