A Hybrid Heuristic Based on Column Generation for Two- and Three- Stage Bin Packing Problems

dc.contributor.author Alvelos,F en
dc.contributor.author Elsa Marília Silva en
dc.contributor.author Valerio de Carvalho,JMV en
dc.date.accessioned 2018-01-11T14:49:37Z
dc.date.available 2018-01-11T14:49:37Z
dc.date.issued 2014 en
dc.description.abstract We address two two-dimensional bin packing problems where the bins are rectangular and have the same size. The items are also rectangular and all of them must be packed with the objective of minimizing the number of bins. In the first problem, the two-stage problem, the items must be packed in levels. In the second problem, the restricted 3-stage problem, items can be grouped in stacks which are packed in levels. We propose a new decomposition model where subproblems are associated with the item that initializes a bin. The decomposition is solved by a heuristic which combines (perturbed) column generation, local search, beam branch-and-price, and the use of a general purpose mixed integer programming solver. This approach is closely related with SearchCol, a framework for solving integer programming / combinatorial optimization decomposition models. Computational results with 500 instances from the literature show that the proposed hybrid heuristic is efficient in obtaining high quality solutions. It uses more 8 and 17 bins than the 7364 and 7340 bins of a compact model from the literature for the 2 and 3-stage problems, respectively, while the sum of the time spent for all instances is 35% and 58% of the time spent by the compact model. en
dc.identifier.uri http://repositorio.inesctec.pt/handle/123456789/5903
dc.identifier.uri http://dx.doi.org/10.1007/978-3-319-09129-7_16 en
dc.language eng en
dc.relation 5675 en
dc.rights info:eu-repo/semantics/embargoedAccess en
dc.title A Hybrid Heuristic Based on Column Generation for Two- and Three- Stage Bin Packing Problems en
dc.type conferenceObject en
dc.type Publication en
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
P-009-Q59.pdf
Size:
239.66 KB
Format:
Adobe Portable Document Format
Description: