An algorithm for the strip packing problem using collision free region and exact fitting placement

The irregular shape packing problem is approached. The container has a fixed width and an open dimension to be minimized. The proposed algorithm constructively creates the solution using an ordered list of items and a placement heuristic. Simulated annealing is the adopted metaheuristic to solve the optimization problem. A two-level algorithm is used to minimize the open dimension of the container. To ensure feasible layouts, the concept of collision free region is used. A collision free region represents all possible translations for an item to be placed and may be degenerated. For a moving item, the proposed placement heuristic detects the presence of exact fits (when the item is fully constrained by its surroundings) and exact slides (when the item position is constrained in all but one direction). The relevance of these positions is analyzed and a new placement heuristic is proposed. Computational comparisons on benchmark problems show that the proposed algorithm generated highly competitive solutions. Moreover, our algorithm updated some best known results. (C) 2012 Elsevier Ltd. All rights reserved.

Home range, movements and diurnal roosts of the endangered thin-spined porcupine, Chaetomys subspinosus (Rodentia: Erethizontidae), in the Brazilian Atlantic Forest

Chaetomys subspinosus is the sole species within the Chaetomyinae subfamily of Caviomorph rodents. This poorly studied porcupine is restricted to the Atlantic Forest in eastern Brazil, where deforestation and habitat fragmentation threaten its survival. Data on the ranging and roosting behavior of C. subspinosus is fairly scarce as it is difficult to observe these behaviors in nature and, consequently, it is very rarely detected during field surveys. We monitored the home ranges of three radio-tagged females over the course of 1 year (2005-2006) and collected data on several aspects of their natural history including movement patterns and the use of diurnal roosts and latrines. The animals were monitored at Parque Estadual Paulo Cesar Vinha, a nature reserve dominated by restinga forests, a subtype of Atlantic Forest occurring on sandy soil. The estimated home range varied little between individuals and was relatively small (mean = 2.14 ha/individual and 1.09 ha/individual using minimum convex polygon and kernel methods, respectively). The animals travelled an average of 147 m/night (range: 21-324 m/night) between two consecutive day roosts. The day roosts were mostly located on vine and liana tangles in the canopy which also aid in connecting the canopy to adjacent trees or the forest floor. Latrines were mostly located near the ground in places heavily protected by spiny bromeliads or by other tangled vegetation. Our data suggests that C. subspinosus has the smallest range among all Neotropical Erethizontids which is likely due to its small size and strictly folivorous diet. Our data also helps explain why C. subspinosus is so difficult to observe in nature: researchers should focus on arboreal masses of tangled vegetation where individuals will normally rest during the day. (C) 2011 Deutsche Gesellschaft fur Saugetierkunde. Published by Elsevier GmbH. All rights reserved.

Suitability of distance metrics as indexes of home-range size in tropical rodent species

Estimators of home-range size require a large number of observations for estimation and sparse data typical of tropical studies often prohibit the use of such estimators. An alternative may be use of distance metrics as indexes of home range. However, tests of correlation between distance metrics and home-range estimators only exist for North American rodents. We evaluated the suitability of 3 distance metrics (mean distance between successive captures [SD], observed range length [ORL], and mean distance between all capture points [AD]) as indexes for home range for 2 Brazilian Atlantic forest rodents, Akodon montensis (montane grass mouse) and Delomys sublineatus (pallid Atlantic forest rat). Further, we investigated the robustness of distance metrics to low numbers of individuals and captures per individual. We observed a strong correlation between distance metrics and the home-range estimator. None of the metrics was influenced by the number of individuals. ORL presented a strong dependence on the number of captures per individual. Accuracy of SD and AD was not dependent on number of captures per individual, but precision of both metrics was low with numbers of captures below 10. We recommend the use of SD and AD instead of ORL and use of caution in interpretation of results based on trapping data with low captures per individual.

Collision free region determination by modified polygonal Boolean operations

Cutting and packing problems are found in numerous industries such as garment, wood and shipbuilding. The collision free region concept is presented, as it represents all the translations possible for an item to be inserted into a container with already placed items. The often adopted nofit polygon concept and its analogous concept inner fit polygon are used to determine the collision free region. Boolean operations involving nofit polygons and inner fit polygons are used to determine the collision free region. New robust non-regularized Boolean operations algorithm is proposed to determine the collision free region. The algorithm is capable of dealing with degenerated boundaries. This capability is important because degenerated boundaries often represent local optimal placements. A parallelized version of the algorithm is also proposed and tests are performed in order to determine the execution times of both the serial and parallel versions of the algorithm.

Parallel Layout Construction Algorithm for Irregular Shape Packing Problems

Cutting and packing problems arise in a variety of industries, including garment, wood and shipbuilding. Irregular shape packing is a special case which admits irregular items and is much more complex due to the geometry of items. In order to ensure that items do not overlap and no item from the layout protrudes from the container, the collision free region concept was adopted. It represents all possible translations for a new item to be inserted into a container with already placed items. To construct a feasible layout, collision free region for each item is determined through a sequence of Boolean operations over polygons. In order to improve the speed of the algorithm, a parallel version of the layout construction was proposed and it was applied to a simulated annealing algorithm used to solve bin packing problems. Tests were performed in order to determine the speed improvement of the parallel version over the serial algorithm