Open Access Open Access  Restricted Access Subscription or Fee Access

3D Arbitrary Sized Heterogeneous Bin Packing Using Hybrid Multi Constrained Optimization: Genetic Approach

N.K. Venkatraman, A. Srivas, S.K. Rajesh Kanna


This paper presents a combinational hybrid Genetic Algorithm (HGA) with packing tuning approach for solving Three Dimensional (3D) Single container arbitrary sized heterogeneous bin packing optimization problem by considering practical constraints in shipment container loading industries. Aim of this paper is to (i) pack 3D arbitrary sized heterogeneous bins in to a container. (ii) Improve packing by optimizing empty volume inside the container using genetic approach. (iii) obtain feasible packing pattern, various practical constraints like box orientation, stack priority, container stability, weight constraint, overlapping constraint, shipment placement constraint were also considered. (iv) Tuning algorithm used sequential packing without gap. 3D container loading problem consists of „n‟ number of boxes being to be packed in to a container of standard dimension in such a way to maximize volume utilization and inturn profit. Furthermore, Boxes to be packed are of various sizes and of heterogeneous shapes. In this research work, several heuristic GA operators were proposed to solve container loading problem that significantly improves search efficiency and to load most of heterogeneous boxes into a container along with optimal position of loaded boxes, box orientation with less computational time. Tuning algorithm was used to make the genetic output in to packing pattern in an understandable format and without empty space in less computational time. In general, combination of Hybrid GA conjunction with tuning algorithm being substantially better and satisfactory than those obtained by applying heuristics to the bin packing directly.


Hybrid Genetic Algorithm, Container Loading, Tuning Algorithm

Full Text:



D.E. Goldberg, “Genetic Algorithm in Search, Optimization and Machine Learning”, Addison Wesley, 1988.

M.Mitchell, “An Introduction to Genetic Algorithm”, MIT Press, 1996.

E.Hopper and B. Turton, “Application of Genetic Algorithm to Packing Problems – A Review”, Springer Verlag, London, pp 279 -288, 1997.

R. Korf, “A New Algorithm of Optimal Bin Packing”, In proc. AAAI, pages 731-736, 2002.

R. Korf, “A Improved Algorithm for Optimal Bin Packing”, In proc. IJCAI, pages 1252 – 1258, 2003.

D.Pisinger, “Heuristic for Container Loading Problem”, European Journal of Operation Research 141, 292 – 382, 2002.

H.Gehring, A. Bortfeldt, “A Genetic Algorithm for Solving the Container Loading Problem”, International transactions in Operation Research, 44, pages 401 – 418, 1997.

KA Dowsland, EA Herbet, “Using Tree Search Bounds To Enhance A Genetic Algorithm Approach Two Rectangle Packing Problems”, European Journal of Operation Research 168, 390-402, 2004.

S. Martello, D. Pisinger, “The Three Dimensional Bin Packing Problem”, Operation research 48, 256-267, 2000.

EE Bischoff, “Three Dimensional Packing of Items with Limited Load Bearing Strength”, European Journal of Operation Research 168, pages 952-966, 2004.

A. Bortfeldt and H. Gehring, “A Hybrid Genetic Algorithm for Container Loading Problem”, European Journal of Operation Research 131, page 143 -161, 2001.

SG. Christensen and D.M. Rousoe, “Container Loading with Multidrop Constraint”, masters thesis, Informatics and mathematical Modelling, Technical University of Denmark, DTU, Lyngby, 2007.

A.P. Davies and E.E. Bischoff, “Weight Distribution Considerations In Container Loading” European Journal of Operation Research 114, pages 509-527, 1999.

John A George and Jennifer M George, “Packing Different Sized Circles into a Rectangular Container”, European Journal of Operation Research 84, pages 693-712, 1995.

E.K. Burke, M.R. Hyde, “Evolving Bin Packing Heuristic with Genetic Programming”, School of computer science and information technology”, UK.

Dyckhoff H. A typology of cutting and packing problems. European Journal of Operation Research 1990; 44:145–59.



  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.