Resumo: Este trabalho aborda o Problema de Máximo Atendimento em Roteamento Multicast com restrições de Qualidade de Serviço (com a sigla em inglês MS-MRP-QoS) aplicado no contexto de redes veiculares ad-hoc, onde é fornecida uma rede veículos para qual deseja-se enviar dados partindo de um nó raiz com destino a um conjunto de nós terminais. A utilização de todos os nós não é obrigatória e cada conexão entre o nó raiz e um nó terminal deve satisfazer à qualidade de serviço conforme limites estabelecidos para cada métrica. O objetivo é maximizar o número de terminais atendidos de acordo com as métricas de qualidade de serviço da rede. Nesta dissertação, foram desenvolvidas formulações de programação inteira mista e quatro relaxações lagrangianas, visando obter limitantes primais e duais de boa qualidade. Também foi desenvolvido um conjunto de métodos heurísticos, dentre eles uma busca local em arborescências, aplicada durante as resoluções das relaxações lagrangianas, e três meta-heurísticas BRKGA com variações no método de decodificação, um deles incorporando informações dos multiplicadores de Lagrange. As metodologias propostas foram submetidas a experimentos computacionais com um conjunto de instâncias geradas com características de redes veiculares ad-hoc. Análises estatísticas foram realizadas para comparar os desempenhos entre as metodologias. Os resultados destacam a eficácia da formulação mista em obter limitantes primais e duais de alta qualidade para todas as instâncias do conjunto. Já a formulação inteira, relaxações lagrangianas e BRKGA obtiveram resultados de boa qualidade e estatisticamente semelhantes Ver menos

Abstract: This work addresses the problem of Maximum Service in Multicast Routing with Quality of Service constraints (MS-MRP-QoS) applied in the context of vehicular ad-hoc networks, where a vehicle network is provided for which it is desired send data from a root node to a set of terminal nodes. The use of all nodes is not mandatory and each connection between the root node and a terminal must satisfy the quality of service according to the limits established for each metric. The objective is to maximize the number of terminals served according to the network's quality of service metrics. In this dissertation, formulations of mixed integer programming and four Lagrangian relaxations were developed, aiming to obtain good quality primal and dual limits. A set of heuristics methods has also been developed, among them a local search in arborescences, applied during the resolution of the Lagrangian relaxations, and three BRKGA meta-heuristics with variations in the decoding method, one of them incorporating information from the Lagrange multipliers. The proposed methodologies were subjected to computational experiments with a set of instances generated with characteristics of ad-hoc vehicular networks. Statistical analyzes were performed to compare the performances between the methodologies. The results highlight the effectiveness of the mixed integer formulation in obtain high quality primal and dual limits for all instances of the set. The integer formulation, Lagrangian relaxations and BRKGA obtained good quality solutions and statistically similar Ver menos