Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

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

Levine, J.M. and Ducatelle, F. (2004) Ant colony optimisation and local search for bin-packing and cutting stock problems. Journal of the Operational Research Society, 55 (7). pp. 705-716. ISSN 0160-5682

[img]
Preview
PDF (strathprints004823.pdf)
Download (148Kb) | Preview

    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.

    Item type: Article
    ID code: 4823
    Keywords: ant colony optimization, bin packing, cutting stock, operational research, Electronic computers. Computer science, Management Information Systems, Strategy and Management, Management Science and Operations Research, Marketing
    Subjects: Science > Mathematics > Electronic computers. Computer science
    Department: Faculty of Science > Computer and Information Sciences
    Related URLs:
    Depositing user: Strathprints Administrator
    Date Deposited: 13 Dec 2007
    Last modified: 05 Sep 2014 13:31
    URI: http://strathprints.strath.ac.uk/id/eprint/4823

    Actions (login required)

    View Item

    Fulltext Downloads: