What is the mathematical complexity of route optimization?
- May 4, 2021
- 2 mins
Route optimization is a field of study that belongs to the mathematical field of Operations Research, and more precisely to the branch of combinatorial optimization. This branch of mathematics studies decision or constrained optimization problems for which there may be a very large number of possible solutions.
One of the fundamental problems related to round optimization is the famous “Traveler’s Problem”, first described in 1832, which consists in finding the way to visit N points that keeps the distance traveled by a driver to a minimum. This problem is equivalent to identifying the cheapest Hamiltonian cycle in a complete graph with weights on the arcs. This problem is known to be NP-complete [1]: i.e., there is no known algorithm capable of solving it quickly in terms of computer complexity (i.e., in polynomial time).
In a more general case with K vehicles, the problem is called Vehicle Routing Problem and was introduced by Danzig and Ramser in 1959 [2]. This generalization can be seen as a two-level optimization problem:
- A problem of assigning tasks to vehicles
- A “traveling salesman” type problem for each vehicle
The fact that we have to solve both levels jointly makes things even more complex.
The fact that we have to solve both levels jointly makes things even more complex.
For 3 points, there are 6 possible rounds.
For 10, there are 3 628 800. And for 60 points, there are as many as atoms in the observable Universe:
The actual problems of logistics can include thousands of points to visit and hundreds of drivers… This combinatorial complexity quickly makes it impossible to explore all the solutions: this is where mathematics comes in to imagine algorithms capable of solving in a few minutes what would take centuries for a computer, even a very powerful one, to try all the solutions in order to find the best one.
Thus, there are two main approaches that can be applied to solve these problems:
- exact algorithms: given enough time and on problems of reasonable size, they are able to find the optimal solution to the problem and prove it. Among them: dynamic programming, integer linear programming, etc.
- approximation algorithms: they can construct good solutions to the problem (potentially optimal, but without the ability to prove it). Among them: greedy algorithms, metaheuristics (genetic algorithms, GRASP, etc.) [3].
In both approaches, the main idea is not to explore all the solutions of the problem, but to make intelligent choices based on the structure of the problem. For example, in a “traveling salesman” problem, the best choice of the next point to visit is most likely among the closest points, and probably not among the farthest ones. This kind of reasoning can limit the search area and quickly converge to optimized, if not optimal, solutions
For decades, researchers have been working on solving more complex versions of the Vehicle Routing Problem that are closer to reality than the rather theoretical one: limited transport capacities, time slots to be respected, departures from several warehouses, etc. These additional constraints make the problem sometimes so complex that simply finding routes that respect all the constraints is a challenge in itself, even before considering optimization.
These theoretical and technical advances have been transferred to transportation professionals and many software solutions integrating route optimization have been designed to help them, contributing to the improvement of Supply Chain performance.
Quantum computing promises, in the next few years, to change the game as regards the difficulty of these calculations. Recent publications show that this is the case, and the first attempts to solve the Traveler’s problem have been initiated [4]. Indeed, thanks to its ability to quickly solve problems that are inaccessible to “classical” computing, quantum computing could revolutionize Supply Chain optimization.
[1] C. H. Papadimitriou. The Euclidean travelling salesman problem is NP-complete. Theoretical Computer Science vol. 4, issue 3, 1977.
[2] G. B. Dantzig, J. H. Ramser. The Truck Dispatching Problem. Management Science vol. 6, no. 1, 1959.
[3] P. Siarry. Métaheuristiques: Recuits simulé, recherche avec tabous, recherche à voisinages variables, méthodes GRASP, algorithmes évolutionnaires, fourmis artificielles, essaims particulaires et autres méthodes d’optimisation. Editions Eyrolles, 2014.
[4] K. Srinivasan, S. Satyajit, B. K. Behera & P. K. Panigrahi. Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience. 2018.
