A Metaheuristic Solution for the Capacitated Vehicle Routing Problem: Empirical Evaluation of Flexible Capacity Constraints via Ant Colony Optimisation

Resumo Técnico: Uma Solução Metaheurística para o Problema de Roteamento de Veículos Capacitados

1. Definição e Contexto do Problema
O estudo aborda um Problema de Roteamento de Veículos Capacitados (CVRP) do mundo real, decorrente de uma operação de coleta de matéria-prima de entrada na Colômbia. A rede logística consiste em um depósito central em Guadalajara de Buga (Valle del Cauca) atendendo trinta centros de distribuição localizados em diversas regiões colombianas (costas, planaltos andinos e zonas industriais). A operação enfrenta ciclos de demanda variáveis (643 a 1.192 pacotes por ciclo) e utiliza uma frota homogênea de dez caminhões Foton FRR Cummins.

Uma restrição operacional crítica é a política de capacidade flexível: embora a capacidade nominal do veículo seja $Q = 150$ pacotes, a política corporativa autoriza uma sobrecarga controlada de 5%, estabelecendo uma capacidade de planejamento efetiva de $Q_{eff} = 157,5$ pacotes. O roteamento deve ser realizado sobre redes rodoviárias não euclidianas derivadas do OpenStreetMap (via OSMnx), onde as complexidades topológicas (corredores montanhosos, ruas de mão única) criam uma assimetria significativa entre as distâncias euclidianas e os custos reais de viagem.

O sistema de planejamento atual, "Rout Now", emprega uma arquitetura "cluster-first, route-second" (agrupar primeiro, rotear depois): ele particiona os nós em 10 clusters geográficos usando k-means (baseado em coordenadas planas) e, em seguida, sequencia cada cluster de forma independente usando Simulated Annealing (SA). Essa abordagem resulta em utilização heterogênea da frota (35%–90%) e implementa sistematicamente todos os 10 veículos, mesmo quando os limites teóricos inferiores sugerem que 6–8 veículos seriam suficientes.

2. Metodologia
A pesquisa propõe e avalia uma metaheurística de Otimização por Colônia de Formigas (ACO) projetada para operar no grafo completo de nós ativos sem particionamento geográfico prévio.

• Formulação Matemática: O problema é modelado como um Programa Linear Inteiro Misto (MILP) utilizando a formulação de Miller–Tucker–Zemlin (MTZ) para eliminação de sub-rotas. A restrição de capacidade é explicitamente relaxada para $Q_{eff} = 157,5$ para modelar a política de sobrecarga dentro da lógica de otimização.
• Arquitetura ACO:
  • Construção: As formigas constroem rotas multi-veículo iterativamente. Um diferencial fundamental é o mecanismo de mascaramento dinâmico: o conjunto de próximos nós viáveis ($F_k$) é filtrado em tempo real para garantir que a carga acumulada não exceda $Q_{eff}$. Isso permite que o algoritmo "empacote" os nós de forma eficiente, explorando a margem de 5% apenas quando necessário para evitar a abertura de uma nova rota.
  • Probabilidade de Transição: A probabilidade de selecionar um nó depende dos rastros de feromônio ($\tau$) e da visibilidade heurística ($\eta = 1/C_{ij}$). Dada a alta variância nos custos rodoviários colombianos (desvio padrão de 47% em relação à média), o peso heurístico ($\beta = 2,0$) foi calibrado para dominar o peso do feromônio ($\alpha = 1,0$), priorizando a eficiência de custo imediata.
  • Mecanismo de Atualização: Aplicam-se as regras padrão de evaporação e depósito, reforçando arcos que contribuem para soluções de baixo custo e alta consolidação.
