The bin packing and the cutting stock problems are two well-known NP-hard combinatorial optimisation problems. Only small instances can be solved exactly, so for real-world problems we have to rely on heuristic solution methods. In recent years, researchers have started to apply evolutionary approaches to these problems, including genetic algorithms and evolutionary programming. In previous work (Ducatelle and Levine, 2001) we give a method for solving the bin packing and the cutting stock problem using ant colony optimisation, a new class of meta-heuristics introduced by Dorigo in 1992. This meta-heuristic is inspired by the path-finding abilities of real ant colonies. It combines an artificial pheromone trail with simple heuristic information to stochastically build new solutions. In our previous work, we show that this approach gives reasonable results, and that it can outperform some existing evolutionary approaches.
In other ant colony work, it has been shown that ant colony optimisation can be made more effective by combination with a local search technique, whereby each ant's solution is improved by a local search procedure before the best solutions are reinforced. In this paper, we combine our previous approach for bin packing and cutting stock problems with a local search procedure based on the Dominance Criterion of Martello and Toth. This local search procedure is applied repeatedly until no further improvement is possible. The combined technique has been tested on Falkenauer's uniform problems and the cutting stock problems of Liang et al, with results that are great improvements on other evolutionary approaches to these problems.
References:
Frederick Ducatelle and John Levine (2001) Ant Colony Optimisation for Bin Packing and Cutting Stock Problems, Proceedings of the UK Workshop on Computational Intelligence 2001, Edinburgh, 10-12 September 2001.