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

Resumo Técnico: Uma Abordagem de Busca em Grande Vizinhança Aprimorada para o Problema de Localização de Instalações com Capacidade e Clientes Incompatíveis

Definição do Problema
Este artigo aborda o Problema de Localização de Instalações com Capacidade e Múltiplas Fontes com Incompatibilidades de Clientes (MS-CFLP-CI). Esta variante estende o clássico MS-CFLP ao introduzir um conjunto de pares de clientes incompatíveis ($I$) que não podem ser atendidos pela mesma instalação. O problema envolve determinar quais instalações abrir (incorrendo em custos de abertura $f_j$) e como distribuir a demanda dos clientes ($d_i$) entre as instalações abertas (incorrendo em custos de transporte $c_{ij}$) para minimizar o custo total. A solução deve satisfazer as restrições de capacidade das instalações ($s_j$), atender integralmente à demanda dos clientes e garantir que nenhum par de clientes incompatíveis compartilhe uma instalação. A presença de restrições de incompatibilidade torna o subproblema de encontrar o fornecimento ótimo a partir das instalações abertas NP-difícil, mesmo quando o conjunto de instalações abertas é fixo.

Metodologia
Os autores propõem uma estrutura de Busca em Grande Vizinhança (LNS) para resolver o MS-CFLP-CI. O núcleo da abordagem envolve destruir iterativamente uma porção da solução atual e repará-la utilizando um solver exato de Programação Mista Inteira (MIP) (Gurobi).

• Representação da Solução: As soluções são representadas como matrizes de quantidades transportadas, apoiadas por estruturas de dados auxiliares que rastreiam instalações abertas/fechadas e clientes atribuídos.
• Solução Inicial: Uma heurística constrói uma solução inicial ordenando as instalações por custo de abertura, selecionando o suficiente para atender à demanda total e adicionando um número específico de instalações extras ($k=5$) para lidar com as restrições de incompatibilidade. Os clientes são atribuídos com base em uma estratégia uniforme.
• Operadores de Destruição: O artigo introduz três novos operadores de destruição projetados especificamente para as restrições de incompatibilidade:
  1. Instalações Mais Baratas (CF): Seleciona uma instalação aleatória e seus clientes, depois identifica outras instalações abertas que oferecem o menor custo médio de transporte para aquele grupo específico de clientes.
  2. Clientes Híbridos (HC): Uma recombinação de duas estratégias. Seleciona uma instalação aleatória e seus clientes, depois identifica "clientes mais baratos" (aqueles com baixo custo de transporte para a instalação) e "clientes caros" (aqueles com alto custo de transporte). Em seguida, seleciona instalações adicionais que oferecem o melhor serviço para esses subconjuntos específicos de clientes.
  3. Instalações Fechadas: Tanto instalações fechadas aleatórias quanto aquelas com a medida de custo mínima ($Q_g$) são incluídas no subproblema para explorar a abertura de novas instalações.
• Operador de Reparo: O subproblema definido pelos elementos destruídos é resolvido exatamente usando o Gurobi. Para gerenciar o tempo computacional, a fase de reparo inclui uma restrição limitando o número de novas instalações abertas a, no máximo, duas a mais do que as atualmente envolvidas no subproblema. Um valor de corte (o custo atual do subproblema) é fornecido ao solver para acelerar a convergência.
• Configuração e Ajuste Fino: Os autores empregam a ferramenta irace para ajuste de parâmetros baseado em recursos, ajustando parâmetros como o tamanho do subproblema ($\nu$) com base na escala da instância (especificamente distinguindo entre instâncias com $\le 700$ e $> 700$ instalações). O algoritmo final, denominado $LNS_{init,accept}$, combina os operadores de destruição propostos com uma heurística de solução inicial aprimorada e um critério de aceitação que permite que soluções com custo igual sejam aceitas, facilitando a fuga de ótimos locais.

Principais Contribuições

• Novo Framework Algorítmico: Esta é a primeira aplicação de Busca em Grande Vizinhança ao problema MS-CFLP-CI.
• Operadores Especializados: O design de operadores de destruição (CF e HC) que levam explicitamente em conta as restrições de incompatibilidade, indo além das heurísticas padrão de localização de instalações.
• Reparo Híbrido Exato/Heurístico: A integração de um solver exato de MIP na fase de reparo, otimizado com restrições específicas para equilibrar a qualidade da solução e o tempo de execução.
• Análise Rigorosa: Um estudo de ablação abrangente e análise estatística (usando testes de Friedman e Nemenyi) para avaliar o impacto de componentes individuais (inicialização, critérios de aceitação, pesos adaptativos).
• Benchmarking Extensivo: Avaliação em dois conjuntos de dados de grande escala (wlp e cflp-ci) contendo até 3.000 instalações e 8.000 clientes.

Resultados Experimentais
O método proposto $LNS_{init,accept}$ foi testado contra metaheurísticas de última geração, incluindo Busca Local Iterada Multi-Início baseada em MineReduce (MR-MS-ILS), GRASP, Algoritmo Evolutivo Codificado por Permutação (PcEA), Múltiplos Inícios Gulosos (MG) e Recozimento Simulado (SA).

• Desempenho: O método proposto superou significativamente todos os métodos existentes em ambos os conjuntos de dados sob dois limites de tempo diferentes ($10\sqrt{m}$ e $m$ segundos).
• Novas Melhores Soluções: A abordagem encontrou novas melhores soluções para todas as 80 instâncias em ambos os conjuntos de dados.
• Significância Estatística: Testes estatísticos confirmaram que as melhorias sobre o método anterior mais eficaz (SA) são estatisticamente significativas.
• Escalabilidade: Enquanto solvers exatos (Gurobi/CPLEX) só puderam resolver instâncias de até 150 instalações até a otimalidade dentro de um tempo razoável, a abordagem LNS lidou efetivamente com instâncias de até 3.000 instalações.
• Redução de Lacuna: Para o conjunto de dados wlp, o método alcançou melhorias de lacuna variando de -0,68% a -1,84% sobre as melhores soluções conhecidas. Para o conjunto de dados cflp-ci, as melhorias variaram de -0,46% a -2,09%.

Significância e Afirmações
Os autores afirmam que seu método representa o estado da arte atual para o problema MS-CFLP-CI. A significância do trabalho reside em sua capacidade de lidar com a complexidade computacional introduzida pelas incompatibilidades de clientes, que metaheurísticas anteriores lutaram para otimizar completamente, particularmente para instâncias maiores. O artigo afirma que a combinação de novos operadores de destruição, uma fase de reparo exata e um ajuste algorítmico específico permite que o método explore vizinhanças de tamanho médio de forma eficaz, encontrando soluções superiores onde o SA e outros métodos estagnam. Os autores observam modestamente que, embora seu método seja atualmente o melhor, trabalhos futuros poderiam envolver Análise do Espaço de Instâncias para entender melhor a dificuldade das instâncias e estender a abordagem para outras variantes de localização de instalações.