O papel da Pesquisa Operacional na indústria moderna vem recebendo cada vez mais destaque e importância nos mais diversos meios, uma vez que visa a maximização ou minimização de uma determinada variável considerada importante para o andamento da empresa. Dentro dos problemas abordados em Pesquisa Operacional está o PRV (Problema de Roteamento de Veículos), que pode ser considerado um dos principais Problemas de Transporte com o objetivo de atender as demandas requisitadas por clientes, localizadas nos mais diversos pontos de uma determinada rede de transporte. De modo geral, o PRV busca encontrar, entre as opções existentes, a melhor rota, de acordo com os parâmetros definidos (custo da viagem, distância, tempo de entrega, carga a ser transportada etc.), de modo a otimizar o processo envolvido. Ainda, por possuir uma ampla gama de aplicações, esses problemas são subdivididos em classes, de acordo com as necessidades específicas de cada cliente, levando em consideração condições como número de veículos, tempo e prioridade de entrega, entre outros. O objetivo inicial da pesquisa realizada busca a avaliação do desempenho dos modelos matemáticos clássicos, encontrados na literatura, para a solução desses problemas. Mais precisamente, a classe em que optou-se pelo estudo, devido à grande aplicação existente, foram os Problemas de Roteamento de Veículos com Janela de Tempo (PRVJT), que busca a otimização do tempo gasto durante o deslocamento do veículo na rota, incluindo, por exemplo, o tempo em que o veículo irá ficar parado em um dado cliente enquanto o serviço é prestado e o tempo que este veículo irá levar para se deslocar de um cliente para o próximo. Assim, o tempo que cada um dos veículos (em caso de existência de frota) irá gastar em uma rota é reduzido ao mínimo e, consequentemente, mais rentável possível, permitindo o atendimento de prazos reduzidos e, consequentemente, otimizando os ganhos do fornecedor e também do cliente. Com base nos resultados obtidos por meio dos modelos matemáticos desenvolvidos, pôde-se concluir que o PRVJT apresenta soluções ótimas apenas para instâncias de pequeno porte, exigindo um tempo computacional extremamente elevado para os casos de médio e grande porte, gerando, nos dois últimos casos, apenas soluções incumbentes. Pôde-se assim constatar que a complexidade dos problemas dessa classe cresce de forma exponencial a partir do crescimento do número de clientes atendidos, inviabilizando a utilização dos modelos matemáticos para problemas mais complexos e de grande porte devido à alta capacidade computacional requisitada por esses.