Use este identificador para citar ou linkar para este item: http://repositorio.ufc.br/handle/riufc/50329
Tipo: Tese
Título: Modelagem multigrafo, decomposição e BRKGA para o problema da árvore geradora generalizada mínima
Título em inglês: Multigraph, decomposition and BRKGA solution approaches for the generalized minimum spanning tree problem
Autor(es): Sousa, Ernando Gomes de
Orientador: Andrade, Rafael Castro
Coorientador: Duhamel, Andréa Cynthia Santos
Palavras-chave: Otimização;Árvore geradora generalizada mínima;Formulações de programação linear inteira mista;Metaheurística BRKGA;Decomposição de Benders
Data do documento: 2019
Citação: SOUSA, Ernando Gomes de. Modelagem multigrafo, decomposição e BRKGA para o problema da árvore geradora generalizada mínima. 2019. 75 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2019.
Resumo: Dado um grafo conexo, não direcionado e m-partido G = (V1 ∪V2 ∪...∪Vm, E), cujo conjunto de vértices é particionado em subconjuntos disjuntos V1,V2,...,Vm e cujas arestas de E conectam somente vértices de clusters distintos, o Problema da Árvore Geradora Generalizada Mínima (denotado por GMSTP, do inglês Generalized Minimum Spanning Tree Problem) consiste em encontrar uma árvore com exatamente m - 1 arestas, as quais conectam V1,V2,...,Vm através da seleção de um único vértice em cada cluster. O GMSTP encontra aplicações em problemas de modelagem de redes, agricultura irrigada, cidades inteligentes, data science, entre outros. Este trabalho apresenta para o GMSTP uma formulação multigrafo original, um procedimento para fixação de vértices que não possam pertencer a uma solução ótima, uma metaheurística Algoritmo Genético Baseado em Chave Aletaória (denotado por BRKGA, do inglês Biased Random Key Genetic Algorithm) e a aplicação do método de decomposição de Benders para uma formulação multifluxo da literatura. Resultados computacionais da formulação multigrafo superam os resultados das melhores formulações da literatura em termos de tempo de CPU para a obtenção de soluções comprovadamente ótimas para instâncias de teste da literatura e a decomposição de Benders aplicada neste trabalho apresenta os melhores resultados dentre todas as estratégias exatas analisadas. Além disso, o BRKGA apresenta melhor performance que metaheurísticas existentes para o problema em termos de qualidade de soluções viáveis obtidas para instâncias benchmark do GMSTP. Por fim, este trabalho abre novas direções de pesquisas para o desenvolvimento de algoritmos para problemas relacionados.
Abstract: Given a connected, undirected, and m-partite graph G = (V1 ∪V2 ∪...∪Vm,E), with set of vertex partitioned into disjoint subsets V1,V2,...,Vm and whose edges of E connect only nodes of distinct clusters, the Generalized Minimum Spanning Tree Problem (GMSTP) looks for a minimum-cost tree with exactly m - 1 edges, connecting V1,V2,...,Vm through the selection of exactly one vertex of each cluster. The GMSTP finds applications in network design, irrigation agriculture, smart cities, data science, among others. This work presents, for the GMSTP, an original multigraph mathematical formulation, a new procedure for eliminating vertices proved to not belong to an optimal solution, a Biased Random Key Genetic Algorithm (BRKGA) metaheuristic, and a Benders decomposition method applied to an existing flow-based formulation. Computational results for the multigraph formulation has better results than for existing formulations for the problem and the Benders decomposition obtains the best results among all the exact strategies analyzed. Moreover, the BRKGA presents better performance than existing metaheuristics with respect to solution quality for benchmark instances of the problem. Finally, this work opens new directions for research and the development of algorithms for related problems.
URI: http://www.repositorio.ufc.br/handle/riufc/50329
Aparece nas coleções:DCOMP - Teses defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2019_tese_egsousa.pdf726,77 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.