Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Exact and evolutionary algorithms for the score-constrained packing problem

Hawa, Asyl 2020. Exact and evolutionary algorithms for the score-constrained packing problem. PhD Thesis, Cardiff University.
Item availability restricted.

[thumbnail of PhD Thesis]
Preview
PDF (PhD Thesis) - Accepted Post-Print Version
Download (1MB) | Preview
[thumbnail of Cardiff University Electronic Publication Form] PDF (Cardiff University Electronic Publication Form) - Supplemental Material
Restricted to Repository staff only

Download (682kB)

Abstract

This thesis concerns the Score-Constrained Packing Problem (SCPP), a combinatorial optimisation problem related to the one-dimensional bin packing problem. The aim of the SCPP is to pack a set of rectangular items from left to right into the fewest number of bins such that no bin is overfilled; however, the order and orientation of the items in each bin affects the feasibility of the overall solution. The SCPP has applications in the packaging industry, and obtaining high quality solutions for instances of the SCPP has the ability to reduce the amount of waste material, costs, and time, which motivates the study in this thesis. The minimal existing research on the SCPP leads us to explore a wide range of approaches to the problem in this thesis, implementing ideas from related problems in literature as well as bespoke methods. To begin, we present an exact algorithm that can produce a feasible configuration of a subset of items in a single bin in polynomial-time. We then introduce a range of methods for the SCPP including heuristics, an evolutionary algorithm framework comprising a local search procedure and a choice of three distinct recombination operators, and two algorithms combining metaheuristics with an exact procedure. Each method is investigated to gain more insight into the characteristics that benefit or hinder the improvement of solutions, both theoretically and computationally, using a large number of problem instances with varying parameters. This allows us to determine the specific methods and properties that produce superior solutions depending on the type of problem instance.

Item Type: Thesis (PhD)
Date Type: Completion
Status: Unpublished
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Funders: EPSRC
Date of First Compliant Deposit: 3 March 2021
Last Modified: 10 Nov 2021 02:25
URI: https://orca.cardiff.ac.uk/id/eprint/139229

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics