A Two-Phase Algorithm to Solve a 3-Dimensional Pallet Loading Problem

摘要

The pallet loading problem (PLP) is an NP-hard problem and is generally tackled by attempting to maximize the number of boxes that can be loaded orthogonally on a pallet. Several methods have been proposed in the literature that focus on maximizing the volume utilization and stability of the pallet. In this paper, a two-phase algorithm is proposed to solve a 3-dimensional PLP while considering humidity, and storage time. In the first phase, the boxes should fit completely within the pallet without any overhang, i.e. the edges of the boxes should be parallel to the edges of the pallet, where the boxes can be rotated by 90°. In the second phase, the number of horizontal layers per pallet is calculated based on three parameters, i.e. maximum allowable height, maximum allowable weight, and dynamic compressive strength of boxes at the bottom layer. The maximum allowable height and maximum allowable weight for the pallet are known. The dynamic compressive strength represents the compressive strength of a box under real conditions. It is a function of the static compressive strength (strength under lab conditions), humidity, storage time etc. Here, static compressive strength of a pallet is calculated using the modified McKee formula. The horizontal layers are loaded using the same pattern to avoid overlapping. Results show the efficiency of the two-phase algorithm in maximizing the number of boxes per pallet (i.e. pallet utilization) and stability.