A Plant Propagation Algorithm for the Bin Packing Problem

Abstract

We consider the one-dimensional Bin Packing Problem (BPP) and its solution using a novel heuristic approach namely the Plant Propagation Algorithm (PPA). The problem can be stated as follows: given a set of objects of various weights, sizes, or any measure, and a set of bins each with fixed capacity, find the minimum number of bins needed to pack all the items such that the sum of the elements packed inside each bin does not exceed its capacity. BPP is a well-studied problem, however, being NP-Hard, the search for a computationally viable solution approach for it continues. In this paper, we report on our implementation of PPA for BPP and its performance against other algorithms on number of non-trivial instances. Computational results and their discussion are included.

Keywords

• Algorithms
• Approximate Solution
• Bin Packing
• Heu