A Hybrid VNS Matheuristic for a Bin Packing Problem with a Color Constraint

  • Yury Kochetov Sobolev Institute of Mathematics

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. The VNS heuristic is applied for 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.

Published
2021-02-08
How to Cite
KOCHETOV, Yury. A Hybrid VNS Matheuristic for a Bin Packing Problem with a Color Constraint. Yugoslav Journal of Operations Research, [S.l.], v. 31, n. 3, p. 285-298, feb. 2021. ISSN 2334-6043. Available at: <https://yujor.fon.bg.ac.rs/index.php/yujor/article/view/827>. Date accessed: 14 nov. 2024.
Section
Articles

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.