Neste trabalho estudamos aspectos algorítmicos do Problema da Cobertura por Sensores. Em linhas gerais, este problema a entrada consiste em uma região a ser monitorada por um conjunto de sensores previamente posicionados, cada qual dotado de bateria com duração limitada, e o objetivo é atribuir a cada sensor um tempo de início, de modo que toda a região seja coberta o maior tempo possível. Focamos nosso estudo no caso unidimensional do problema, chamado Problema da Cobertura de Faixa Restrita, no qual a região a ser monitorada é um intervalo (da reta real). Estudamos diversas variantes, de acordo com os subintervalos que os sensores cobrem (se de tamanhos fixos ou variados), e de acordo com a duração das baterias (se uniformes ou não). Estudamos também o caso preemptivo: quando os sensores podem ser ligados mais de uma vez. Para este último caso, projetamos um algoritmo polinomial bem simples. O Problema da Cobertura de Faixa Restrita é NP-difícil no caso não-preemptivo em que os sensores têm bateria de duração variável. Para este caso, em 2009 Gibson e Varadarajan apresentaram um algoritmo polinomial que provaram ser uma 5-aproximação. Provamos que este algoritmo tem fator de aproximação 4, e mostramos que este fator é justo. Apresentamos também formulações lineares inteiras para este caso, e os resultados computacionais obtidos. / We study the algorithmic aspects of the Sensor Cover Problem. Broadly speaking, in this problem the input consists of a region to be covered by a set of sensors previously positioned, each one powered with a battery of limited duration, and the objective is to assign to each sensor an initial time, so as to cover the given region for as long as possible. We focus our study on the one-dimensional case of the problem, called Restricted Strip Cover Problem, in which the region to be covered is an interval (of the real line). We study several variants, according to the type of the subintervals the sensors cover (if they have fixed length or not), to the duration of the batteries (if uniform or not). We also study the preemptive case: when the sensors can be turned on and off more than once. For this case, we designed a simple polynomial-time algorithm. The Restricted Strip Cover Problem is NP-hard in the non-preemptive case in which the sensors have non-uniform duration batteries. For this case, in 2009 Gibson and Varadarajan designed a polynomial-time algorithm which they proved to be a 5-aproximation. We prove that this algorithm has approximation ratio 4, and show that this ratio is tight. We also present two integer linear formulations for this case, and report on the computational results obtained with this approach.

Neste trabalho estudamos aspectos algorítmicos do Problema da Cobertura por Sensores. Em linhas gerais, este problema a entrada consiste em uma região a ser monitorada por um conjunto de sensores previamente posicionados, cada qual dotado de bateria com duração limitada, e o objetivo é atribuir a cada sensor um tempo de início, de modo que toda a região seja coberta o maior tempo possível. Focamos nosso estudo no caso unidimensional do problema, chamado Problema da Cobertura de Faixa Restrita, no qual a região a ser monitorada é um intervalo (da reta real). Estudamos diversas variantes, de acordo com os subintervalos que os sensores cobrem (se de tamanhos fixos ou variados), e de acordo com a duração das baterias (se uniformes ou não). Estudamos também o caso preemptivo: quando os sensores podem ser ligados mais de uma vez. Para este último caso, projetamos um algoritmo polinomial bem simples. O Problema da Cobertura de Faixa Restrita é NP-difícil no caso não-preemptivo em que os sensores têm bateria de duração variável. Para este caso, em 2009 Gibson e Varadarajan apresentaram um algoritmo polinomial que provaram ser uma 5-aproximação. Provamos que este algoritmo tem fator de aproximação 4, e mostramos que este fator é justo. Apresentamos também formulações lineares inteiras para este caso, e os resultados computacionais obtidos. / We study the algorithmic aspects of the Sensor Cover Problem. Broadly speaking, in this problem the input consists of a region to be covered by a set of sensors previously positioned, each one powered with a battery of limited duration, and the objective is to assign to each sensor an initial time, so as to cover the given region for as long as possible. We focus our study on the one-dimensional case of the problem, called Restricted Strip Cover Problem, in which the region to be covered is an interval (of the real line). We study several variants, according to the type of the subintervals the sensors cover (if they have fixed length or not), to the duration of the batteries (if uniform or not). We also study the preemptive case: when the sensors can be turned on and off more than once. For this case, we designed a simple polynomial-time algorithm. The Restricted Strip Cover Problem is NP-hard in the non-preemptive case in which the sensors have non-uniform duration batteries. For this case, in 2009 Gibson and Varadarajan designed a polynomial-time algorithm which they proved to be a 5-aproximation. We prove that this algorithm has approximation ratio 4, and show that this ratio is tight. We also present two integer linear formulations for this case, and report on the computational results obtained with this approach.

