An heuristic method based on Lagrangean relaxation for the manufacturer's pallet loading problem

In this study we develop a heuristic method, based on Lagrangean and surrogate relaxation, to solve the manufacturer's pallet loading problem. Such a problem consists in arranging the maximum number of boxes by layer on the pallet, thus optimizing the utilization of the pallet's surface. We applied a method of reduction of the problem and a Lagrangean heuristic in a subgradient optimization procedure. We compare the solutions that were found with the solutions produced by other methods of the literature and solutions utilized in practice. For this, we utilize data obtained from the literature as well as actual data provided by a local carrier.