Reactive GRASP-Based Algorithm for Pallet Building Problem with Visibility and Contiguity Constraints

In this paper, we study a pallet building problem that originates from a case study in a company that produces robotized systems for freight transportation and logistics. The problem takes into account well-known constraints, such as rotation and stackability, and other specific constraints such as visibility and contiguity among items belonging to the same family. We formalize the problem and then solve it by means of a GRASP metaheuristic. The algorithm is based on an Extreme Points heuristic and a reactive mechanism. It uses a two-step strategy, in which items are first grouped into horizontal layers, and then layers are stacked one over the other to form pallets. The performance of the algorithm is assessed through extensive computational tests on real-world instances. The results show that the GRASP is able to create very compact packings for most of the instances with a limited computational effort.