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.

Stochastic scheduling - A flow shop no wait application and solutions

Minimizing the makespan of a flow-shop no-wait (FSNW) schedule where the processing times are randomly distributed is an important NP-Complete Combinatorial Optimization Problem. In spite of this, it can be found only in very few papers in the literature. By considering the Start Interval Concept, this problem can be formulated, in a practical way, in function of the probability of the success in preserve FSNW constraints for all tasks execution. With this formulation, for the particular case with 3 machines, this paper presents different heuristics solutions: by integrating local optimization steps with insertion procedures and by using genetic algorithms for search the solution space. Computational results and performance evaluations are commented. Copyright (C) 1998 IFAC.

Planejamento da expansão de sistemas de transmissão usando a metaheurística de busca em vizinhança variável

Pós-graduação em Engenharia Elétrica - FEIS

Método heurístico para criação de linhas de trabalho em problemas de escalonamento de pessoal

Pós-graduação em Engenharia Mecânica - FEG

An improved tabu-based vector optimal algorithm for design optimizations of electromagnetic devices

This paper introduces an improved tabu-based vector optimal algorithm for multiobjective optimal designs of electromagnetic devices. The improvements include a division of the entire search process, a new method for fitness assignment, a novel scheme for the generation and selection of neighborhood solutions, and so forth. Numerical results on a mathematical function and an engineering multiobjective design problem demonstrate that the proposed method can produce virtually the exact Pareto front, in both parameter and objective spaces, even though the iteration number used by it is only about 70% of that required by its ancestor.

Strategies to reduce the number of variables and the combinatorial search space of the multistage transmission expansion planning problem

This paper proposes strategies to reduce the number of variables and the combinatorial search space of the multistage transmission expansion planning problem (TEP). The concept of the binary numeral system (BNS) is used to reduce the number of binary and continuous variables related to the candidate transmission lines and network constraints that are connected with them. The construction phase of greedy randomized adaptive search procedure (GRASP-CP) and additional constraints, obtained from power flow equilibrium in an electric power system are employed for more reduction in search space. The multistage TEP problem is modeled like a mixed binary linear programming problem and solved using a commercial solver with a low computational time. The results of one test system and two real systems are presented in order to show the efficiency of the proposed solution technique. © 1969-2012 IEEE.

Basic ingredients for mathematical modeling of tumor growth in vitro: Cooperative effects and search for space

Based on the literature data from HT-29 cell monolayers, we develop a model for its growth, analogous to an epidemic model, mixing local and global interactions. First, we propose and solve a deterministic equation for the progress of these colonies. Thus, we add a stochastic (local) interaction and simulate the evolution of an Eden-like aggregate by using dynamical Monte Carlo methods. The growth curves of both deterministic and stochastic models are in excellent agreement with the experimental observations. The waiting times distributions, generated via our stochastic model, allowed us to analyze the role of mesoscopic events. We obtain log-normal distributions in the initial stages of the growth and Gaussians at long times. We interpret these outcomes in the light of cellular division events: in the early stages, the phenomena are dependent each other in a multiplicative geometric-based process, and they are independent at long times. We conclude that the main ingredients for a good minimalist model of tumor growth, at mesoscopic level, are intrinsic cooperative mechanisms and competitive search for space. © 2013 Elsevier Ltd.

A New Approach to Reducing Search Space and Increasing Efficiency in Simulation Optimization Problems via the Fuzzy-DEA-BCC

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

Crystallization, preliminary X-ray analysis and molecular-replacement solution of haemoglobin-II from the fish matrinxa (Brycon cephalus)

Haemoglobins constitute a set of proteins with interesting structural and functional properties, especially when the two large animal groups reptiles and fishes are focused on. Here, the crystallization and preliminary X-ray analysis of haemoglobin-II from the South American fish matrinxa (Brycon cephalus) is reported. X-ray diffraction data have been collected to 3.0 Angstrom resolution using synchrotron radiation (LNLS). Crystals were determined to belong to space group P2(1) and preliminary structural analysis revealed the presence of two tetramers in the asymmetric unit. The structure was determined using the standard molecular-replacement technique.

Object-Space Road Extraction in Rural Areas Using Stereoscopic Aerial Images

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

A Beam Search Method to Solve the Problem of Assignment Cells to Switches in a Cellular Mobile Network

Assigning cells to switches in a cellular mobile network is known as an NP-hard optimization problem. This means that the alternative for the solution of this type of problem is the use of heuristic methods, because they allow the discovery of a good solution in a very satisfactory computational time. This paper proposes a Beam Search method to solve the problem of assignment cell in cellular mobile networks. Some modifications in this algorithm are also presented, which allows its parallel application. Computational results obtained from several tests confirm the effectiveness of this approach and provide good solutions for large scale problems.

Evasive Maneuvers in Space Debris Environment and Technological Parameters

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

An effortless hybrid method to solve economic load dispatch problem in power systems

This paper proposes a new approach and coding scheme for solving economic dispatch problems (ED) in power systems through an effortless hybrid method (EHM). This novel coding scheme can effectively prevent futile searching and also prevents obtaining infeasible solutions through the application of stochastic search methods, consequently dramatically improves search efficiency and solution quality. The dominant constraint of an economic dispatch problem is power balance. The operational constraints, such as generation limitations, ramp rate limits, prohibited operating zones (POZ), network loss are considered for practical operation. Firstly, in the EHM procedure, the output of generator is obtained with a lambda iteration method and without considering POZ and later in a genetic based algorithm this constraint is satisfied. To demonstrate its efficiency, feasibility and fastness, the EHM algorithm was applied to solve constrained ED problems of power systems with 6 and 15 units. The simulation results obtained from the EHM were compared to those achieved from previous literature in terms of solution quality and computational efficiency. Results reveal that the superiority of this method in both aspects of financial and CPU time. (C) 2011 Elsevier Ltd. All rights reserved.

A Strategy to Solve the Multistage Transmission Expansion Planning Problem

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

Proposal of a Transmission Line Model Based on Lumped Elements: An Analytic Solution

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