Despacho online para o problema dinâmico de roteamento de veículos

Exportado OPUSMade available in DSpace on 2019-08-11T15:12:08Z (GMT). No. of bitstreams: 1 humbertocesar.pdf: 1350452 bytes, checksum: a8e9855efe873d35f911708871ff7be8 (MD5) Previous issue date: 20A alocação de veículos para uma determinada demanda de consumidores está sujeita a uma explosão combinatória de possibilidades, devido ao aumento exponencial de alternativas e de acordo com o crescimento do tamanho do problema. Quando são consideradas alterações no ambiente, como o surgimento de novos consumidores, o Problema de Roteamento de Veículos (PRV) se torna dinâmico e ainda mais complexo e imprevisível. É comum encontrar na literatura do Problema Dinâmico de Roteamento de Veículos (PDRV) trabalhos que utilizam uma abordagem periódica para o roteamento dos veículos. Esta forma de tratamento divide o dia em intervalos bem definidos e trata vários problemas estáticos ao longo do tempo. Como principal contribuição, este trabalho propõe a utilização de algoritmos de roteamento como tomada de decisão imediata ou de curto prazo para tratar os PDRVs. Nesta abordagem, os consumidores são informados rapidamente (online) quando serão atendidos. Este trabalho mostra que a abordagem de roteamento online pode ter maior impacto sobre os custos se comparada a abordagem periódica. Além da contribuição sobre o roteamento online, este trabalho apresenta duas heurísticas híbridas para resolver o Problema estático de Roteamento de Veículos com Janela de Tempo (PRVJT). Ambas exploram a formulação do Problema de Particionamento de Conjuntos para solucionar o PRVJT. O primeiro algoritmo híbrido é especialmente proposto para atender contextos dinâmicos do PRVJT, em que novas soluções devem ser encontradas rapidamente. O segundo algoritmo híbrido é mais robusto, alcança melhores resultados e é indicado para contextos estáticos. Resultados computacionais mostram que as heurísticas propostas são competitivas em comparação com outros algoritmos da literatura que tratam a bem conhecida base de testes de Solomon. Este trabalho superou o melhor resultado conhecido em oito instâncias, considerando a minimização da distância total do PRVJT. Além disso, o segundo algoritmo melhorou ou igualou 82,1% dos melhores resultados conhecidos para a base de testes de SolomonThe allocation of vehicles for a specific customers demand is subject to a combinatorial explosion of possibilities by the exponential increase of alternatives according to growth of the problem size. When environmental changes are considered, such as the advent of new customers, the Vehicle Routing Problem becomes dynamic and even more complex and unpredictable. It is common to find, in the literature of the Dynamic VRP (DVRP), works that use a periodic approach to the vehicles dispatch. This treatment way divides the day at well-defined intervals and handles many static problems over time. As its main contribution, this work proposes the use of online dispatches to treat DVRPs. In this approach, the customers are quickly informed when they will be attended. This work shows that the online dispatch may have a greater impact on costs compared to the periodic dispatch. In addition of online dispatch contribution, this work presents two hybrid heuristics to solve the static Vehicle Routing Problem with Time Windows (VRPTW). Both heuristics explore the set partitioning formulation for the VRPTW. The first hybrid algorithm is specially proposed to attend dynamic contexts of the VRPTW, where new solutions must be quickly found. The second hybrid algorithm is more robust, it achieves best results and it is indicated for static contexts. Computational results show that the proposed heuristics are competitive in comparison with other algorithms of literature considering the well-known Solomons database. This work has found eight new best solutions considering the total distance minimization for VRPTW. Moreover, the second algorithm has obtained results better or equal to 82.1% of the best-known results from Solomons instances