Author
Ekici, Ali
Publication Date
2023-08-01
Publication Place
-
Elsevier
Subject
Item conflicts, Large neighborhood search, Lower bound, Packing, Variable-sized bin packing
Type
Periodical
Language
English
Digital
Yes
Manuscript
No
Library
Özyeğin University
Library Asset ID
0377-2217
Record ID
4e06ec6b-606f-4e8d-a2e1-456a5b30292b
Library Location
Industrial Engineering
Date
2023-08-01
Sample Text
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
