A K-means clustering and machine learning enhanced hybrid optimization approach for large-scale container loading problems

Abstract

The Three-Dimensional Container Loading Problem (3D-CLP) is a well-known NP-hard combinatorial optimization problem that plays a critical role in logistics and transportation systems. Efficient utilization of container space directly affects transportation costs, operational efficiency, and environmental sustainability. Even small improvements in space usage can significantly reduce fuel consumption and carbon emissions. However, solving large-scale real-world container loading problems remains computationally challenging due to practical constraints such as item rotations, stackability requirements, weight limits, loading priorities, and mixed loading restrictions. This thesis addresses a real-world container loading problem encountered in a logistics company in Turkey and proposes an integrated hybrid optimization framework to handle large-scale instances under realistic industrial constraints. The proposed methodology combines clustering-based preprocessing, multi-level heuristic packing, column generation, and supervised machine learning within a unified architecture. First, K-Means clustering is employed as a preprocessing mechanism to group items according to dimensional similarity. This step reduces combinatorial complexity and improves structural coherence during packing. The number of clusters is determined through a multi-criteria evaluation using the Elbow method, Silhouette index, Davies–Bouldin index, and Calinski–Harabasz score. This systematic and data-driven selection ensures balanced cluster compactness while avoiding unnecessary fragmentation. Following clustering, a two-level three-dimensional heuristic packing strategy is applied. In the first level, items within each cluster are packed into compact and stable blocks while satisfying feasibility, weight, orientation, and stackability constraints. In the second level, these blocks are allocated to containers using a Column Generation framework combined with a 3D Best-Fit Decreasing with Orientation procedure. This decomposition-based structure enhances space utilization and solution robustness. To further improve computational efficiency, a supervised machine learning model is integrated into the column generation process to predict promising reduced-cost columns. Since only a small portion of generated patterns contribute to improvement, the machine learning component functions as a screening mechanism, reducing unnecessary feasibility evaluations and accelerating convergence. Computational experiments conducted on benchmark datasets and real industrial instances demonstrate significant improvements in container utilization compared to baseline heuristic approaches and manual loading strategies. The proposed framework also achieves substantial reductions in computational time for large-scale instances. Overall, this thesis bridges the gap between theoretical optimization techniques and practical logistics applications by introducing a scalable, data-driven, and computationally efficient solution architecture for complex three-dimensional container loading problems.