Optimizing Space Utilization In Container Packing: A Comparative Analysis of Packing Algorithms

Raghavendra Kamath

doi:10.57159/gadl.jcmm.2.3.23062

Authors

Raghavendra Kamath Department of Mechanical and Industrial Engineering, Manipal Institute of Technology, Manipal Academy of Higher Education, Manipal, Karnataka, India 576104

DOI:

https://doi.org/10.57159/gadl.jcmm.2.3.23062

Keywords:

Container Packing Problem, Optimization, Shelfing with Rotation, Shelfing with Search, Guillotine Algorithm

Abstract

Container packing presents a complex optimization problem that seeks to efficiently pack diverse items into a fixed-size container. This study provides a comparative analysis of four algorithms -- Greedy Shelf, Shelfing with Rotation, Shelfing with Search, and Guillotine Paper Cutting -- investigating their proficiency in solving the container packing problem. Utilizing a set of four packages with differing dimensions and IDs, The study evaluated the performance of each algorithm. The results demonstrated that the Shelfing with Search algorithm outperformed its counterparts by yielding a stack height of 3019610 L units. Conversely, the Guillotine Paper Cutting algorithm performed poorly, with a stack height of 7537295 units. This research also explored the impact of different sorting methods on packing efficiency, revealing that sorting packages in descending order of height yields superior results. Consequently, this study provides an extensive evaluation of the various algorithms used for container packing, while suggesting promising directions for future research to enhance packing efficiency.

References

G. Yaskov, T. Romanova, I. Litvinchev, and S. Shekhovtsov, “Optimal packing problems: from knapsack problem to open dimension problem,” in International Conference on Intelligent Computing & Optimization, pp. 671–678, Springer, 2019.

J.-L. Lin, C.-H. Chang, and J.-Y. Yang, “A study of optimal system for multiple-constraint multiple-container packing problems,” in International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, pp. 1200– 1210, Springer, 2006.

Y.-B. Shin and E. Kita, “Solving two-dimensional packing problem using particle swarm optimization,” Computer Assisted Methods in Engineering and Science, vol. 19, no. 3, pp. 241–255, 2017.

T. G. Crainic, G. Perboli, and R. Tadei, “Extreme point-based heuristics for three-dimensional bin packing,” Informs Journal on Computing, vol. 20, no. 3, pp. 368–384, 2008.

S. Erbayrak, V. O¨ zkır, and U. M. Yıldırım, “Multi-objective 3d bin packing problem with load balance and product family concerns,” Computers & Industrial Engineering, vol. 159, p. 107518, 2021.

H. Pa˚lsson, Packaging Logistics: Understanding and managing the economic and environmental impacts of packaging in supply chains. Kogan Page Publishers, 2018.

C. A. Vega-Mej´ıa, J. R. Montoya-Torres, and S. M. Islam, “Consideration of triple bottom line objectives for sustainability in the optimization of vehicle routing and loading operations: a systematic literature review,” Annals of Operations Research, vol. 273, pp. 311–375, 2019.

C. Bierwirth and F. Meisel, “A follow-up survey of berth allocation and quay crane scheduling problems in container terminals,”

European Journal of Operational Research, vol. 244, no. 3, pp. 675–689, 2015.

N. Tsolakis, D. Zissis, S. Papaefthimiou, and N. Korfiatis, “Towards ai driven environmental sustainability: an application of automated logistics in container port terminals,” International Journal of Production Research, vol. 60, no. 14, pp. 4508–4528, 2022.

E. Sdoukopoulos and M. Boile, “Port-hinterland concept evolution: A critical review,” Journal of Transport Geography, vol. 86, p. 102775, 2020.

S. Nurosidah, “The shift of containerization influence: 50-year logistics innovation in international business,” The Business & Management Review, vol. 8, no. 4, p. 93, 2017.

L. Kroon and G. Vrijens, “Returnable containers: an example of reverse logistics,” International Journal of Physical Distribution & Logistics Management, vol. 25, no. 2, pp. 56–68, 1995.

M. Hifi, R. M’hallah, et al., “A literature review on circle and sphere packing problems: Models and methodologies,” Advances in Operations Research, vol. 2009, 2009.

S. Kumaraswamy and M. K. Nair, “Bin packing algorithms for virtual machine placement in cloud computing: a review,”

International Journal of Electrical and Computer Engineering, vol. 9, no. 1, p. 512, 2019.

A. Lodi, S. Martello, M. Monaci, and D. Vigo, “Two-dimensional bin packing problems,” Paradigms of combinatorial optimization: Problems and new approaches, pp. 107–129, 2014.

A. Lodi, S. Martello, and D. Vigo, “Recent advances on two-dimensional bin packing problems,” Discrete Applied Mathematicsics, vol. 123, no. 1-3, pp. 379–396, 2002.

D. Pisinger, “Heuristics for the container loading problem,” European Journal of Operational Research, vol. 141, no. 2, pp. 382– 392, 2002.

S. Sweep, “Three-dimensional bin-packing issues and solutions,” 2003.

P. Ramanan, “Average-case analysis of the smart next fit algorithm,” Information processing letters, vol. 31, no. 5, pp. 221–225, 1989.

A. Lodi, S. Martello, and D. Vigo, “Heuristic and metaheuristic approach for a class of two-dimensional bin packing problems,” Informs Journal on Computing, vol. 11, no. 4, pp. 345–357, 1999.

A. Lodi, S. Martello, and D. Vigo, “Neighborhood search algorithm for the guillotine non-oriented two-dimensional bin packing problem,” Meta-heuristics: advances and trends in local search paradigms for optimization, pp. 125–139, 1999.

B. S. Baker and J. S. Schwarz, “Shelf algorithms for two-dimensional packing problems,” SIAM Journal on Computing, vol. 12, no. 3, pp. 508–525, 1983.

K. A. Dowsland, “Some experiments with simulated annealing techniques for packing problems,” European Journal of Operational Research, vol. 68, no. 3, pp. 389–399, 1993.