A hybrid vns matheuristic for a bin packing problem with a color constraint

Research output: Contribution to journalArticlepeer-review

Abstract

We study a new variant of the bin packing problem with a color constraint. Given a finite set of items, each item has a set of colors. Each bin has a color capacity, the total number of colors for a bin is the unification of colors for its items and cannot exceed the bin capacity. We need to pack all items into the minimal number of bins. For this NP-hard problem, we present approximability results and design a hybrid matheuristic based on the column generation technique. A hybrid VNS heuristic is applied to the pricing problem. The column generation method provides a lower bound and a core subset of the most promising bin patterns. Fast heuristics and exact solution for this core produce upper bounds. Computational experiments for test instances with number of items up to 500 illustrate the efficiency of the approach.

Original languageEnglish
Pages (from-to)2
Number of pages1
JournalYugoslav Journal of Operations Research
Volume31
Issue number3
DOIs
Publication statusPublished - 2021

Keywords

  • Column Generation
  • Large Neighborhood
  • Local Search
  • Matheuristic
  • VNS

OECD FOS+WOS

  • 5.02 ECONOMICS AND BUSINESS
  • 5.09 OTHER SOCIAL SCIENCES
  • 1.01 MATHEMATICS

Fingerprint

Dive into the research topics of 'A hybrid vns matheuristic for a bin packing problem with a color constraint'. Together they form a unique fingerprint.

Cite this