Annealing, Cylinder Packing By Simulated. (English) Zbl 1181.90231
Summary: This paper is motivated by the problem of loading identical items of circular base (tubes, rolls,…) into a rectangular base (the pallet). For practical reasons, all the loaded items are considered to have the same height. The resolution of this problem consists in determining the positioning pattern of the circular bases of the items on the rectangular pallet, while maximizing the number of items. This pattern will be repeated for each layer stacked on the pallet. Two algorithms based on the meta-heuristic Simulated Annealing have been developed and implemented. The tuning of these algorithms parameters implied running intensive tests in order to improve its efficiency. The algorithms developed were easily extended to the case of non-identical circles.
MSC:
| 90C27 | Combinatorial optimization |
References:
| [1] | Correia M., A new upper bound for the cylinder packing problem (2000) |
| [2] | Dowsland K.A., Optimising the palletisation of cylinders in cases, OR Spektrum 13 pp 204– (1991) · Zbl 0729.90912 · doi:10.1007/BF01719396 |
| [3] | Fraser H., Integrated container loading software for pulp and paper industry, European Journal of Operational Research 77 pp 466– (1994) · Zbl 0800.90656 · doi:10.1016/0377-2217(94)90410-3 |
| [4] | Garey M., Computers and Intractability: A guide to the theory of NP-completeness (1979) · Zbl 0411.68039 |
| [5] | George J., Packing different sized circles into a rectangular container, European Journal of Operational Research 84 pp 693– (1995) · Zbl 0928.90077 · doi:10.1016/0377-2217(95)00032-L |
| [6] | Goldberg M., The packing of equal circles in a square, Mathematics Magazine pp 24– (1970) · Zbl 0188.55004 · doi:10.2307/2688107 |
| [7] | Hifi M., Circular cutting problem: A simulated annealing approach. Technical report 94.15 (1994) |
| [8] | Isermann H., Heuristiken zur Lösung des zweidimensionalen Packproblems für Rundgefäb e, OR Spektrum 13 pp 213– (1991) · Zbl 0739.90012 · doi:10.1007/BF01719397 |
| [9] | Maranas C.D., New results in the packing of equal circles in a square, Discrete Mathematics 142 pp 287– (1995) · Zbl 0835.52016 · doi:10.1016/0012-365X(93)E0230-2 |
| [10] | Pirlot M., General local search heuristics in combinatorial optimization: a tutorial, Belgium Journal of Operations Research, Statistics and Computer Science 32 pp 7– (1992) · Zbl 0768.90062 |
| [11] | Reeves C., Modern Heuristic Techniques for Combinatorial Problems: Advanced Topics in Computer Science (1995) |
| [12] | Stoyan Y.G., Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints, International Transactions in Operational Research 5 pp 45– (1998) · Zbl 0910.90240 · doi:10.1111/j.1475-3995.1998.tb00101.x |
| [13] | Vidal R., Applied Simulated Annealing: Lecture Notes in Economics and Mathematical Systems (1993) · Zbl 0789.90064 |
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.
