Navegando por Autor "Rezende, Josiane da Costa Vieira"
Agora exibindo 1 - 4 de 4
Resultados por página
Opções de Ordenação
Item Um algoritmo híbrido para resolução de problemas binários.(2015) Rezende, Josiane da Costa Vieira; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Souza, Sérgio Ricardo deEste trabalho apresenta um método híbrido, denominado HGVPRLB, para resolver problemas lineares binários. O método combina os procedimentos Greedy Randomized Adaptive Search Procedures -- GRASP, Variable Neighborhood Descent -- VND, propagação de restrições, e cortes Local branching. Como em todo algoritmo GRASP, o método HGVPRLB apresenta duas fases, que interagem entre si até que o tempo limite seja atingido. A primeira fase visa a construção de uma solução inicial; a segunda, por sua vez, visa ao refinamento dessa solução construída. Na fase de construção, é utilizado o resolvedor CBC e um procedimento de propagação de restrições, de forma a gerar uma solução inicial para o problema. O resolvedor CBC relaxa as variáveis binárias, isto é, atribui o valor de cada variável no intervalo real [0,1]. O procedimento propagação de restrições possui a finalidade de verificar se existe solução viável ao se fixar uma determinada variável no valor 1. Se esta solução existir, ele poderá retornar, ainda, um conjunto de possíveis fixações das demais variáveis. Na fase de refinamento são utilizados cortes Local branching controlados pelo procedimento VND até que um tempo previamente definido seja atingido. Os cortes Local Branching utilizam um resolvedor de programação linear inteira como uma ferramenta caixa-preta para explorar eficientemente subespaços das soluções do problema. O método desenvolvido foi aplicado a um conjunto de problemas binários da biblioteca MIPLIB 2010 com o intuito de verificar sua capacidade de obter soluções viáveis de qualidade variando-se o tempo de processamento. Os experimentos computacionais realizados mostraram que, quando o tempo de processamento aumenta, o método consegue aumentar tanto o número de soluções viáveis quanto a qualidade delas. Além disso, o método desenvolvido se mostrou superior a outro método da literatura, bem como a dois outros resolvedores de código aberto nesses dois indicadores de avaliação.Item Collecting large volume data from wireless sensor network by drone.(2023) Silva, Rone Ilídio da; Rezende, Josiane da Costa Vieira; Souza, Marcone Jamilson FreitasData collection is the most important task in wireless sensor networks (WSN). Each sensor node has to send the sensed data to a special node called sink, which is the user interface. The sensor nodes far from the sink send data to intermediate nodes that forward it by multi-hop data paths. This characteristic leads to higher energy consumption in the sensor nodes close to the sink since they have to relay data from all other sensor nodes. The literature presents several studies that use mobile sinks for data collection to reduce the number of hops in the data paths and distributes the energy consumption, considering that the nodes close to the mobile sink change. However, the majority of these studies consider only the network limitation, such as energy. Furthermore, they also consider sensor nodes sending only one data packet to the mobile sink. This work assumes a quad-copter drone as a mobile sink and sensor nodes having several data packets to send to the sink. We propose two GRASP-based heuristics to define drone tours for data collection. Since this vehicle has limited flight time, the primary metric analyzed here is the overall data collection time. Furthermore, they guarantee that the mobile sink will stay a minimal time inside the radio range of each sensor node to ensure that all of them will have enough time to send all data. The heuristics achieve this guarantee by looking for a subset of locations, among the infinite points inside the monitored area, where the drone will hover for data gathering. Hence, the proposed heuristics have to search for good locations to reduce the data gathering time and define the shortest path to reduce the trip time. Simulated experiments showed that the proposed GRASP-based heuristics outperformed the greed algorithm found as state of the art for this type of scenario, mainly when the volume of data stored in each sensor node is high.Item Gathering data in wireless sensor networks by drone.(2020) Rezende, Josiane da Costa Vieira; Souza, Marcone Jamilson Freitas; Silva, Rone Ilídio da; Souza, Marcone Jamilson Freitas; Teixeira, Fernando Augusto; Coelho, Igor Machado; Ochi, Luiz Satoru; Penna, Puca Huachi Vaz; Coelho, Vitor Nazário; Silva, Rone Ilidio daThe benefits of using mobile sinks or data mules for data collection in Wireless Sensor Network (WSN) have been studied in several studies. However, most of them consider only the WSN limitations and sensor nodes having no more than one data packet to transmit. This paper considers each sensor node having a relatively larger volume of data stored in its memory. That is, they have several data packets to send to sink. We also consider a drone with hovering capability, such as a quad-copter, as a mobile sink to gather this data. Hence, the mobile collector eventually has to hover to guarantee that all data will be received. Drones, however, have a limited power supply that restricts their flying time. Hence, the drone’s energy cost must also be considered to increase the amount of collected data from the WSN. This work investigates the problem of determining the best drone tour for data gathering in a WSN. We focus on minimizing the overall drone flight time needed to collect all data from the WSN. We propose an algorithm to create a subset of sensor nodes to send data to the drone during its movement and, consequently, reduce its hovering time. The proposed algorithm guarantees that the drone will stay a minimum time inside every sensor node’s radio range. The computational experiments showed that our proposal significantly outperforms the state-of-the-art methods in finding drone tours in this type of scenario.Item HMS : a hybrid multi-start algorithm for solving binary linear programs.(2018) Rezende, Josiane da Costa Vieira; Souza, Marcone Jamilson Freitas; Coelho, Vitor Nazário; Martins, Alexandre XavierThis work presents a hybrid multi-start algorithm for solving generic binary linear programs. This algorithm, called HMS, is based on a Multi-Start Metaheuristic and combines exact and heuristic strategies to address the problem. The initial solutions are generated by a strategy that applies linear programming and constraint propagation for defining an optimized set of fixed variables. In order to refine them, a local search, guided by a Variable Neighborhood Descent heuristic, is called, which, in turn, uses Local Branching cuts. The algorithm was tested in a set of binary LPs from the MIPLIB 2010 library and the results pointed out its competitive performance, resulting in a promising matheuristic.