Detalhes bibliográficos
Ano de defesa: |
2019 |
Autor(a) principal: |
Sousa, Ernando Gomes de |
Orientador(a): |
Não Informado pela instituição |
Banca de defesa: |
Não Informado pela instituição |
Tipo de documento: |
Tese
|
Tipo de acesso: |
Acesso aberto |
Idioma: |
por |
Instituição de defesa: |
Não Informado pela instituição
|
Programa de Pós-Graduação: |
Não Informado pela instituição
|
Departamento: |
Não Informado pela instituição
|
País: |
Não Informado pela instituição
|
Palavras-chave em Português: |
|
Link de acesso: |
http://www.repositorio.ufc.br/handle/riufc/50329
|
Resumo: |
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. |