A RANDOMIZED HEURISTIC FOR THE CONTAINER LOADING PROBLEM: FURTHER INVESTIGATIONS

Abstract

The knapsack container loading problem is the problem of loading a subset of rectangular boxes into a rectangular container of fixed dimensions such that the volume of the packed boxes is maximized. A new heuristic based on the wall-building approach was proposed earlier. That heuristic divides the problem into a number of layers and the packing of layers is done using a randomized heuristic. Further investigations of randomized heuristic are discussed in this paper. We focused on ways to find proportions of the mixture of heuristics which would lead to better performance of the algorithm. New results are compared with earlier research and some other constructive heuristics. The performance of the corresponding algorithms is experimentally compared for homogeneous and heterogeneous instances. Proposed improvements allow to achieve better filling ratio without increasing the computational complexity of the algorithm.