Optimizing The Packing Of Cylinders Into A Rectangular Container: A Nonlinear Approach

The container loading problem has important industrial and commercial applications. An increase in the number of items in a container leads to a decrease in cost. For this reason the related optimization problem is of economic importance. In this work, a procedure based on a nonlinear decision problem to solve the cylinder packing problem with identical diameters is presented. This formulation is based on the fact that the centers of the cylinders have to be inside the rectangular box defined by the base of the container (a radius far from the frontier) and far from each other at least one diameter. With this basic premise the procedure tries to find the maximum number of cylinder centers that satisfy these restrictions. The continuous nature of the problem is one of the reasons that motivated this study. A comparative study with other methods of the literature is presented and better results are achieved. © 2003 Elsevier B.V. All rights reserved.16011933Birgin, E.G., Biloti, R., Tygel, M., Santos, L.T., Restricted optimization: A clue to a fast and accurate implementation of the common reflection surface stack method (1999) Journal of Applied Geophysics, 42, pp. 143-155Birgin, E.G., Chambouleyron, I., Martínez, J.M., Estimation of the optical constants and the thickness of thin films using unconstrained optimization (1999) Journal of Computational Physics, 151, pp. 862-880Birgin, E.G., Martínez, J.M., A box constrained optimization algorithm with negative curvature directions and spectral projected gradients (2001) Computing, 15 (SUPPL.), pp. 49-60Birgin, E.G., Martínez, J.M., Large-scale active-set box-constrained optimization method with spectral projected gradients (2002) Computational Optimization and Applications, 23, pp. 101-125Birgin, E.G., Martínez, J.M., Raydan, M., Nonmonotone spectral projected gradient methods on convex sets (2000) SIAM Journal on Optimization, 10, pp. 1196-1211Birgin, E.G., Martínez, J.M., Raydan, M., SPG: Software for convex-constrained optimization (2001) ACM Transactions on Mathematical Software, 27, pp. 340-349Correia, M.H., Oliveira, J.F., Ferreira, J.S., Cylinder packing by simulated annealing (2000) Pesquisa Operacional, 20, pp. 269-284Correia, M.H., Oliveira, J.F., Ferreira, J.S., A new upper bound for the cylinder packing problem (2001) International Transactions in Operational Research, 8, pp. 571-583Dennis Jr., J.E., Schnabel, R.B., (1983) Numerical Methods for Unconstrained Optimization and Nonlinear Equations, , Englewoods Cliffs, NJ: Prentice-HallDowsland, K.A., Optimising the palletisation of cylinders in cases (1991) OR Spectrum, 13, pp. 204-212Isermann, H., Heuristiken zur Lösung des zweidimensionalen Packproblem für Rundgefäße (1991) OR Spectrum, 54, pp. 213-223Fraser, H.J., George, J.A., Integrated container loading software for pulp and paper industry (1994) European Journal of Operational Research, 77, pp. 466-474Friedman, E., http://www.stetson.edu/~efriedma/packing.htmlGeorge, J.A., George, J.M., Lamar, B.W., Packing different-sized circles into a rectangular container (1995) European Journal of Operational Research, 84, pp. 693-712Graham, R.L., Lubachevsky, B.D., Nurmela, K.J., Östergard, P.R.J., Dense packing of congruent circles in a circle (1998) Discrete Mathematics, 181, pp. 139-154Luenberger, D.G., (1984) Linear and Nonlinear Programming, , Reading, MA: Addison-WesleyPeikert, R., http://www.cg.inf.ethz.ch/~peikert/personal/CirclePackings/Schrage, L., A more portable Fortran random number generator (1979) ACM Transactions on Mathematical Software, 5, pp. 132-138Szabó, P.G., http://www.inf.u-szeged.hu/~pszabo/Pack.htm