A lookahead matheuristic for the unweighed variable-sized two-dimensional bin packing problem

Sergey Polyakovskiy and M’Hallah, Rym

European Journal of Operational Research, 2022, vol. 299, issue 1, 104-117

Abstract: The unweighed oriented variable-sized two-dimensional guillotine bin packing problem consists in packing without overlap small rectangular items into large non-identical rectangular bins, with the items obtained via guillotine cuts. It minimizes the waste of the used bins. It is herein approximately solved using a hybrid matheuristic, which applies a sequence of low-level mixed-integer programs that reserve space for unpacked items and that are guided by feasibility constraints and by upper bounds on the objective function. The embedded constraints constitute a lookahead mechanism that prohibits the investigation of infeasible directions and constrains the search to improving ones. The matheuristic further employs high-level diversification and intensification mechanisms. The diversification incorporates a sequential value correction algorithm that tags a pseudo-price to each item to govern the fitness functions of mixed integer programs and subsequently their solution construction process. The intensification is a local search that investigates the neighbourhood of promising solutions. The extensive computational experiments provide evidence of the good performance of the proposed matheuristic. For the variable-sized bin packing benchmark instances, the matheuristic matches and improves 90.8% of the upper bounds. For the single bin-size bin packing benchmark instances, the matheuristic further proves the optimality of 82.6% upper bounds while it matches 14.4% and improves 2.6% existing bounds.

Keywords: Cutting; Variable-sized bin packing; Matheuristic; Lookahead search; Feasibility constraints (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721007293
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:299:y:2022:i:1:p:104-117

DOI: 10.1016/j.ejor.2021.08.037

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 ().