O problema do caixeiro viajante alugador : um estudo algorítmico

The Car Rental Salesman Problem (CaRS) is a variant of the classical Traveling Salesman Problem which was not described in the literature where a tour of visits can be decomposed into contiguous paths that may be performed in different rental cars. The aim is to determine the Hamiltonian cycle that results in a final minimum cost, considering the cost of the route added to the cost of an expected penalty paid for each exchange of vehicles on the route. This penalty is due to the return of the car dropped to the base. This paper introduces the general problem and illustrates some examples, also featuring some of its associated variants. An overview of the complexity of this combinatorial problem is also outlined, to justify their classification in the NPhard class. A database of instances for the problem is presented, describing the methodology of its constitution. The presented problem is also the subject of a study based on experimental algorithmic implementation of six metaheuristic solutions, representing adaptations of the best of state-of-the-art heuristic programming. New neighborhoods, construction procedures, search operators, evolutionary agents, cooperation by multi-pheromone are created for this problem. Furtermore, computational experiments and comparative performance tests are conducted on a sample of 60 instances of the created database, aiming to offer a algorithm with an efficient solution for this problem. These results will illustrate the best performance reached by the transgenetic algorithm in all instances of the dataset

Algorítmo evolucionário para a distribuição de produtos de petróleo por redes de polidutos

The distribution of petroleum products through pipeline networks is an important problem that arises in production planning of refineries. It consists in determining what will be done in each production stage given a time horizon, concerning the distribution of products from source nodes to demand nodes, passing through intermediate nodes. Constraints concerning storage limits, delivering time, sources availability, limits on sending or receiving, among others, have to be satisfied. This problem can be viewed as a biobjective problem that aims at minimizing the time needed to for transporting the set of packages through the network and the successive transmission of different products in the same pipe is called fragmentation. This work are developed three algorithms that are applied to this problem: the first algorithm is discrete and is based on Particle Swarm Optimization (PSO), with local search procedures and path-relinking proposed as velocity operators, the second and the third algorithms deal of two versions based on the Non-dominated Sorting Genetic Algorithm II (NSGA-II). The proposed algorithms are compared to other approaches for the same problem, in terms of the solution quality and computational time spent, so that the efficiency of the developed methods can be evaluated

O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico

The Hiker Dice was a game recently proposed in a software designed by Mara Kuzmich and Leonardo Goldbarg. In the game a dice is responsible for building a trail on an n x m board. As the dice waits upon a cell on the board, it prints the side that touches the surface. The game shows the Hamiltonian Path Problem Simple Maximum Hiker Dice (Hidi-CHS) in trays Compact Nth , this problem is then characterized by looking for a Hamiltonian Path that maximize the sum of marked sides on the board. The research now related, models the problem through Graphs, and proposes two classes of solution algorithms. The first class, belonging to the exact algorithms, is formed by a backtracking algorithm planed with a return through logical rules and limiting the best found solution. The second class of algorithms is composed by metaheuristics type Evolutionary Computing, Local Ramdomized search and GRASP (Greed Randomized Adaptative Search). Three specific operators for the algorithms were created as follows: restructuring, recombination with two solutions and random greedy constructive.The exact algorithm was teste on 4x4 to 8x8 boards exhausting the possibility of higher computational treatment of cases due to the explosion in processing time. The heuristics algorithms were tested on 5x5 to 14x14 boards. According to the applied methodology for evaluation, the results acheived by the heuristics algorithms suggests a better performance for the GRASP algorithm

O problema do caixeiro alugador com coleta de bonus: um estudo algoritmico

