Técnicas de otimização multiobjetivo e otimização estocástica para o roteamento de fluxos em redes

• Ano de defesa: 2019
• Autor(a) principal: Fernandes, Kátia Cilene Costa
• Orientador(a): Pinto, Leizer de Lima
• Banca de defesa: Pinto, Leizer de Lima, Cardoso, Kleber Vieira, Vieira, Flávio Henrique Teles, Bueno, Elivelton Ferreira, Abelém, Antônio Jorge Gomes
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Goiás
• Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação (INF)
• Departamento: Instituto de Informática - INF (RG)
• País: Brasil
• Palavras-chave em Português: Roteamento de fluxos em redes; Otimização biobjetivo; Aalgoritmo polinomial; Otimização estocástica; Técnica -constraint
• Palavras-chave em Inglês: Network flow routing; Biobjective optimization; Polynomial algorithm; -constraint technique
• Área do conhecimento CNPq: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tede/9506

In this work we are interested in optimization problems related to network flow routing. Three models and an exact and polynomial algorithm are presented. The first model is a bi-objective integer programming problem in which the objective functions refer to the load balancing of the network and the length of the paths through which the flows are routed. An exact and polynomial algorithm based on the -constraint technique is presented. The second model differs from the first one with respect to the weights of the flows and the qualities of the links. In these parameters can assume different values. The last model is a stochastic single-objective flow routing problem. It aims to minimize the bottleneck of the network, respecting a certain limit on the length of the paths through which flows are routed. In addition, the link qualities are random variables, which can be approximated by a discrete and finite set. Implementations were developed in C++ language using the CPLEX solver for the resolution of instances. Grid topologies and random topologies based on the Barabási-Albert model were used in our computational experiments. The network flow settings defined here are those commonly used in wireless sensor networks and wireless mesh networks. The analysis of computational results provides the decision maker valuable informations about which factors most affect the solutions.