A Differential Pheromone Grouping Ant Colony Optimization Algorithm for the 1-D Bin Packing Problem

Abstract

The bin packing problem (BPP) is a well-researched and important NP-hard problem with many contemporary applications (e.g. stock cutting, machine scheduling), which requires a set of items with variable sizes to be packed into a set of fixed-capacity containers. Many metaheuristic approaches have been successfully trialled on this problem, including evolutionary algorithms, ant colony optimization and local search techniques. The most successful variants of these approaches use grouping techniques whereby the algorithm considers sets of items together rather than as separate decision variables. This paper presents an Ant Colony Optimization integrated with a grouping technique and a novel differential pheromone procedure for bin packing. The proposed differential pheromone grouping ACO shows state-of-the-art results for ACO approaches in BPP and approaches the performance of the best evolutionary methods.