This paper introduces a new variant of the Traveling Car Renter Problem, named Prizecollecting Traveling Car Renter Problem. In this problem, a set of vertices, each associated with a bonus, and a set of vehicles are given. The objective is to determine a cycle that visits some vertices collecting, at least, a pre-defined bonus, and minimizing the cost of the tour that can be traveled with different vehicles. A mathematical formulation is presented and implemented in a solver to produce results for sixty-two instances. The proposed problem is also subject of an experimental study based on the algorithmic application of four metaheuristics representing the best adaptations of the state of the art of the heuristic programming.We also provide new local search operators which exploit the neighborhoods of the problem, construction procedures and adjustments, created specifically for the addressed problem. Comparative computational experiments and performance tests are performed on a sample of 80 instances, aiming to offer a competitive algorithm to the problem. We conclude that memetic algorithms, computational transgenetic and a hybrid evolutive algorithm are competitive in tests performed

Thermal relationships and exercise physiology in anuran amphibians: Integration and evolutionary implications

Thermal and water balance are coupled in anurans, and species with particularly permeable skin avoid overheating more effectively than minimizing variance of body temperature. In turn, temperature affects muscle performance in several ways, so documenting the mean and variance of body temperature of active frogs can help explain variation in behavioral performance. The two types of activities studied in most detail, jumping and calling, differ markedly in duration and intensity, and there are distinct differences in the metabolic profile and fiber type of the supporting muscles. Characteristics of jumping and calling also vary significantly among species, and these differences have a number of implications that we discuss in some detail throughout this paper. One question that emerges from this topic is whether anuran species exhibit activity temperatures that match the temperature range over which they perform best. Although this seems the case, thermal preferences are variable and may not necessarily reflect typical activity temperatures. The performance versus temperature curves and the thermal limits for anuran activity reflect the thermal ecology of species more than their systematic position. Anuran thermal physiology, therefore, seems to be phenotypically plastic and susceptible to adaptive evolution. Although generalizations regarding the mechanistic basis of such adjustments are not yet possible, recent attempts have been made to reveal the mechanistic basis of acclimation and acclimatization. (C) 2007 Elsevier B.V. All rights reserved.

Evolutionary and biogeographic history of the subfamily Neoplecostominae (Siluriformes: Loricariidae)

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

Evolutionary dynamics of heterochromatin in the genome of Dichotomius beetles based on chromosomal analysis

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

Characterization of invasive fish species in a river transposition region: evolutionary chromosome studies in the genus Hoplias (Characiformes, Erythrinidae)

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

Cytogenetic Mapping of 5S and 18S rRNAs and H3 Histone Genes in 4 Ancient Proscopiidae Grasshopper Species: Contribution to Understanding the Evolutionary Dynamics of Multigene Families

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

Integrating cytogenetics and genomics in comparative evolutionary studies of cichlid fish

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

Evolutionary dynamics of rRNA gene clusters in cichlid fish

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

Molecular organization of 5S rDNA in sharks of the genus Rhizoprionodon: insights into the evolutionary dynamics of 5S rDNA in vertebrate genomes

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

Evolutionary perspectives on seed consumption and dispersal by fishes

Fishes probably were the first vertebrate seed dispersers, yet little research has examined this phenomenon. We review evidence of fruit and seed consumption by fishes, and analyze the evolution of frugivory and granivory using South American serrasalmids as a model. Frugivory and granivory are observed among diverse fish taxa worldwide, although most reports are from the Neotropics. Frugivory and granivory among serrasalmids apparently are derived from omnivory, with powerful jaws and specialized dentition appearing as major adaptations. No particular fruit traits seem to be associated with seed dispersal by fishes (ichthyochory). Recent experimental evidence of ichthyochory suggests that fishes can influence riparian vegetation dynamics. Because of deleterious human impacts on aquatic ecosystems worldwide, many critical interactions between plants and fishes have been disrupted before they could be studied. Exotic frugivorous fishes have recently become established on foreign continents, with unknown ecological consequences.

Chromosomal organization of the 18S and 5S rRNAs and histone H3 genes in Scarabaeinae coleopterans: insights into the evolutionary dynamics of multigene families and heterochromatin

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

Evolutionary history of Scinax treefrogs on land-bridge islands in south-eastern Brazil

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