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

Standard

A hybrid vns matheuristic for a bin packing problem with a color constraint. / Kochetov, Yury; Kondakov, Arteam.

в: Yugoslav Journal of Operations Research, Том 31, № 3, 2021, стр. 2.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Kochetov, Y & Kondakov, A 2021, 'A hybrid vns matheuristic for a bin packing problem with a color constraint', Yugoslav Journal of Operations Research, Том. 31, № 3, стр. 2. https://doi.org/10.2298/YJOR200117009K

APA

Kochetov, Y., & Kondakov, A. (2021). A hybrid vns matheuristic for a bin packing problem with a color constraint. Yugoslav Journal of Operations Research, 31(3), 2. https://doi.org/10.2298/YJOR200117009K

Vancouver

Kochetov Y, Kondakov A. A hybrid vns matheuristic for a bin packing problem with a color constraint. Yugoslav Journal of Operations Research. 2021;31(3):2. doi: 10.2298/YJOR200117009K

Author

Kochetov, Yury ; Kondakov, Arteam. / A hybrid vns matheuristic for a bin packing problem with a color constraint. в: Yugoslav Journal of Operations Research. 2021 ; Том 31, № 3. стр. 2.

BibTeX

@article{cf7e142264894def97412b6dfa9aca86,

title = "A hybrid vns matheuristic for a bin packing problem with a color constraint",

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.",

keywords = "Column Generation, Large Neighborhood, Local Search, Matheuristic, VNS",

author = "Yury Kochetov and Arteam Kondakov",

year = "2021",

doi = "10.2298/YJOR200117009K",

language = "English",

volume = "31",

pages = "2",

journal = "Yugoslav Journal of Operations Research",

issn = "0354-0243",

publisher = "University of Belgrade",

number = "3",

}

RIS

TY - JOUR

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

AU - Kochetov, Yury

AU - Kondakov, Arteam

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Column Generation

KW - Large Neighborhood

KW - Local Search

KW - Matheuristic

KW - VNS

UR - http://www.scopus.com/inward/record.url?scp=85115795995&partnerID=8YFLogxK

U2 - 10.2298/YJOR200117009K

DO - 10.2298/YJOR200117009K

M3 - Article

AN - SCOPUS:85115795995

VL - 31

SP - 2

JO - Yugoslav Journal of Operations Research

JF - Yugoslav Journal of Operations Research

SN - 0354-0243

IS - 3

ER -

ID: 34358759