Abstract
In this paper, we introduce a generalization of the Generalized Bin Packing Problem called Generalized Bin Packing Problem with bin-dependent item profits (GBPPI). In GBPPI, various bin types are available with their own capacities and costs. A set of compulsory and non-compulsory items are also given, with volume and bin-dependent profits. The aim of GBPPI is to determine an assignment of items to bins such that the overall profit is minimized. The importance of GBPPI is confirmed by a number of applications. In fact, the introduction of bin-dependent item profits allows GBPPI to be applied at a strategical and tactical level in cross-country and multi-modal transportation problems, and also at an operational level in last-mile logistic environments.
After providing a Mixed Integer Programming formulation of the problem, we introduce efficient heuristics that can effectively address GBPPI involving instances with up to 1000 items. Extensive computational tests demonstrate the accuracy of the proposed heuristics. Finally, we present a case study of a well-known international courier operating in northern Italy. The problem approached by the international courier is GBPPI. Our methodology largely outperforms the policies of the company.
Authors Baldi M.M., De Giovanni L., Perboli G., Tadei R.
Journal Omega-The International Journal of Management Science
Year 2016
