Journal international d'intelligence d'essaim et de calcul évolutif

Abstrait

Un algorithme immunologique pour l'optimisation combinatoire : le problème de la distribution de carburant comme étude de cas

Pavone M*, Costanza J et Cutello V

Résumé Les problèmes de routage sont des tâches classiques d'optimisation combinatoire qui trouvent une grande applicabilité dans de nombreux scénarios industriels et réels. Une variante difficile du problème de routage est le problème de distribution de carburant (FDP) auquel une entreprise de transport doit faire face dans ses opérations quotidiennes. L'activité principale d'une entreprise de carburant de transport consiste à réapprovisionner tous ses magasins, c'est-à-dire les stations-service, le long d'une carte géographique, dans le but de minimiser ses coûts globaux. Dans ce travail de recherche, nous présentons une heuristique hybride basée sur la métaphore du système immunitaire pour résoudre le FDP, qui demande essentiellement de trouver un ensemble d'itinéraires aussi courts que possible pour un nombre fixe de véhicules de l'entreprise afin de satisfaire les différentes demandes reçues des clients. En particulier, l'algorithme immunologique présenté s'inspire du principe de sélection clonale, dont les principales caractéristiques sont le clonage, l'hyper-mutation et les opérateurs de vieillissement. Cet algorithme est également caractérisé par (i) une approche déterministe basée sur l'algorithme de recherche en profondeur (DFS) - utilisé dans le schéma d'attribution d'un sommet à un véhicule - et (ii) un opérateur de recherche locale, basé sur l'exploration du voisinage. L'algorithme a été testé sur une instance de données réelle, avec 82 sommets, et 25 autres instances artificielles différentes, tirées du test de coloration de graphes DIMACS. Les résultats expérimentaux présentés dans ce travail prouvent non seulement la robustesse et l'efficacité de l'algorithme développé, mais montrent également la qualité de la recherche locale et de l'approche basée sur l'algorithme DFS. Les deux méthodologies aident l'algorithme à mieux explorer l'espace de recherche complexe.