CISUC

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 that
arises 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.