Instance space analysis for the generalized bin packing problem algorithms

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.

Grantor dc:publisher.institution

Department of Statistical Sciences

Year dc:date.issued

2025

Author dc:creator

• Netshitungulu, Funanani

Advisor dc:contributor.advisor

• Rakotonirainy, Rosephine Georgina

• Instance space analysis

Language dc:language.iso

en

Handle dc:identifier.uri

http://hdl.handle.net/11427/42542

OAI identifier oai:identifier

oai:open.uct.ac.za:11427/42542