A Fit Degree Based Two-Step Lookahead Algorithm for Solving the Container Loading Problem

Abstract:

This paper presents a Fit Degree based Two-step Lookahead algorithm (FDTL) for the NP hard container loading problem. Several evaluation criteria, the fit degrees, are defined to construct different initial solutions as well as to explore different portions of the search space. Then a two-step lookahead tree search procedure is incorporated for the sufficient search such that the algorithm could find better layouts compared to a one-step lookahead tree search procedure. FDTL is tested on two sets of typical instances: 800 instances as proposed by Bischoff and Ratcliff (1995), and 15 instances as proposed by Loh and Nee (1992). Experiments show that this new algorithm improves among the known algorithms on the space utilization.

• Periodical: Applied Mechanics and Materials (Volumes 135-136)
• Pages: 30-36
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.135-136.30
• Online since: October 2011
• Authors: Kun He, Wen Qi Huang
• Keywords: Combinational Optimization, Container Loading, Heuristics, Logistic

References

[1] K. He, W. Q. Huang, A caving degree based flake arrangement approach for the container loading problem, Computers & Industrial Engineering, vol. 59(2), p.344–351, (2010).

DOI: 10.1016/j.cie.2010.05.007

[2] T. Fanslau, A. Bortfeldt, A tree search algorithm for solving the container loading problem, INFORMS Journal on Computing, vol. 22(2), p.222–235, (2010).

DOI: 10.1287/ijoc.1090.0338

[3] K. He, W. Q. Huang, An efficient placement heuristic for three-dimensional rectangular packing, Computers & Operations Research 38(1), p.227–233, (2011).

DOI: 10.1016/j.cor.2010.04.015

[4] W. Q. Huang, K. He, A caving degree approach for the single container loading problem, European Journal of Operational Research, vol. 196(7), p.93–101, (2009).

DOI: 10.1016/j.ejor.2008.02.024

[5] E. E. Bischoff, M. S. W. Ratcliff, Issues in the Development of Approaches to Container Loading, OMEGA – The International Journal of Management Science, vol. 23(4), p.377–390, (1995).

DOI: 10.1016/0305-0483(95)00015-g

[6] T. H. Loh, A. Y. C. Nee, A packing algorithm for hexahedral boxes, Proceedings of the Industrial Automation 92 Conference, p.115–126. Singapore: Industrial Automation Association, (1992).

[7] H. Gehring, A. Bortfeldt, A genetic algorithm for solving the container loading problem, International Transactions in Operational Research, vol. 4, p.401–418, (1997).

DOI: 10.1111/j.1475-3995.1997.tb00095.x

[8] A. Bortfeldt, H. Gehring, Applying tabu search to container loading problems, Operations Research Proceedings 1998, p.533–538. Zurich: Springer, (1998).

DOI: 10.1007/978-3-642-58891-4_84

[9] A. Bortfeldt, H. Gehring, A hybrid genetic algorithm for the container loading problem, European Journal of Operational Research, vol. 131, p.143–161, (2001).

DOI: 10.1016/s0377-2217(00)00055-2

[10] H. Gehring, A. Bortfeldt, A Parallel Genetic Algorithm for Solving the Container Loading Problem, International Transactions in Operational Research, vol. 9(4), p.497–511, (2002).

DOI: 10.1111/1475-3995.00369

[11] A. Bortfeldt, H. Gehring and D. Mack, A parallel tabu search algorithm for solving the container loading problem, Parallel Computing, vol. 29(5), p.641–662, (2003).

DOI: 10.1016/s0167-8191(03)00047-4

[12] D. Mack, A. Bortfeldt and H. Gehring, A parallel hybrid local search algorithm for the container loading problem, International Transactions in Operational Research, vol. 11(5), p.511–533, (2004).

DOI: 10.1111/j.1475-3995.2004.00474.x

[13] A. Lim, B. Rodrigues and Y. Yang, 3-D Container Packing Heuristics, Applied Intelligence, vol. 22(2), p.125–134, (2005).

DOI: 10.1007/s10489-005-5601-0

[14] A. Moura, J. F. Oliveira, A GRASP approach to the container-loading problem, IEEE Intelligent Systems, vol. 20(4), p.50–57, (2005).

DOI: 10.1109/mis.2005.57

[15] E. E. Bischoff, Three-dimensional packing of items with limited load bearing strength, European Journal of Operational Research, vol. 168, p.952–966, (2006).

DOI: 10.1016/j.ejor.2004.04.037

[16] F. Parreño, R. Alvarez-Valdes, J. M. Tamarit and J. F. Oliveira, A maximal-space algorithm for the container loading problem, INFORMS Journal on Computing, vol. 20(3), p.412–422, (2008).

DOI: 10.1287/ijoc.1070.0254

[17] F. Parreño, R. Alvarez-Valdes, J. F. Oliveira and J. M. Tamarit, Neighborhood structures for the container loading problem: a VNS implementation, Journal of Heuristics, vol. 16(1) , p.1–22, (2010).

DOI: 10.1007/s10732-008-9081-3

[18] J. Terno, G. Scheithauer, U. Sommerweiß and J. Riehme, An efficient approach for the multi-pallet loading problem, European Journal of Operational Research, vol. 123, p.372–381, (2000).

DOI: 10.1016/s0377-2217(99)00263-5

[19] M. Eley, Solving container loading problems by block arrangement, European Journal of Operational Research, vol. 141, p.393–409, (2002).

DOI: 10.1016/s0377-2217(02)00133-9

[20] Z. J. Wang, K. W. Li and J. K. Levy, A heuristic for the container loading problem: a tertiary-tree-based dynamic space decomposition approach, European Journal of Operational Research, vol. 191(1), p.86–99, (2008).

DOI: 10.1016/j.ejor.2007.08.017