Empresas estão procurando reduzir seus custos e aumentar seu desempenho e competitividade. Neste cenário de redução de custos, a logística colaborativa pode ser uma aliada. Numa rede complexa, onde embarcadores muitas vezes nem sabem da existência de outros embarcadores com demandas complementares, existe um potencial de sinergia e redução de custos através da diminuição de deslocamentos de veículos sem carga, ou seja, deslocamentos para reposicionar os veículos. Visando essa redução, o Problema de Cobertura de Rotas (PCR), que tem como objetivo cobrir rotas no mínimo custo, une as demandas de frete de vários embarcadores e tenta minimizar os deslocamentos sem cargas (reposicionamentos), reduzindo assim o custo total de toda a rede dos embarcadores envolvidos. Esta pesquisa propõe um modelo e uma heurística para resolver, em grande escala através de programação paralela, uma expansão do PCR. / Companies are looking to reduce costs and improve performance and competitiveness. In this cost-cutting scenario, collaborative logistics can be an ally. In a complex network where shippers often do not know of the existence of other shippers with complementary demands, there is potential for synergy and cost savings by reducing unloaded travelling of vehicles, i.e, the distance and time to reposition the vehicles\'. Towards that reduction, the Lane Covering Problem (LCP), which aims to cover at least cost routeslinks the various shippers\' demands of freight and tries to minimize operations without loads (repositioning), thus reducing the total cost of the entire network for involved shippers. This research proposes a model and an heuristic to solve, in large-scale through parallel programming, an expansion of the PCR.

A crescente necessidade de buscar operações mais eficientes, com menor custo e mais sustentáveis tem feito com que empresas passassem a procurar oportunidades pelas quais estes objetivos pudessem ser atingidos. Na área de transportes encontrou-se na colaboração uma oportunidade para tal. Este trabalho trata o problema de cobertura rotas com cardinalidade restrita (PCRCR), onde empresas que realizam viagens de carga cheia se unem com o objetivo de reduzir o deslocamento vazio de veículos através da formação de ciclos. É chamado de problema de cardinalidade restrita uma vez que limitamos o número de máximo de viagens no ciclo, o que torna este problema NP-Hard. Existem na literatura duas heurísticas (construtivas) e um modelo por programação linear inteira para a solução deste problema. Este trabalho apresenta uma heurística baseada em um método de busca local que reduziu em média 3,19% os melhores resultados apresentados na literatura. Também são apresentados os tempos de execução de cada um dos algoritmos e a importância de escolher de uma boa solução inicial quando se deseja implantar uma Heurística com Busca Local. / The growing need to seek more efficient, lower cost and more sustainable operations has caused industries to seek opportunities in which these objectives could be achieved. In the area of transportation, collaboration is an opportunity for that. This work deals with the cardinality constrained lane covering problem (CCLCP), where companies who uses full truck loads join efforts in order to reduce empty vehicle travel through closed cycle formation. It is known as cardinality constraint problem as the maximum number of trips in the cycle is limited to an integer number, which makes this problem NP-Hard. There are two heuristics in the literature (constructive) and an integer linear programming model for solving this problem. This work presents a heuristic based on a local search method that reduced an average of 3.19% the better results in the literature. It also presents the execution times of each algorithm and the importance of choosing a good initial solution when you want to create a Local Search Heuristic.

Empresas estão procurando reduzir seus custos e aumentar seu desempenho e competitividade. Neste cenário de redução de custos, a logística colaborativa pode ser uma aliada. Numa rede complexa, onde embarcadores muitas vezes nem sabem da existência de outros embarcadores com demandas complementares, existe um potencial de sinergia e redução de custos através da diminuição de deslocamentos de veículos sem carga, ou seja, deslocamentos para reposicionar os veículos. Visando essa redução, o Problema de Cobertura de Rotas (PCR), que tem como objetivo cobrir rotas no mínimo custo, une as demandas de frete de vários embarcadores e tenta minimizar os deslocamentos sem cargas (reposicionamentos), reduzindo assim o custo total de toda a rede dos embarcadores envolvidos. Esta pesquisa propõe um modelo e uma heurística para resolver, em grande escala através de programação paralela, uma expansão do PCR. / Companies are looking to reduce costs and improve performance and competitiveness. In this cost-cutting scenario, collaborative logistics can be an ally. In a complex network where shippers often do not know of the existence of other shippers with complementary demands, there is potential for synergy and cost savings by reducing unloaded travelling of vehicles, i.e, the distance and time to reposition the vehicles\'. Towards that reduction, the Lane Covering Problem (LCP), which aims to cover at least cost routeslinks the various shippers\' demands of freight and tries to minimize operations without loads (repositioning), thus reducing the total cost of the entire network for involved shippers. This research proposes a model and an heuristic to solve, in large-scale through parallel programming, an expansion of the PCR.

