Pallets are the most common form of packaging in the retail industry. Their building involves the solution of a three-dimensional packing problem with side practical constraints such as item support and pallet stability, leading to what is known as the mixed-case palletization problem. Motivated by the fact that solving industry-size instances is still very challenging for current methods, we propose a new solution methodology that combines data analysis at the instance level and optimization to build pallets. Item heights are analyzed to identify possible layers and to derive relationships on the positions of items. They are clustered, creating pairs and trios then combined to generate layers of even height. This layering approach ensures item stability and support. The pallet formation problem is solved using a reduced-size mixed integer program as well as a two-dimensional heuristic. Computational tests on industry data shows a high efficiency of the solution approach in producing high-quality solutions with item stability and support in fast computational times.
Supervisor: Samir Elhedhli