Les fourmis reines du réseau

En situation d''encombrement le trafic se répartit de manière égale sur les deux branches. Des interactions inhibitrices se produisant à l'intersection des deux branches : les fourmis qui s'engagent sur une branche et rentrent en collision avec des congénères sont automatiquement redirigées sur l'autre branche. Le suivi de piste génère donc sa propre régulation.

© CNRS Photothèque / Gilles VIDAL

Tracé d'une piste chimique

source

A la piste chimique qu’elle trace, la fourmi ajoute une gestuelle particulière. lors de sa rencontre avec une autre fourmis elle danse et l' attouche de ses antennes. La fourmis qui a déjà ingurgité de la nourriture régurgite une partie de la nourriture contenue dans le jabot et la donne à consommer par la deuxième fourmis. Elle renseigne donc d' autres fourmis sur la nature et la destination ( larves, nymphes etc ).

Transferts de ces résultats aux algorithmes

Fort de ce premier constat, Marco Dorigo a transféré ces résultats expérimentaux à des problèmes mathématiques d'optimisation combinatoire. Il démontre ainsi qu'il est désormais possible de trouver le chemin le plus court pour relier plusieurs points appartenant à un ensemble. Et les applications ne se limitent pas à une simple démonstration mathématique. En appliquant la logique observée sur les insectes à des fourmis artificielles déposant une phéromone tout aussi artificielle, le procédé peut en effet être transféré dans une dimension très pratique (calcul du trajet idéal pour des livreurs...).

Il a donc pu écrire l' analogie entre objets comparables

fourmis = livreurs

Le chemin est alors aux fourmis ce que la route est aux livreurs

Outre cette optimisation des distances, les comportements collectifs des fourmis ont également parmi à Marco Dorigo de concevoir des colonies de robots capables 'de résoudre des problèmes imprévus et qu'ils ne pourraient pas surmonter individuellement'. Le franchissement de crevasses lors d'une exploration spatiale en serait une parfaite application. Marco Dorigo, avec l'aide de son équipe, a conçu un algorithme (AntNet), puis un programme qui simule des fourmis artificielles pouvant répandre, mais aussi sentir, des phéromones tout aussi virtuelles. Déjà testé sur le réseau de la Fondation Nationale Américaine des Sciences, ainsi que sur celui de l'opérateur téléphonique japonais NTT, il a produit des résultats plus que satisfaisant selon les scientifiques. Les tests consistent à lâcher périodiquement des fourmis virtuelles dans les nœuds du réseau, sans qu'elles connaissent leur position. Les chercheurs leur demandent ensuite de se rendre à un point précis. La répartition des phéromones virtuelles permet ensuite de dresser une carte grâce à laquelle il devient aisé de définir la route la plus rapide d'un point à un autre. La cartographie s'avère très précieuse pour optimiser et rationaliser la gestion des flux de données dans un réseau. "Cette méthode aboutit à une utilisation plus efficace des ressources d'Internet. Mais les fourmis virtuelles peuvent également permettre aux gens de trouver plus facilement leur chemin dans la masse d'informations et de données que représente Internet", explique Marco Dorigo.

Fourmis et transports !

M. Luca Maria Gambardella, ancien spécialiste en informatique de l'Université de Pise, aujourd'hui directeur de la recherche à l'Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA) à Manno (TI) a eu le coup de génie d'allier les fourmis de M. Marco Dorigo aux techniques locales de recherche. De la sorte, le principe des phéromones se transforme en technologie ouvrant de toutes nouvelles voies. Car M. Gambardella cherchait un exemple pratique pour la faire entrer dans la logistique et les transports. C'est M. Piero Pina, chef de la Société de distribution d'huile de chauffage PINA Petrola SA à Grancia, qui va lui en donner l'occasion. M. Pina cherchait à améliorer l'efficacité des livraisons à ses 20'000 clients tessinois tout en tenant mieux compte de leurs besoins, à planifier de façon optimale les chemins à suivre par ses camions-citernes, et à comprimer les frais correspondants. Le cas était tout indiqué pour l'intelligence collective des fourmis puisque différents facteurs venaient compliquer la desserte. Les camions-citernes étaient de taille très différente; il en était de même de la longueur et du diamètre des tuyaux; les déplacements étaient souvent problématiques par suite de la forte densité du trafic. Par ailleurs, la météorologie ne manquait pas de jouer certains tours. Finalement, il n'était guère possible de planifier suffisamment tôt les commandes de la clientèle; souvent, le combustible liquide ne pouvait être livré qu'à certaines heures. Après avoir analysé la situation, M. Gambardella, Dr. Inf., et son équipe décidèrent de procéder en trois étapes:

