A beam search algorithm for the biobjective container loading problem

Ignacio Araya, Mauricio Moyano and Cristobal Sanchez

European Journal of Operational Research, 2020, vol. 286, issue 2, 417-431

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

Keywords: multiobjective optimization; container loading problem; beam search; greedy (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172030254X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:286:y:2020:i:2:p:417-431

DOI: 10.1016/j.ejor.2020.03.040

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().