# A particular approach for the 3-Dimensional Packing Problem with additional Constraints

### Authors

### Abstract

This paper focus a restrained concretization of the general NP-hard Container Loading Problem thatarises from a real world application. This particular problem can be informally described as: given

dierent sets of bins and boxes, nd the packing of the boxes into the smallest number of bins obeying

some additional restrictions on the placement. The mathematical programming formulation that appears

to better model this application is the Three-dimensional Bin{Packing Problem (3D{BPP) which is no

more that an extension of the classic Bin{Packing Problem to the orthogonal packing of solid objects.

An alternate non-linear formulation for the 3D{BPP problem version as well as the numerical results of

new designed heuristic algorithms (CPBOX and BOXCP) for the approximation of the optimal solution

using boxes and bins of heterogeneous dimensions. Moreover, we also present a heuristic specically

designed to work under very particular storage application restrictions. The numerical results indicate

that all of these new heuristics have good performance standards specially when applied to replications

of real input data.

### Keywords

Three-dimensional Packing, multi-criteria optimization, heuristic algorithms, real problem application### Subject

Operations Research### Journal

Computers and Operations Research, Vol. 37, #11, pp. 1968-1976, Elsevier, November 2010### Cited by

#### Year 2017 : 1 citations

Li, T.-H.S, Liu, C.-Y., Kuo, P.-H., Fang, N.-C., Li, C.-H., Cheng, C.-W., Hsieh, C.-Y., Wu, L.-F., Liang, J.-J., Chen, C.-Y. A Three-Dimensional Adaptive PSO-Based Packing Algorithm for an IoT-Based Automated e-Fulfillment Packaging System. IEEE ACCESS, Volume 5, pp 9188-9205, 2017

#### Year 2016 : 5 citations

Ran Wang , Trung Thanh Nguyen, Shayan Kavakeb, Zaili Yang, Changhe Li, "Benchmarking Dynamic Three-Dimensional Bin Packing Problems Using Discrete-Event Simulation", Applications of Evolutionary Computation, Lecture Notes in Computer Science, Vol. 9598, pp 266-279, 2016

Zhao, X., Bennell, J.A., Bekta?, T., Dowsland, K., "A comparative review of 3D container loading algorithms", International Transactions in Operational Research, 23 (1-2), pp. 287-320.

Wang, R., Nguyen, T.T., Kavakeb, S., Yang, Z., Li, C. , "Benchmarking dynamic three-dimensional bin packing problems using discrete-event simulation", LNCS - Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics,

9598, pp. 266-279.

Huang, Y.-H., Hwang, F.J., Lu, H.-C., "An effective placement method for the single container loading problem", Computers and Industrial Engineering 97, pp. 212-221.

Paquay, Célia, Michael Schyns, and Sabine Limbourg. "A mixed integer programming formulation for the three?dimensional bin packing problem deriving from an air cargo application." International Transactions in Operational Research 23.1-2 (2016): 187-213.

#### Year 2015 : 3 citations

Ahire, Sanjay L.; Malhotra, Manoj K.; Jensen, John B.Carton-mix optimization for Walmart.com distribution centers. Interfaces 45 (4), pp. 341-357 JUL-AUG 2015

Li, X., Zhang, K. A hybrid differential evolution algorithm for multiple container loading problem with heterogeneous containers 2015 Computers and Industrial Engineering 90, pp. 305-313

Tsai, J.-F., Wang, P.-C., Lin, M.-H. A global optimization approach for solving three-dimensional open dimension rectangular packing problems 2015 Optimization 64 (12), pp. 2601-2618

#### Year 2014 : 3 citations

C. M. Schenekemberg; D. V. Kurpe; C. T. Scarpin. MODELO DE PROGRAMAÇÃO LINEAR INTEIRA PARA O PROBLEMA DE CARREGAMENTO DE MÚLTIPLOS CONTÊINERES COM RESTRIÇÕES DE CARREGAMENTO COMPLETO DE GRUPO DE ITENS E DE ESTABILIDADE VERTICAL. CNMAI - Congresso Nacional de Matemática Aplicada à Indústria,18-21 novembro 2014, Caldas Novas, G0, Brazil

Zhao, X., Bennell, J. A., Bektas, T., Dowsland, K. "A comparative review of 3D container loading algorithms", International Transactions in Operational Research, Vol. 23, Issue 1-2 (2016), pp. 287–320.

Paquay, C. and Schyns, M. and Limbourg, S., "A mixed integer programming formulation for the three-dimensional bin packing problem deriving from an air cargo application", International Transactions in Operational Research, Vo. 23, Issue 1-2

(2016), pp. 187–213, DOI:10.1111/itor.12111 (Published online: 30 July 2014).

#### Year 2013 : 4 citations

Tlili, T.; Faiz, S.; Krichen, S.; "A particle swarm optimization for solving the one dimensional container loading problem," Proc. of Intl. Conf. on Modeling, Simulation and Applied Optimization (ICMSAO), pp.1,4, 2013

Bortfeldt, A.; Wäscher, G.; "Constraints in container loading – A state-of-the-art review", European Journal of Operational Research, Vol. 229, Issue 1, pp 1-20, 2013

Lacomme, P.; Toussaint, H.; Duhamel, C. ``A GRASP×ELS for the vehicle routing problem with basic three-dimensional loading constraints'', Engineering Applications of Artificial Intelligence, Available online 24 May 2013,

Ceschia, Sara. Local search algorithms for integrated logistics. AI Communications, 2013, 26.3: 325-326.

#### Year 2012 : 3 citations

Hu, N.-Z.; Li, H.-L.; Tsai, J.-F.; ``Solving Packing Problems by a Distributed Global Optimization Algorithm,'' Mathematical Problems in Engineering, vol. 2012, Article ID 931092, 2012.

Wang-sheng, L.; Hua-yi, Y.; Mao-qing, L. ``The Heuristic Algorithm of Stacking Layer for the Three-Dimensional Packing of Fixed-Size Cargoes'', Green Communications and Networks, Lecture Notes in Electrical Engineering, 113: 453-460, 2012

Wang-sheng, L.; Hua-yi, Y.; Mao-qing, L. ``The Heuristic Algorithm of Stacking Layer for the Three-Dimensional Packing of Fixed-Size Cargoes'', Computer, Informatics, Cybernetics and Applications, Lecture Notes in Electrical Engineering, 107: 605-612, 2012

Sara Ceschia, "Local Search Algorithms for Integrated Logistics", PhD Thesis in Research in Industrial and Information Engineering, Dipartimento di Ingegneria Elettrica, Gestionale e Meccanica, Universita degli Studi di Udine, Italia, 2012

#### Year 2011 : 2 citations

Wu, K.; Liu, L.; Liu, J.; Li, W.; Xie, G.; Tong, X.; Lin, Y. ``Researches on Grid Security Authentication Algorithm in Cloud Computing'', Journal of Networks, Vol 6, No 11 (2011), 1639–1646, 2011.

Duhamel,C.; Lacomme, P.; Toussaint, H. ”A GRASPxELS for the vehicle routing problem with three-dimensional loading constraints”, Research Report LIMOS / RR-11-01, 2011.

#### Year 2009 : 1 citations

Armentano, V.; de Araújo,O. ; ``Carregamento de contêiner com restrições de múltiplos destinos'', XLII SBPO, Brasil, 2009.