Modelagem multigrafo, decomposição e BRKGA para o problema da árvore geradora generalizada mínima

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.