Um modelo híbrido estocástico para tratamento do problema de roteamento de veículos com janela de tempo

Abstract

A alocação de veículos para uma determinada demanda de consumidores, espalhados geograficamente, está sujeita a uma explosão combinatória de possibilidades, devido às infinitas alternativas de escalonamento. Esta característica impossibilita, para grandes demandas, o tratamento deste problema por algoritmos exatos, ou seja, aqueles que buscam com garantia a solução ótima do problema. Em contrapartida, existem os métodos heurísticos, que são capazes de resolver tais problemas de forma satisfatória, mas não garantindo que a solução alcançada seja a melhor possível. Esta dissertação apresenta, como principal contribuição, um Sistema Híbrido (SH) para o conhecido Problema de Roteamento de Veículos com Janela de Tempo (PRVJT). Este SH é composto dos métodos (i) Recozimento Simulado Não Monotônico (RSNM), (ii) Subida na Encosta (SE) e (iii) Reinício Aleatório (RA). Os métodos foram combinados visando promover a diversificação e a intensificação na busca por soluções do PRVJT. Como contribuição secundária, este trabalho apresenta um arcabouço de métodos estatísticos que é capaz de ajustar parâmetros de sistemas estocásticos para otimização de desempenho. Os resultados dos experimentos realizados com o modelo proposto foram comparados com cada um dos melhores resultados individuais, alcançados anteriormente, pelos diferentes algoritmos conhecidos, para toda a base de dados de Solomon. Os resultados obtidos pelo SH se mostraram relevantes, tendo o método superado ou igualado 37 das 56 instâncias testadas, caracterizando o SH como um método eficaz e robusto no tratamento do PRVJT