[pt] Um avanço importante gerado pela tecnologia de TV digital é a possibilidade de interatividade com os usuários, realizada por meio do assim chamado canal de retorno. As redes ad hoc têm um grande potencial para atender esse tipo de serviço, pois podem ser empregadas em diversas áreas geográficas e idealmente de forma independente de infra- estrutura. Isso diminui o seu custo e propícia o aumento da velocidade de implantação deste tipo de rede. Uma das principais questões técnicas a serem resolvidas no contexto das redes móveis ad hoc é a necessidade de algoritmos eficientes para a realização do roteamento dos pacotes. O projeto Terminodes, desenvolvido pelo Instituto Federal de Tecnologia da Suíça, desenvolveu um protocolo de roteamento que utiliza a informação de localização. Este método de roteamento é freqüentemente proposto como um meio para prover escalabilidade em redes ad hoc distribuídas sobre áreas geográficas extensas. O roteamento baseado em localização é difícil quando há áreas de exclusão na topologia da rede e os nós são móveis ou freqüentemente desconectados para fins de economia de bateria. Portanto, a investigação da robustez do protocolo para esses casos é fundamental para avaliar seu uso em redes que podem servir como canal de retorno de TV digital. / [en] An important advance generated by the technology of digital TV is the possibility of interactivity with the users, what is done by means of the return channel. The mobile ad hoc networks have a great potential to provide this type of service, because it can ideally be used in diverse geographic areas and independent of any infrastructure. This minimizes the costs and the time needed to implement the network for this canal. One of the main questions techniques in the context of the mobile ad hoc networks is the necessity of efficient routing algorithms. The Terminodes project, developed by the Federal Institute of Technology of Switzerland, developed a routing protocol that is based in location information. This routing method frequently is a way to provide scalability in large ad hoc networks. The routing based on location is difficult when it has areas of exclusion in the topology of the network and the nodes are mobile or they are frequently disconnected to save battery. Therefore, assess the robustness of the protocol for these cases is basic to evaluate its use in networks for the digital TV return channel.

[pt] A indústria das comunicações tem passado nos últimos anos, mundialmente, por profundas transformações. A Internet é a responsável pela maior destas transformações. Com o advento da Internet, existe a necessidade de uma banda de transmissão maior para o tráfego de dados. Para resolver esse problema, surgiu o conceito de redes ópticas e a multiplexação no domínio do comprimento de onda. Entretanto, isso criou um outro problema: o roteamento dos pacotes. A maior parte das redes de comunicação hoje em dia, ainda possui muitos sinais eletrônicos, o que significa que os sinais ópticos precisam ser convertidos em elétricos para serem ampliados, regenerados ou roteados e, depois, reconvertidos para ópticos. Isso acaba gerando atrasos na transmissão dos sinais e um gargalo nas redes ópticas. Para minimizar este problema, vários algoritmos foram criados. Apegando-se a tais fatos, este estudo explora o tema para implementar um algoritmo de enumeração recursiva, que tem como objetivo alocação de comprimentos em redes ópticas, visando minimizar o custo total de transmissão. Esse algoritmo foi testado e comparado com o algoritmo de programação linear, que fornece a solução ótima. / [en] The communication industry was passing in lastest years by great transformations in world. Internet is the mainly responsable for that, because there is the necessity of a large band to data transmission. The optical networks concept and wavelength division multiplexing technology were arised in order to solve this problem. However, this created another problem: the packet routing. The major part of communications networks still has electronics signals. This means that the optical signals have to be converted into electrical signals to be amplified, regenerated and routed and later recovered into optical. This implies in a delay on the data transmission and creates a bottleneck in the optical networks. Some algorithms have been created to minimize this problem. This dissertation has tried to develop an algorithm to solve RWA (routing and wavelength assignment) problems, aiming at the minimum total cost to transmitt datas. This algorithm was tested and compared with the linear program algorithm that gives the optimal solution to RWA problem.

