Soluções para o Problema do Roteamento de Veículos

Abstract

Grande parte do valor final dos produtos destinados aos clientes está diretamente ligada ao processo de distribuição, por isso, serviços baseados em entregas visam abranger o maior número possível de clientes para minimizar os custos. No entanto, encontrar rotas que realmente minimizem os custos de entrega é uma tarefa desafiadora. Além disso, a definição de quais custos minimizar seja o custo total da entrega, o número de veículos na frota, o tempo de entrega, entre outros. Nesse contexto, surge o Problema do Roteamento de Veículos (PRV), proposto por Dantzig e Ramser. Os desafios reais são delineados por diversas restrições, como a capacidade dos veículos, janelas de tempo para atendimento de clientes e proibições em determinados caminhos. Essas restrições geram distintas variações do PRV, cada uma refletindo um cenário específico do mundo real. A presença dessas restrições solidifica o PRV como um dos problemas mais desafiadores no âmbito da otimização combinatória. Vale destacar que o PRV é classificado como NP-difícil. Um problema NP-difícil indica que não há algoritmo eficiente conhecido para resolver todas as instâncias do problema em tempo polinomial. O PRV representa um desafio computacional substancial, motivando o desenvolvimento de uma variedade de heurísticas, meta-heurísticas e modelos híbridos para abordar eficazmente essas complexidades, uma vez que encontrar soluções ótimas pode ser impraticável em um tempo razoável. O objetivo deste trabalho é apresentar o PRV e algumas de suas variações e propor uma solução para o Problema do Roteamento de Veículos Capacitado (PRVC) usando Algoritmos Genéticos (AGs). O restante deste trabalho está organizado da seguinte maneira: a Seção 2 destaca alguns trabalhos relacionados, evidenciando a evolução do estado da arte, a Seção 3 aborda o referencial teórico para fundamentar o projeto, a Seção 4 expõe a metodologia adotada na implementação do trabalho, a Seção 5 engloba os experimentos realizados e a análise dos resultados obtidos e, por fim, a Seção 6 aborda a conclusão e os trabalhos futuros.