Un algorithme continu de colonie d’abeilles artificielles pour résoudre les problèmes d’implantation d’installations sans capacité

Des manières plus intelligentes de placer des entrepôts

Toute entreprise qui expédie des marchandises est confrontée à une question simple mais coûteuse : où implanter nos entrepôts ou centres de service pour desservir les clients de façon bon marché et fiable ? Cet article aborde ce casse-tête à l’aide d’un algorithme inspiré de la façon dont les abeilles cherchent de la nourriture, et montre comment une version améliorée de cette méthode inspirée des abeilles peut planifier ces emplacements avec plus de précision et de régularité que de nombreuses techniques concurrentes.

Le défi du choix des emplacements

Le problème mathématique derrière le choix d’emplacements d’entrepôts s’appelle le problème d’implantation d’installations sans capacité (uncapacitated facility location). Imaginez une liste d’emplacements potentiels où vous pourriez ouvrir des entrepôts, chacun ayant un coût d’ouverture fixe, et une carte de clients, chacun devant être servi par exactement un site ouvert, moyennant un coût de livraison. L’objectif est de décider quels sites ouvrir et quels clients chaque site doit desservir, de sorte que la somme des coûts d’ouverture et de livraison soit la plus faible possible. Même pour des ordinateurs, le nombre de combinaisons possibles explose à mesure que le réseau grandit, ce qui implique qu’il faut des stratégies de recherche astucieuses plutôt que la force brute.

S’inspirer du butinage des abeilles

L’algorithme de colonie d’abeilles artificielles (ABC) emprunte au comportement des abeilles réelles lorsqu’elles explorent leur environnement. Dans l’algorithme, chaque « abeille » représente une solution possible. Les abeilles employées explorent autour de leur solution actuelle, les abeilles observatrices se concentrent sur les solutions prometteuses, et les abeilles éclaireuses abandonnent les choix médiocres et sautent vers de nouvelles régions. L’ABC a été conçu à l’origine pour ajuster des valeurs numériques continues, comme tourner un bouton vers le haut ou vers le bas. Cependant, les décisions d’implantation d’entrepôts sont essentiellement binaires : ouvrir ce site ou pas ; affecter ce client ici ou ailleurs. L’ABC classique peine donc à moins d’être entouré de mécanismes supplémentaires pour traduire entre nombres continus et décisions oui/non.

Transformer une recherche lisse en décisions nettes

Les auteurs proposent une variante qu’ils appellent ABC continu, ou cABC, qui conserve la recherche lisse de la méthode d’origine mais la rend naturellement apte à gérer des choix binaires. Elle permet à l’algorithme de parcourir un espace continu entre 0 et 1, traitant chaque valeur comme la probabilité qu’une installation soit ouverte. Une règle simple convertit ensuite ces valeurs en décisions nettes ouvert/fermé. Pour éviter de partir d’un ensemble de conjectures pauvres ou trop étroites, le cABC utilise un motif « chaotique » pour disperser largement ses solutions initiales dans l’espace de recherche. Lorsqu’une solution d’essai implique qu’aucune installation n’est ouverte du tout, ou enfreint autrement les règles, un processus de réparation dynamique ajuste automatiquement plusieurs de ses choix pour la rendre viable sans s’éloigner excessivement des régions prometteuses.

Essaims guidés et ajustements adaptatifs

Au-delà de cette configuration de base, le cABC ajoute plusieurs raffinements pour aider les abeilles virtuelles à coopérer plus efficacement. Plutôt que d’ajuster la position d’une abeille uniquement sur la base d’elle-même et d’un partenaire aléatoire, l’algorithme laisse parfois d’autres solutions choisies au hasard guider le changement, utilisant occasionnellement des solutions très bonnes et parfois des moins bonnes pour conserver à la fois focalisation et diversité. Un schéma variant dans le temps perturbe progressivement davantage de parties d’une solution à mesure que la recherche avance, permettant un partage d’information plus profond entre les abeilles. Pendant la phase où les abeilles observatrices choisissent quelles solutions affiner, une règle de probabilité modifiée garantit que même les candidats médiocres reçoivent un certain niveau d’attention, réduisant le risque que l’essaim s’effondre trop vite autour d’une seule option. Enfin, lorsqu’une position d’abeille échoue pendant trop longtemps, le cABC ne la jette pas ; il crée plutôt une version « opposée » de cette solution, qui se trouve souvent plus proche d’un meilleur territoire tout en réutilisant les connaissances déjà acquises.

Mettre l’essaim d’abeilles à l’épreuve

Pour vérifier l’efficacité de ces idées, les auteurs ont exécuté le cABC sur deux grandes collections de problèmes tests standard tirés de la littérature en recherche opérationnelle, couvrant des réseaux de taille modeste à très grande. Ils ont comparé ses résultats à ceux de l’ABC original et à onze autres algorithmes avancés basés sur des métaphores différentes, incluant les lucioles, les corbeaux, les sauterelles et les graines d’arbres. Dans ces tests, le cABC non seulement égalait ou améliorait les meilleurs coûts connus dans la plupart des cas, mais le faisait aussi de manière beaucoup plus fiable, atteignant souvent la meilleure solution à presque chaque exécution indépendante. Son avantage était particulièrement net sur les exemples les plus grands et les plus exigeants, où d’autres méthodes restaient fréquemment bloquées sur des configurations plus coûteuses.

Ce que cela signifie pour la planification réelle

Concrètement, ce travail propose un planificateur « inspiré des abeilles » plus fiable pour décider où implanter entrepôts, usines ou centres de service. En laissant l’algorithme raisonner en probabilités continues puis en les transformant proprement en décisions binaires—tout en réparant les mauvaises estimations et en maintenant la diversité—le cABC explore le paysage des options à la fois largement et en profondeur. Le résultat est un outil capable de trouver des configurations moins coûteuses et de le faire de manière constante, ce qui en fait un candidat solide pour les entreprises et planificateurs qui doivent concevoir des réseaux de distribution économes en coûts dans un monde logistique complexe et à grande échelle.

Citation: An, M., Xiang, W., Jiang, Y. et al. A continuous artificial bee colony algorithm for solving uncapacitated facility location problems. Sci Rep 16, 8780 (2026). https://doi.org/10.1038/s41598-026-37792-5

Mots-clés: implantation d’installations, intelligence en essaim, métaheuristique d’optimisation, planification logistique, colonie d’abeilles artificielles