Quelle complexité mathématique pour l’optimisation de tournées ?
- 2 août 2020
- 3 mins
L’optimisation de tournées est un champ d’étude qui appartient au domaine mathématique de la Recherche Opérationnelle, et plus précisément de l’optimisation combinatoire. Cette branche des mathématiques étudie des problèmes de décision ou d’optimisation sous contraintes pour lesquels il peut y avoir un très grand nombre de solutions possibles.
L’un des problèmes fondamentaux lié à l’optimisation de tournées est le fameux « Problème du Voyageur de Commerce », dont on trouve la première description en 1832 et qui consiste à trouver la façon de visiter N points qui minimise la distance parcourue par un agent itinérant. Formellement cela revient à identifier un cycle hamiltonien de moindre coût dans un graphe complet muni de pondération sur les arcs. Ce problème est notoirement connu pour être NP-complet [1] : c’est-à-dire qu’il n’existe pas a priori d’algorithme capable de le résoudre rapidement au sens de la complexité informatique (i.e.en temps polynomial).
Dans le cas plus général avec K véhicules, le problème est appelé Vehicle Routing Problem et a été introduit dans la littérature par Dantzig et Ramser en 1959 [2]. On peut voir cette généralisation comme un problème d’optimisation à deux niveaux :
- Un problème d’affectation des tâches aux véhicules
- Un problème de type “voyageur de commerce” pour chaque véhicule
Le fait de devoir résoudre les deux niveaux conjointement complexifie encore les choses.
Pour se rendre compte de l’aspect fortement combinatoire de ce problème, on peut calculer le nombre de tournées possibles en fonction du nombre de points à visiter :
Pour 3 points, il y a 6 tournées possibles.
Pour 10, il y en a déjà 3 628 800. Et pour 60 points, il y en a autant que d’atomes dans l’Univers observable :
Les problèmes réels de logistique peuvent inclure des milliers de points à visiter et des centaines de chauffeur… Cette explosion combinatoire rend très rapidement impossible toute exploration exhaustive des solutions : c’est là qu’interviennent les mathématiques pour imaginer des algorithmes capables de résoudre en quelques minutes ce qui prendrait des siècles à un ordinateur, même très puissant, qui essaierait toutes les solutions afin de trouver la meilleure.
Ainsi, il y a deux grandes approches qui se dégagent pour résoudre ces problèmes :
- des algorithmes exacts : avec assez de temps et sur des problèmes de taille raisonnable, ils sont capables de trouver la solution optimale du problème et de le prouver. Parmi eux : programmation dynamique, programmation linéaire en nombres entiers, etc.
- des algorithmes approchés : ils sont capables de construire des bonnes solutions au problème (potentiellement optimales, mais sans capacité à le prouver). Parmi eux : algorithmes de type “greedy”, métaheuristiques (algorithmes génétiques, GRASP, etc.) [3]
Dans les deux approches, l’idée principale est de ne pas explorer toutes les solutions au problème, mais de faire des choix intelligents basés sur la structure du problème. Par exemple, sur un problème de voyageur de commerce, le meilleur choix du prochain point à visiter est très probablement parmi les points les plus proches, et sans doute pas parmi ceux qui sont les plus éloignés. Ce genre de raisonnement peut permettre de limiter l’espace de recherche et converger rapidement vers des solutions optimisées, à défaut d’être optimales.
Pendant des décennies, les chercheurs ont travaillé à résoudre des versions plus complexes et plus proches de la réalité que la version assez théorique du Vehicle Routing Problem : capacités d’emport limitées, créneaux de temps à respecter, départs de plusieurs dépôts, etc. Ces contraintes supplémentaires rendent le problème parfois si complexe que simplement trouver des tournées qui respectent l’ensemble des contrainte est un défi en soi, avant même de parler d’optimisation.
Ces progrès théoriques et techniques ont pu être transférés vers les professionnels du transport et de nombreuses solutions logicielles intégrant de l’optimisation de tournées ont été conçues pour les y aider, contribuant à l’amélioration des performances de la Supply Chain.
L‘informatique quantique promet, dans les prochaines années, de changer la donne quant à la difficulté de ces calculs. Des publications récentes travaillent en ce sens et des premières tentatives de résolution du Voyageur de Commerce ont été lancées [4]. En effet, de par sa capacité à résoudre rapidement les problèmes inaccessibles à l’informatique “classique”, le calcul quantique pourrait contribuer à révolutionner un peu plus l’optimisation de la Supply Chain au sens large.
[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.
