Ant colony optimisation and local search for bin-packing and cutting stock problems

J Levine, F Ducatelle

Research output: Contribution to journalArticle

116 Citations (Scopus)

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 ACO.
LanguageEnglish
Pages705-716
Number of pages12
JournalJournal of the Operational Research Society
Volume55
Issue number7
Early online date18 Jun 2004
DOIs
Publication statusPublished - 31 Jul 2004

Fingerprint

Ant colony optimization
Bins
Heuristic methods
Combinatorial optimization
Local search (optimization)
Cutting stock problem
Local search
Bin packing
Evolutionary algorithms
Genetic algorithms
Evolutionary

Keywords

  • ant colony optimization
  • bin packing
  • cutting stock
  • operational research

Cite this

@article{acc888d0cb8649ada5d0a30a69cf751e,
title = "Ant colony optimisation and local search for bin-packing and cutting stock problems",
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 ACO.",
keywords = "ant colony optimization, bin packing, cutting stock, operational research",
author = "J Levine and F Ducatelle",
year = "2004",
month = "7",
day = "31",
doi = "10.1057/palgrave.jors.2601771",
language = "English",
volume = "55",
pages = "705--716",
journal = "Journal of Operational Research Society",
issn = "0160-5682",
number = "7",

}

Ant colony optimisation and local search for bin-packing and cutting stock problems. / Levine, J; Ducatelle, F.

In: Journal of the Operational Research Society, Vol. 55, No. 7, 31.07.2004, p. 705-716.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Ant colony optimisation and local search for bin-packing and cutting stock problems

AU - Levine, J

AU - Ducatelle, F

PY - 2004/7/31

Y1 - 2004/7/31

N2 - 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 ACO.

AB - 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 ACO.

KW - ant colony optimization

KW - bin packing

KW - cutting stock

KW - operational research

U2 - 10.1057/palgrave.jors.2601771

DO - 10.1057/palgrave.jors.2601771

M3 - Article

VL - 55

SP - 705

EP - 716

JO - Journal of Operational Research Society

T2 - Journal of Operational Research Society

JF - Journal of Operational Research Society

SN - 0160-5682

IS - 7

ER -