On the generalized bin packing problem

On the generalized bin packing problem

0.00 Avg rating0 Votes
Article ID: iaor2017484
Volume: 24
Issue: 3
Start Page Number: 425
End Page Number: 438
Publication Date: May 2017
Journal: International Transactions in Operational Research
Authors: ,
Keywords: heuristics, transportation: general, programming: dynamic
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.