• Design Experimental:
  • Cenários: Dez cenários operacionais distintos (S-1 a S-10), representando um mês completo de ciclos de planejamento, foram extraídos de dados reais da empresa.
  • Repetição: Cada cenário foi executado 20 vezes independentemente com diferentes sementes aleatórias para isolar a variância estocástica.
  • Comparação com Baseline: Os resultados do ACO foram comparados contra o baseline "Rout Now" (k-means + SA) usando matrizes de distância OSMnx idênticas para garantir a validade interna.
  • Validação Estatística: O teste de postos sinalizados de Wilcoxon foi aplicado às médias das distâncias totais das 20 execuções por cenário para testar a significância estatística.

3. Principais Resultados
A abordagem ACO demonstrou melhorias sistemáticas e estatisticamente significativas em relação ao baseline em todos os dez cenários:

• Redução de Frota: No cenário de maior demanda (S-3; 1.192 pacotes), o ACO reduziu a frota ativa de 10 veículos (baseline) para 8 veículos, correspondendo ao limite inferior teórico ($\lceil 1192/157,5 \rceil = 8$). Em todos os cenários, a frota ativa foi reduzida em aproximadamente 20%.
• Distância e Custo:
  • Distância Total: Reduzida em uma média de 20,05% (variando de 19,97% a 20,25%). Em S-3, a distância caiu de 11.023 km para 8.790,5 km.
  • Custo de Combustível: Economia estimada de 16,05% no cenário crítico (aprox. 941.340 COP por ciclo).
  • Tempo Operacional: Reduzido em 20,02%.
• Utilização de Capacidade: O ACO alcançou uma consolidação quase perfeita, elevando a utilização média de capacidade de ~79,47% (baseline) para 99,50% em S-3. As rotas na solução ACO operaram entre 96% e 101% da capacidade nominal, com rotas específicas explorando a margem de sobrecarga de 5% para evitar a necessidade de um nono veículo.
• Significância Estatística: O teste de postos sinalizados de Wilcoxon resultou em um estatístico de $W=0$ (todas as diferenças favoreceram o ACO) com um p-valor $< 0,01$, rejeitando a hipótesia nula de igualdade de medianas e confirmando a robustez das melhorias.

4. Significância e Contribuições
O artigo reivindica três contribuições científicas primárias:

1. Avaliação Empírica de Restrições Flexíveis: Documenta como a modelagem explícita de uma restrição de capacidade flexível ($Q_{eff}$) dentro de uma metaheurística construtiva permite uma consolidação de carga coordenada que é estruturalmente impossível para arquiteturas de particionamento prévio. O estudo demonstra que a tolerância de 5% não é meramente um buffer de segurança, mas uma alavanca estratégica para redução de frota quando gerenciada dinamicamente.
2. Robustez em Topologias do Mundo Real: O trabalho fornece evidências de que metaheurísticas inspiradas na natureza (especificamente ACO) superam heurísticas clássicas de "cluster-first, route-second" em redes rodoviárias complexas e não euclidianas. O estudo destaca que o particionamento geográfico prévio (k-means) falha em considerar as assimetrias da rede rodoviária, enquanto o ACO opera no espaço de custo real.
3. Identificação de Mecanismo Causal: O artigo identifica o "mascaramento dinâmico" de nós inviáveis durante a construção da rota como o mecanismo causal para o sucesso. Isso permite que o algoritmo realize um "empacotamento eficiente" da demanda, explorando organicamente a margem de sobrecarga para minimizar o número de rotas, uma capacidade ausente no baseline de clusters geográficos fixos.

5. Limitações e Trabalhos Futuros
Os autores observam que o estudo é limitado a um contexto industrial específico sem janelas de tempo (VRPTW) ou restrições de horas de motorista. Direções de pesquisas futuras propostas incluem:

• Estender o modelo para VRPTW para incorporar cronogramas de recepção.
• Abordar a incerteza da demanda via VRP Estocástico (SVRP).
• Desenvolver formulações multiobjetivo (ex: minimização de emissões de CO₂) usando algoritmos evolucionários.
• Integrar o núcleo ACO como um microsserviço para testes A/B controlados dentro de sistemas logísticos existentes.