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 applicationSubject
Operations ResearchJournal
Computers and Operations Research, Vol. 37, #11, pp. 1968-1976, Elsevier, November 2010Cited 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.