Geodesic
A Hybrid VNS Matheuristic for a Bin Packing Problem With a Color Constraint
Yugoslav journal of operations research, Tome 31 (2021) no. 3, p. 285 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

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.
Classification : 90B85, 90C26
Keywords: VNS, Matheuristic, Local Search, Large Neighborhood, Column Generation 
@article{YJOR_2021_31_3_a0,
     author = {Yury Kochetov and Arteam Kondakov},
     title = {A {Hybrid} {VNS} {Matheuristic} for a {Bin} {Packing} {Problem} {With} a {Color} {Constraint}},
     journal = {Yugoslav journal of operations research},
     pages = {285 },
     year = {2021},
     volume = {31},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2021_31_3_a0/}
}
TY  - JOUR
AU  - Yury Kochetov
AU  - Arteam Kondakov
TI  - A Hybrid VNS Matheuristic for a Bin Packing Problem With a Color Constraint
JO  - Yugoslav journal of operations research
PY  - 2021
SP  - 285 
VL  - 31
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/YJOR_2021_31_3_a0/
LA  - en
ID  - YJOR_2021_31_3_a0
ER  - 
%0 Journal Article
%A Yury Kochetov
%A Arteam Kondakov
%T A Hybrid VNS Matheuristic for a Bin Packing Problem With a Color Constraint
%J Yugoslav journal of operations research
%D 2021
%P 285 
%V 31
%N 3
%U http://geodesic.mathdoc.fr/item/YJOR_2021_31_3_a0/
%G en
%F YJOR_2021_31_3_a0
Yury Kochetov; Arteam Kondakov. A Hybrid VNS Matheuristic for a Bin Packing Problem With a Color Constraint. Yugoslav journal of operations research, Tome 31 (2021) no. 3, p. 285 . http://geodesic.mathdoc.fr/item/YJOR_2021_31_3_a0/