3D-Multi Constrained Heterogeneous Packing Using Genetic Approach

Abstract:

This paper presents a combination of Genetic Algorithm (GA) and Tuning algorithm, for optimizing Three Dimensional (3D) arbitrary sized heterogeneous box packing into a container, by considering practical constraints facing in the logistics industries. Objective of this research is to pack four different shapes of boxes of varying sizes into a container of standard dimension, without violating various practical constraints. Inorder to obtain a real time feasible packing pattern, Genetic Algorithm is developed to maximize the container volume utilization and inturn profit [9]. It significantly improves the search efficiency with less computational time and loads most of the heterogeneous boxes into the container by considering its optimal position and orientation. Tuning algorithm is used to decode the genetic output into user understandable sequential packing pattern and to fill the left-out empty space inside the container. In general, GA in conjunction with the tuning algorithm is substantially better than those obtained by applying heuristics to the bin packing directly.

• Periodical: Advanced Materials Research (Volumes 479-481)
• Pages: 1825-1830
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.479-481.1825
• Online since: February 2012
• Authors: Rajesh Kanna, P. Malliga, K. Sarukesi
• Keywords: Container Loading, Genetic Algorithm (GA), Logistic, Tuning Algortihm

References

[1] D.E. Goldberg, "Genetic Algorithm in Search, Optimization and Machine Learning", Addison Wesley, (1998).

[2] E.Hopper and B. Turton, "Application of Genetic Algorithm to Packing Problems – A Review", Springer Verlag, London, (1997), 279 -288.

[3] KA Dowsland, EA Herbet, "Using Tree Search Bounds To Enhance A Genetic Algorithm Approach Two Rectangle Packing Problems", European Journal of Operation Research, (2006), 168, 390-402.

DOI: 10.1016/j.ejor.2004.04.030

[4] R. E. Korf, "An Improved Algorithm for Optimal Bin Packing", International procding IJCAI, (2003 ), 1252 – 1258.

[5] D.Pisinger, "Heuristic for Container Loading Problem", European Journal of Operation Research 141, (2002). 292 – 382.

[6] H.Gehring, A. Bortfeldt, "A Genetic Algorithm for Solving the Container Loading Problem", International transactions in Operation Research, 44, (1997), 401 – 418.

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

[7] S. Martello, D. Pisinger,"The Three Dimensional Bin Packing Problem", European Journal of Operation research 48, (2000), 256-267.

DOI: 10.1287/opre.48.2.256.12386

[8] EE Bischoff, "Three Dimensional Packing of Items with Limited Load Bearing Strength", European Journal of Operation Research 168, (2004), 952-966.

DOI: 10.1016/j.ejor.2004.04.037

[9] A. Bortfeldt and H. Gehring, "A Hybrid Genetic Algorithm for Container Loading Problem", European Journal of Operation Research 131, (2001), 143 -161.

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

[10] SG. Christensen and D.M. Rousoe, "Container Loading with Multidrop Constraint", masters thesis, Informatics and mathematical Modelling, Technical University of Denmark, DTU, Lyngby, http://www2.imm.dtu.dk/pubdb/p.php?5225, (2007).

DOI: 10.13052/jsame2245-4551.2018003

[11] A.P. Davies and E.E. Bischoff,"Weight Distribution Considerations In Container Loading" European Journal of Operation Research 114, (1999), 509-527.

DOI: 10.1016/s0377-2217(98)00139-8

[12] John A George and Jennifer M George,"Packing Different Sized Circles into a Rectangular Container", European Journal of Operation Research 84, (1995), 693-712.

DOI: 10.1016/0377-2217(95)00032-l

[13] E.K. Burke, M.R. Hyde, "Evolving Bin Packing Heuristic with Genetic Programming", School of computer science and information technology", UK. http://cs.nott.ac.uk/~mvh.