A crescente necessidade de buscar operações mais eficientes, com menor custo e mais sustentáveis tem feito com que empresas passassem a procurar oportunidades pelas quais estes objetivos pudessem ser atingidos. Na área de transportes encontrou-se na colaboração uma oportunidade para tal. Este trabalho trata o problema de cobertura rotas com cardinalidade restrita (PCRCR), onde empresas que realizam viagens de carga cheia se unem com o objetivo de reduzir o deslocamento vazio de veículos através da formação de ciclos. É chamado de problema de cardinalidade restrita uma vez que limitamos o número de máximo de viagens no ciclo, o que torna este problema NP-Hard. Existem na literatura duas heurísticas (construtivas) e um modelo por programação linear inteira para a solução deste problema. Este trabalho apresenta uma heurística baseada em um método de busca local que reduziu em média 3,19% os melhores resultados apresentados na literatura. Também são apresentados os tempos de execução de cada um dos algoritmos e a importância de escolher de uma boa solução inicial quando se deseja implantar uma Heurística com Busca Local. / The growing need to seek more efficient, lower cost and more sustainable operations has caused industries to seek opportunities in which these objectives could be achieved. In the area of transportation, collaboration is an opportunity for that. This work deals with the cardinality constrained lane covering problem (CCLCP), where companies who uses full truck loads join efforts in order to reduce empty vehicle travel through closed cycle formation. It is known as cardinality constraint problem as the maximum number of trips in the cycle is limited to an integer number, which makes this problem NP-Hard. There are two heuristics in the literature (constructive) and an integer linear programming model for solving this problem. This work presents a heuristic based on a local search method that reduced an average of 3.19% the better results in the literature. It also presents the execution times of each algorithm and the importance of choosing a good initial solution when you want to create a Local Search Heuristic.

Este trabalho é focado num problema clássico das Ciências e Engenharia, que consiste em cobrir um objeto por esferas de mesmo raio, a ser minimizado. A abordagem prática usual conta com sérias desvantagens. Logo, faz-se necessário trabalhar com isto de forma diferenciada. A técnica proposta aqui envolve a utilização de resultados célebres da geometria algébrica real, que tem como peça central o positivstellensatz de Stengle e, fazendo a devida relação entre esses resultados e otimização com restrições envolvendo representações naturais por somas de quadrados, é possível reduzir o problema original a um de programação semidefinida não linear. Mas, por contar com particularidades que favorecem a aplicação do paradigma de restauração inexata, esta foi a técnica utilizada para resolvê-lo. A versatilidade da técnica e a possibilidade de generalização direta dos objetos envolvidos destacam-se como grandes vantagens desta abordagem, além da visão algébrica inovadora do problema. / This work is focused on a classic problem from Engineering. Basically, it consists of finding the optimal positioning and radius of a set of equal spheres in order to cover a given object. The common approach to this carries some substantial disadvantages, what makes it necessary to nd a dierent way. Here, we explore some renowned results from real algebraic geometry, which has Stengle\'s positivstellensatz as one of its central pieces, and SOS optimization. Once the proper link is made, the original problem can be reduced to a nonlinear semidenite programming one, which has peculiarities that favours the application of an inexact restoration paradigm. We point out the algebraic view and the no use of discretizations as great advantages of this approach, besides the notable versatility and easy generalization in terms of dimension and involved objects.

