Ant colony optimization and local search for bin packing and cutting stock problems
Open Access
- 1 July 2004
- journal article
- Published by Taylor & Francis Ltd in Journal of the Operational Research Society
- Vol. 55 (7), 705-716
- https://doi.org/10.1057/palgrave.jors.2601771
Abstract
The Bin Packing Problem and the Cutting Stock Problem are two related classes of NP-hard combinatorial optimization 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 evolutionary approaches to these problems, including Genetic Algorithms and Evolutionary Programming. In the work presented here, we used an ant colony optimization (ACO) approach 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 compete with existing evolutionary methods, whereas the hybrid approach can outperform the best-known hybrid evolutionary solution methods for certain problem classes. The hybrid ACO approach is also shown to require different parameter values from the pure ACO approach and to give a more robust performance across different problems with a single set of parameter values. The local search algorithm is also run with random restarts and shown to perform significantly worse than when combined with ACOKeywords
This publication has 18 references indexed in Scilit:
- A new evolutionary approach to cutting stock problems with and without contiguityComputers & Operations Research, 2002
- Swarm IntelligencePublished by Oxford University Press (OUP) ,1999
- Hybrid genetic algorithms for bin-packing and related problemsAnnals of Operations Research, 1996
- Ant system: optimization by a colony of cooperating agentsIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1996
- A hybrid grouping genetic algorithm for bin packingJournal of Heuristics, 1996
- Cutting and packingEuropean Journal of Operational Research, 1995
- Genetic algorithms for cutting stock problems: With and without contiguityLecture Notes in Computer Science, 1995
- Cutting stock problems and solution proceduresEuropean Journal of Operational Research, 1991
- A typology of cutting and packing problemsEuropean Journal of Operational Research, 1990
- A Linear Programming Approach to the Cutting-Stock ProblemOperations Research, 1961