Métodos heurísticos aplicados ao problema de agrupamento de entregas em veículos de uma frota heterogênea

Abstract

The problem of grouping deliveries in a heterogeneous fleet of vehicles is complex and essential for the distribution of goods in an industry. Known in the literature as Variable Sized Bin Packing (VSBPP), this problem consists of, given a set of objects (deliveries), to determine the minimum number of bins needed to allocate this transport. The present work sought to solve one hundred problems of different benchmarking test instances of the literature with different cost functions, through the methods: mathematical modeling, greedy constructive heuristics, Simulated Annealing, Variable Neighborhood Search, hybrid meta-heuristics of Simulated Annealing with Variable Neighborhood Search ; verifying which method stands out to the others as to its efficiency and effectiveness. The experimental results showed that, in the problems in which the cost function is linear or concave, the greedy constructive heuristic has the best performance, and for the cost with the convex function the hybrid metaheuristic has the best performance. In the problems belonging to the subgroup of small instances, the robust VNS solutions were considered, mathematical modeling solved problems with up to 20 items and SA obtained good quality solutions.