Heurística baseada em agrupamentos hierárquicos para resolver um problema de roteamento de veículos dinâmico e estocástico

Abstract

This monograph presents the development of algorithms to solve a specific case of the Stochas tic and Dynamic Capacitated Vehicle Routing Problems (SD-CVRP), known as the Last Mile Incremental Capacitated Vehicle Routing Problem (ICVRP). The proposed approach involves applying a strategy based on hierarchical clustering models to determine vehicle assignments for each analyzed delivery. This application aims to generate efficient routes to optimize key metrics such as distance traveled, number of routes generated, and execution time of the various process stages. Experimental results, obtained from over one hundred thousand deliveries across eleven regions in Brazil, demonstrate the effectiveness of the proposed approach for solving the ICVRP and show competitive performance. Compared to the K-means Greedy approach, which had the lowest total distance traveled among the reference algorithms, the proposed solution reduced the total distance by 2,500 km and maintained a competitive execution time, with a difference of less than 2 minutes compared to the QRP Sweep algorithm, the fastest among those tested. However, the proposed method showed an increase of nearly 52% in the distance traveled compared to the static VRP, offset by a 75% reduction in execution time. When compared to the MAS method from Loggi, the solution showed an increase of 19% in the total distance traveled. These results indicate the feasibility and efficiency of the solution for the ICVRP while highlighting potential opportunities for future improvements.