Avaliação de desempenho do algoritmo de Clarke-Wright para a construção de rotas e de seu aprimoramento utilizando busca local

Abstract

The Vehicle Routing Problem (VRP) still represents a significant challenge in modern days due to its computational complexity. There is no efficient method capable of solving all possible cases, which range from small instances to massive instances containing tens of thousands of points to be considered. In this work, we take a step back in time to analyze and compare two of the earliest comprehensive solutions to this problem in terms of efficiency and performance. The first one is the Clarke and Wright algorithm proposed in 1964, and the second is the application of the 2-opt method, proposed a few years earlier in 1958, on the result generated by the previous algorithm. Applying this improvement method on top of a constructive heuristic further enhances the result. It brings it closer to the optimal solution at a low computational cost. Both algorithms were manually implemented using the Python programming language, enabling direct executions where we can directly observe the cost of the resulting solutions.