CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / No problema do Caminho MÃnimo com RestriÃÃo ProbabilÃstica de Atraso MÃximo visamos considerar o fator tempo no projeto de rotas de transporte de cargas em malhas viÃrias a custo mÃnimo, atentando à crescente incerteza nos tempos de percurso dessas rotas em malhas reais, e observÃ-lo tendo em mente estratÃgias de qualidade de serviÃo, de forma a obtermos um compromisso entre o custo de percurso e a conformidade ao prazo de chegada ao destino. Realizamos um estudo de problemas relacionados na literatura da Ãrea de otimizaÃÃo em redes de transporte, de forma a tentarmos conhecer melhor o problema a ser estudado, sobre o qual nÃo tomamos conhecimento de trabalhos existentes. Desenvolvemos um esquema para enumeraÃÃo de partiÃÃes do espaÃo de soluÃÃes do problema, que utiliza uma decomposiÃÃo em L para selecionar partiÃÃes de forma inteligente, e que à auxiliado por soluÃÃes de relaxaÃÃes do problema de forma a obter cotas para o custo Ãtimo. AlÃm disso, desenvolvemos algumas estratÃgias de ramificaÃÃo e de poda para um esquema de Branch-and-Bound, com uma fase de prÃ-processamento, de forma a tentar resolver o problema diretamente. Os resultados computacionais obtidos demonstram que somos competitivos com a ferramenta comercial utilizada para comparaÃÃo em instÃncias de menor porte para o problema. Para as demais instÃncias, essa ferramenta se mostrou mais eficiente quanto ao tempo necessÃrio para a resoluÃÃo. / In the Probabilistic Delay Constrained Shortest Path problem we aim to consider the time factor in the design of cargo routing paths in road networks at minimum cost, considering the increasing uncertainty in travel times of these routes in real networks, and keeping in mind strategies of quality of service, in order to obtain a compromise between the travel costs and the compliance of the arrival time at the destination. We conducted a study of related problems in the literature of transport networks optimization, in order to better understand the problem to be addressed, about which we are not aware of existing works. We developed a scheme for enumerating partitions of the solution space of this problem, which uses an L decomposition to select these partitions wisely, and is aided by solutions to relaxations of the problem to obtain bounds for the optimal cost. In addition, we developed some branching and pruning strategies for a Branch-and-Bound scheme, with a pre-processing phase, in order to try and solve the problem directly. The computational results show that we are competitive with the commercial tool used for comparison in the smaller instances. For the remaining instances, this tool is more efficient in the time required for solving the problem.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Nesta dissertaÃÃo, nosso principal objetivo foi desenvolver uma tÃcnica de resoluÃÃo para um problema na Ãrea de telecomunicaÃÃes. O problema em questÃo à chamado de problema de PonderaÃÃo de Rodadas (PR) e foi inicialmente proposto em [Klasing,Morales,Perennes, 2008]. O contexto do problema envolve uma rede sem fio, onde as comunicaÃÃes sÃo realizadas via ondas de rÃdio e a rede funciona atravÃs de uma operaÃÃo da rede que satisfaz certas restriÃÃes. Inicialmente, explicamos como à formada uma rede de rÃdio e descrevemos a forma de operaÃÃo da rede de rÃdio junto Ãs restriÃÃes usando um modelo matemÃtico. Em seguida, formalizamos o problema PR como um problema de otimizaÃÃo, especificando suas restriÃÃes, correspondente à geraÃÃo do conjunto de possÃveis operaÃÃes da rede, e critÃrio de otimizaÃÃo, referente ao uso dos recursos da rede. Posteriormente, mostramos um estudo preliminar do problema de ColoraÃÃo FracionÃria (CF) e apresentamos uma tÃcnica de resoluÃÃo deste problema atravÃs do uso de uma heurÃstica lagrangeana baseada em uma relaxaÃÃo lagrangeana de uma formulaÃÃo de programaÃÃo inteira do problema. Essa tÃcnica de resoluÃÃo à entÃo adaptada para o problema PR, consistindo na principal contribuiÃÃo de nossa pesquisa. Por fim, mostramos os resultados computacionais e anÃlises das nossas implementaÃÃes para os problemas CF e PR. / In this dissertation, our main objective was to develop a technique for resolution to a problem in the area of telecommunications. The problem in question is called Round Weighting Problem (RWP) and was originally proposed in (KLASING; MORALES; PeRENNES, 2008). The context of the problem involves a wireless network where communications are performed by radio waves and the network operates through a network operation that satises the constraints of the problem. Initially, we explain how a radio network is formed and describe the mode of operation of the radio network with restrictions using a mathematical model. Then, we formalize the RWP as an optimization problem, specifying their restrictions, corresponding to the generation of the set of possible network operations, and optimization criterion, regarding the use of network resources. Subsequently, we show a preliminary study of the Fractional Coloring problem (FC problem) and present a technique to solve this problem through the use of a lagrangian heuristic based on a lagrangian relaxation of an integer programming formulation of the problem. This resolution technique is then adapted to the RWP, consisting in the main contribution of our research. Finally, we show the computational results and analyzes of our implementations for the Fractional Coloring problem and RWP.