[pt] Este trabalho estuda o efeito de conversores de comprimento de onda em nós de redes multiplexadas por divisão de comprimento de onda totalmente ópticas ou transparentes. Foram executadas simulações para estudar os benefícios da introdução de conversores nas arquiteturas de rede. Ademais, são propostas heurísticas para alocação de conversores de comprimento de onda, baseadas na utilização destes. Os desempenhos das heurísticas são avaliados comparando-as com outros algoritmos estabelecidos na literatura. / [en] This work studies the effect of wavelength converters at nodes of wavelength division multiplexed all-optical networks. Simulations were performed to study the benefit of wavelength converters on network architectures. Moreover, wavelength converter placement heuristics based on the utilization of these devices are proposed. The performances of the heuristics are tested against existing converter placement algorithms in literature.

[pt] Os problemas advindos da área de logística de transportes, em especial no que diz respeito ao uso racional de frotas de veículos, são amplamente estudados na área de otimização combinatória. A natureza intrinsicamente combinatorial desses problemas sugere que boa parte deles pode ser formulada e resolvida como um problema de programação linear inteira. Contudo, a maioria dos algoritmos atualmente disponíveis não consegue encontrar, em tempos computacionais aceitáveis, a solução ótima para instâncias de porte razoável. O sucesso desses algoritmos tem sido limitado, em parte devido ao fato dos mesmos não explorarem avanços recentes na área de programação linear inteira. Algumas dessas novas técnicas e suas aplicações a problemas de roteamento de veículos são o objeto de estudo desta dissertação. Primeiro são apresentadas as técnicas básicas de decomposição de problemas de programação linear e linear inteira e de geração de colunas. A resolução de problemas de programação linear inteira neste contexto é tratada em seguida, com a descrição do algoritmo branch-and-bound e das variações branch-and-cut, branch-and-price e branch-and- cut-and-price. Em seguida são descritos problemas de roteamento onde essa metodologia foi aplicada. Inicialmente, é apresentado o problema de roteamente do veículos com restrição de capacidade, o PRVC. Em seguida são apresentados problemas de roteamento de veículos com janela de tempo e frota heterogenea. Para cada problema, descrevemos como as técnicas descritas acima foram aplicadas e os resultados computacionais para um grande número de instâncias. Finalmente, no último capítulo, mostramos um caso real da aplicação do problema de roteamento de veículos com janela de tempo e frota heterogênea, que é o caso do problema de distribuição de jornais numa grande empresa de comunicação do Rio de Janeiro. / [en] Optimization techniques have an important role in Transportation Logistics. The combinatorial nature of several problems related to this area seggests integer programming as a natural approach to solve them. Nevertheless, there are many cases in which instances of reasonable size are still beyond the resolution capability of the algotithms presented in the literature. The sucess of the known algotithms have therefore been limited partly to the fact that most of them have not incorporated any recent relevant advances in the combinatorial optimization field. Some of these new techniques and their applications are the main subject of this dissertation. Firstly, basic decomposition techniques for linear and integer programming problems, as well as the relates column generation approach are addressed. This is followed by the presentation of a reformulation technique for linear and integer programming, which is alternative to the well known Dantzig-Wolfe master program. The new possibilities arousing from this approach are explored and the resulting consequences to the standard branch-and-bound algotithm and its variations branch-and- cut, branch-and-prince and branch-and-cut-and-price are presented. Later, routing problems where this methodology was applied were addressed with the capacitated vehicle routing problems - CVRP and followed by vehicle routing problems with time windows and heterogeneous fleet. For each problem, it is described how the techniques mentioned above were reported. Finally, in the last time windows and heterogeneous fleet, which is the case of a newspaper distribution in a major communication company in Rio de Janeiro.

