Multi-objective optimisation of the generalized bin packing problem

Plumbley, Andrea

Multi-objective optimisation of the generalized bin packing problem

Thesis / Dissertation

2025

Publisher

University of Cape Town

Department

Department of Statistical Sciences

Faculty

Faculty of Science

Abstract

This project aimed to investigate multi-objective optimisation of the generalized bin packing problem, which involves the allocation of compulsory and non-compulsory items into a set of bins. The items have characteristics such as weight, width, height, and due date, while the bins have characteristics such as capacity and cost. The main objective of this problem is to minimize cost which usually corresponds to minimizing the number of bins used. However, in many real-world applications there may be multiple objectives that are trying to be met, and these may be competing such as item due dates and load balancing objectives. Classical methods for solving such problems involve combining the objectives into a single objective or converting some of the objectives into constraints with associated goals. Both approaches require one to have prior knowledge of the decision-makers' preferences in terms of a trade-off between the different objectives which are often difficult to obtain. In this work, a multi-objective evolutionary model is proposed to tackle the generalized bin packing problem. The proposed approach optimises the problem across multiple objectives, allowing decision-makers to make a trade-off between solutions presented as a Pareto front. Two objective combinations were considered: cost and item lateness, and cost and load imbalance. The developed model was tested on one- and two-dimensional problem instances, demonstrating its ability to minimize objectives and provide a set of conflicting solutions in certain cases. The results also highlighted potential limitations of the algorithm, such as premature convergence and a lack of solution diversity. Potential reasons for these limitations and recommendations for future research to improve the current algorithm are discussed. This work contributes to the limited literature on multi-objective optimisation of the generalized bin packing problem, providing a multi-objective evolutionary algorithm for the problem, while also highlighting some of the problems encountered when performing multi-objective optimisation.

Keywords

Bin

Packing

Reference:

Collections

Masters

Full item page