Submitted by Liliane Ferreira (ljuvencia30@gmail.com) on 2018-03-08T14:57:43Z No. of bitstreams: 2 Dissertação - Kamyla Maria Ferreira - 2018.pdf: 2406020 bytes, checksum: 87a4f31f5a394055dd9a84a1c7c73512 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-03-12T11:16:50Z (GMT) No. of bitstreams: 2 Dissertação - Kamyla Maria Ferreira - 2018.pdf: 2406020 bytes, checksum: 87a4f31f5a394055dd9a84a1c7c73512 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-03-12T11:16:50Z (GMT). No. of bitstreams: 2 Dissertação - Kamyla Maria Ferreira - 2018.pdf: 2406020 bytes, checksum: 87a4f31f5a394055dd9a84a1c7c73512 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-02-16 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This research deals with the resolution of problems that involve the location, routing, and packing decisions with focus on the location routing problem, capacitated vehicle routing problem with two-dimensional loading constraints, and location routing problem with two-dimensional loading constraints. For that, it is proposed a framework that reuses part of the algorithms, which are of a common domain, such that the development of the project is systematized. The objective of the framework is allowing the resolution of different variants of problems that integrate location, routing, and packing decisions without the need to replicate algorithms. As a proposal for an algorithm, it is developed a hybrid heuristic, which involves the cooperation between the simulated annealing and the artificial algae algorithm. The simulated annealing has four neighborhood operators, local search, and three procedures to diversify the solution. The artificial algae algorithm is combined with the skyline method in order to verify the feasibility of the two-dimensional packing constraints. Once the framework and heuristics have been codified, computational experiments are performed to test its performance, as well as comparisons are made with the most recent results published in the literature. The results show that the heuristic is competitive with other methods from the literature since it could obtain 36.25% solutions equal to the best ones reported in the literature of the location routing problem, besides the average GAP being 0.57%. For the vehicle routing problem with two-dimensional loading constraints, the heuristic could obtain 43.05% solutions equal to the best known in the literature, besides the average GAP being 3.33%. The results obtained for the location routing problem with twodimensional loading constraints were satisfactory. / Este trabalho trata da resolução de problemas que envolvem decisões de localização, roteamento e empacotamento com foco nos problemas de localização e roteamento, roteamento de veículos capacitado com restrições de empacotamento bidimensional, e localização e roteamento com restrições de empacotamento bidimensional. Para tanto, propõe-se um framework capaz de reutilizar parte dos algoritmos, que são de domínio comum, para que o desenvolvimento do projeto seja sistematizado. O objetivo é que o framework possibilite a resolução de diferentes variantes do problema que integram as decisões de localização, roteamento e empacotamento sem ter que replicar algoritmos. Como proposta de algoritmo, desenvolve-se uma heurística híbrida, a qual envolve a cooperação entre dois métodos, o recozimento simulado e o algoritmo artificial de algas. O recozimento simulado possui quatro operadores de vizinhança, procedimentos de busca local e três procedimentos para diversificar a solução. O algoritmo artificial de algas é combinado com a técnica Skyline para verificar as restrições de empacotamento bidimensional. A partir da codificação do framework e da heurística, experimentos computacionais foram realizados para testar o seu desempenho e comparar os resultados com os mais recentes da literatura. Os resultados indicam que a heurística é competitiva com os demais métodos da literatura, sendo possível obter 36,25% de soluções iguais às melhores reportadas na literatura do problema de localização e roteamento, além do GAP médio ter sido de 0,57%. No problema de roteamento de veículos com restrições de empacotamento bidimensional, a heurística obteve 43,05% soluções iguais às melhores conhecidas na literatura, além do GAP médio ter sido de 3,33%. Os resultados obtidos para o problema de localização e roteamento com restrições de empacotamento bidimensional foram satisfatórios.

