Please use this identifier to cite or link to this item: http://www.monografias.ufop.br/handle/35400000/2674
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorMartins, Alexandre Xavierpt_BR
dc.contributor.authorButinholi, Matheus de Araujo-
dc.date.accessioned2020-09-28T20:12:02Z-
dc.date.available2020-09-28T20:12:02Z-
dc.date.issued2020-
dc.identifier.citationBUTINHOLI, Matheus de Araujo. Heurísticas para o problema de p-concentradores não capacitados de máxima cobertura com alocação simples. 2020. 34 f. Monografia (Graduação em Engenharia de Produção) - Instituto de Ciências Exatas e Aplicadas, Universidade Federal de Ouro Preto, João Monlevade, 2020.pt_BR
dc.identifier.urihttp://www.monografias.ufop.br/handle/35400000/2674-
dc.description.abstractO presente trabalho apresenta um estudo sobre o problema de cobertura máxima de p-eixos não capacitados com alocação simples (Uncapacitated Single Allocation p-hub Maximal Covering Problem - USApHMCP), que tem como objetivo maximizar a cobertura de um conjunto de nós de uma rede através de p-eixos. Foram desenvolvidas quatro estratégias como alternativas para solucionar o problema, um modelo de programação matemática para resolução exata do problema, duas heurísticas construtivas conectadas à procedimentos de refinamento via buscas locais, a busca em vizinhança variável (VNS) e a descida em vizinhança variável (VND), e uma meteheuristica, o Simulated Annealing (SA). Para analisar a eficiência dos algoritmos desenvolvidos, foram utilizadas duas instâncias da literatura, Civil Aeronautics Board (CAB) e Australian Post (AP). Além disso, também foi proposto um conjunto de instâncias que possui um número maior de nós quando comparadas às outras duas da literatura. Quanto ao resultado, o método exato e o VND demonstraram ser boas opções para instâncias de pequeno e médio porte, obtendo resultados formidáveis em um curto tempo de processamento, embora tenham apresentado certa deficiência em encontrar bons resultados para instâncias de maior porte. Por outro lado, o VNS e o SA foram alternativas que tiveram um bom desempenho para as instâncias de pequeno e grande porte.pt_BR
dc.language.isopt_BRpt_BR
dc.subjectOtimização combinatóriapt_BR
dc.subjectRedes eixo-raiopt_BR
dc.subjectHeurísticapt_BR
dc.subjectProgramação matemáticapt_BR
dc.titleHeurísticas para o problema de p-concentradores não capacitados de máxima cobertura com alocação simples.pt_BR
dc.typeTCC-Graduaçãopt_BR
dc.contributor.refereeOliveira, Paganini Barcellos dept_BR
dc.contributor.refereeSilva, Thiago Augusto de Oliveirapt_BR
dc.contributor.refereeMartins, Alexandre Xavierpt_BR
dc.description.abstractenThe present work presents a study on Uncapacitated Single Allocation p-hub Maximal Covering Problem (USApHMCP), which aims to maximize the coverage of a set of nodes in a network through p-hubs. Four strategies were developed as alternatives to solve the problem, a mathematical programming model for exact problem resolution, two constructive heuristics connected to refinement procedures via local searches, the Variable Neighborhood Search (VNS) and the Variable Neighborhood Descent (VND ), and a metaheuristic, Simulated Annealing (SA). To analyze the efficiency of the developed algorithms, two instances of the literature were used, Civil Aeronautics Board (CAB) and Australian Post (AP). Besides, a set of instances has also been proposed that has a greater number of nodes when compared to the other two in the literature. As for the result, the exact method and the VND proved to be good options for small and medium-sized instances, obtaining formidable results in short processing time, although there is a certain deficiency in finding good results for larger processing. On the other hand, VNS and SA demonstrated good performance for small and large instances.pt_BR
dc.contributor.authorID16.1.8029pt_BR
Appears in Collections:Engenharia de Produção - JMV

Files in This Item:
File Description SizeFormat 
MONOGRAFIA_HeurísticaProblemaPConcentradores.pdf708,5 kBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons