Meta-heurísticas baseadas na busca em vizinhança variável para resolução do Bin Packing Problem e Variable Sized Bin Packing Problem e aplicação no problema de distribuição física de café torrado e moído

Abstract

This study involves the grouping of loads problem and its application to a roasted and ground coffee industry. Methods based on the Variable Neighborhood Search (VNS) meta-heuristic are developed in order to solve the problem of Bin Packing with homogeneous fleet (BPP) and Variable Sized Bin Packing Problem (VBSPP) and to evaluate the applicability of the methods in real distribution situations for roasted and ground coffee. Transportation costs represent more than 50% of logistics costs for industries in this sector, therefore, it is of great importance to develop methods that support decision making. The studied problem encompasses two problems that are widely discussed in the literature, the (BPP) and the VSBPP, such problems have non-polynomial computational complexity and for high-size problems exact solutions are not feasible due to the times, thus, heuristic methods are used to generate solutions close to the optimal and in acceptable computational time. Three meta-heuristics based on Variable Neighborhood Search (VNS) were developed. The metaheuristics were implemented in C language and the generated results were validated in the test instances proposed by Falkenauer (1994) regarding the quality, repeatability and computational time spent for both BPP and VSBPP. The proposed meta-heuristics obtained remarkable performance when compared to other similar studies available in the literature, with evidence for the meta-heuristic VNS-3 that showed results that proved its effectiveness, efficiency and robustness. Finally, the VNS-3 method was applied to real data of a roasted and ground coffee industry and demonstrated the applicability and undeniable competitive advantage of the use of such methods by companies present in the market and lacking in logistic costs reduction.