A beam search algorithm for the biobjective container loading problem

In this work we deal with a biobjective variant of the single container loading problem. The problem consists in packing a set of boxes into a large box or container. In addition to the usual objective related to maximize the volume utilization, we include a second objective consisting on maximizing the total profit (e.g., weight or priority) of the loaded boxes. We propose to adapt BSG, a state-of-the-art single-objective algorithm for solving the biobjective problem. BSG can be seen as an incomplete version of a breadth first search in which each level of the search tree is restricted to a fixed number of promising nodes. In order to select the most promising nodes, the algorithm constructs a solution from them by using a greedy algorithm and evaluates the objectives. To deal with two objectives, we propose to select nodes by using well-known multi-objective criteria based on dominance and crowding distance related to the greedy evaluations. We go a little bit further and orient the greedy algorithm to one objective or the other by using a mechanism which changes the configuration of the heuristic function dynamically. The proposal is compared with BSG in a set of well-known instances reporting a 24% increase in the hypervolume indicator. Compared to other biobjective approaches, the reported results are also promising. Codes and test instances are available in: https://github.com/rilianx/Metasolver#bo-bsg