Skip to main content
No Access

A reactive GRASP algorithm for the container loading problem with load-bearing constraints

Published Online:pp 669-694https://doi.org/10.1504/EJIE.2014.065734

The container loading problem consists in packing a set of boxes of different dimensions into a large container of fixed dimensions, usually with the objective of maximising the container load. In practical problems, besides the geometric constraints of not exceeding the container dimensions and ensuring the non-overlapping of boxes, other requirements may appear, such as total weight, weight balance or support. In this paper we address the problem of maximising container volume utilisation while respecting a set of practical constraints: full support of boxes, allowed orientations and load-bearing capacity. We have developed different heuristics for solving the problem and we have combined them into a GRASP algorithm. The algorithm is composed of a constructive phase with a reactive method for selecting the heuristics which are best for each instance, and an improving phase in which several improvement methods are applied. An extensive computational study shows the efficiency of the proposed procedure.

Keywords

container loading, packing, load-bearing strength, GRASP

References

  • 1. E.E. Bischoff, M.S.W. Ratcliff, '‘Issues in the development of approaches to container loading’' Omega (1995) Google Scholar
  • 2. E.E. Bischoff, '‘Three dimensional packing of items with load bearing strength’' European Journal of Operational Research (2006) Google Scholar
  • 3. A. Bortfeldt, H. Gehring, '‘A hybrid genetic algorithm for the container loading problem’' European Journal of Operational Research (2001) Google Scholar
  • 4. A. Bortfeldt, H. Gehring, D. Mack, '‘A parallel tabu search algorithm for solving the container loading problem’' Parallel Computing (2003) Google Scholar
  • 5. S.A. Canuto, M.G.C. Resende, C.C. Ribeiro, '‘Local search with perturbations for the prize-collecting Steiner tree problem in graphs’' Networks (2001) Google Scholar
  • 6. S. Ceschia, A. Schaerf, '‘Local search for a multi-drop multi-container loading problem’' Journal of Heuristics (2013) Google Scholar
  • 7. S.G. Christensen, D.M. Rousoe, '‘Container loading with multi-drop constraints’' International Transactions in Operational Research (2009) Google Scholar
  • 8. I.T. Christou, S. Vassilaras, '‘A parallel hybrid greedy branch and bound scheme for the maximum distance 2-matching problem’' Computers and Operations Research (2013) Google Scholar
  • 9. A.P. Davies, Approaches to the Container Loading Problem (2000) Google Scholar
  • 10. O.C.B. De Ara´ujo, V.A. Armentano, '‘A multi-start random constructive heuristic for the container loading problem’' Pesquisa Operational (2007) Google Scholar
  • 11. X. Delorme, X. Gandibleux, J. Rodriguez, '‘GRASP for set packing problems’' European Journal of Operational Research (2003) Google Scholar
  • 12. M. Eley, '‘Solving container loading problems by block arrangements’' European Journal of Operational Research (2002) Google Scholar
  • 13. T. Fanslau, A. Bortfeldt, '‘A tree search algorithm for solving the container loading problem’' INFORMS Journal on Computing (2010) Google Scholar
  • 14. S.P. Fekete, J. Schepers, J.C. Van der Veen, '‘An exact algorithm for higher-dimensional orthogonal packing’' Operations Research (2007) Google Scholar
  • 15. T.A. Feo, M.G.C. Resende, '‘Greedy randomized adaptive search procedures’' Journal of Global Optimization (2010) Google Scholar
  • 16. H. Gehring, A. Bortfeldt, '‘A genetic algorithm for solving the container loading problem’' International Transactions in Operational Research (2002) Google Scholar
  • 17. H. Gehring, A. Bortfeldt, '‘A parallel genetic algorithm for solving the container loading problem’' International Transactions in Operational Research (2002) Google Scholar
  • 18. J.A. George, D.F. Robinson, '‘A heuristic for packing boxes into a container’' Computers and Operations Research (1980) Google Scholar
  • 19. P.C. Gilmore, R.E. Gomory, '‘Multistage cutting stock problems of two and more dimensions’' Operations Research (1965) Google Scholar
  • 20. J. Hemminki, '‘Container loading with variable strategies in each layer’' (1994) Google Scholar
  • 21. M. Hifi, '‘Approximate algorithms for the container loading problem’' International Transactions in Operational Research (2002) Google Scholar
  • 22. Z. Jin, K. Ohno, J. Du, '‘An efficient approach for the three-dimensional container packing problem with practical constraints’' Asia-Pacific Journal of Operational Research (2007) Google Scholar
  • 23. L. Junqueira, R. Morabito, D.S. Yamashita, '‘Three-dimensional container loading models with cargo stability and load bearing constraints’' Computers and Operations Research (2012) Google Scholar
  • 24. S.C.H. Leung, D. Zhang, C. Zhou, T. Wu, '‘A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem’' Computers and Operations Research (2012) Google Scholar
  • 25. A. Lim, H. Ma, C. Qiu, W. Zhu, '‘The single container loading problem with axle weight constraints’' International Journal of Production Economics (2013) Google Scholar
  • 26. D. Mack, A. Bortfeldt, H. Gehring, '‘A parallel hybrid local search algorithm for the container loading problem’' International Transactions in Operational Research (2004) Google Scholar
  • 27. O.C. Makarem, R.A. Haraty, '‘Smart container loading’' Journal of Computational Methods in Science and Engineering (2010) Google Scholar
  • 28. S. Martello, D. Pisinger, D. Vigo, '‘The three-dimensional bin packing problem’' Operations Research (2000) Google Scholar
  • 29. R. Marti, J.M. Moreno Vega, '‘Metodos multiarranque’' Inteligencia Artificial (2003) Google Scholar
  • 30. R. Morabito, M. Arenales, '‘An AND/OR-graph approach to the container loading problem’' International Transactions in Operational Research (1994) Google Scholar
  • 31. A. Moura, J.F. Oliveira, '‘A GRASP approach to the container loading problem’' IEEE Intelligent Systems (2005) Google Scholar
  • 32. J.A. Nelder, R. Mead, '‘A simplex method for function minimization’' Computer Journal (1965) Google Scholar
  • 33. B.K.A. Ngoi, M.L. Tay, E.S. Chua, '‘Applying spatial representation techniques to the container packing problem’' International Journal of Production Research (1994) Google Scholar
  • 34. C. Park, J. Seo, '‘A GRASP approach to transporter scheduling for ship assembly block operations management’' European Journal of Industrial Engineering (2013) Google Scholar
  • 35. F. Parreño, R. Alvarez-Valdes, J.F. Oliveira, J.M. Tamarit, '‘A maximal-space algorithm for the container loading problem’' INFORMS Journal on Computing (2008) Google Scholar
  • 36. F. Parreño, R. Alvarez-Valdes, J.F. Oliveira, J.M. Tamarit, '‘A hybrid GRASP/VND algorithm for two-and three-dimensional bin packing’' Annals of Operations Research (2010) Google Scholar
  • 37. D. Pisinger, '‘Heuristics for the container loading problem’' European Journal of Operational Research (2002) Google Scholar
  • 38. M. Prais, C.C. Ribeiro, '‘Reactive GRASP: an application to a matrix decomposition problem in TDMA traffic assignment’' INFORMS Journal on Computing (2000) Google Scholar
  • 39. M.S.W. Ratcliff, E.E. Bischoff, '‘Allowing for weight considerations in container loading’' OR Spectrum (1998) Google Scholar
  • 40. J. Ren, Y. Tian, T. Sarawagi, '‘A tree search method for the container loading problem with shipment priority’' European Journal of Operational Research (2011) Google Scholar
  • 41. M.G.C. Resende, R.F. Werneck, '‘A hybrid heuristic for the p-median problem’' Journal of Heuristics (2004) Google Scholar
  • 42. C.C. Ribeiro, E. Uchoa, R.F. Werneck, '‘A hybrid GRASP with perturbations for the Steiner problem in graphs’' INFORMS Journal on Computing (2001) Google Scholar
  • 43. G. Scheithauer, '‘Algorithm for the container loading problem’' Operational Research Proceedings 1991 (1992) Google Scholar
  • 44. C-H. Tang, '‘A scenario decomposition-genetic algorithm method for solving stochastic air cargo container loading problems’' Transportation Research Part E (1992) Google Scholar
  • 45. J. Terno, G. Scheithauer, U. Sommerweis, J. Rieme, '‘An efficient approach for the multi-pallet loading problem’' European Journal of Operational Research (2000) Google Scholar
  • 46. G. W¨ascher, H. Haussner, H. Schumann, '‘An improved typology of cutting and packing problems’' European Journal of Operational Research (2007) Google Scholar
  • 47. S. Yan, Y.L. Shih, F.Y. Shiao, '‘Optimal cargo container loading plans under stochastic demands for air express carriers’' Transportation Research Part E (2008) Google Scholar