.png){kind=icon}
.png){kind=icon}
Return
On the generalized bin packing problem
.png){kind=icon}
OA
AI
DOI：10.1111/itor.12258.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The generalized bin packing problem (GBPP) is a novel packing problem arising in many transportation and logistic settings, characterized by multiple items and bins attributes and the presence of both compulsory and non-compulsory items. In this paper, we study the computational complexity and the approximability of the GBPP. We prove that the GBPP cannot be approximated by any constant, unless P=NP. We also study the particular case of a single bin type and show that when an unlimited number of bins is available, the GBPP can be reduced to the bin packing with rejection (BPR) problem, which is approximable. We also prove that the GBPP satisfies Bellman's optimality principle and, exploiting this result, we develop a dynamic programming solution approach. Finally, we study the behavior of standard and widespread heuristics such as the first fit, best fit, first fit decreasing, and best fit decreasing. We show that while they successfully approximate previous versions of bin packing problems, they fail to approximate the GBPP.
Keywords:
bin packing problem
variable cost and size bin packing problem
approximation
Bellman's optimality principle
dynamic programming
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.9
Papers:
1.8K
Citations:
3.7K