Fast Neighborhood Search Heuristics for the Colored Bin Packing Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911947546427392 |
|---|---|
| author | da Silva, Renan F. F. Borges, Yulle G. F. Schouery, Rafael C. S. |
| author_facet | da Silva, Renan F. F. Borges, Yulle G. F. Schouery, Rafael C. S. |
| contents | The Colored Bin Packing Problem (CBPP) is a generalization of the Bin Packing Problem (BPP). The CBPP consists of packing a set of items, each with a weight and a color, in bins of limited capacity, minimizing the number of used bins and satisfying the constraint that two items of the same color cannot be packed side by side in the same bin. In this article, we proposed an adaptation of BPP heuristics and new heuristics for the CBPP. Moreover, we propose a set of fast neighborhood search algorithms for CBPP. These neighborhoods are applied in a meta-heuristic approach based on the Variable Neighborhood Search (VNS) and a matheuristic approach that combines linear programming with the meta-heuristics VNS and Greedy Randomized Adaptive Search (GRASP). The results indicate that our matheuristic is superior to VNS and that both approaches can find near-optimal solutions for a large number of instances, even for those with many items. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_04471 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Fast Neighborhood Search Heuristics for the Colored Bin Packing Problem da Silva, Renan F. F. Borges, Yulle G. F. Schouery, Rafael C. S. Artificial Intelligence Optimization and Control 68T20, 90C59 The Colored Bin Packing Problem (CBPP) is a generalization of the Bin Packing Problem (BPP). The CBPP consists of packing a set of items, each with a weight and a color, in bins of limited capacity, minimizing the number of used bins and satisfying the constraint that two items of the same color cannot be packed side by side in the same bin. In this article, we proposed an adaptation of BPP heuristics and new heuristics for the CBPP. Moreover, we propose a set of fast neighborhood search algorithms for CBPP. These neighborhoods are applied in a meta-heuristic approach based on the Variable Neighborhood Search (VNS) and a matheuristic approach that combines linear programming with the meta-heuristics VNS and Greedy Randomized Adaptive Search (GRASP). The results indicate that our matheuristic is superior to VNS and that both approaches can find near-optimal solutions for a large number of instances, even for those with many items. |
| title | Fast Neighborhood Search Heuristics for the Colored Bin Packing Problem |
| topic | Artificial Intelligence Optimization and Control 68T20, 90C59 |
| url | https://arxiv.org/abs/2310.04471 |