Resolução do problema de roteamento de veículos com janelas de tempo e incerteza nos tempos de viagem e serviço por meio de um algoritmo simheurístico.

Abstract

Uma das formas de adotar processos logísticos mais ágeis e adaptados aos perfis dos clientes é a otimização da utilização de veículos e de suas rotas de entrega, objetivando a minimização dos custos envolvidos na operação. Na literatura, este problema corresponde ao Problema de Roteamento de Veículos (PRV). Para tratar complicações realistas e generalizações do modelo básico de roteamento, surge o Problema de Roteamento de Veículos com Janelas de Tempo (PRVJT), onde os clientes devem ser atendidos dentro de um certo período de tempo. Em cenários reais, o tempo de viagem e serviço das rotas pode ser afetado por diversos aspectos, como a má qualidade das vias e condições meteorológicas, o que gera uma incerteza intrínseca aos problemas deste tipo. O presente trabalho tem como objetivo o desenvolvimento de um algoritmo baseado nas chamadas simheuristics, de forma a combinar as meta-heurísticas ILSVNS com as Simulações de Monte-Carlo para encontrar boas soluções para o PRVJT com incerteza nos tempos de viagem e serviço em tempo computacional aceitável. Em um primeiro momento o problema é resolvido em sua forma determinística e, posteriormente, os tempos determinísticos são substituídos por amostras aleatórias de uma função densidade de probabilidade pré-determinada. Por fim, são avaliados os impactos da presença da incerteza nas soluções encontradas. O método proposto foi validado através da comparação dos resultados obtidos com resultados encontrados na literatura para instâncias de pequeno porte, onde a diferença entre os resultados foi mínima ou nenhuma. O algoritmo se mostrou eficiente para resolução de instâncias com clientes distribuídos aleatoriamente e para instâncias com clientes agrupados. Entretanto, os resultados foram consideravelmente piores para instâncias que possuem essas duas características em conjunto.