A Hybrid Matheuristic Framework for the Chinese Postman Problem with Load-Dependent Costs

Resumo Técnico: Uma Estrutura Matheurística Híbrida para o Problema do Carteiro Chinês com Custos Dependentes de Carga

Definição do Problema
Este artigo aborda o Problema do Carteiro Chinês com Custos Dependentes de Carga (CPP-LC), uma variante do clássico Problema de Roteamento de Arcos (ARP). No CPP-LC, o custo de percorrer uma aresta não é apenas uma função de seu comprimento, mas também depende do peso bruto do veículo (peso próprio mais a carga atual) no momento da travessia. Esta formulação reflete a logística do mundo real, onde o consumo de combustível e as emissões aumentam com a carga do veículo. Diferente do CPP padrão, que é solucionável em tempo polinomial, o CPP-LC é geralmente fortemente NP-difícil. O objetivo é encontrar uma rota que comece e termine em um depósito, servindo cada aresta de um grafo conexo pelo menos uma vez, enquanto minimiza o custo total de viagem dependente de carga.

Metodologia
Os autores propõem o MaLD, uma estrutura matheurística híbrida que integra busca metaheurística com programação matemática para equilibrar exploração e intensificação. A estrutura opera através dos seguintes componentes:

1. Formulação Matemática: O estudo utiliza uma formulação de Programação Linear Inteira Mista (MILP) de roteamento de arcos (adaptada de Corberán et al.) para modelar o problema. Para aumentar a eficiência computacional, os autores empregam modelos MILP "reduzidos" que focam em subsequências específicas de arestas em vez de todo o caso do problema.
2. Busca Local: Uma solução inicial é gerada usando uma Heurística Construtiva Gananciosa (GCH). Esta é refinada por meio de um procedimento de busca local que utiliza um movimento de "deslocamento geral". Neste movimento, um subconjunto de arestas é removido aleatoriamente e reinserido na sequência em posições que minimizam o custo total, avaliado usando uma abordagem de programação dinâmica para determinar as direções de travessia ideais.
3. Procedimento de Reordenação: Uma etapa crítica de pré-processamento garante que a rota satisfaça a restrição de que uma aresta seja servida na primeira vez que for visitada. Se uma aresta for percorrida sem serviço (deadheading) antes de ser servida, a sequência é reordenada para servir a aresta mais cedo. Este ajuste frequentemente reduz a carga do veículo mais rapidamente, diminuindo os custos subsequentes de deadheading.
4. Intensificação: Após a busca local e reordenação, o algoritmo entra em uma fase de intensificação. Uma subsequência de arestas consecutivas é selecionada, e um modelo MILP reduzido é resolvido para encontrar a permutação ideal dessas arestas, mantendo o restante da rota fixa. Isso permite uma exploração profunda de vizinhanças específicas que metaheurísticas puras poderiam perder.
5. Otimização por Colônia de Formigas (ACO): Para fornecer uma comparação abrangente, os autores também implementam uma metaheurística ACO. Nesta abordagem, formigas artificiais constroem soluções ao percorrer estados que representam arestas e suas direções de travessia. Trilhas de feromônio são atualizadas com base na qualidade da solução para guiar buscas futuras.

Principais Contribuições

• Estrutura Híbrida: A principal contribuição é o design do MaLD, que combina efetivamente a velocidade da busca local heurística com a exatidão da intensificação baseada em MILP.
• Extensão Algorítmica: Enquanto o trabalho anterior (Corberán et al.) introduziu Busca Local Iterada (ILS) e Busca de Vizinhança Variável (VNS) para o CPP-LC, este artigo introduz o ACO como uma metaheurística comparativa e desenvolve a estrutura MaLD para superar os métodos existentes.
• Escalabilidade e Eficiência: O artigo demonstra que resolver modelos MILP reduzidos em subsequências permite que a estrutura escape de ótimos locais encontrados por metaheurísticas puras, particularmente em instâncias maiores, sem incorrer nos custos de tempo proibitivos de resolver o MILP completo.

Resultados Experimentais
Os métodos propostos foram avaliados em três conjuntos de dados variando de pequenos (8–10 arestas) a grandes (até 232 arestas), cobrindo grafos Eulerianos e instâncias de Christofides e Hertz et al.

• Qualidade da Solução: O MaLD alcançou consistentemente a maior qualidade de solução. Encontrou soluções ótimas para todas as instâncias pequenas onde os ótimos eram conhecidos e superou ILS, VNS e ACO em instâncias médias e grandes. Especificamente, o MaLD melhorou as soluções de ILS e VNS em aproximadamente 6–7% para instâncias de médio porte e por uma média de 1,35% para as maiores instâncias.
• Eficiência Computacional:
  • Instâncias Pequenas: Para instâncias muito pequenas, o GCH foi o mais rápido, e ILS/VNS foram altamente competitivos. O MaLD foi ligeiramente mais lento, mas ainda assim atingiu a otimalidade.
  • Instâncias Grandes: O ACO demonstrou forte escalabilidade, muitas vezes superando ILS e VNS em qualidade de solução, mantendo tempos computacionais significativamente menores devido às suas capacidades de execução paralela. No entanto, o MaLD permaneceu superior em qualidade de solução, embora com custos computacionais mais elevados (ex: ~1262 segundos para o maior grupo vs. ~14 segundos para o ACO).
• Análise de Componentes: A análise de sensibilidade revelou que o componente de intensificação é crítico para a qualidade da solução em instâncias maiores, contribuindo mais para a redução de custos do que o componente de busca local nesses cenários. A remoção da intensificação levou a aumentos significativos de custo (ex: ~211.000 unidades para o maior grupo).

Significância e Alegações
O artigo afirma que a estrutura MaLD é uma estratégia eficaz para resolver problemas de roteamento complexos com dependência de carga, onde os custos de viagem são dinâmicos com base na carga útil. Os resultados destacam que estratégias de otimização híbridas, que unem a pesquisa operacional (MILP exato) e métodos computacionais inteligentes (metaheurísticas), são necessárias para abordar a natureza fortemente NP-difícil do CPP-LC. Embora o ACO se prove uma alternativa competitiva e escalável para instâncias grandes, a abordagem matheurística fornece a qualidade de solução mais robusta. Os autores observam que sua implementação e conjuntos de dados estão disponíveis publicamente para facilitar pesquisas futuras em logística inteligente e roteamento consciente de energia.