A two-phase constructive algorithm for the single container mix-loading problem

Manufacturers usually store their products in palletized storage units (PSUs). PSUs are convenient for storage but sometimes not cost-effective for transportation because they may result in large empty spaces of waste in containers. To improve the utilization of its containers, a manufacturer is willing to remove products from PSUs (a process called depalletizing) and load the individual products, together with other PSUs, into a container. Once a PSU is depalletized, its products must be loaded into the container. No PSU can be depalletized if the total volume of complete PSUs loaded in the container is not maximized. We introduce this problem as the single container mix-loading problem (SCMLP). Then, we develop a two-phase constructive algorithm for the SCMLP that uses a stochastic beam-search-based method developed for loading items into a given set of spaces as the sub-routine. In the first phase, the stochastic beam-search-based method is called upon to load PSUs into the container. In the second phase, a proper set of PSUs is selected, and the stochastic beam-search-based method is used to load all products of the selected PSUs into the remaining spaces in the container. The performance of our algorithm is demonstrated by experiments conducted on a set of instances generated from the historical data of the manufacturer. Besides, we also used the well-known 1500 single container loading problem instances to test the performance of our stochastic beam-search-based method, and the results showed that our approach is highly competitive with state-of-the-art methods.