The problems examined originate from industrial projects. In one project, our team was contracted by a buying agent for a large multi-national retailer to investigate better ways to formulate packing plans for the loading of goods into multiple containers. Typically, the goods come in the form of 3D rectangular carton boxes, which are to be loaded into 3D rectangular containers of various standard sizes. Each type of container has a different associated cost of shipping. The task is to select a set of containers that can contain all items while minimizing this shipping cost. We call this problem the Multiple Container Loading Cost Minimization Problem (MCLCMP)....[ Read more ]

The problems examined originate from industrial projects. In one project, our team was contracted by a buying agent for a large multi-national retailer to investigate better ways to formulate packing plans for the loading of goods into multiple containers. Typically, the goods come in the form of 3D rectangular carton boxes, which are to be loaded into 3D rectangular containers of various standard sizes. Each type of container has a different associated cost of shipping. The task is to select a set of containers that can contain all items while minimizing this shipping cost. We call this problem the Multiple Container Loading Cost Minimization Problem (MCLCMP).

If a set of boxes can be loaded into a container, we call the set of boxes and the associated container a loading pattern. MCLCMP can be naturally formulated as a set cover problem, where the set to be covered is the set of all boxes and a loading pattern "covers" a subset of boxes. We would like to select loading patterns from a set of candidates to cover all boxes while minimizing the total cost of the associated containers. Our approaches to the MCLCMP are essentially two-level approaches. The burden of finding feasible loading patterns is left to the algorithms for the Single Container Loading Problem (SCLP).

We first develop efficient algorithms for the SCLP, and then proceed to devise three set cover based algorithms for the MCLCMP in increasing order of sophistication and effectiveness. The special case of the MCLCMP where all containers are identical is the well-known 3D bin packing problem (3D-BPP); we propose a new algorithm that exploits specific features of the 3D-BPP. Computational experiments on benchmark data suggest that our new algorithms for the SCLP, MCLCMP and 3D-BPP outperform all prior approaches.