Este trabalho é focado num problema clássico das Ciências e Engenharia, que consiste em cobrir um objeto por esferas de mesmo raio, a ser minimizado. A abordagem prática usual conta com sérias desvantagens. Logo, faz-se necessário trabalhar com isto de forma diferenciada. A técnica proposta aqui envolve a utilização de resultados célebres da geometria algébrica real, que tem como peça central o positivstellensatz de Stengle e, fazendo a devida relação entre esses resultados e otimização com restrições envolvendo representações naturais por somas de quadrados, é possível reduzir o problema original a um de programação semidefinida não linear. Mas, por contar com particularidades que favorecem a aplicação do paradigma de restauração inexata, esta foi a técnica utilizada para resolvê-lo. A versatilidade da técnica e a possibilidade de generalização direta dos objetos envolvidos destacam-se como grandes vantagens desta abordagem, além da visão algébrica inovadora do problema. / This work is focused on a classic problem from Engineering. Basically, it consists of finding the optimal positioning and radius of a set of equal spheres in order to cover a given object. The common approach to this carries some substantial disadvantages, what makes it necessary to nd a dierent way. Here, we explore some renowned results from real algebraic geometry, which has Stengle\'s positivstellensatz as one of its central pieces, and SOS optimization. Once the proper link is made, the original problem can be reduced to a nonlinear semidenite programming one, which has peculiarities that favours the application of an inexact restoration paradigm. We point out the algebraic view and the no use of discretizations as great advantages of this approach, besides the notable versatility and easy generalization in terms of dimension and involved objects.

Orientadora: Gordana Manic / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2013

