Algoritmos de Branch-Cut-and-Price para Roteamento de Veículos em Clusters

Favoritar este trabalho
Como citar esse trabalho?
Detalhes
  • Tipo de apresentação: Trabalho completo (oral)
  • Eixo temático: 12. L&T – Logística e Transportes
  • Palavras chaves: Roteamento de veículos; geração de colunas; Modelagem;
  • 1 Universidade Federal Fluminense

Algoritmos de Branch-Cut-and-Price para Roteamento de Veículos em Clusters

Matheus Freitas Antunes

Universidade Federal Fluminense

Resumo

O problema de roteamento de veículos em clusters é uma generalização do clássico roteamento com capacidade. O conjunto de clientes é particionado em clusters, todos os clientes no mesmo cluster deve ser visitados em sequencia em uma única rota. Este artigo propõe dois modelos para o problema. O primeiro deles é semelhante ao usado no clássico problema de roteamento de veículos com capacidade. O segundo tira mais proveito das características particulares do problema, pré-calculando todos os caminhos hamiltonianos mais curtos intra-cluster. Ambos os modelos são implementados e resolvidos pelo algoritmo de branch-cut-and-price existente no pacote VRPSolver. Experimentos computacionais indicam que o segundo modelo é superior. Comparando-se esse modelo com o melhor algoritmo existente na literatura, um branch-and-cut, observa-se resultados melhores na maioria das instâncias com mais de 100 clientes.

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!