Heuristics for container loading of furniture

We consider a container loading problem that occurs at a typical furniture manufacturer. Each furniture item has an associated profit. Given container dimensions and a set of furniture items, the problem is to determine a subset of items with maximal profit sum that is loadable in the container. In the studied company, the problem arises hundreds of times daily during transport planning. Instances may contain more than one hundred different items with irregular shapes. To solve this complex problem we apply a set of heuristics successively that each solve one part of the problem. Large items are combined in specific structures to ensure proper protection of the items during transportation and to simplify the problem. The solutions generated by the heuristic has an average loading utilization of 91.3% for the most general instances with average running times around 100 seconds.