Solving a highly constrained multi-level container loading problem from practice

Abstract: The container loading problem considered in this thesis is to determine placements of a set of packages within one or multiple shipping containers. Smaller packages are consolidated on pallets prior to being loaded in the shipping containers together with larger packages. There are multiple objectives which may be summarized as fitting all the packages while achieving good stability of the cargo as well as the shipping containers themselves. According to recent literature reviews, previous research in the field have to large extent been neglecting issues relevant in practice. Our real-world application was developed for the industrial company Atlas Copco to be used for sea container shipments at their Distribution Center (DC) in Texas, USA. Hence all applicable practical constraints faced by the DC operators had to be treated properly. A high variety in sizes, weights and other attributes such as stackability among packages added complexity to an already challenging combinatorial problem. Inspired by how the DC operators plan and perform loading manually, the batch concept was developed, which refers to grouping of boxes based on their characteristics and solving subproblems in terms of partial load plans. In each batch, an extensive placement heuristic and a load plan evaluation run iteratively, guided by a Genetic Algorithm (GA). In the placement heuristic, potential placements are evaluated using a scoring function considering aspects of the current situation, such as space utilization, horizontal support and heavier boxes closer to the floor. The scoring function is weighted by coefficients corresponding to the chromosomes of an individual in the GA population. Consequently, the fitness value of an individual in the GA population is the rating of a load plan. The loading optimization software has been tested and successfully implemented at the DC in Texas. The software has been proven capable of generating satisfactory load plans within acceptable computation times, which has resulted in reduced uncertainty and labor usage in the loading process. Analysis using real sea container shipments shows that the GA is able to tune the scoring coefficients to suit the particular problem instance being solved.