Detalhes bibliográficos
| Ano de defesa: |
2024 |
| Autor(a) principal: |
Albuquerque, Kerven Maciel Monteiro de |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| 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://repositorio.ifpb.edu.br/jspui/handle/177683/3486
|
Resumo: |
Um grafo com arestas rotuladas (GAR) ? um grafo no qual cada aresta ? associada a um r?tulo, ou cor. Esses r?tulos permitem representar caracter?sticas qualitativas, em contraste ?s caracter?sticas quantitativas que podem ser expressas por custos ou capacidades. A literatura tem dado aten??o crescente a problemas definidos sobre GARs. Este trabalho introduz o problema do fluxo com rotula??o m?nima (PFRM), definido sobre um d?grafo com arcos rotulados e capacitados. Nele, busca-se um conjunto m?nimo de r?tulos tal que seja poss?vel encontrar um fluxo com valor igual ou superior a um valor dado. S?o propostos m?todos exatos e heur?sticos para o PFRM. Como m?todos exatos, s?o propostos uma formula??o baseada em cortes coloridos e dois algoritmos de branch and cut. Como m?todos heur?sticos, um GRASP reativo e um algoritmo gen?tico melhorado com constru??o gulosa aleatorizada baseada em GRASP, elitiza??o e recombina??o por caminhos, al?m de um m?todo de manuten??o din?mica de fluxo. Os experimentos computacionais realizados demonstraram a efici?ncia dos m?todos propostos em inst?ncias de tamanho moderado, em compara??o com as solu??es encontradas na literatura. |
