Novas aplicações de metaheurísticas na solução do problema de planejamento da expansão do sistema de transmissão de energia elétrica

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Network reconfiguration of distribution systems using metaheuristics and reliability measures

In an evermore competitive environment, power distribution companies need to continuously monitor and improve the reliability indices of their systems. The network reconfiguration (NR) of a distribution system is a technique that well adapts to this new deregulated environment for it allows improvement of system reliability indices without the onus involved in procuring new equipment. This paper presents a reliability-based NR methodology that uses metaheuristic techniques to search for the optimal network configuration. Three metaheuristics, i.e. Tabu Search, Evolution Strategy, and Differential Evolution, are tested using a Brazilian distribution network and the results are discussed. © 2009 IEEE.

On the optical flow model selection through metaheuristics

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Metaheuristics for a crop rotation problem

This paper presents a mathematical model adapted from literature for the crop rotation problem with demand constraints (CRP-D). The main aim of the present work is to study metaheuristics and their performance in a real context. The proposed algorithms for solution of the CRP-D are a genetic algorithm, a simulated annealing and hybrid approaches: a genetic algorithm with simulated annealing and a genetic algorithm with local search algorithm. A new constructive heuristic was also developed to provide initial solutions for the metaheuristics. Computational experiments were performed using a real planting area and semi-randomly generated instances created by varying the number, positions and dimensions of the lots. The computational results showed that these algorithms determined good feasible solutions in a short computing time as compared with the time spent to get optimal solutions, thus proving their efficacy for dealing with this practical application of the CRP-D.

Estudo da movimentação de plantas aquáticas imersas presentes no reservatório da UHE Eng. Souza Dias - Jupiá

O objetivo deste estudo foi desenvolver um método para determinação de pontos de reprodução e de suas respectivas importâncias na disseminação das espécies E. densa, E. najas e C. demersum no reservatório de Jupiá. Foram monitorados dez locais nos quais se encontrou registro de altas infestações dessas espécies. Dois desses locais situam-se no rio Paraná, nas lagoas denominadas de Ferradura e Pernilongo; os outros oito sítios estão localizados no rio Tietê, nas lagoas marginais Testemunha, Barrenta, Vírgula e Flórida, e no leito do rio nos pontos Acima da Ponte dos Barrageiros, Abaixo da Ponte, Baía ao Lado da Ponte e em frente da Praia de Itapura. em cada um desses sítios de reprodução foram liberados e monitorados dez blocos de plantas aquáticas imersas por mês. Os blocos possuíam volume de 0,14 cm³ e receberam uma etiqueta plástica de identificação externa e uma bóia de cor laranja, com o objetivo de serem facilmente localizadas ou visualizadas à distância. Após a soltura, cada bloco foi georreferenciado por meio de um aparelho GPS, sendo o seu deslocamento avaliado a cada 15 dias. Os sítios Lagoa Vírgula, Lagoa Testemunha e Lagoa Barrenta destacaram-se quanto ao número de blocos (30, 20 e 19 blocos, respectivamente), que percorreram distâncias superiores a 500 m e, conseqüentemente, saíram de seus respectivos locais de reprodução. A grande maioria dos blocos permaneceu dentro da Lagoa Flórida; somente 12 blocos saíram e alcançaram o leito do rio Tietê. O sítio denominado Leito Acima da Ponte foi o que mais se destacou dentre os três localizados no leito do rio Tietê, pois forneceu 18 blocos de plantas, enquanto os sítios Abaixo da Ponte e Baía ao Lado da Ponte forneceram 15 e 14 blocos, respectivamente. O sítio Praia de Itapura foi o que apresentou menor importância em relação ao fornecimento de plantas imersas no rio Tietê, sendo localizadas apenas 11 bóias com deslocamento superior a 500 m. Os sítios de reprodução localizados no rio Paraná também contribuíram para o fornecimento de plantas imersas ao reservatório de Jupiá; nove blocos saíram da Lagoa Pernilongo e apresentaram deslocamentos superiores a 500 m. Entretanto, os sítios Lagoa Barrenta e Lagoa Ferradura foram aqueles que mais contribuíram com a chegada de plantas na tomada de água da UHE Eng. Souza Dias, uma vez que foram recolhidos, respectivamente, seis e quatro blocos de plantas provenientes desses locais de dispersão. A metodologia utilizada mostrou-se eficaz quanto à avaliação da movimentação de plantas aquáticas imersas dentro do reservatório de Jupiá.

Hybrid evolutionary algorithm for the Capacitated Centered Clustering Problem

The Capacitated Centered Clustering Problem (CCCP) consists of defining a set of p groups with minimum dissimilarity on a network with n points. Demand values are associated with each point and each group has a demand capacity. The problem is well known to be NP-hard and has many practical applications. In this paper, the hybrid method Clustering Search (CS) is implemented to solve the CCCP. This method identifies promising regions of the search space by generating solutions with a metaheuristic, such as Genetic Algorithm, and clustering them into clusters that are then explored further with local search heuristics. Computational results considering instances available in the literature are presented to demonstrate the efficacy of CS. (C) 2010 Elsevier Ltd. All rights reserved.

