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

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

dc.contributorLazzarini, Camilla Miguel Carrara
dc.contributorCunha, André Luiz Barbosa Nunes da
dc.contributorAraújo, Fernando de
dc.creatorSilva Junior, Amilton
dc.date2018-09-10T16:23:57Z
dc.date2018-09-10T16:23:57Z
dc.date2018-04-09
dc.date.accessioned2023-09-28T20:24:02Z
dc.date.available2023-09-28T20:24:02Z
dc.identifierSILVA 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.
dc.identifierhttps://repositorio.ufu.br/handle/123456789/22437
dc.identifierhttp://dx.doi.org/10.14393/ufu.di.2018.1151
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/9050004
dc.descriptionThis 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.
dc.descriptionDissertação (Mestrado)
dc.descriptionEste 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.
dc.formatapplication/pdf
dc.languagepor
dc.publisherUniversidade Federal de Uberlândia
dc.publisherBrasil
dc.publisherPrograma de Pós-graduação em Engenharia Civil
dc.rightsAcesso Aberto
dc.subjectVariable Neighborhood Search
dc.subjectVNS
dc.subjectBPP
dc.subjectVSBPP
dc.subjectDistribuição física
dc.subjectPhysical distribution
dc.subjectAgrupamento de cargas
dc.subjectGrouping of loads
dc.subjectEngenharia civil
dc.subjectCafé - Indústria
dc.subjectCafé - Transporte
dc.subjectLogística empresarial - Modelos matemáticos
dc.subjectCNPQ::ENGENHARIAS::ENGENHARIA CIVIL::INFRA-ESTRUTURA DE TRANSPORTES
dc.titleMeta-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
dc.titleMetaheuristics 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
dc.typeDissertação


Este ítem pertenece a la siguiente institución