A HYBRID APPROACH COMBINING K-MEANS CLUSTERING AND HEURISTICS FOR THE CONTAINER LOADING PROBLEM: A REAL-CASE APPLICATION

Background: The three-dimensional container loading problem (CLP) is an NP-hard optimization problem with significant implications for logistics efficiency and sustainability. Even minor improvements in space utilization can substantially reduce transportation costs and environmental impact. Although numerous heuristics and metaheuristics have been proposed, clustering-based preprocessing approaches—particularly K-Means—have received limited attention. Objective: This study proposes a hybrid framework that integrates K-Means clustering with a two-level three-dimensional (3D) heuristic to improve space utilization, computational efficiency, and practical applicability. Methods: The proposed approach follows a two-stage design that combines clustering and heuristic packing. In Stage 1, items are grouped according to dimensional similarity using K-Means, with the number of clusters determined by the Elbow, Silhouette, Davies–Bouldin, and Calinski–Harabasz indices. In Stage 2, each cluster is packed as a compact block using a two-level 3D Best-Fit heuristic, subject to feasibility, weight, and stackability constraints. Results: Experiments on benchmark and industrial datasets achieved container utilization improvements of 12–15% over a baseline 3D Best-Fit heuristic and 19–24% over manual loading, while reducing runtime by approximately 30–35× (from over one hour to less than two minutes). Conclusions: K-Means-based preprocessing substantially enhances heuristic 3D loading container performance, yielding higher space utilization and significantly shorter runtimes compared with a baseline heuristic. The proposed approach, therefore, offers a transparent, scalable, and computationally efficient alternative that bridges the gap between simple greedy heuristics and complex metaheuristics.