In this Dissertation, the Vehicle Routing Problem with Drones (VRPD), motivated by the growing interest on Unmanned Aerial Vehicles (UAVs, or Drones) by the industry and their applications in logistics is studied. A pioneer work by (MURRAY; CHU, 2015) shows a combination between UAV and a truck to deliver products, presenting an adaptation to the Traveling Salesman Problem (TSP). After a literature review, an extension of the model from Murray and Chu (2015) we present a model for the problem with multiple vehicles. This model is developed as a Mixed Integer Linear Programming (MILP) problem and solved with the solver CPLEX. A heuristic based on a Hybrid Genetic Algorithm (HGA) is also developed and presented. Our results show that the use of drones reduces the total mileage of the trucks by a significant percentage. / Nessa monografia estuda-se o Problema do Roteamento de Veículos com Drones (PRVD), motivado pelo crescente interesse da indústria em Veículos Aéreos Não Tripulados (VANTs) e suas aplicações em logística. O trabalho pioneiro de (MURRAY; CHU, 2015) mostra uma combinação entre VANT e um caminhão para realização de entregas de produtos, no qual foi proposta uma adaptação do Problema do Caixeiro Viajante (PCV). Após uma revisão de literatura, apresenta-se uma extensão do modelo de Murray and Chu (2015) para o problema com múltiplos veículos. Desenvolveu-se um modelo de Programação Linear Inteira Mista que foi resolvido com o solver CPLEX. Uma heurística basead em um Algoritmo Genético Híbrido também foi desenvolvido e é apresentada. Resultados mostram que a utilização dos VANTs reduzem a quilometragem dos caminhões significativamente.

A aplicação eficiente de agrotóxicos é um desafio na produção agrícola, mesmo considerando os avanços com a agricultura de precisão. O efeito deriva é o principal responsável pela ineficiência no controle das pragas ou doenças, pelo desperdício de recursos e pela contaminação ambiental. Para minimizar a deriva é essencial conhecer as condições ambientais como vento, temperatura e umidade. Esta pesquisa propõe o uso das redes de sensores sem fio como sistema de monitoramento ambiental e de suporte ao processo de pulverização agrícola, especialmente a pulverização executada por aeronave. São propostas três funcionalidades para o sistema: avaliação das condições ambientais, verificando se as condições estão apropriadas para a pulverização, buscando minimizar a ocorrência da deriva; suporte na definição e manutenção da rota do veículo pulverizador por meio dos dados do vento, de modo a efetuar ajustes na rota de pulverização e manter a aplicação do defensivo agrícola na área alvo; e a avaliação da eficácia da pulverização por meio dos dados da deposição do produto pulverizado coletados pela rede de sensores. Para viabilizar a utilização das redes de sensores sem fio no controle da deriva é proposto um protocolo de roteamento de dados que visa garantir a coleta dos dados pelos nós e a entrega para o veículo pulverizador, mesmo sendo ele um avião e se deslocando em alta velocidade. Para demonstrar a viabilidade do sistema proposto, foi desenvolvido um sistema de simulação computacional que considera os aspectos das redes de sensores sem fio e as características do protocolo de roteamento proposto. Os resultados demonstraram sua viabilidade, demonstrando que as redes de sensores sem fio podem ser utilizadas como suporte em um sistema de controle da deriva, incrementando a qualidade da pulverização, reduzindo custos e a contaminação ambiental. / The efficient application of low cost pesticides is a challenge for agricultural production. Pesticide drift is the major cause of money loss, inefficiency in crop disease control, and environmental contamination in the crop spraying process. At the time of application, it is essential to know the environmental conditions, such as wind, temperature and humidity to minimize contamination by pesticide drift. This study proposes the use of wireless sensor networks in a support and control system for crop spraying, especially in aircraft application methods. Three system functionalities are proposed: In the first case, the sensor network evaluates environmental data at the time of application to notify the user if the environmental conditions are suitable for continuing with the application. The second case evaluates the wind speed and its direction to suggest corrections in the path of a spray vehicle. Due to this alteration in the vehicle path, the pesticide will be applied only in the appropriate area. The final case involves collecting data samples and analyzing the quality of the spraying operation by evaluating the deposition of pesticide over the crop. This work proposes a new routing data protocol to make possible the use of wireless sensor networks in aerial crop spraying. It ensures that the sensor node data will be delivered to the sink node. Through computer simulations, wireless sensor networks are shown to be useful in crop spraying to minimize and to control pesticide drift, to improve the quality of application, to reduce environmental contamination and to reduce costs and the duration of the application operation.

