Des fourmis à l'IA : résoudre des problèmes logistiques complexes grâce à des algorithmes inspirés de la nature

Apprendre de la nature : comment les fourmis résolvent des problèmes complexes

Lorsqu'une colonie de fourmis envoie des ouvrières à la recherche de nourriture sur un nouveau territoire, ces dernières commencent par errer sans but jusqu'à ce qu'elles trouvent une source de nourriture. En marchant, elles laissent de petites quantités de phéromones (que l'on pourrait comparer à l'utilisation que nous faisons du parfum pour nous rendre plus attrayants aux yeux de nos semblables) sur le sol, marquant ainsi le chemin qu'elles ont emprunté.

Ces "pistes de phéromones" s'évaporent progressivement avec le temps, mais les nouvelles fourmis et celles déjà en route peuvent détecter les phéromones laissées par leurs prédécesseurs et sont généralement plus enclines à suivre les pistes à l'odeur plus forte. Les chemins plus courts accumulent les phéromones plus rapidement car les fourmis font davantage d'allers-retours, renforçant ainsi ces chemins avec plus de phéromones en un temps plus court.

En conséquence, les itinéraires plus courts deviennent de plus en plus attrayants, tandis que les itinéraires plus longs, dont les signaux de phéromone sont plus faibles en raison d'une moindre densité et d'une évaporation plus rapide, finissent par être abandonnés. Au fil du temps, ce processus optimise naturellement le chemin de recherche de nourriture de la colonie vers le chemin le plus court disponible. Toutefois, si un blocage soudain se produit sur le chemin le plus court, les fourmis peuvent toujours trouver d'autres chemins car ils conservent certaines traces de phéromones qui les guident pour qu'elles les explorent à nouveau.

Des études ont également montré que les phéromones peuvent contenir des informations sur la qualité et le type de la source de nourriture (1), qui sont ensuite utilisées pour optimiser le système logistique en fonction de la demande de la colonie. Les fourmis ne sont pas les seules à savoir résoudre les problèmes d'acheminement, on trouve des systèmes similaires chez les mousses, les abeilles, les oiseaux, les chauves-souris, les loups, les lucioles et même au sein de notre système génétique qui tente combine et fait muter nos gènes pour assurer notre évolution biologique. En règle générale, ces systèmes s'articulent autour de deux forces : une méthode pour explorer des nouveaux espaces de solutions et une structure de mémoire pour apprendre des erreurs et renforcer les comportements gratifiants ou efficaces.

L'intelligence, l'adaptabilité et la complexité du modèle utilisé collectivement par les fourmis ont donné naissance à un domaine scientifique appelé ”Ant Colony Optimization" (2) dont fait partie l'un de mes articles (3) publié en 2017, article que j'utilise ici pour analyser certains problèmes très spécifiques, notamment logistiques.

Un défi en temps réel : optimiser la logistique moderne

Il existe de nombreuses similitudes entre les problèmes logistiques rencontrés par les fourmis et notre monde. Les entreprises de logistique fonctionnent avec un nombre limité de véhicules, dont chacun représente une capacité opérationnelle qui doit être maximisée. Cette limitation est renforcée par les contraintes réglementaires sur les heures de travail des conducteurs, qui sont mises en place pour assurer la sécurité, et qui limitent de facto le temps de livraison disponible chaque jour.

L'équilibre entre l'utilisation de ces ressources (limitées) et la nécessité de servir une large base de clients est une préoccupation majeure. La hiérarchisation des clients ajoute un autre niveau de complexité. Avec des clients dont le niveau d'importance varie en fonction de facteurs tels que les contrats, la valeur stratégique ou les accords de niveau de service, les entreprises de logistique doivent développer une stratégie de hiérarchisation des services qui soit en phase avec leurs objectifs commerciaux.

Les créneaux durant lesquelles les clients sont disponibles pour recevoir des livraisons compliquent encore la situation, ce qui exige que les itinéraires soient planifiés avec précision. L'optimisation des itinéraires est un défi essentiel, qui implique le calcul des itinéraires les plus efficaces que les véhicules doivent emprunter pour minimiser le temps et la distance de déplacement tout en maximisant le nombre de clients desservis (et sur un créneau donné donc...).

Cette tâche est également rendue plus difficile par des conditions dynamiques telles que la structure du trafic, l'état des routes et les contraintes de capacité des véhicules, qui peuvent toutes varier considérablement d'un jour à l'autre. La gestion des coûts est un autre aspect essentiel des opérations logistiques.

Les coûts opérationnels, y compris la consommation de carburant, les frais liés aux émissions de carbone, l'entretien des véhicules et les salaires des chauffeurs, doivent être gérés avec soin pour maintenir la rentabilité. En outre, le risque de pénalités financières ou de dommages aux relations commerciales résultant de livraisons tardives ou manquées ajoute un impératif financier au maintien d'un service ponctuel.

D'un point de vue mathématique, ce problème logistique peut être considéré comme une variante du problème d'orientation (Orienteering Problem) (4) dans la catégorie des problèmes de routage de véhicules. Il s'inspire des recherches sur les courses d'orientation (5), qui s'apparentent à une chasse au trésor dont le point de départ et d'arrivée se situe à des endroits spécifiques et dont l'objectif est de visiter le plus grand nombre possible d'endroits "gratifiants" tout au long du parcours.

