File(s) under permanent embargo
Strip packing with hybrid ACO: placement order is learnable
conference contribution
posted on 2008-01-01, 00:00 authored by Dhananjay ThiruvadyDhananjay Thiruvady, B Meyer, A T ErnstThis 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
Event
Evolutionary Computation. Congress (2008 : Hong Kong, China)Series
Evolutionary Computation CongressPagination
1207 - 1213Publisher
Institute of Electrical and Electronics EngineersLocation
Hong Kong, ChinaPlace of publication
Piscataway, N.J.Publisher DOI
Start date
2008-06-01End date
2008-06-06ISBN-13
9781424418237Language
engPublication classification
E1.1 Full written paper - refereedEditor/Contributor(s)
[Unknown]Title of proceedings
CEC 2008 : Proceedings of the 2008 IEEE Congress on Evolutionary ComputationUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC