Packing different-sized circles into a rectangular container

Packing different-sized circles into a rectangular container

0.00 Avg rating0 Votes
Article ID: iaor19981889
Country: Netherlands
Volume: 84
Issue: 3
Start Page Number: 693
End Page Number: 712
Publication Date: Aug 1995
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics
Abstract:

This paper is motivated by the problem of fitting pipes of different diameters into a shipping container. Here we study the subproblem of fitting circles of different sizes into a rectangle since that problem is a central part of the larger problem. We formulate this situation as a nonlinear mixed integer programming problem and develop a number of heuristic procedures for (approximately) solving this problem. The heuristics are based on a variety of solution building rules that emulate the process of packing a container. Some of these methods, including a genetic algorithm, were based on a more structured design intended to provide solutions which are ‘stable’ from a stowage viewpoint. These heuristics are described in detail and their relative performances are compared for a sample set of 66 randomly generated problems. Based on this sample, the best performing heuristic methods were a quasi-random technique and a genetic algorithm of the ‘stable’ solution structure.

Reviews

Required fields are marked *. Your email address will not be published.