O comportamento dinâmico das redes sem fio as torna muito peculiares e de difícil análise. No entanto, algumas destas redes, como as de sensores com funcionamento intermitente, redes periódicas ou cíclicas e as do sistema de satélites de órbita baixa têm um comportamento dinâmico relativamente previsível, pois as variações da topologia da rede no tempo são quase que determinísticas. Recentemente, um modelo teórico -- grafos evolutivos -- foi proposto com o intuito de capturar o comportamento dinâmico destas redes e formalizar algoritmos de roteamento de custo mínimo, além de outros. Os algoritmos e idéias obtidos com este modelo são teoricamente muito eficientes, mas, no entanto, antes deste trabalho não existiam estudos do uso destes modelos em situações práticas. Assim, o objetivo deste trabalho é analisar a aplicabilidade da teoria de grafos evolutivos na construção de protocolos de roteamento eficientes em cenários realistas. Foram implementados dois protocolos de roteamento para redes móveis ad hoc baseados nos algoritmos de grafos evolutivos, são eles: Jornada que Chega Mais Cedo e Jornada Mais Curta. Extensivas simulações foram realizadas utilizando o simulador de redes NS2 e os resultados foram comparados com outros quatro protocolos clássicos para este tipo de rede: AODV, DSR, OLSR e DSDV. Os resultados preliminares mostram que este recente modelo tem muito potencial para ser uma ferramenta poderosa no desenvolvimento e análise de algoritmos para redes dinâmicas com comportamento previsível. No entanto, foram apontados alguns aspectos que precisam ser melhores estudados para que estes algoritmos possam ser utilizados em situações reais. / The assessment of routing protocols for wireless networks is a difficult task, because of the networks\' highly dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and low earth orbit satellites systems, have more predictable dynamics, as the temporal variations in the network topology are somehow deterministic, which may make them easier to study. Recently, a graph theoretic model -- the evolving graphs -- was proposed to help to capture the dynamic behavior of these networks, in view of the construction of least cost routing and other algorithms. The algorithms and insights obtained through this model are theoretically very efficient and intriguing. However, before this work there was no study on the use of such theoretical results into practical situations. Therefore, the objective of our work is to analyze the applicability of the evolving graph theory in the construction of efficient routing protocols in realistic scenarios. We use the NS2 network simulator to first implement two evolving graph based routing protocols: Foremost Journey and Shortest Journey, They are evaluated and compared to four major ad-hoc protocols: AODV, DSR, OLSR and DSDV. Interestingly, our experiments show that evolving graphs have all the potentials to be an effective and powerful tool in the development and analysis of algorithms for dynamic networks, with predictable dynamics at least. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model.

Este trabalho apresenta um estudo teórico da Técnica de Geração de Colunas (GC) aplicada em alguns Problemas de Roteamento de Veículo (PRV). Essa técnica foi inicialmente utilizada para tratar problemas de otimização de grande porte com estruturas especiais[Dantzig & Wolfe, 1960]. Dentre as diversas classes de problemas de roteamento; revisamos a aplicação dessa técnica a dois casos particulares: O problema de roteamento de helicópteros em plataformas marítimas, cujo objetivo minimizar o custo total do transporte; O problema de roteamento com janela de tempo, onde a função objetivo é descrita pelo tamanho da frota e o custo do percurso. Revisamos e implementamos um algoritmo de caminho mínimo com janela de tempo (CMJT). Esse algoritmo surge como um sub-problema do algoritmo Primai Simplex para resolver o problema de partição de conjunto, utilizado para modelar o problema de roteamento com janela de tempo. / This work presents a study about the Column Generation Technique (CG) applied to some Vehicle Ftouting Problems. The technique was first used to deal with optimization problems having special structures. Among the vaa-ious classes of routing problems, we review the use of the technique in two specific cases: Ftouting helicopters for crew exchanges on off-shore locations, where the objective is to minimize the total transportation cost; Ftouting with time windows, where the objective function is composed by the size of the fleet and the cost of route. We review and implement a shortest path algorithm with time windows. This algorithm aa-ises as a sub-problem in the Primai Simplex algorithm to solve the linear relaxation of the set partitioning problem used to model the routing problem with time windows.

