×

Optimizing the packing of cylinders into a rectangular container: A nonlinear approach. (English) Zbl 1067.90133

Summary: 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 from the literature is presented and better results are achieved.

MSC:

90C27 Combinatorial optimization
90C25 Convex programming

Software:

SPG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Birgin, 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, Journal of Applied Geophysics, 42, 143-155 (1999)
[2] Birgin, E. G.; Chambouleyron, I.; Martı́nez, J. M., Estimation of the optical constants and the thickness of thin films using unconstrained optimization, Journal of Computational Physics, 151, 862-880 (1999) · Zbl 1017.74501
[3] Birgin, E. G.; Martı́nez, J. M., A box constrained optimization algorithm with negative curvature directions and spectral projected gradients, Computing, 15, Suppl., 49-60 (2001) · Zbl 1002.65067
[4] Birgin, E. G.; Martı́nez, J. M., Large-scale active-set box-constrained optimization method with spectral projected gradients, Computational Optimization and Applications, 23, 101-125 (2002) · Zbl 1031.90012
[5] Birgin, E. G.; Martı́nez, J. M.; Raydan, M., Nonmonotone spectral projected gradient methods on convex sets, SIAM Journal on Optimization, 10, 1196-1211 (2000) · Zbl 1047.90077
[6] Birgin, E. G.; Martı́nez, J. M.; Raydan, M., SPG: Software for convex-constrained optimization, ACM Transactions on Mathematical Software, 27, 340-349 (2001) · Zbl 1070.65547
[7] Correia, M. H.; Oliveira, J. F.; Ferreira, J. S., Cylinder packing by simulated annealing, Pesquisa Operacional, 20, 269-284 (2000) · Zbl 1181.90231
[8] Correia, M. H.; Oliveira, J. F.; Ferreira, J. S., A new upper bound for the cylinder packing problem, International Transactions in Operational Research, 8, 571-583 (2001) · Zbl 0992.90056
[9] Dennis, J. E.; Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1983), Prentice-Hall: Prentice-Hall Englewoods Cliffs, NJ · Zbl 0579.65058
[10] Dowsland, K. A., Optimising the palletisation of cylinders in cases, OR Spectrum, 13, 204-212 (1991) · Zbl 0729.90912
[11] Isermann, H., Heuristiken zur Lösung des zweidimensionalen Packproblem für Rundgefäße, OR Spectrum, 54, 213-223 (1991) · Zbl 0739.90012
[12] Fraser, H. J.; George, J. A., Integrated container loading software for pulp and paper industry, European Journal of Operational Research, 77, 466-474 (1994) · Zbl 0800.90656
[13] E. Friedman, http://www.stetson.edu/ efriedma/packing.html; E. Friedman, http://www.stetson.edu/ efriedma/packing.html
[14] George, J. A.; George, J. M.; Lamar, B. W., Packing different-sized circles into a rectangular container, European Journal of Operational Research, 84, 693-712 (1995) · Zbl 0928.90077
[15] Graham, R. L.; Lubachevsky, B. D.; Nurmela, K. J.; Östergard, P. R.J., Dense packing of congruent circles in a circle, Discrete Mathematics, 181, 139-154 (1998) · Zbl 0901.52017
[16] Luenberger, D. G., Linear and Nonlinear Programming (1984), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0241.90052
[17] R. Peikert, http://www.cg.inf.ethz.ch/ peikert/personal/CirclePackings/; R. Peikert, http://www.cg.inf.ethz.ch/ peikert/personal/CirclePackings/
[18] Schrage, L., A more portable Fortran random number generator, ACM Transactions on Mathematical Software, 5, 132-138 (1979) · Zbl 0403.68041
[19] P.G. Szabó, http://www.inf.u-szeged.hu/ pszabo/Pack.html; P.G. Szabó, http://www.inf.u-szeged.hu/ pszabo/Pack.html
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.