[pt] A natureza intrinsicamente combinatorial de muitos problemas advindos da área de logística de transportes, em especial aqueles que dizem respeito ao uso racional de frotas de veículos, sugere que boa parte dos mesmos pode ser formulada e resolvida como um problema de programação linear inteira. Contudo, a maioria dos algoritmos até o momento disponíveis não consegue encontrar, em tempos computacionais aceitáveis, a solução ótima para instâncias de porte razoável. O objeto de estudo desta tese é a exploração de técnicas mais recentes da área de programação linear inteira e suas aplicações a problemas de roteamento de veículos. A primeira parte da tese descreve, além das técnicas básicas de decomposição de problemas de programação linear e linear inteira e de geração de colunas, uma proposta de reformulação de problemas de programação linear inteira alternativa àquela que gera o tradicional problema mestre de Dantzig-Wolfe, geralmente utilizados em abordagens por geração de colunas. A resolução de problemas de programação linear inteira neste contexto é tratada em seguida, com a descrição do algoritmo branch-and-bound e das variações branch-and-cut, branch-and-price e branch-and-cut-and-price. Na segunda parte da tese, inicialmente, é apresentada a técnica denominada de Geração Projetada de Colunas e sua aplicação ao problema de Roteamento de Veículos com Restrição de Capacidade. Em seguida é abordada a resolução do problema de Roteamento de Veículos sobre Arcos, através de sua transformação ao primeiro problema citado e uso de um algoritmo branch-and- cut-and-price. Finalmente, é proposto um novo problema na área de redistribuição de veículos de aluguel, para o qual é proposta uma formulação segundo uma abordagem por geração de colunas. São apresentados, ainda, procedimentos para a geração de colunas e resultados computacionais obtidos com um algoritmo branch-and-price para essa formulação. / [en] Optimization techniques have an important role in Transportation Logistics. The combinatorial nature of the problems related to this area suggests integer programming as a natural approach to their resolution. Nevertheless there are many cases where even instances of reasonable size still beyond the resolution capability of the current known algorithms. The success of the known algorithms have therefore been limited. This can be justified by the fact the most of them leave important recent advances in the combinatorial optimization field unexplored. Some of these new techniques and their applications are the main subject of this thesis. In the first part, the basic decomposition techniques for linear and integer programming problems as well as the related column generation approach is addressed. This is followed by the presentation of a reformulation technique for linear and integer programming which is alternative to the well known Dantzig-Wolfe master program. The new possibilities coming from this approach are explored and the resulting consequences to the standard branch-and- bound algorithm and its variations branch-and-cut, branch-and- price and branchand- cut-and-price are presented. The second part of this text addresses the application of the metodologies described in part one to routing problems where capacity constraints are considered. First, a techinque named Projected Column Generation is described in the context of the Capacitated Vehicle Routing Problem. Then, it is presented a new transformation from the Capacitated Arc Routing Problem to the Capacitated Vehicle Routing Problem as well as a tailored branch-and-cut-and-price to solve this problem. Finally, a new problem in vehicle redistrubution is described together with a column generation approach for its resolution. Computational results for all applications are presented.

[pt] Redes veiculares (VANETs — Vehicle Ad Hoc NETworks) constituem um caso especial de redes ad hoc em que os nós são veículos equipados com uma interface de comunicação sem fio. Esses veículos podem se mover a velocidades elevadas, e a transmissão de dados em cenários urbanos pode ser facilmente bloqueada por prédios ou outros obstáculos. Tais fatores contribuem para tornar a comunicação inter-veicular intermitente, e dificultar o roteamento de pacotes. Um dos principais desafios dos protocolos de roteamento em VANETs é evitar as ruas onde o volume de tráfego esteja baixo, uma vez que a escassez de veículos nessas ruas tende a impossibilitar a propagação de pacotes através delas. Por esse motivo, a informação sobre o volume de tráfego em cada rua é fundamental para se determinar a melhor rota entre dois veículos. Especificamente em cenários urbanos, a mudança de estado dos semáforos provoca uma flutuação do tráfego de veículos ao longo do tempo. Em vista disso, esta tese propõe o TLAR (Traffic Light Aided Routing), um novo algoritmo de roteamento para VANETs que explora a variação de estado dos semáforos para inferir quais ruas oferecerão uma maior probabilidade de sucesso de propagação de pacotes. Resultados de simulação mostram que o algoritmo apresenta um bom desempenho comparado ao de propostas existentes. / [en] VANETs (Vehicle Ad Hoc NETworks) are a special case of mobile ad hoc networks where vehicles are equiped with wireless communication interfaces. These vehicles may move at high speeds and data transmission in urban scenarios may easily be blocked by buildings and other sort of obstacles. Such factors contribute to make inter-vehicle communication intermitent and packet routing more difficult. One of the main challenges faced by routing protocols is avoiding low-traffic streets, where the lack of vehicles tend to make packet forwarding impossible. For this reason, traffic information on each street is essential for the computation of the best route between any given two vehicles. Specifically in urban scenarios, traffic light transitions cause significant fluctuations on traffic flow over time. Given this fact, this thesis proposes TLAR (Traffic Light Aided Routing), a new routing algorithm for VANETs that exploits traffic light transition timings in order to determine which streets will offer the greatest probabilities for successful packet forwarding. Simulation results indicate a good performance of this algorithm compared to existing approaches.

