Abstract
This paper studies the three dimensional strip packing problem (3DSPP) with practical constraints. The objective is to pack a set of three-dimensional items into a three-dimensional container with one open dimension such that the used length of the open dimension is minimized. Several practical constraints, including the orientation, support, multiple-drop, moving and maximum length overlap, are considered. An open space heuristic is proposed to decode a given sequence of items into a feasible solution, and a random local search is used to improve the solution. Computational experiments on 30 practical instances are used to test the performance of our approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Allen, S.D., Burke, E.K.E., Kendall, G.: A hybrid placement strategy for the three-dimensional strip packing problem. Eur. J. Oper. Res. 209(3), 219–227 (2011)
Bortfeldt, A., Gehring, H.: Two metaheuristics for strip packing problems. In: Proceedings band der 5th International Conference of the Decision Sciences Institute, 141(2), pp. 1153–1156 (1999)
Bortfeldt, A., Gehring, H.: A hybrid genetic algorithm for the container loading problem. Eur. J. Oper. Res. 131(1), 143–161 (2001)
Bortfeldt, A., Mack, D.: A heuristic for the three-dimensional strip packing problem. Eur. J. Oper. Res. 183(3), 1267–1279 (2007)
Parreño, F., Alvarez-Valdes, R., Oliveira, J.F., Tamarit, J.M.: Neighborhood structures for the container loading problem: a VNS implementation. J. Heuristics 16(1), 1–22 (2010)
Parreño, F., Alvarez-Valdes, R., Tamarit, J.M., Oliveira, J.F.: A maximal-space algorithm for the container loading problem. INFORMS J. Comput. 20(3), 412–422 (2008)
Pisinger, D.: Heuristics for the container loading problem. Eur. J. Oper. Res. 141(2), 382–392 (2002)
Wei, L., Oon, W.-C., Zhu, W., Lim, A.: A reference length approach for the 3D strip packing problem. Eur. J. Oper. Res. 220(1), 37–47 (2012)
Wei, L., Wang, Y., Cheng, H., Huang, J.: An open space based heuristic for the 2D strip packing problem with unloading constraints. Appl. Math. Model. 70, 67–81 (2019)
Zhang, Z., Wei, L., Lim, A.: An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints. Transp. Res. Part B Methodological 82, 20–35 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Liu, Q., Lin, D., Zhang, H., Wei, L. (2020). A Heuristic Approach to the Three Dimensional Strip Packing Problem Considering Practical Constraints. In: Fujita, H., Fournier-Viger, P., Ali, M., Sasaki, J. (eds) Trends in Artificial Intelligence Theory and Applications. Artificial Intelligence Practices. IEA/AIE 2020. Lecture Notes in Computer Science(), vol 12144. Springer, Cham. https://doi.org/10.1007/978-3-030-55789-8_23
Download citation
DOI: https://doi.org/10.1007/978-3-030-55789-8_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-55788-1
Online ISBN: 978-3-030-55789-8
eBook Packages: Computer ScienceComputer Science (R0)