Abordagens mono e multiobjetivo para o problema de roteamento de veículos capacitados com restrições tridimensionais de carregamento
Carregando...
Data
2020-02-28
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Centro Federal de Educação Tecnológica de Minas Gerais
Resumo
Com a expansão da internet, o transporte de produtos ocupa uma das funções mais importantes no comércio eletrônico. Um dos parâmetros com elevado impacto nessa importância está nos altos custos envolvidos com o transporte na economia. Diante desse fato, é considerável analisar os problemas reais enfrentados pelos atores desse ramo de atividade. As questões que se referem ao roteamento e carregamento de veículos, em decorrência de suas complexidades, constituem uma das aplicações com maior potencial na área de otimização. Com o foco de facilitar essas questões, este trabalho tem como objetivo solucionar o problema de roteamento de veículos capacitados com restrições tridimensionais de carregamento (3L-CVRP). Este trabalho traz soluções para o problema em duas modelagens distintas, mono-objetivo e multiobjetivo. No mono-objetivo, a finalidade é minimizar a distância total percorrida pelos veículos. Foram implementados os seguintes algoritmos: Algoritmo Genético, Variable Neighborhood Search (VNS), Simulated Annealing e Busca Tabu. No Algoritmo Genético, utilizou-se as soluções geradas pelas técnicas Greedy Randomized
Adaptive Search Procedure (GRASP) e soluções resolvidas por programação linear inteira (PLI) utilizando o pacote comercial CPLEX aplicadas ao problema de roteamento de veículos capacitados (CVRP) para construir a população inicial. No restante dos algoritmos implementados, as soluções do PLI obtidas pelo CPLEX foram utilizadas como solução inicial. Os resultados obtidos foram comparados aos da literatura e entre os algoritmos construídos. Na abordagem multiobjetivo, acrescentou-se o objetivo de minimizar a quantidade de veículos utilizados para a entrega dos itens. Foi feito a implementação do algoritmo Non-Dominated Sorting Genetic Algorithm II (NSGA-II) aplicado ao CVRP e 3L-CVRP. Para o CVRP, as soluções encontradas foram comparadas às da literatura. O algoritmo alcançou resultados satisfatórios, se aproximando do estado da arte, e em algumas instâncias, superando as soluções obtidas. Para o 3L-CVRP, os resultados alcançados exploraram novas soluções para o problema em comparação com a literatura.
Descrição
Palavras-chave
Programação heurística, Otimização combinatória, Transporte de carga, Contêineres