Os objetivos desta monografia foram analisar as propriedades de topologias de redes complexas, analisar as potencialidades e comparar desempenho de softwares gratuitos de geração de topologias e simular roteamento de tráfego em redes de telecomunicações. As principais topologias analisadas foram a regular, aleatória e livre de escala. As propriedades topológicas incluem o grau nodal, a distribuição de grau, o coeficiente de agrupamento, o comprimento médio do caminho, além do efeito mundo pequeno. Foram avaliadas as potencialidades de três ferramentas gratuitas de geração e análise de redes, o B-A, Pajek e NetLogo. Como exemplos de aplicação em redes de telecomunicações, com destaque para redes ópticas utilizando técnica de multiplexação por divisão de comprimento de onda, foram implementados os seguintes algoritmos de roteamento de tráfego: roteamento fixo com alocação de comprimento de onda sequencial fixa e roteamento adaptativo com alocação de comprimento de onda menos usado, mais usado, aleatória e busca exaustiva. O desempenho dos algoritmos de roteamento e alocação de comprimentos de onda de modo nas topologias analisadas foram comparados. / The purposes of this master\'s thesis are to analyze the properties of complex network topologies, analyze and compare the performance of free software for generating topologies and simulate traffic routing in telecommunication networks. The main topologies analyzed were the regular, random and scale-free. The topological properties include the nodal degree, the distribution degree, clustering coefficient, average path length and small-world effect. The performance of the free softwares B-A, Pajek and Netlogo were evaluated. As examples of application in telecommunication networks, especially for optical networks using wavelength division multiplexing technique, the following routing traffic algorithms were implemented: Fixed routing with first-fit wavelength assignment and adaptive routing with least used wavelength assignment, most used, random and exhaustive search. The performance of algorithms for routing and wavelength allocation employed in the analyzed topologies was compared.

[pt] Redes Manhattan Street (MS) têm sido descritas como um arranjo linear bidimensional de nós, semelhante à configuração de ruas e avenidas de Manhattan. O roteamento por deflexão é implementado encaminhando os pacotes que atingem um determinado nó a uma de suas saídas de forma síncrona ou assíncrona. O principal objetivo deste trabalho consiste na simulação e análise de redes totalmente ópticas configuradas segundo a topologia MS. O roteamento por deflexão e o assincronismo são considerados, para evitar complexidade eletrônica e armazenamento de pacotes no domínio óptico. Serão apresentadas as características das redes MS, suas propriedades estruturais e os parâmetros utilizados para analisar seu desempenho. Uma metodologia analítica dedicada a obtenção teórica destes parâmetros será introduzida. Serão apresentados alguns conceitos básicos sobre simulação de redes;diversas simulações da rede proposta utilizando os protocolos UDP e TCP; uma descrição do software que foi utilizado para realizar as simulações; uma comparação entre os resultados obtidos através da simulação e os obtidos através da metodologia analítica; e uma análise do efeito da latência na vazão do protocolo TCP. / [en] Manhattan Street (MS) Networks are bidimensional linear node sets arranged as the avenues and streets of Manhattan. The simulation and analysis of all-optical MS networks is the central target of this paper. In order to avoid using complex electronics and/or optical domain buffers, the deflection routing and the asynchronism are taken into account in the analysis. Deflection routing is performed by conveying incoming packets towards one of the two outputs. The characteristics of MS Networks are presented, along with their structural properties and the parameters used for performance analysis. An analytical methodology for the theoretical obtaining of these parameters is described. Some basic concepts on network simulation are discussed. Several simulations of the proposed network are presented, using both UDP and TCP protocols, and the software used for simulations is also described. The obtained results are compared and discussed with respect to the previously described analytic methodologies. Finally, the effect of network latency on the TCP-protocol throughput is assessed.

