Um algoritmo híbrido para os problemas de roteamento de veículos estático e dinâmico com janela de tempo

O Problema de Roteamento de Veículos com Janela de Tempo (PRVJT) estático é um dos problemas bem conhecidos em otimização combinatória que mais tem recebido atenção nos últimos anos. O objetivo do problema é planejar rotas para uma frota de veículos, sem violação das restrições de tempo e capacidade, minimizando custos. Os custos normalmente estão relacionados à distância total percorrida, ao número de veículos necessário ao atendimento, ao tempo total de espera dos veículos nos consumidores ou à combinação destes. O Problema de Roteamento de Veículos Dinâmico com Janela de Tempo (PRVDJT), por outro lado, é uma generalização do anterior onde parte das informações relevantes são conhecidas somente após o início do processo de otimização.Métodos exatos têm sido normalmente propostos para a versão estática do PRVJT. Melhores resultados com este tipo de método têm sido possível devido ao uso de modernas técnicas de planos de corte (branch-and-cut) e implementações paralelas. Entretanto, 23 dos 56 problemas de Solomon continuam em aberto. Adicionalmente, em muitos casos um tempo proibitivo é necessário para encontrar a solução exata. Muitas heurísticas têm sido desenvolvidas para possibilitar uma solução de boa qualidade dentro de um intervalo aceitável de processamento. Utilizando a distância total percorrida como único objetivo, uma abordagem híbrida é proposta neste trabalho para o PRVJT, utilizando um eficiente algoritmo genético combinado com uma formulação do problema por particionamento de conjunto. Testes foram realizados utilizando cálculos com dupla precisão e com inteiros, possibilitando comparar os resultados com aqueles anteriores, gerados por métodos exatos e heurísticas. Os resultados computacionais mostram que a heurística proposta supera todas as anteriores em termos de distância total percorrida. Os resultados utilizando cálculos com inteiros também são muito competitivos, comparados aos ótimos conhecidos na literatura.Entretanto, a maioria das heurísticas utilizam a redução do número de veículos como primeiro objetivo e a distância total percorrida somente como segundo, sujeito ao primeiro. Uma fase adicional foi então proposta minimizando o número de veículos. Uma seleção baseada em um processo de torneio utilizando critérios hierárquicos foi proposta para o algoritmo genético. Todos os melhores resultados da literatura em termos de número de veículos para as instâncias de Solomon foram alcançados. Depois de minimizado o número de veículos, a proposta inicial para minimização de distância é utilizada, sob uma população de indivíduos solução com número de veículos reduzido.Finalmente, a proposta é aplicada ao problema dinâmico, onde parte dos consumidores são incluídos ou cancelados após o início do processo de otimização. As instâncias de Solomon foram modificadas, possibilitando considerar vários graus de dinamismo. Com resultados desejados para o problema dinâmico, foi possível avaliar a qualidade dos resultados alcançados na proposta para o PRVDJT. Os resultados foram significativos, e mostram que o algoritmo proposto é superior àqueles do tipo re-otimização.The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known and complex combinatorial problem, which has received considerable attention in recent years. The objective of the problem is to plan routes for vehicles, with no violated constraints, minimizing costs. The costs normally are related to the total travel distance, the number of vehicle or routes utilized, the total wait time in the customers or combination of theses. The DVRPTW is the dynamic generalization of the VRPTW, where part of the informationis only known after the initial of the optimization process. Exact methods have normally proposed for the static version of the VRPTW. Results from this type of approach have been improved exploring parallel implementations and modern branch-and-cut techniques. However, 23 out of the 56 high order instances from Solomons test set still remain unsolved. Additionally, in many cases a prohibitive time is needed to find the exact solution. Many efficient heuristic methods have been developed to make possible a good solution in a reasonable amount of time. Using travel distance as themain objective, in this thesis, a robust heuristic approach for the VRPTW using an efficient genetic algorithm and a set partitioning formulation is proposed. The tests were run using both, real numbers and truncated data type, making it possible to compare the results with previous heuristic and exact methods. Furthermore, computational results show that the proposed heuristic approach outperforms all previous known heuristic methods in the literature, in terms of the minimal travel distance. However, a great number of heuristics has used the number of vehicles as the first objective and travel distance as the second, subject to the first. An additional phase is proposed to minimize the number of vehicles. Initially, a hierarchical tournament selection genetic algorithm is applied. It can reach all best results in number of vehicles of the 56 Solomons problems explored in the literature. After then, the two phase approach, the genetic and the set partitioning, is applied to minimize the travel distance as the second objective. Finally, the proposed framework is applied a dynamic version of the problem. Using part of customers being inserted or canceled after the initial of the optimization process, the instances of Solomon are modified, making it possible to consider many degrees of dynamism. The fact of the desired results of the dynamic version of the proposed instances are the same of the static version, has make possible to evaluate the quality of the results from the proposed heurist for the DVRPTW