[pt] Com o advento do comércio eletrônico, o mercado passou a atuar cada vez mais intensamente através de suas fronteiras geográficas e, como consequência, as empresas necessitam constantemente de inovações e melhorias na gestão de suas operações para se manterem competitivas. Desta forma, encontrar soluções de fretes que consigam atender longas distâncias em um curto prazo pode ser tão decisivo quanto o fator custo, por isso, os estudos acadêmicos em otimização de rotas intermodais estão em contínua evolução para se aproximarem dos modelos reais. Nesse contexto, esta dissertação busca solucionar um problema de roteamento aeroterrestre de transporte de cargas, com linhas aéreas predeterminadas e frotas próprias e heterogêneas. Uma extensão do problema de roteamento de veículos é elaborada com a inclusão de arcos que representam as possíveis linhas aéreas. O modelo é aplicado em um resolvedor de Programação Linear Inteira Mista e, primeiramente, é realizado um teste de validação com demandas fictícias em todos os locais. Em seguida, o modelo é aplicado no planejamento real de um órgão governamental em três períodos distintos. São realizadas análises sobre a velocidade de solução; a decisão de utilizar o modal aéreo, terrestre ou intermodal; e sobre os ganhos do modelo. Em comparação com as rotas efetivamente realizadas, o modelo traz redução de 7 por cento a 55 por cento dos custos com transportes. Com esses resultados, conclui-se que é imprescindível que os detentores de frota própria de aeronaves e caminhões utilizem o modal aéreo apenas como atividades acessórias, ou seja, que estejam cumprindo outras missões em conjunto (transporte de passageiros, por exemplo), ou para atender locais remotos. / [en] With the advent of e-commerce, the market has started to act more and more intensively across its geographic borders and, as a consequence, companies constantly need innovations and improvements in the management of their operations in order to remain competitive. Thus, finding freight solutions that can serve long distances in the short term can be as decisive as the cost factor, for this reason, academic studies in intermodal routing optimization are continually evolving to approach real models. In this context, this thesis seeks to solve a problem of air-land cargo routing, with predetermined airlines and their own heterogeneous fleets. We elaborated an extension of the vehicle routing problem by including arcs that represent overhead lines. The model is applied to a Mixed Integer Linear Programming solver and, firstly, a validation test is performed with fictitious demands in all locations. It is then applied to the actual planning of a government agency in three different periods. We performed analyses on the solution speed; the decision to use the air, land or intermodal modal; and about the earnings of the model. In comparison with the routes actually carried out, the model reduces transport costs by 7 percent to 55 percent. With this results, it is concluded that it is essential that owners of their aircraft and trucks fleet use the air modal only as secondary activities, in other words, that they are fulfilling more missions together (transportation of passengers, for example), or to deliver to remote locations.

[pt] Este trabalho apresenta uma aplicação prática do roteamento de navios com coleta-e-entrega e janelas de tempo para o alívio de plataformas de petróleos para exportação. Especificamente para este caso, os navios aliviadores fazem o transporte do petróleo de plataformas offshore diretamente para um terminal de transbordo, onde a carga será transferida para outro navio para ser exportado. Foram propostas adaptações a um modelo de programação linear inteira mista já existente, buscando descrever as peculiaridades deste processo e facilitar a sua resolução pelo método exato. O modelo foi testado com dados realísticos de uma empresa petrolífera e pode fornecer soluções de alta qualidade para testes com períodos de até 30 dias em um tempo de processamento computacional inferior a 10 minutos, estando assim adequado ao uso na rotina do programador de navios desta empresa. / [en] This study presents a practical application of ship routing with pickup-anddelivery and time windows for offloading operations in offshore oil platforms. Specifically in this case, the shuttle tankers transport crude oil from the offshore platforms directly to an onshore terminal, where the cargo will be transferred to another vessel to be exported. Adaptations to an existing mixed-integer linear programming model are proposed to better represent this process and facilitate its resolution by the exact method. The model was tested with realistic data from an oil and gas company and it can provide high-quality solutions for tests with periods up to 30 days, in a processing time of less than 10 minutes, thus being suitable for use in the routine of the company s ship programmer.

