A beam search algorithm for the biobjective container loading problem

IGNACIO DANIEL ARAYA ZAMORANO, Mauricio Moyano, Cristobal Sanchez

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

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

Original languageEnglish
Pages (from-to)417-431
Number of pages15
JournalEuropean Journal of Operational Research
Volume286
Issue number2
DOIs
StatePublished - 16 Oct 2020
Externally publishedYes

Keywords

  • beam search
  • container loading problem
  • greedy
  • multiobjective optimization

Fingerprint Dive into the research topics of 'A beam search algorithm for the biobjective container loading problem'. Together they form a unique fingerprint.

Cite this