A Heuristic Algorithm for the Container Loading Problem with Heterogeneous Boxes

The container loading problem (CLP) is notoriously known to be NP-hard, an intrinsically difficult problem that is too complex to be solved in polynomial time on a system of serial computers. Heuristic algorithms are often the only viable option to tackle this type of combinatorial optimization problems. This article puts forward a heuristic algorithm based on a tertiary tree model to handle the CLP with heterogeneous rectangular boxes. A dynamic spatial decomposition method is employed to partition the unfilled container space after a group of homogeneous boxes is loaded into the container. This decomposition approach, together with an optimal-fitting sequencing rule and an inner-left-corner-occupying placement rule, permits a holistic filling strategy to pack a container. A comparative study with existing algorithms and an illustrative example demonstrate the efficiency of this heuristic algorithm.