[pt] No cenário atual da economia mundial, é essencial aumentar a integração entre os diferentes atores da cadeia de suprimentos das empresas, reduzindo custos operacionais e melhorando a eficiência. O roteamento de navios é parte imprescindível dessa integração no comércio marítimo global, sendo objeto de estudo de muitos autores. Neste trabalho, apresentamos diferentes metodologias para resolver variantes do Problema de Roteamento Marítimo com Estoques. Esse problema envolve um grande número de variáveis e é computacionalmente complexo de ser resolvido. Nossa principal motivação é resolver um caso real de roteamento de navios de uma grande empresa do setor de Óleo e Gás, obtendo soluções de alta qualidade em tempos computacionais plausíveis e melhorando os resultados atuais da empresa. Todas as metodologias desenvolvidas são baseadas em uma combinação de uma meta-heurística com um modelo matemático de programação linear. Uma das principais diferenças entre as metodologias está no modelo matemático para resolver o problema de estoque, onde testamos abordagens de tempo discreto e tempo contínuo. As outras diferenças dizem respeito ao número de produtos avaliados (único ou múltiplos produtos) e à meta-heurística usada (heurística de busca local com um fator de probabilidade de Simulated Annealing ou Hybrid Variable Neighborhood Search). Para a metodologia que utiliza um modelo de tempo discreto, os resultados são satisfatórios, com violações baixas e pontuais do estoque em um tempo computacional aceitável. Para a metodologia que utiliza um modelo de tempo contínuo, os resultados são ainda melhores, uma vez que, em reduzido tempo computacional, as violações de estoque permanecem baixas ou inexistentes, dependendo do cenário avaliado e da meta-heurística utilizada. Os resultados obtidos neste trabalho são notáveis e permitem sua aplicação prática em casos reais. / [en] In the current scenario of the world economy, it is essential to increase the integration between the different players in the companies supply chain, reducing operational costs, and improving efficiency. Ship routing is a substantial part of this integration regarding global maritime commerce, being the object of study by many authors. In this work, we present different methodologies to solve variants of the Maritime Inventory Routing Problem. This problem involves a large number of variables and is a computationally complex problem to solve. Our primary motivation is to solve a ship routing real case of a large company in the Oil and Gas sector, achieving high-quality solutions in plausible processing times and improving companies current results. All developed methodologies are based on a metaheuristic combination with a linear mathematical model. One of the main differences between the methodologies lies in the mathematical model to solve the inventory problem, where we tested discrete-time and continuous-time approaches. Other differences concern the number of evaluated products (single or multi-product) and the metaheuristic used (local search heuristics with a Simulated Annealing probability factor or Hybrid Variable Neighborhood Search). For the methodology using the discretetime model, the results are satisfactory, with low and punctual inventory violations in an acceptable computational time. For the methodology using the continuous-time model, the results are better once, in reduced computational time, inventory violations remain low or non-existent, depending on the scenario evaluated and the metaheuristic used. The results obtained in this work are remarkable and allow its practical application for real cases.

