An Enhanced Large Neighborhood Search Approach for the Capacitated Facility Location Problem with Incompatible Customers

Résumé technique : Une approche de recherche à grand voisinage améliorée pour le problème de localisation de sites avec capacités et clients incompatibles

Définition du problème
Cet article traite du problème de localisation de sites multi-sources avec capacités et incompatibilités entre clients (MS-CFLP-CI). Cette variante étend le MS-CFLP classique en introduisant un ensemble de paires de clients incompatibles ($I$) qui ne peuvent pas être servis par le même site. Le problème consiste à déterminer quels sites ouvrir (encourageant des coûts d'ouverture $f_j$) et comment répartir la demande des clients ($d_i$) parmi les sites ouverts (encourageant des coûts de transport $c_{ij}$) afin de minimiser le coût total. La solution doit satisfaire les contraintes de capacité des sites ($s_j$), répondre pleinement à la demande des clients et garantir qu'aucun deux clients incompatibles ne partagent un site. La présence de contraintes d'incompatibilité rend le sous-problème de recherche d'une offre optimale depuis les sites ouverts NP-difficile, même lorsque l'ensemble des sites ouverts est fixé.

Méthodologie
Les auteurs proposent un cadre de recherche à grand voisinage (LNS) pour résoudre le MS-CFLP-CI. Le cœur de l'approche consiste à détruire itérativement une partie de la solution courante et à la réparer en utilisant un solveur exact de programmation en nombres entiers mixtes (MIP) (Gurobi).

• Représentation de la solution : Les solutions sont représentées sous forme de matrices de quantités expédiées, soutenues par des structures de données auxiliaires suivant les sites ouverts/fermés et les clients assignés.
• Solution initiale : Une heuristique construit une solution de départ en triant les sites par coût d'ouverture, en sélectionnant suffisamment d'entre eux pour satisfaire la demande totale, et en ajoutant un nombre spécifique de sites supplémentaires ($k=5$) pour gérer les contraintes d'incompatibilité. Les clients sont assignés selon une stratégie uniforme.
• Opérateurs de destruction : L'article introduit trois nouveaux opérateurs de destruction conçus spécifiquement pour les contraintes d'incompatibilité :
  1. Sites les moins chers (CF) : Sélectionne un site aléatoire et ses clients, puis identifie d'autres sites ouverts offrant le coût de transport moyen le plus bas pour ce groupe spécifique de clients.
  2. Clients hybrides (HC) : Une recombinaison de deux stratégies. Il sélectionne un site aléatoire et ses clients, puis identifie les « clients les moins chers » (ceux ayant un faible coût de transport vers le site) et les « clients les plus chers » (ceux ayant un coût élevé). Il sélectionne ensuite des sites supplémentaires offrant le meilleur service pour ces sous-ensembles spécifiques de clients.
  3. Sites fermés : Les sites fermés aléatoires et ceux ayant la mesure de coût minimale ($Q_g$) sont inclus dans le sous-problème pour explorer l'ouverture de nouveaux sites.
• Opérateur de réparation : Le sous-problème défini par les éléments détruits est résolu exactement à l'aide de Gurobi. Pour gérer le temps de calcul, la phase de réparation inclut une contrainte limitant le nombre de nouveaux sites ouverts à au maximum deux de plus que ceux actuellement impliqués dans le sous-problème. Une valeur de coupure (le coût actuel du sous-problème) est fournie au solveur pour accélérer la convergence.
• Configuration et réglage : Les auteurs utilisent l'outil irace pour le réglage des paramètres basé sur les caractéristiques, ajustant des paramètres tels que la taille du sous-problème ($\nu$) en fonction de l'échelle de l'instance (distinguant spécifiquement les instances avec $\le 700$ et $> 700$ sites). L'algorithme final, nommé $LNS_{init,accept}$, combine les opérateurs de destruction proposés avec une heuristique de solution initiale améliorée et un critère d'acceptation permettant d'accepter des solutions de coût égal, facilitant ainsi la sortie des optima locaux.

Contributions clés

• Cadre algorithmique novateur : Il s'agit de la première application de la recherche à grand voisinage au problème MS-CFLP-CI.
• Opérateurs spécialisés : La conception d'opérateurs de destruction (CF et HC) qui prennent explicitement en compte les contraintes d'incompatibilité, allant au-delà des heuristiques standard de localisation de sites.
• Réparation hybride exacte/heuristique : L'intégration d'un solveur MIP exact dans la phase de réparation, optimisé avec des contraintes spécifiques pour équilibrer la qualité de la solution et le temps d'exécution.
• Analyse rigoureuse : Une étude d'ablation complète et une analyse statistique (utilisant les tests de Friedman et Nemenyi) pour évaluer l'impact des composants individuels (initialisation, critères d'acceptation, poids adaptatifs).
• Évaluation comparative approfondie : Évaluation sur deux ensembles de données à grande échelle (wlp et cflp-ci) contenant jusqu'à 3 000 sites et 8 000 clients.

Résultats expérimentaux
La méthode proposée $LNS_{init,accept}$ a été testée contre des métaheuristiques de l'état de l'art, notamment la recherche locale itérée multi-démarrages basée sur MineReduce (MR-MS-ILS), GRASP, l'algorithme évolutionnaire à codage par permutation (PcEA), la recherche gloutonne multi-démarrages (MG) et le recuit simulé (SA).

• Performance : La méthode proposée surpasse significativement toutes les méthodes existantes sur les deux ensembles de données selon deux limites de temps différentes ($10\sqrt{m}$ et $m$ secondes).
• Nouvelles meilleures solutions : L'approche a trouvé de nouvelles meilleures solutions pour toutes les 80 instances des deux ensembles de données.
• Signification statistique : Les tests statistiques ont confirmé que les améliorations par rapport à la meilleure méthode précédente (SA) sont statistiquement significatives.
• Évolutivité : Alors que les solveurs exacts (Gurobi/CPLEX) ne pouvaient résoudre des instances jusqu'à 150 sites à l'optimalité dans un temps raisonnable, l'approche LNS a géré efficacement des instances jusqu'à 3 000 sites.
• Réduction de l'écart : Pour l'ensemble de données wlp, la méthode a obtenu des améliorations d'écart allant de -0,68 % à -1,84 % par rapport aux meilleures solutions connues. Pour l'ensemble de données cflp-ci, les améliorations ont varié de -0,46 % à -2,09 %.

Importance et affirmations
Les auteurs affirment que leur méthode représente l'état de l'art actuel pour le problème MS-CFLP-CI. L'importance du travail réside dans sa capacité à gérer la complexité computationnelle introduite par les incompatibilités entre clients, que les métaheuristiques précédentes peinaient à optimiser pleinement, en particulier pour les grandes instances. L'article affirme que la combinaison d'opérateurs de destruction novateurs, d'une phase de réparation exacte et d'un réglage algorithmique spécifique permet à la méthode d'explorer efficacement des voisinages de taille moyenne, trouvant des solutions supérieures là où le recuit simulé et d'autres méthodes stagnent. Les auteurs notent modestement que, bien que leur méthode soit actuellement la meilleure, un travail futur pourrait impliquer une analyse de l'espace des instances pour mieux comprendre la difficulté des instances et étendre l'approche à d'autres variantes de localisation de sites.