An Efficient Codification to Solve Distribution Network Reconfiguration for Loss Reduction Problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

The cross-entropy method and its application to minimize the ripple of magnetic levitation forces of a maglev system

This paper explores firstly the potential of a new evolutionary method - the Cross-Entropy (CE) method in solving continuous inverse electromagnetic problems. For this purpose, an adaptive updating formula for the smoothing parameter, some mutation operation, and a new termination criterion are proposed. The proposed CE based metaheuristics is applied to reduce the ripple of the magnetic levitation forces of a prototype Maglev system. The numerical results have shown that the ripple of the magnetic levitation forces of the prototype system is reduced significantly after the design optimization using the proposed algorithm.

A metaheuristic to solve the transmission expansion planning

In this letter, a genetic algorithm (GA) is applied to solve - the static and multistage transmission expansion planning (TEP) problem. The characteristics of the proposed GA to solve the TEP problem are presented. Results using some known systems show that the proposed GA solves a smaller number of linear programming problems in order to find the optimal solutions and obtains a better solution for the multistage TEP problem.

Distribution network reconfiguration using an efficient evolutionary algorithm

Network reconfiguration is an important tool to optimize the operating conditions of a distribution system. This is accomplished modifying the network structure of distribution feeders by changing the open/close status of sectionalizing switches. This not only reduces the power losses, but also relieves the overloading of the network components. Network reconfiguration belongs to a complex family of problems because of their combinatorial nature and multiple constraints. This paper proposes a solution to this problem, using a specialized evolutionary algorithm, with a novel codification, and a brand new way of implement the genetic operators considering the problem characteristics. The algorithm is presented and tested in a real distribution system, showing excellent results and computational efficiency. © 2007 IEEE.

Lot sizing and furnace scheduling in small foundries

A lot sizing and scheduling problem prevalent in small market-driven foundries is studied. There are two related decision levels: (1) the furnace scheduling of metal alloy production, and (2) moulding machine planning which specifies the type and size of production lots. A mixed integer programming (MIP) formulation of the problem is proposed, but is impractical to solve in reasonable computing time for non-small instances. As a result, a faster relax-and-fix (RF) approach is developed that can also be used on a rolling horizon basis where only immediate-term schedules are implemented. As well as a MIP method to solve the basic RF approach, three variants of a local search method are also developed and tested using instances based on the literature. Finally, foundry-based tests with a real-order book resulted in a very substantial reduction of delivery delays and finished inventory, better use of capacity, and much faster schedule definition compared to the foundry's own practice. © 2006 Elsevier Ltd. All rights reserved.

Evolutionary multi-move path-relinking for transmission network expansion planning

This paper presents the application of a new metaheuristic algorithm to solve the transmission expansion planning problem. A simple heuristic, using a relaxed network model associated with cost perturbation, is applied to generate a set of high quality initial solutions with different topologies. The population is evolved using a multi-move path-relinking with the objective of finding minimum investment cost for the transmission expansion planning problem employing the DC representation. The algorithm is tested on the southern Brazilian system, obtaining the optimal solution for the system with better performance than similar metaheuristics algorithms applied to the same problem. ©2010 IEEE.

GRASP with evolutionary path-relinking for the capacitated arc routing problem

The Capacitated Arc Routing Problem (CARP) is a well-known NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours servicing a subset of required edges under vehicle capacity constraints. There are numerous applications for the CARP, such as street sweeping, garbage collection, mail delivery, school bus routing, and meter reading. A Greedy Randomized Adaptive Search Procedure (GRASP) with Path-Relinking (PR) is proposed and compared with other successful CARP metaheuristics. Some features of this GRASP with PR are (i) reactive parameter tuning, where the parameter value is stochastically selected biased in favor of those values which historically produced the best solutions in average; (ii) a statistical filter, which discard initial solutions if they are unlikely to improve the incumbent best solution; (iii) infeasible local search, where high-quality solutions, though infeasible, are used to explore the feasible/infeasible boundaries of the solution space; (iv) evolutionary PR, a recent trend where the pool of elite solutions is progressively improved by successive relinking of pairs of elite solutions. Computational tests were conducted using a set of 81 instances, and results reveal that the GRASP is very competitive, achieving the best overall deviation from lower bounds and the highest number of best solutions found. © 2011 Elsevier Ltd. All rights reserved.

An iterated sample construction with path relinking method: Application to switch allocation in electrical distribution networks

We present a metaheuristic approach which combines constructive heuristics and local searches based on sampling with path relinking. Its effectiveness is demonstrated by an application to the problem of allocating switches in electrical distribution networks to improve their reliability. Our approach also treats the service restoration problem, which has to be solved as a subproblem, to evaluate the reliability benefit of a given switch allocation proposal. Comparisons with other metaheuristics and with a branch-and-bound procedure evaluate its performance. © 2012 Published by Elsevier Ltd.