Entre-temps, l'équipe de PINA Petroli et les informaticiens de la Haute Ecole Spécialisée du Tessin (SUPSI) ont conçu un progiciel à plusieurs modules. Ainsi, le module de pronostic des besoins de la clientèle estime la consommation de combustible de chaque client, tout en tenant compte de divers paramètres tels que la température extérieure, le comportement précédent de commande du client et la taille de la cuve à mazout du client. Grâce à cette prévoyance, les commandes urgentes ont régressé, alors que les contacts positifs avec la clientèle s'amplifiaient.

Le module de planification des tournées (hors ligne), basé sur des algorithmes s'inspirant des fourmis, détermine les itinéraires optimaux de desserte avec un nombre défini de livraisons et de commandes préalables, dans une fenêtre correspondante de livraison. Ce module assiste le préposé à la logistique dans sa prise de décision qu'il peut tout à sa guise agencer et modifier en permanence.

Le module de simulation de routes lui permet de tester la praticabilité des routes quant aux différentes conditions météorologiques et routières. Le module de planification des tournées (en ligne) suit le statu quo des camions-citernes, tout en indiquant leur position exacte. Complété par des appareils GSM / GPS, il facilite l'ordonnancement des livraisons urgentes qui doivent être exécutées le jour de la passation de commande. L'ensemble du système est entièrement compatible avec la banque de données interne et avec le système Petrodat utilisé dans le commerce des huiles minérales, ce qui garantit une communication sûre avec les chauffeurs de camions‑citernes. En deux minutes seulement, les responsables de l'organisation des tournées peuvent maintenant ordonnancer les livraisons pour toute une semaine en prenant en charge plus de 100 commandes.

L’intelligence des fourmis appliquée à l’ordonnancement des conteneurs

Les algorithmes s'inspirant des fourmis ont également servi à mettre au point un processus efficace d'enregistrement / gestion des conteneurs à La Spezia. Ce port situé sur la côte ligurienne est avec ses 600 000 m² de surface le plus grand centre de transbordement de conteneurs dans la Mer Méditerranée. Le partenaire industriel ContShip Italia, une entreprise de transport intermodale dont le siège se trouve à La Spezia Container Terminal (LSCT), devait faire face à une situation délicate, car plusieurs décideurs tels que les responsables de l'allocation de place d'entreposage, les planificateurs‑armateurs, et les préposés aux ressources voulaient faire entendre leur voix au chapitre. L'équipe de l'IDSIA s'attela au problème, en le subdivisant en plusieurs niveaux et en différents espaces de temps. Tout d'abord, il s'agissait d'analyser les données historiques, en l'occurrence les mouvements de conteneurs des deux dernières années dans le port de La Spezia, afin de pouvoir pronostiquer les événements futurs. Ensuite, il y avait lieu de planifier de façon optimale les activités liées à la localisation des conteneurs ainsi que les opérations de chargement et de déchargement. A cet effet, il fallait déterminer le nombre indispensable de grues de quai et de places d'entreposage pour assurer le mouvement des conteneurs d'un bateau à la place d'entreposage et inversement, afin d'être en mesure de décharger et de charger un navire dans un temps déterminé. Finalement, il convenait de modéliser le terminal ainsi que d'en simuler la taille et les opérations. "Il en résulta un module de pronostic, un module de planification et un module de simulation", se plaît à résumer M. Gambardella. « Chez ContShip Italia, ces modules aident les responsables de la planification dans la bonne organisation de l'enregistrement des containers, et ce, sur deux plans: à court terme d'une part, en ce qui concerne les opérations quotidiennes de chargement et de déchargement; à long terme d'autre part, pour ce qui est du taux d'occupation et de la politique portuaire d'entreposage."

Source

ADIT : Ambassade de France en Belgique - Vigie Informatique Appliquée numéro 90 - 1/3/2004 - réf. 18777ADIT : Ambassade de France en Belgique - Vigie Informatique Appliquée numéro 90 - 1/3/2004 - réf. 18777