Made available in DSpace on 2015-04-11T14:02:47Z (GMT). No. of bitstreams: 1 Andre Ricardo Melo Araujo.pdf: 3722790 bytes, checksum: 1876d821e1e927795304f1c1ee7bbb67 (MD5) Previous issue date: 2013-03-01 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / Wireless Sensor Network (WSN) is a special kind of ad hoc networks composed of devices capable of processing, storing, sensing the environment, and transmitting data via wireless communication interface. The sensor nodes have several limitations, among them the capacity of energy because to the reduced size. For this reason, many searches have been done with a view to improving the energy consumption of sensor nodes. This work aims to address the Problem of Coverage, Clustering and Routing with Mobile Sink (PCAR-SM, in portuguese Problema de Cobertura, Agrupamento e Roteamento com Sorvedouro Móvel) in WSN with mobile sink consisting of: given a set of sensor nodes and a monitoring area, develop algorithms to find the best subset of sensor nodes to cover the monitoring area, group them in a smaller number of clusters and find the shortest route to mobile sink navigate. The PCAR-SM is a strategy used to reduce the energy consumption of sensor nodes, data collisions, interference and redundant data in networks with high concentration of sensor nodes per area. The purpose of this paper is to solve each problem separately and together, in order to evaluate the impact of each problem on the other. The Coverage Problem has been solved with two metaheuristics: an Genetic Algorithm (GA) and a Greedy Randomized Adaptive Search Procedure (GRASP) algorithm. In the latter we used two representations of solution: (a) representation by sensor, where each element of the solution vector represents a sensor node that must be switched on or off; (b) representation by demand, where each element of the solution vector represents a demand point will indicate which sensor node cover it. The AG uses only the representation by demand. The computational results for Coverage Problem used the benchmark of Beasley s OR Library and it was possible seen that the GRASP with representation by demand achieved better results than the GA and the GRASP with representation by sensor when the optimization criterion is to minimize the total cost of each sensor node used in the solution. For Clustering Problem was created approach of virtual grids. In this approach, we divide the area into grids and clusters are formed by a set of adjacent grids (maximum 5 grids in group) forming a cross schematic. The aim of the problem is to minimize the number of clusters in the area. With this approach, we can model the Clustering Problem as a Set Cover Problem (SCP) without overlapping (an element does not belong to more than one set), which was treated by a greedy heuristic called Greedy Clustering Algorithm (GCA). The virtual grids proved to be a good solution because it is simple to identify a node which grid it belongs. Its simplicity also makes it a appropriate method for a distributed version. The Routing Problem of sink was modeled as the Travelling Salesman Problem (TSP), where the mobile sink part of a corner of the monitoring area, runs through the area visiting all clusters and returns to the starting point. For this, we propose two greedy approaches based on nearest neighbor, the Routing Greedy Algorithm - Center (RGA-C) and Routing Greedy Algorithm - Border (RGA-B). The route of the sink was also solved by a heuristic based on algorithm Centralized Spatial Partitioning (CSP). In CSP approach, the route is fixed and reminds the movement of a snake. The results show that fixed route produces a path with smaller size compared to the greedy heuristic for TSP. We analyze also the PCAR-SM, creating heuristic strategies. The union of the Clustering Problem and Routing Problem proved more beneficial in relation to the size of the sink s route. The union of Coverage Problem and Clustering Problem only proved beneficial when the communication radius was about 3,9 times greater than the sensing radius. Our results show that solve problems together allows some changes in the algorithms will lead to better results. / As Redes de Sensores Sem Fio (RSSFs) são um tipo especial de redes ad hoc constituídas por dispositivos capazes de processar, armazenar, sensoriar o ambiente e transmitir dados via interface de comunicação sem fio, denominados nós sensores. Os nós sensores possuem várias limitações, dentre elas, a capacidade de energia devido ao tamanho reduzido. Por isto, muitas pesquisas foram feitas tendo em vista a melhoria no consumo de energia dos nós sensores. Este trabalho tem como objetivo tratar o Problema de Cobertura, Agrupamento e Roteamento com Sorvedouro Móvel (PCAR-SM) em RSSF com nó sorvedouro móvel, que consiste em: dado um conjunto de nós sensores e uma área de monitoramento, desenvolver algoritmos para encontrar o melhor subconjunto de nós sensores que cubra a área de monitoramento, juntá-los no menor número de grupos possíveis e encontrar a menor rota para um nó sorvedouro móvel percorrer. O PCAR-SM é uma estratégia utilizada para diminuir o consumo de energia dos nós sensores, a colisão de dados, as interferências e os dados redundantes em redes com alta concentração de nós sensores por área. A proposta deste trabalho é resolver cada problema separadamente e em conjunto, de modo a avaliar o impacto de cada problema na solução do outro. O Problema de Cobertura foi resolvido com duas metaheurísticas: um Algoritmo Genético (AG) e um algoritmo Greedy Randomized Adaptive Search Procedure (GRASP). Neste último foram utilizadas duas representações de solução: (a) representação por sensor, onde cada elemento do vetor de solução representa um nó sensor que estará ligado ou desligado; (b) representação por demanda, onde cada elemento do vetor de solução representa um ponto de demanda no qual indicará qual o nó sensor o cobre. O AG utiliza apenas a representação por demanda. Os resultados computacionais para o Problema de Cobertura utilizaram o benchmark da Beasley s OR Library e foi possível constatar que o GRASP com representação por demanda obteve melhores resultados que o AG e o GRASP com representação por sensor quando o critério de otimização é minimizar a soma total dos custos de cada nó sensor utilizado na solução. Para o Problema de Agrupamento foi criada uma abordagem de grades virtuais. Nesta abordagem dividimos a área em grades e os grupos são formados por um conjunto de grades adjacentes (no máximo 5 grades) formando um esquema de cruz. O objetivo do problema é minimizar o número de grupos na área. A partir desta abordagem, pode-se modelar o Problema de Agrupamento como um Problema de Cobertura de Conjuntos (PCC) sem sobreposição (um elemento não pertence a mais de um conjunto), que foi tratada por uma heurística gulosa denominada Greedy Clustering Algorithm (GCA). Os grades virtuais provou ser uma boa solução por ser simples para um nó identificar a qual grade ele pertence. Sua simplicidade ainda o torna uma método adequado para uma versão distribuída. O Problema de Roteamento do nó sorvedouro foi modelado como o Problema do Caixeiro Viajante (PCV), onde o nó sorvedouro móvel parte de um canto da área de monitoramento, percorre a área visitando todos os grupos e retorna ao ponto inicial. Para isto, propomos duas abordagens gulosas baseadas no vizinho mais próximo, o Routing Greedy Algorithm - Center (RGA-C) e o Routing Greedy Algorithm - Border (RGA-B). A rota do nó sorvedouro também foi resolvida por uma heurística baseada no algoritmo Centralized Spatial Partitioning (CSP). Na abordagem CSP, a rota é fixa e lembra o movimento de uma cobra. Os resultados mostram que a rota fixa gera um percurso com tamanho menor em comparação com as heurísticas gulosas para o PCV. Analisamos, ainda, o PCAR-SM, criando estratégias heurísticas. Aunião dos Problema de Agrupamento e Roteamento, provou ser mais benéfica em relação ao tamanho da rota do nó sorvedouro, já a união do Problema de Cobertura com o Problema de Agrupamento só mostrou ser benéfica quando o raio de comunicação era aproximadamente 3, 9 vezes maior que o raio de sensoriamento. Nossos resultados, mostram que resolver os problemas em conjunto permite que algumas mudanças nos algoritmos levem a melhores resultados.