A Pattern-Guided Hybrid Ant Colony Optimization with Local Search for the Bin Packing Problem

Abstract

The bin packing problem (BPP) is a well-known NP-hard combinatorial optimization problem with long-standing relevance in logistics and manufacturing. In this paper, we address limitations of Ant Colony Optimization (ACO) when applied to the BPP. While ACO is a competitive approach for this problem, it often suffers from premature convergence and insufficient exploitation of packing patterns. We propose a hybrid ACO approach that combines local search with a construction phase guided by frequent packing patterns extracted from elite solutions. Instead of relying solely on pheromone information, the algorithm explicitly exploits recurring item combinations that are empirically associated with good packings. Solution refinement is performed through a set of local improvement procedures, including a local branching-based intensification strategy that explores structured neighborhoods around high-quality solutions to reduce the number of bins further. The method was evaluated on several well-established benchmark sets, including Falkenauer, Scholl, Schwerin, and Wäscher instances, and compared with a Mixed Integer Programming (MIP) baseline and a Max-Min Ant System (MMAS). The results show higher success rates and more stable performance across independent runs, indicating that the proposed hybrid strategy improves solution quality for the BPP, while also achieving lower root mean square error and standard deviation.