A two-dimensional bin-packing problem with conflict penalties

Abstract

In this paper, we address the two-dimensional bin-packing (2BP) problem with variable conflict penalties, which incur if conflicting items are loaded into the same bin. Such a problem is observed in applications such as supermarket chains and automobile components transportation. The problem not only focuses on minimisation of number of bins used, but also deals with the conflict penalties at the same time. We propose a heuristic method based on the IMA algorithm and adapt it to solve this problem. A local search procedure is also designed to further improve the solutions. For instances derived from benchmark test data, the computational results indicate that the adapted IMA heuristic algorithm with local search effectively balances the number of bins used and the conflict penalties. The algorithm outperforms several adapted approaches that are well known for the 2BP problems.

Keywords:

• bin packing with conflict penalties
• heuristics
• tabu search

Acknowledgement

The authors are indebted to the anonymous reviewers for their valuable comments, suggestions, and remarks. This research is supported by National Nature Science Foundation of China (No. 70972019, No. 71131004 and No. 71372133), and Program for New Century Excellent Talents in University (NCET-10-0410).