Heurísticas para o Problema do Empacotamento Colorido

• Renan F. F. da Silva Unicamp http://orcid.org/0000-0003-1142-3343
• Yulle G. F. Borges Unicamp
• Rafael C. S. Schouery Unicamp https://orcid.org/0000-0002-0472-4810

DOI: https://doi.org/10.5753/etc.2021.16374

Resumo

O Problema do Empacotamento Colorido (CBPP) é uma generalização do Problema do Empacotamento (BPP) onde, dado um conjunto de itens com um tamanho e uma cor, devemos empacotar os itens em recipientes de capacidade limitada, minimizando a quantidade de recipientes utilizados e satisfazendo a restrição que dois itens de mesma cor não podem ser empacotados lado a lado em um mesmo recipiente. Neste artigo, propomos a adaptação de heurísticas do BPP para o CBPP acompanhado de algumas heurísticas novas para o problema. Propomos também uma heurística para o CBPP baseada em Variable Neighborhood Search. Os resultados indicam que a nossa abordagem é capaz de encontrar boas soluções para instâncias grandes do problema.

Palavras-chave: BPP, CBPP, Metaheuristic, VNS

Referências

Böhm, M., Sgall, J., and Veselý, P. (2014). Online colored bin packing. Proceedings of the 12th International Workshop Approximation and Online Algorithms, pages 35–46.

Dósa, G. and Epstein, L. (2014). Colorful bin packing. Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory, pages 170–181.

Fleszar, K. and Hindi, K. S. (2002). New heuristics for one-dimensional bin-packing. Computers & Operations Research, 29(7):821–839.

Johnson, D., Demers, A., Ullman, J., Garey, M., and Graham, R. (1974). Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput., 3:299–325.

Loh, K.-H., Golden, B., and Wasil, E. (2008). Solving the one-dimensional bin packing problem with a weight annealing heuristic. Computers & Operations Research, 35(7):2283–2291.

Mladenović, N. and Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11):1097–1100.