What is and how does route optimization work?

It’s the process of finding the best delivery routes for a fleet of one or more vehicles, which will satisfy a set of customers, considering restrictions for customers, vehicles and drivers.

Which route is better than another depends on the objective of the optimization. There are many variations and specializations of these types of problems, but they usually aim to reduce the time spent or the amount of distance traveled by occupying the minimum amount of vehicles.

In the world of mathematics and computer science, the problem is formally known as a vehicle routing problem (VRP), and corresponds to a combinatorial optimization and integer programming problem. This works by intelligently analyzing the set of solutions that satisfy the restrictions entered, choosing those that are best evaluated according to whether time or distance is optimized.

According to the optimization theory, finding the optimal solution for this type of problem is NP-Hard, which means that only when the number of vehicles and destinations is relatively small, it is possible to find the effectively shorter solution by comparing all possible solutions between them. But finding the optimal solution for a very big problem could take an exceedingly long time. That is why to find solutions in a reasonable time it is necessary to use methods, or meta-heuristics, that allows to search for the optimal solution without having to analyze all possible solutions one by one, and thus better approach the optimum in a time controlled, but without necessarily guaranteeing that the solution found is the best.

The type of heuristics used for these types of problems are known as local search. Optiroute uses Tabu Search as a meta-heuristic to evaluate the different solutions, in the standard configuration of the search. In the exhaustive search configuration Guided Local search is used.