Avanços nas tecnologias de comunicação e processamento de sinais além de mudar a forma de como realizar negócios em todo o mundo, têm motivado o surgimento de serviços e aplicações multimídia na Internet de forma crescente. Como conseqüência, é possível conceber, desenvolver, implantar e operar serviços de distribuição de vídeo digital na Internet, tanto na abordagem sob-demanda quanto ao vivo. Com o aumento das aplicações multimídia na rede, torna-se cada vez mais complexo e necessário definir um modelo eficiente que possa realizar o gerenciamento efetivo e integrado de todos os elementos e serviços que compõe um sistema computacional. Pensando assim, este trabalho propõe uma arquitetura de gerenciamento baseado em políticas aplicada à distribuição de conteúdo multimídia com controle de QoS (Quality of Service) em redes de sobreposição (overlay). A arquitetura é baseada nos padrões de gerenciamento por políticas definida pela IETF (Internet Engineering Task Force) que, através de informações contextuais (rede e clientes) administra os serviços disponíveis no sistema. Faz uso dos requisitos de QoS providos pela rede de distribuição e os compara com os requisitos mínimos exigidos pelos perfis das aplicações previamente mapeados em regras de políticas. Dessa forma é possível controlar e administrar os elementos e serviços do sistema, afim de melhor distribuir recursos aos usuários deste sistema. / Advances in communication technologies and signal processing have not only changed the way business is conducted around the world, but have also driven the development of services and multimedia applications on the Internet. As a result, it is possible to design, develop, deploy and operate services for digital video distribution on the Internet, both according to an on-demand approach and live. Because of the increase in multimedia applications on the network, it has become increasingly more complex and necessary to define an efficient architecture that can achieve the effective and integrated management of all the elements and services that compose a computer system. With this in mind, this study proposes developing a robust and efficient architecture based on IETF (Internet Engineering Task Force) policy management standards applied to multimedia distribution content with QoS (Quality of Service) control in Overlay Networks. This architecture makes use of QoS requirements provided by the distribution network and compares them to the minimum requirements demanded by each type of application previously mapped in the policy rules. This system makes it possible to control and manage system information and services and also to distribute resources to system users better.

Made available in DSpace on 2016-04-04T18:31:42Z (GMT). No. of bitstreams: 1 LUCAS AUGUSTO DE ARAUJO MARQUES LEAO.pdf: 1843994 bytes, checksum: 99d00d63745d6c077be1b0e0f8b0d518 (MD5) Previous issue date: 2015-05-12 / Wireless Sensor Networks (WNS) have been applied as monitoring solution for building management systems. The sensors are responsible for monitoring environment aspects such as temperature, lighting and energy consumption. However, the sensors are exposed to adverse conditions and frequent environment changes, which can dramatically affect communication and data flow. Thus, this work proposes a routing algorithm based on fuzzy logic to identify the best routes in an indoor wireless sensor network. The evaluated parameters are presented (RSSI, Standard Deviation and Packet Error Rate) along with the cost definition process for each route, the best route identification sequence and the results obtained in simulation and experimentation. The proposed solution mixes WSN routing techniques along with fuzzy logic to characterize and define the link cost. The developed algorithm was faced with a routing solution based on RSSI. The experiments demonstrate that the solution allows the selection of higher quality links, reducing the probability of packet loss in comparison to the algorithm based on RSSI. / As Redes de Sensores Sem Fio (RSSF) t?m sido uma solu??o amplamente utilizada no contexto de sistemas de gerenciamento de edifica??es. Os sensores s?o respons?veis por monitorar diversos aspectos do ambiente, como temperatura, ilumina??o e consumo de energia. Entretanto, os sensores est?o expostos a condi??es adversas e mudan?as constantes do ambiente, que podem afetar de maneira definitiva a comunica??o e flu?ncia dos dados. Neste sentido, este trabalho apresenta uma proposta de algoritmo de roteamento baseado em l?gica difusa para identifica??o dos melhores caminhos em uma rede de sensores sem fio indoor. S?o apresentados os par?metros utilizados (RSSI, Desvio Padr?o do RSSI e Taxa de Erro de Pacote) para a defini??o do custo de cada caminho, a sequ?ncia de identifica??o de melhor caminho e os resultados obtidos em simula??o e aplica??o pr?tica. A solu??o proposta agrega t?cnicas de roteamento em RSSF ? utiliza??o de l?gica difusa para caracteriza??o e defini??o dos custos dos enlaces entre os sensores. O algoritmo desenvolvido foi confrontado com uma solu??o de roteamento baseada em RSSI. Os experimentos demonstram que a solu??o permite a sele??o de enlaces de melhor qualidade, reduzindo a probabilidade de perda de pacote em compara??o ao algoritmo baseado apenas em RSSI.

