Back to the program.
Ant Colony Optimisation and Aggressive Local Search for Bin Packing and Cutting Stock Problems
Frederick Ducatelle
fducatelle@hotmail.com

Abstract

The Bin Packing Problem and the Cutting Stock Problem are two related classes of NP-hard combinatorial optimisation problems. Exact solution methods can only be used for very small instances, so for real-world problems we have to rely on heuristic methods. In recent years, researchers have started to apply meta-heuristics to these problems, including Genetic Algorithms and Evolutionary Programming. In the work presented here, we tried to use the ACO meta-heuristic to solve both Bin Packing and Cutting Stock Problems. We present a pure ACO approach, as well as an ACO approach augmented with a simple but very effective local search algorithm. It is shown that the pure ACO approach can outperform some existing solution mehods, whereas the hybrid approach can compete with the best known solution methods. The Local Search algorithm is also run with random restarts and shown to perform worse than when combined with ACO.