Resumo Técnico: Uma Metaheurística Híbrida para o Problema de Roteamento de Veículos com Capacidade de Família

Definição do Problema

O artigo aborda o Problema de Roteamento de Veículos com Capacidade de Família (F-CVRP), uma generalização do Problema do Caixeiro Viajante com Família (FTSP) e do clássico Problema de Roteamento de Veículos com Capacidade (CVRP). No F-CVRP, uma frota homogênea de $K$ veículos com capacidade $Q$ parte de um depósito único para atender a um conjunto de clientes particionados em famílias. Diferente do CVRP padrão, onde cada cliente deve ser visitado, o F-CVRP exige que um número específico de membros ($v_l$) de cada família $l$ seja visitado, enquanto os demais membros dessa família podem ser deixados sem visita. O objetivo é minimizar o custo total de roteamento, respeitando as restrições de capacidade dos veículos e cumprindo os requisitos exatos de visitação para cada família.

À medida que as instâncias do problema escalam, os métodos exatos tornam-se computacionalmente proibitivos. Consequentemente, o artigo foca no desenvolvimento de uma heurística rápida e de alta qualidade, capaz de entregar soluções dentro de orçamentos de tempo rigorosos, servindo tanto como um resolvedor autônomo quanto como um provedor de limites primais para estruturas exatas.

Metodologia: A Metaheurística Híbrida ILS+SP

Os autores propõem o ILS+SP, uma metaheurística híbrida que combina uma estrutura de Busca Local Iterada (ILS) com uma fase de pós-otimização de Particionamento de Conjuntos (SP). O algoritmo opera da seguinte forma:

1. Núcleo de Busca Local Iterada (ILS)

A busca é impulsionada por uma estrutura de ILS que mantém um pool de rotas ($P$) e rastreia a melhor solução viável encontrada ($s^*$).

• Solução Inicial: Gerada via uma heurística de Inserção Paralela de Melhor Desempenho (BPI), construindo $K$ rotas ao inserir iterativamente clientes para minimizar o aumento de custo, garantindo que as contagens de visitas das famílias sejam atendidas.
• Busca Local (RVND): A busca local emprega uma estratégia de Descida de Vizinhança de Variável Aleatória (RVND). Ela explora um portfólio de nove vizinhanças:
  • Entre rotas (5): Swap(1,1), Swap(2,1), Swap(2,2), Shift(1,0), Shift(2,0).
  • Intrarrota (3): Exchange, Reinsertion, Or-opt2.
  • Especializada (1): MemberRelocate, um operador específico do problema que remove um cliente visitado e insere um membro não visitado da mesma família na melhor posição entre todas as rotas.
  • Todas as vizinhanças preservam as restrições estruturais das contagens de visitas das famílias e o número de rotas ativas ($K$).
• Critério de Aceitação: Ao contrário da busca local padrão, o algoritmo aceita movimentos de piora baseados em um critério de Simulated Annealing (SA) com um cronograma de resfriamento baseado no tempo. Isso permite que a busca escape de mínimos locais.
• Perturbação: Para diversificar a busca, o algoritmo aplica uma de três perturbações aleatórias (RandomSwap, RandomShift ou RandomMemberRelocate) à solução atual antes de reentrar na busca local.
• Tratamento de Penalidades: As violações de capacidade são tratadas via um coeficiente de penalidade dinâmica ($\theta$) na função objetivo, que é ajustado com base na viabilidade da solução atual para guiar a busca em direção a regiões viáveis.

2. Pós-Otimização por Particionamento de Conjuntos (SP)

Ao esgotar o orçamento de tempo, o algoritmo realiza uma etapa final de otimização. Ele formula um problema de Particionamento de Conjuntos (SP) sobre o pool de rotas com capacidade viável ($P$) coletado durante todo o processo de busca.

• O modelo SP seleciona um subconj conjunto de rotas para minimizar o custo total enquanto satisfaz os requisitos de visita das famílias e utiliza exatamente $K$ rotas.
• Como o pool $P$ contém as rotas que compõem a melhor solução encontrada até o momento ($s^*$), a solução ótima do SP é garantidamente tão boa quanto ou melhor que $s^*$.

Principais Contribuições

O artigo destaca quatro contribuições primárias que distinguem este trabalho do estado da arte (especificamente o ILS de Bernardino e Paias, 2024):

1. Hibridização com Particionamento de Conjuntos: A introdução de uma fase de pós-otimização SP para reotimizar o pool de rotas, um componente de matheurística ausente em abordagens anteriores.
2. Busca Local Aprimorada: A implementação da vizinhança MemberRelocate, que insere de forma ótima membros da família não visitados na melhor posição entre todas as rotas, em vez de simplesmente trocá-los no mesmo lugar.
3. Exploração de Vizinhança Aleatorizada: O uso de RVND para randomizar a ordem de exploração das vizinhanças, contrastando com a ordem fixa utilizada na literatura anterior.
4. Aceitação por Simulated Annealing: A adoção de um critério de SA para aceitar soluções piores, substituindo a aceitação estrita de apenas melhorias de métodos anteriores, melhorando assim o equilíbrio entre intensificação e diversificação.

Resultados Computacionais

Os autores avaliaram o ILS+SP em dois conjuntos de benchmarks:

1. Benchmark Padrão (144 instâncias): Derivado do conjunto de Augerat et al. (1995), contendo instâncias com mais de 50 clientes.
   • Desempenho: O método venceu ou empatou em todas as instâncias contra a heurística de estado da arte de Bernardino e Paias (2024).
   • Redução de Gap: O gap médio para a Melhor Solução Conhecida (BKS) foi reduzido de 1,84% (melhor anterior) para 0,01%.
2. Benchmark de Escalabilidade (120 instâncias): Um novo conjunto de instâncias maiores (até 142 clientes) derivado do CVRP Set X (Uchoa et al., 2017).
   • Desempenho: O algoritmo alcançou um gap médio de 0,47% com um tempo de execução médio de 37 segundos, demonstrando escalabilidade para problemas de maior tamanho.

Significância e Alegações

O artigo posiciona o ILS+SP como uma solução robusta e escalável para o F-CVRP. Os autores afirmam que, ao integrar uma pós-otimização de matheurística (SP) com uma sofisticada estrutura de ILS apresentando vizinhanças específicas do problema e aceitação por SA, o método supera significativamente as heurísticas existentes. Os resultados sugerem que a abordagem é capaz não apenas de igualar ou melhorar as melhores soluções conhecidas para benchmarks estabelecidos, mas também escala efetivamente para instâncias maiores e mais complexas, tornando-se uma ferramenta valiosa tanto para aplicação autônoma quanto para integração em estruturas de solução exatas.