Followed by Randomness
Rolling dice has been a divine act since ancient times. For Pre-Christians who lived along the Mediterranean Sea, the die was the law of the land. Since then human beings have not shied away from exploiting its power in all spheres of life, be it for recreation, gambling, moving economy, predicting the weather, and even developing computationally efficient algorithms for immensely hard problems.
Why routing algorithms?
Algorithms have greatly helped humanity in automating an immense number of processes that emanated during the industrial revolution. An algorithm is nothing but a sequence of instructions given to a machine on how to perform a task. At Locus, we solve NP-hard optimization problems and the algorithms that we build are sublimely mathematical in flavor.
What is NP-hardness?
An NP-hard optimization problem of size N has a solution space of size greater than any polynomial in N. Let us consider a derivative of the famous traveling salesman problem — you have to visit your friends’ houses to give your Diwali wishes and gifts but the constraint is that you have only a day at your disposal. Before you even start, you want to figure out the best way you could visit your friends so that you spend the least amount of time traveling and are able to finish as early as possible.
If you have N friends, the number of ways you could visit them is factorial( N), also represented as N!. A straightforward procedure is to evaluate all the N! tours and then choose the best one. However, the hitch here is that N! scales faster than an exponential function as N grows large. Even for a small N=20, this would execute approximately ¹⁰¹⁸ operations. Assuming that a computer performs ¹⁰¹² operations per second, which is quite optimistic, the execution time of this algorithm would be ¹⁰⁶ seconds ≈ 12 days. Clearly this is not a viable option.
Rather than unintelligently testing all solutions, both good and bad, a far better approach is to logically construct a solution that is guaranteed to be the best possible one. However, even the best of such strict approaches need an astronomically large number of operations to produce a solution.
At Locus we do play dice
Instead of performing a mindless exhaustive search, or building the perfect solution slowly and painfully, it turns out that making millions of intelligent guesses can yield excellent solutions rapidly.
Another intuitive approach is to start with a random tour out of these possible 20! tours and keep improving iteratively by making small tweaks until no small tweak can improve the tour. Since the solution obtained here is best compared to all similar solutions, it is referred to as a local optimum. A limitation of this approach is that it considers only a small subset of all possible configurations. Hence, the solution obtained might be highly inferior with respect to the best one.
The best scenario when searching the solution space would be if the algorithm can figure out when and how to get out of these local optima. The algorithms that we design at Locus not only explore a larger part of the solution space but also intelligently exploit the power of die to jump out of the local optimum. We give our algorithm a chance to accept a worse solution than the existing one in expectation of finding an even better solution later. A substantial trait of this algorithm is that after hopping out of a local optimum it is able to find better solutions in future iterations.
Games that we play
3D Box Packing: We pack freight in the most optimal way. When pushing a box in the cargo, our algorithm rolls a biased die to figure out the best orientation to place this box. The die is more favorable to the configuration that has better packing efficiency.
Vehicle Routing Problem: We generate the best routes for a fleet of vehicles on its way to make deliveries within restricted time-windows. When assigning a task to a fleet our algorithm gives chance to all vehicles but recommends those that are in the vicinity of the current delivery’s location. The die favors the assignment that will result in less time and distance being traveled on the road while respecting the hard constraints like volume breach and time windows.
Moreover, the algorithms that we design are perceptive enough to infer the biases of these dice. As the algorithm continues to improve upon the solution, it gradually builds robustness to accepting a less optimal solution for VRP. Below is an illustration depicting the value of these biases during the course of a run of the algorithm.
Monte Carlo to Las Vegas
The technique described above falls under the domain of Monte Carlo algorithms. There also exist algorithms that can always find the best solution, such celebrated randomized algorithms are known as Las Vegas algorithms. Fortunately, there do not exist Las Vegas type algorithms for the problems that we solve. At Locus, we are developing and training intelligent dice which will help us drive to Vegas!
Locus offers best route optimization software to enterprises to improve last-mile deliveries with greater cost-efficiency. Get in touch with us for a free demo.
Originally published at https://blog.locus.sh on November 2, 2017.
