| On 2002-06-28 at 11:00:00 (Brussels Time) |
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.