[pt] O Capacitated Vehicle Routing Problems (CVRP) é uma versão seminal do problema de roteamento de veículos, um clássico problema em Pesquisa Operacional. Introduzido por Dantzig e Ramser, o CVRP generaliza o Traveling Salesman Problem (TSP) e o Bin Packing Problem (BPP). Problemas de roteamento aparecem em diversas aplicações no mundo real, geralmente no contexto de diminuição de custos, emissão de poluentes ou energia dentro das atividades relacionadas ao transporte. De fato, estes custos podem ficar entre 5 por cento e 20 por cento do custo total do produto. Por isto, qualquer economia nos custos de roteamento pode ser relevante. O CVRP é definido da seguinte maneira: dado um conjunto de n mais 1 localidades - um depósito e n clientes - as distâncias entre cada par de localidades, as demandas inteiras associadas a cada cliente e a capacidade do veículo, quer se obter um conjunto de rotas que comecem no depósito, visitem cada cliente apenas uma vez e retornem ao depósito. A distâncias percorrida deve ser mínima e a soma das demandas dos clientes presentes em cada rota não pode exceder a capacidade do veículo. Este trabalho considera que o número de veículos disponíveis é conhecido. Algoritmos no estado da arte para encontrar e provar que uma solução é ótima, para o CVRP, calculam seus limites inferiores através de geração de colunas e depois os melhoram com a adição de planos de corte. As colunas geradas podem ser rotas elementares, onde obrigatoriamente cada cliente é visitado somente uma vez, ou uma relaxação desta obrigação com o uso de q-rotas ou ng-rotas, que diferem apenas em como é permitido que um cliente seja revisitado dentro de uma mesma rota. Já os cortes são classificados como robustos, aquele que são definidos sobre as variáveis dos arcos, e não robustos (ou fortes), que são os definidos sobre as variáveis do problema mestre da geração de colunas. O termo robusto, usado acima, se refere a como a adição do corte modifica a eficiência da resolução do problema de pricing. Além do descrito acima, o algoritmo exato mais eficiente para o CVRP usa muitos elementos, o que torna sua replicação uma tarefa difícil e longa. O objetivo deste trabalho é determinar o quão bom são os limites inferiores obtidos com geração de colunas de ng-rotas usando apenas cortes de capacidade e os recentes subset row cuts de memória limitada. Além disto, é avaliado o ganho conseguido com a consideração deste tipo de corte forte e as combinações com outras técnicas, como por exemplo, Decremental Space State Relaxation (DSSR), Completion Bounds, ng-rotas e cortes de capacidade sobre a formulação de Set Partitioning. Extensos experimentos computacionais são apresentados em conjunto com a análise dos resultados obtidos. / [en] The Capacitated Vehicle Routing Problem (CVRP) is the seminal version of the vehicle routing problem, a classical problem in Operational Research. Introduced by Dantzig e Ramser, the CVRP generalizes the Traveling Salesman Problem (TSP) and the Bin Packing Problem (BPP). In addition, routing problems arise in several real world applications, often in the context of reducing costs, polluent emissions or energy within transportation activities. In fact, the cost with transportation can be roughly estimated to represent 5 per cent to 20 per cent of the overall cost of a delivered product. This means that any saving in routing can be much relevant. The CVRP is stated as follows: given a set of n plus 1 locations - a depot and n customers - the distances between every pair of locations, integer demands associated with each customer, and a vehicle capacity, we are interested in determining the set of routes that start at the depot, visits each customer exactly once and returns to the depot. The total distance traveled by the routes should be minimized and the sum of the demands of customers on each route should not exceed the vehicle capacity. This work considers that the number of available vehicles is given. State of the art algorithms for finding and proving optimal solutions for the CVRP compute their lower bounds through column generation and improving it by adding cutting planes. The columns generated may be elementary routes, where customers are visited only once, or relaxations such as q-routes and the more recent ng-routes, which differ on how they allow repeating customers along the routes. Cuts may be classified as robust, those that are defined over arc variables, and non-robust (or strong), those that are defined over the column generation master problem variables. The term robust used above refers to how adding the cut modifies the efficiency of solving the pricing problem. Besides the description above, the most efficient exact algorithms for the CVRP use too many elements turning its replication a hard long task. The objective of this work is to determine how good can be lower bounds computed by a column generation algorithm on ng-routes using only capacity cuts and a family of strong cuts, the limited memory subset row cuts. We assess the leverage achieved with the consideration of this kind of strong cuts and its combination with others techniques like Decremental Space State Relaxation (DSSR), Completion Bounds, ng-Routes and Capacity Cuts over a Set Partitioning formulation of the problem. Extensive computational experiments are presented along with an analysis of the results obtained.