Instance space analysis for the generalized bin packing problem algorithms

Netshitungulu, Funanani

Instance space analysis for the generalized bin packing problem algorithms

Thesis / Dissertation

2025

Publisher

University of Cape Town

Department

Department of Statistical Sciences

Faculty

Faculty of Science

Abstract

Instance space analysis for the generalized bin packing problem algorithms In the generalised bin packing problem, the objective is to pack a selected set of profitable non-compulsory items with all the compulsory ones into a set of bins such that the resulting packing cost is minimised. The total cost is given by the difference between the cost of the selected bins and the total profit of the loaded items. This type of problem is encountered in logistics, mainly in the transportation industry which has grown massively over the years. In this thesis, six improved heuristics are proposed to tackle this problem. The aim is to investigate the upper bound solutions provided by such heuristic approaches to the problem. An Instance Space Analysis is also applied to test the efficiency and effectiveness of the algorithms in respect of the problem instance space. In particular, the relationship between the problem instance features and the algorithm performance is studied. The results indicate that the chosen features are able to explain the difficulty of the problem instances, highlighting the strengths and weaknesses of the various algorithms. This work contributes to the advancement of research in the context of packing problem instance space analysis.

Keywords

Instance space analysis

Reference:

Collections

Masters

Full item page