Algoritmos para o Problema de Roteamento de Arcos aplicado à Coleta de Resíduos Urbanos

Vol 57, 2025 - 340573
Trabalho completo (Oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

Neste artigo, considera-se o Problema do Roteamento em Arcos Capacitado (CARP), que consiste em determinar rotas de custo mínimo para uma frota de veículos, de forma que cada conexão requerida de um grafo misto seja atendida por exatamente um veículo. É apresentada uma abordagem baseada na decomposição do grafo em setores, com cada setor sendo classificado segundo propriedades de conectividade e balanceamento de graus. Para cada classe, adotam-se estratégias específicas: setores Eulerianos são resolvidos pelo algoritmo de Hierholzer; setores fracamente conexos com graus desbalanceados são tratados pelo Algoritmo Húngaro combinado ao Hierholzer; e setores desconexos são abordados por meio de uma formulação de programação linear inteira. Dessa forma, a abordagem explora a estrutura do problema para integrar técnicas heurísticas e exatas, visando à obtenção eficiente de soluções. Experimentos em instâncias da literatura e em dados reais de Itajubá-MG indicam que a abordagem é promissora em contextos práticos.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Federal de Itajubá
  • 2 Universidade Estadual de Campinas (UNICAMP)
  • 3 Cerebral Diagnostics (Canada)
Eixo Temático
  • L&T – Logística e Transportes
Palavras-chave
Roteamento de Arcos Capacitados
Setorização
Abordagem Híbrida.