Um Conjunto de Restrições Fortalecidas para o Problema de Cobertura Multi-Veículo

Vol 55, 2023 - 160611
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

O Problema da Cobertura Multi-Veículo envolve um depósito, clientes e facilidades obrigatórias e opcionais. O objetivo é encontrar rotas de custo total mínimo, onde cada rota começa e termina no depósito, visita no máximo p pontos, não visita diretamente nenhum cliente e cada facilidade obrigatória é visitada exatamente uma vez por uma das rotas. Além disso, para cada cliente, deve haver ao menos uma facilidade opcional visitada que esteja a no máximo uma distância beta deste cliente. Para o PCMV, propomos um conjunto de restrições que são incorporadas ao problema mestre de um dos dois principais algoritmos de Branch-and-cut-and-price (BCP) existentes na literatura. Apresentamos resultados computacionais para 96 instâncias benchmark do problema que mostram que o algoritmo BCP que usa as restrições propostas supera os outros dois métodos e obteve todas as 96 soluções ótimas, onde duas delas eram até o momento desconhecidas.

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 Fluminense
Eixo Temático
  • 14. OC – Otimização Combinatória
Palavras-chave
Problema de Cobertura Multi-Veículo; Branch-and-cut-and-price; VRP-Solver