Improved Packing Representation Model for the Orthogonal Packing Problem

Abstract:

The multidimensional NP-hard orthogonal bin packing problem is considered in the article. Usually the problem is solved using heuristic algorithms of discrete optimization which optimize a selection sequence of objects to be packed in containers. The quality and speed of getting the resulting packing for a given sequence of placing objects is determined by the used packing representation model. In the article presented a new packing representation model for constructing the orthogonal packing. The proposed model of potential containers describes all residual free spaces of containers in packing. The developed model is investigated on well-known standard benchmarks of three-dimensional orthogonal bin packing problem. The model can be used in development of applied software for the optimal allocation of orthogonal resources.

• Periodical: Applied Mechanics and Materials (Volume 390)
• Pages: 591-595
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.390.591
• Online since: August 2013
• Authors: Alexander V. Chekanin, Vladislav A. Chekanin
• Keywords: Bin Packing Problem, Orthogonal Packing, Packing, Packing Problem, Packing Representation Model, Three-Dimensional Packing

References

[1] M. Gary, D. Johnson: Computers Intractability: a Guide to the Theory of NP-completeness (W.H. Freeman, San Francisco 1979).

[2] A. Lodi, S. Martello, M. Monaci: Two-dimensional packing problems: A survey. European journal of operational research. Vol. 141: 2 (2002), pp.241-252.

DOI: 10.1016/s0377-2217(02)00123-6

[3] Y. Wu, W-K. Li, M. Goh, R. de Souza: Three dimensional bin packing problem with variable bin height. European journal of operational research. Vol. 202: 2 (2010), pp.347-355.

DOI: 10.1016/j.ejor.2009.05.040

[4] G. Wascher, H. HauBner, H. Schumann: An improved typology of cutting and packing problems. European journal of operational research. Vol. 183: 3 (2007), pp.1109-1130.

DOI: 10.1016/j.ejor.2005.12.047

[5] V.A. Chekanin, A.V. Chekanin: Effective models of representations of orthogonal resources in solving the packing problem. Information and Control Systems (Informatsionno-Upravlyayushchiye systemy). Vol. 5 (2012), pp.29-32, in Russian.

[6] V.A. Chekanin: The effective solving of the two-dimensional packing task of rectangular objects. Jouranl of computer and information technology (Vestnik komp'yuternykh i informatsionnykh tekhnologiy). Vol. 6 (2011), pp.35-39, in Russian.

[7] V.A. Chekanin, A.V. Chekanin: Optimization of the solution of the orthogonal packing problem. Applied informatics (Prikladnaya informatika). Vol. 4 (2012), pp.55-62, in Russian.

[8] S. Martello, D. Pisinger, D. Vigo: The three-dimensional bin packing problem. Operations Research. Vol. 48: 2 (2000), pp.256-267.

DOI: 10.1287/opre.48.2.256.12386

[9] O. Faroe, D. Pisinger, M. Zachariasen: Guided local search for the three-dimensional bin packing problem. INFORMS, Journal on Computing. Vol. 15: 3 (2003), pp.267-283.

DOI: 10.1287/ijoc.15.3.267.16080

[10] T.G. Crainic, G. Perboli, R. Tadei: Extreme point-based heuristics for three-dimensional bin packing. INFORMS, Journal on Computing. Vol. 20: 3 (2008), pp.368-384.

DOI: 10.1287/ijoc.1070.0250

[11] A. Lodi, S. Martello, D. Vigo: Heuristic algorithms for the three-dimensional bin packing problem. European Journal of Operational Research. Vol. 141: 2 (2002), pp.410-420.

DOI: 10.1016/s0377-2217(02)00134-0

[12] M.A. Boschetti: New lower bounds for the finite three-dimensional bin packing problem. Discrete Applied Mathematics. Vol. 140 (2004), pp.241-258.

DOI: 10.1016/j.dam.2003.08.004