Abordagem heurística paralelizada para a resolução do problema do roteamento de veículos capacitados com base na estratégia ”cluster first route second”

Abstract

The Capacited Vehicle Routing Problem (CVRP) seeks to determine a set of routes for a homogeneous fleet of vehicles from a central warehouse bound to a set of customers who demands products. As one of the most important and complex problems related to the logistics of distribution, heuristics to the problem are constantly developed. On this way, this paper addresses the heuristic approach based on strategy “Cluster First Route Second” that consists of grouping customers according to demand to further build routes for the groups formed. The approach employs classical algorithms Teitz and Bart (1968) and Gillett and Johnson (1976) for solving the clustering problem, while the routes for each group are constructed by the nearest neighbor heuristic and refinements arising from exchanges by 2-opt. It is also used parallel computing to reduce the computational time. Simulations performed with the classic instances available in the shown literature results on a performance of 15,0% instead. The results took an advantage of consuming a computational processing time shorter than 7 seconds to solve each instance.