Um estudo com abordagem heurística para problemas de roteamento de veículos com janelas de tempo e múltiplos depósitos
Carregando...
Data
2023-02-27
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Centro Federal de Educação Tecnológica de Minas Gerais
Resumo
Este trabalho trata de alguns problemas de roteamento de veículos com janelas de tempo e múltiplos depósitos. Nesse conjunto estão problemas com roteamento fechado e aberto que objetivam a redução na distância ou na quantidade de veículos. Esse conjunto de problemas é NP-difícil, pois eles têm como subproblema, o Problema de Roteamento de Veículos (PRV), onde os clientes são atendidos por uma frota de veículos de mesma capacidade homogênea, em que os custos são dados pela distância total percorrida ou quantidade total de veículos utilizados no atendimento aos clientes. Para resolver esses problemas, o Smart General Variable Neighborhood Search com Busca Local Adaptativa (SGVNSBLA) é apresentado. O algoritmo alterna o mecanismo de busca local entre duas estratégias diferentes. Na primeira estratégia, o método Randomized Variable Neighborhood Descent (RVND) realiza a busca local e, ao aplicar essa estratégia, as vizinhanças com os melhores vizinhos recebem uma pontuação maior. Na segunda estratégia, o método de busca local é aplicado apenas em uma única vizinhança, escolhida pelo método da roleta. Assim, a aplicação da primeira estratégia de busca local serve como método de aprendizagem para aplicação da segunda estratégia. Para testar esses algoritmos, usamos instâncias de benchmark do MDVRPTW envolvendo até 960 clientes, 12 depósitos e 120 veículos, num total de 48 instâncias teste. Para fins de comparação, outros algoritmos baseados em vizinhança também foram implementados. Os resultados encontrados permitiram avaliar a contribuição das estruturas de vizinhanças utilizadas nas soluções que buscam a redução na quantidade de veículos. Os resultados mostram que o desempenho do SGVNSBLA superou o dos outros algoritmos implementados visando a redução da frota. Houve uma redução da frota de veículos em 91,18% das instâncias avaliadas e o tamanho da frota alcançou uma redução média de até 23,32% em problemas com janelas de tempo e múltiplos depósitos. Ao se avaliar essas instâncias com roteamento aberto, houve redução na quantidade de veículos em 100% das instâncias, com baixa variabilidade.
Descrição
Palavras-chave
Programação heurística, Otimização combinatória, Veículos, Algoritmos, Softwares