A FIRST FIT HYBRID HEURISTIC FOR SOLVING TWO-DIMENSIONAL MULTI-OBJECTIVE CONTAINER LOADING PROBLEMS

Sammanfattning

The container loading problem is a combinatorial optimization problem with many important real-world use cases. However in literature the container loading problem is often over-simplified leading to solutions that are not applicable by real-world practitioners. This thesis introduces and formalizes a new family of container loading problems that includes an unrepresented set of real world container loading problems. The proposed problem type is most notably treating load balance as a hard constraint and using a weight and load balance multi-objective instead of the more traditional space utilization objective. To solve the problem a hybrid heuristic is proposed, the algorithm uses a first fit heuristic on container level for placement, a best fit layer approach for exact placement, a hill climbing swapping procedure and a best fit removal procedure. The algorithm is evaluated using an ablation study on real world data. The results show that the algorithm was able to be successfully applied to solve the proposed problem, and all steps but the balancing procedure had an undoubtedly positive effect. Applying the initial balancing step lead to an increase in total cargo weight but a reduction in load balance. The hybrid heuristic together with the problem formalization gives real world practitioners a useful tool in tackling real-world container loading problems and builds a foundation for future research of practical container loading problems.