A large neighborhood search algorithm and lower bounds for the variable-sized bin packing problem with conflicts

Name: A large neighborhood search algorithm and lower bounds for the variable-sized bin packing problem with conflicts
Author: Ekici, Ali

İsim	A large neighborhood search algorithm and lower bounds for the variable-sized bin packing problem with conflicts
Yazar	Ekici, Ali
Basım Tarihi:	2023-08-01
Basım Yeri	- Elsevier
Konu	Item conflicts, Large neighborhood search, Lower bound, Packing, Variable-sized bin packing
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	0377-2217
Kayıt Numarası	4e06ec6b-606f-4e8d-a2e1-456a5b30292b
Lokasyon	Industrial Engineering
Tarih	2023-08-01
Örnek Metin	In this paper, we study the Variable-Sized Bin Packing Problem with Conflicts (VSBPPC). In VSBPPC, a set of items each with a certain size has to be packed into bins of various types. Bin types differ in terms of their capacity and cost, and certain pairs of items cannot be packed into the same bin due to conflicts. The goal is to pack the items into the bins such that the total cost of the used bins is minimized. VSBPPC generalizes both the Variable-Sized Bin Packing Problem (VSBPP) and Bin Packing Problem with Conflicts (BPPC). We propose new lower bounds and develop a large neighborhood search algorithm for the problem. In the proposed solution approach, we destroy the solution by unpacking some of the bins and then repair the solution by a greedy method considering the unit cost of packing each item followed by a local search procedure. In the local search phase, we improve the repaired solution by (i) transferring items from its current bin to another bin, and (ii) swapping the items between bins. We evaluate the performance of the proposed solution approach not only against a lower bound but also against the benchmark algorithms from the literature. The proposed solution approach outperforms the benchmark algorithms with at least a margin of 4.39% on average. Moreover, the solutions obtained by the proposed approach have an average optimality gap of 2.77% with respect to the lower bound.
DOI	10.1016/j.ejor.2022.12.042
Cilt	308

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

A large neighborhood search algorithm and lower bounds for the variable-sized bin packing problem with conflicts

Yazar Ekici, Ali

Basım Tarihi 2023-08-01

Basım Yeri - Elsevier

Konu Item conflicts, Large neighborhood search, Lower bound, Packing, Variable-sized bin packing

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 0377-2217

Kayıt Numarası 4e06ec6b-606f-4e8d-a2e1-456a5b30292b

Lokasyon Industrial Engineering

Tarih 2023-08-01

Örnek Metin In this paper, we study the Variable-Sized Bin Packing Problem with Conflicts (VSBPPC). In VSBPPC, a set of items each with a certain size has to be packed into bins of various types. Bin types differ in terms of their capacity and cost, and certain pairs of items cannot be packed into the same bin due to conflicts. The goal is to pack the items into the bins such that the total cost of the used bins is minimized. VSBPPC generalizes both the Variable-Sized Bin Packing Problem (VSBPP) and Bin Packing Problem with Conflicts (BPPC). We propose new lower bounds and develop a large neighborhood search algorithm for the problem. In the proposed solution approach, we destroy the solution by unpacking some of the bins and then repair the solution by a greedy method considering the unit cost of packing each item followed by a local search procedure. In the local search phase, we improve the repaired solution by (i) transferring items from its current bin to another bin, and (ii) swapping the items between bins. We evaluate the performance of the proposed solution approach not only against a lower bound but also against the benchmark algorithms from the literature. The proposed solution approach outperforms the benchmark algorithms with at least a margin of 4.39% on average. Moreover, the solutions obtained by the proposed approach have an average optimality gap of 2.77% with respect to the lower bound.

DOI 10.1016/j.ejor.2022.12.042

Cilt 308