Exact and approximate methods for the score-constrained packing problem

Hawa, Asyl, Lewis, Rhydian ORCID: https://orcid.org/0000-0003-1046-811X and Thompson, Jonathan 2022. Exact and approximate methods for the score-constrained packing problem. European Journal of Operational Research 302 (3) , pp. 847-859. 10.1016/j.ejor.2022.01.028

Preview

PDF - Accepted Post-Print Version Download (507kB) | Preview

Abstract

This paper investigates a packing problem related to the one-dimensional bin packing problem in which the order and orientation of items influences the feasibility of a solution. We give an exact polynomial-time algorithm for the Constrained Ordering Problem, explaining how it can be used to find a feasible packing of items in a single bin. We then introduce an evolutionary algorithm for the multi-bin version of the problem, which incorporates the exact algorithm along with a local search procedure and three recombination operators. The mechanisms and results produced by each of the recombination operators are compared, and we discuss the circumstances in which each approach proves most advantageous.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Publisher:	Elsevier
ISSN:	0377-2217
Date of First Compliant Deposit:	17 January 2022
Date of Acceptance:	17 January 2022
Last Modified:	26 Jul 2024 21:33
URI:	https://orca.cardiff.ac.uk/id/eprint/146726

Citation Data

Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item