Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/22437
Document type: Dissertação
Access type: Acesso Aberto
Title: 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
Alternate title (s): Metaheuristics based on variable neighborhood search for Bin Packing Problem e Variable Sized Bin Packing Problem resolution and application to the problem of physical distribution of roasted and ground coffee
Author: Silva Jr, Amilton
First Advisor: Lazzarini, Camilla Miguel Carrara
First member of the Committee: da Cunha, André Luiz Barbosa Nunes da
Second member of the Committee: Araújo, Fernando de
Summary: Este estudo envolve a resolução do problema de agrupamento de entregas e sua aplicação em distribuição física de uma indústria de café torrado e moído. São desenvolvidos métodos baseados na meta-heurística Busca em Vizinhança Variável (Variable Neighborhood Search – VNS) de forma a solucionar o problema de Bin Packing com frota homogênea (BPP) e com frota heterogênea (Variable Sized Bin Packing Problem – VBSPP) realizar a aplicação dos métodos em situações reais de distribuição de café torrado e moído. Os custos com transporte representaram mais de 50% dos custos logísticos nas empresas brasileiras em 2015, portanto, é de grande importância o desenvolvimento de métodos que deem suporte à tomada de decisão neste setor. Os problemas estudados são amplamente abordados na literatura, o BPP e o VSBPP, tais problemas têm complexidade computacional não polinomial e para problemas de porte elevado soluções exatas são inviáveis devido aos tempos computacionais despendidos, assim sendo, métodos heurísticos são utilizados para gerar soluções próximas do ótimo e em tempo computacional aceitável. Desenvolveu-se três meta-heurísticas baseadas em busca em vizinhança variável (Variable Neighborhood Search - VNS). As meta-heurísticas foram implementadas em linguagem C e os resultados gerados foram validados nas instâncias de testes propostas por Falkenauer (1994) quanto à qualidade, repetibilidade e tempo computacional gasto tanto para o BPP quanto para o VSBPP. As meta-heurísticas propostas obtiveram desempenho notável quando comparadas a outros estudos similares disponíveis na literatura, com evidência para a meta-heurística VNS-3 que mostrou resultados que comprovaram sua eficácia, eficiência e robustez. Por fim, o método VNS-3 foi aplicado a dados reais de uma indústria de café torrado e moído e comprovou aplicabilidade e vantagem competitiva da utilização de tais métodos por empresas presentes no mercado e carentes de redução de custos logísticos.
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.
Keywords: Variable Neighborhood Search
VNS
BPP
VSBPP
Distribuição física
Physical distribution
Agrupamento de cargas
Grouping of loads
Engenharia civil
Café - Indústria
Café - Transporte
Logística empresarial - Modelos matemáticos
Area (s) of CNPq: CNPQ::ENGENHARIAS::ENGENHARIA CIVIL::INFRA-ESTRUTURA DE TRANSPORTES
Language: por
Country: Brasil
Publisher: Universidade Federal de Uberlândia
Program: Programa de Pós-graduação em Engenharia Civil
Quote: SILVA JUNIOR, A. 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. 54 p. Dissertação de Mestrado, Faculdade de Engenharia Civil, Universidade Federal de Uberlândia, 2018. Disponível em: http://dx.doi.org/10.14393/ufu.di.2018.1151.
Document identifier: http://dx.doi.org/10.14393/ufu.di.2018.1151
URI: https://repositorio.ufu.br/handle/123456789/22437
Date of defense: 9-Apr-2018
Appears in Collections:DISSERTAÇÃO - Engenharia Civil

Files in This Item:
File Description SizeFormat 
MetaHeuristicasBaseadas.pdf11.39 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.