Submitted by CARLA MARIA GOULART DE MORAES (carlagm) on 2015-04-01T18:43:13Z No. of bitstreams: 1 CristianoGalafassi.pdf: 2977122 bytes, checksum: 5d851dbaf2aea5f9599c6ce44fa55ba0 (MD5) / Made available in DSpace on 2015-04-01T18:43:13Z (GMT). No. of bitstreams: 1 CristianoGalafassi.pdf: 2977122 bytes, checksum: 5d851dbaf2aea5f9599c6ce44fa55ba0 (MD5) Previous issue date: 2011 / CNPQ – Conselho Nacional de Desenvolvimento Científico e Tecnológico / Este trabalho aborda o Problema de Roteamento de Veículos Capacitado com Janelas de Tempo, onde devem ser atendidas as restrições de capacidade do veículo e as janelas de tempo de atendimento do cliente. Para resolver tal problema serão utilizadas as metaheurísticas Busca Tabu e Algoritmos Genéticos, além do desenvolvimento de um Algoritmo Híbrido baseado nas duas metaheurísticas. Busca-se contribuir com o desenvolvimento de um Algoritmo Híbrido focado no Problema de Roteamento de Veículos que utilize o poder de intensificação da Busca Tabu e o poder de diversificação do Algoritmo Genético, objetivando a obtenção de soluções de boa qualidade sem comprometer o tempo computacional. Nos experimentos, no que tange a Busca Tabu, analisa-se o processo de busca da através da variação do tamanho da Lista Tabu e do número máximo de iterações sem melhora do valor da função objetivo, como critério de parada, aplicados a uma política de intensificação. Para o Algoritmo Genético, é analisada a influência e o comportamento da busca com base em três operadores de cruzamento aplicados a duas políticas de elitismo. Ainda assim, para o Algoritmo Híbrido, analisa-se o impacto do tamanho da Lista Tabu e das taxas de Mutação e Cruzamento. Por fim, os resultados obtidos são comparados com os melhores métodos heurísticos encontrados na literatura e com métodos exatos, onde o Algoritmo Híbrido mostra-se robusto, obtendo soluções ótimas para diversas instancias de problemas. / This paper approaches the Capacitated Vehicle Routing Problem with Time Windows, which must obey the restrictions on vehicle capacity and time windows for customer service. To solve this problem will be used two metaheuristics, Tabu Search and Genetic Algorithms, and are developed an hybrid algorithm based on this two metaheuristics. The aim is to contribute with the development of a Hybrid Algorithm focused on Vehicle Routing Problem that uses the Tabu Search intensification power and the Genetic Algorithms diversification power, in order to obtain good quality solutions without compromising the computational time. In the experiments, with respect to Tabu Search, we analyze the search process by varying the size of the Tabu List and the maximum number of iterations without improvement in objective function value, such as stopping criterion, applied to an intensification policy. For the genetic algorithm are analyzed the influence and the search behavior on the basis of three crossover operators, applied to two elitism policies. Still, for the hybrid algorithm, we analyze the impact of the Tabu List size and rates of mutation and crossover. Finally, the results are compared with the best heuristics in the literature and with exact methods, where the Hybrid Algorithm shows robust, getting several optimal solutions.