Le défi réside dans les limites de temps et/ou de distance, ce qui signifie que vous ne pouvez pas visiter tous les endroits et que vous devez choisir les stratégiquement pour maximiser les réussites. S'il est relativement facile de créer et d'évaluer des solutions réalisables, il est en revanche très difficile de trouver la solution optimale et de prouver qu'elle l'est, même avec l'augmentation de la puissance de calcul. Il n'existe pas d'algorithme spécifique qui garantisse la recherche de la solution optimale dans un délai raisonnable, de sorte que la seule option consiste souvent à évaluer toutes les combinaisons de lieux et d'itinéraires.

Pour illustrer l'échelle de complexité, considérons un problème de course d'orientation avec seulement trois emplacements à trouver : vous devrez évaluer 16 itinéraires possibles, dont un itinéraire vide, trois itinéraires à emplacement unique, six combinaisons de deux emplacements et six itinéraires avec les trois emplacements. Cela semble gérable, mais si nous étendons le problème à 10 emplacements, environ 9 864 101 itinéraires doivent être évalués, ce qui reste dans les limites des calculateurs commerciaux pour les problèmes de base. Cependant, dans la logistique "réelle", avec 100 arrêts potentiels, plusieurs véhicules et des contraintes supplémentaires, la résolution optimale de ce problème pourrait devenir impossible sur le plan informatique.

Des fourmis à l'IA : repousser les limites avec le machine learning

Une approche consiste à concevoir des algorithmes informatiques qui imitent le comportement des organismes naturels décrits précédemment. Par exemple, chaque segment de route entre deux lieux se voit initialement attribuer une valeur de phéromone égale. Les "fourmis virtuelles" représentent les solutions, construisant des itinéraires en ajoutant séquentiellement des emplacements d'une manière similaire au jeu de la roulette d'un enfant : tous les emplacements non visités sont placés sur la roue, mais ceux dont la valeur de phéromone est plus élevée occupent des sections plus grandes, ce qui les rend plus susceptibles d'être sélectionnés. Une fois que chaque fourmi a généré un itinéraire réalisable, les valeurs de phéromone des segments de route dans l'itinéraire de la fourmi la plus performante sont renforcées, tandis que les phéromones sur les autres segments de route sont réduites.

Ce processus est répété des milliers de fois, en fonction des contraintes de temps définies par l'utilisateur. Comme dans la nature, l'algorithme explore initialement une grande variété de segments de route et d'emplacements, mais au fur et à mesure qu'il progresse, il se concentre davantage sur la précision et l'exploration de solutions proches de la meilleure solution, guidé par la mémoire des phéromones. Ce type d'algorithme, appelé "ant colony optimization", a été proposé à l'origine par Dorigo et al. (2) et fait partie de nombreuses métaheuristiques inspirées de la nature pour résoudre des problèmes mathématiques complexes.

Si les algorithmes inspirés de la nature se sont révélés efficaces pour résoudre des problèmes mathématiques complexes, les progrès de l'intelligence artificielle et de l'apprentissage automatique (machine learning) repoussent les limites encore plus loin. Les techniques basées sur l'apprentissage automatique, en particulier celles qui impliquent l'apprentissage dit "par renforcement" et les réseaux neuronaux, offrent de nouvelles façons d'aborder les problèmes de routage et d'optimisation en apprenant à partir des données et en s'adaptant en temps réel. Ces approches basées sur l'IA peuvent prédire des solutions de haute qualité, ajuster dynamiquement les stratégies et gérer des scénarios plus complexes, à grande échelle et avec des contraintes multiples.

En exploitant les forces du machine learning, nous pouvons aller au-delà de l'imitation des processus naturels et développer des algorithmes encore plus efficaces et intelligents pour résoudre les problèmes d'optimisation les plus difficiles dans les domaines, notamment, de la logistique et du transport.

Références

(1) The role of multiple pheromones in food recruitment by ants. A. Dussutour, S. C. Nicolis, G. Shephard, M. Beekman, D. J. T. Sumpter. J Exp Biol (2009) 212 (15): 2337–2348. https://doi.org/10.1242/jeb.029827

(2) M. Dorigo, M. Birattari and T. Stutzle, "Ant colony optimization," in IEEE Computational Intelligence Magazine, vol. 1, no. 4, pp. 28-39, Nov. 2006, https://doi.org/10.1109/MCI.2006.329691

(3) Verbeeck, C., Vansteenwegen, P. & Aghezzaf, EH. The time-dependent orienteering problem with time windows: a fast ant colony system. Ann Oper Res 254, 481–505 (2017). https://doi.org/10.1007/s10479-017-2409-3

(4) Aldy Gunawan, Hoong Chuin Lau, Pieter Vansteenwegen. Orienteering Problem: A survey of recent variants, solution approaches and applications (2016) European Journal of Operational Research, Volume 255, Issue 2, Pages 315-332. https://doi.org/10.1016/j.ejor.2016.04.059

(5) I-Ming Chao, Bruce L. Golden, Edward A. Wasil. The team orienteering problem (1996),
European Journal of Operational Research, Volume 88, Issue 3, Pages 464-474. https://doi.org/10.1016/0377-2217(94)00289-4