Deakin University
Browse

Strip packing with hybrid ACO: placement order is learnable

Version 2 2024-06-05, 04:38
Version 1 2019-07-11, 14:25
conference contribution
posted on 2024-06-05, 04:38 authored by Dhananjay ThiruvadyDhananjay Thiruvady, B Meyer, AT Ernst
This paper investigates the use of hybrid metaheuristics based on Ant Colony Optimization (ACO) for the strip packing problem. Here, a fixed set of rectangular items of fixed sizes have to be placed on a strip of fixed width and infinite height without overlaps and with the objective to minimize the height used. We analyze a commonly used basic placement heuristic (BLF) by itself and in a number of hybrid combinations with ACO. We compare versions that learn item order only, item rotation only, both independently, and rotations conditionally upon placement order. Our analysis shows that integrating a learning meta-heuristic provides a significant performance advantage over using the basic placement heuristic by itself. The experiments confirm that even just learning a placement order alone can provide significant performance improvements. Interestingly, learning item rotations provides at best a marginal advantage. The best hybrid algorithm presented in this paper significantly outperforms previously reported strip packing meta-heuristics.

History

Pagination

1207-1213

Location

Hong Kong, China

Start date

2008-06-01

End date

2008-06-06

ISBN-13

9781424418237

Language

eng

Publication classification

E1.1 Full written paper - refereed

Editor/Contributor(s)

[Unknown]

Title of proceedings

CEC 2008 : Proceedings of the 2008 IEEE Congress on Evolutionary Computation

Event

Evolutionary Computation. Congress (2008 : Hong Kong, China)

Publisher

Institute of Electrical and Electronics Engineers

Place of publication

Piscataway, N.J.

Series

Evolutionary Computation Congress

Usage metrics

    Research Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC