A multistart variable neighborhood descent metaheuristic for the board packing problem

Sergio Pérez-Peló (), Anna Martínez-Gavara (), Jesús Sánchez-Oro () and Ana D. López-Sánchez ()
Additional contact information
Sergio Pérez-Peló: Universidad Rey Juan Carlos
Anna Martínez-Gavara: Universitat de València
Jesús Sánchez-Oro: Universidad Rey Juan Carlos
Ana D. López-Sánchez: Universidad Pablo de Olavide

Annals of Operations Research, 2025, vol. 352, issue 1, No 7, 193-216

Abstract: Abstract The Board Packing Problem (BoPP) considers a rectangular board divided in cells with m rows and n columns. In this problem, a subset from a set of rectangles with different costs may be allocated on the cells, and in turns, each cell has an associated revenue obtained if a rectangle is placed on it. The objective of the BoPP is to allocate rectangles on the board, covering cells in order to maximize the total profit, measured as the revenues of the selected cells where the rectangle is placed minus the cost of purchasing such rectangles. The revenue of a cell is collected only once, and only if a rectangle is covering the cell. We propose a Variable Neighborhood Descent (VND) approach for solving the BoPP. Two constructive procedures are proposed for generating the initial solution for the VND: a totally greedy approach and a greedy randomized method to favor diversity. The experimental comparison analyses the contribution of each component of the final algorithm and then performs a competitive testing to evaluate the performance of the algorithm when comparing it with the best method found in the state of the art. The superiority of the proposal is supported by non-parametric statistical tests.

Keywords: Metaheuristics; GRASP; Variable neighborhood search; Combinatorial optimization; Board packing problem (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-025-06787-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:annopr:v:352:y:2025:i:1:d:10.1007_s10479-025-06787-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-025-06787-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().