Evolutionary Algorithms for Bin Packing Problem with Maximum Lateness and Waste Minimization

The Bin Packing Problem (BPP) is a well-known NP-hard problem with numerous real-world applications. This study aims to minimize waste and maximum lateness in a one-dimensional BPP. To solve the problem, we exploit a classical greedy algorithm in two different settings: it is firstly adapted as decoder in a standard Genetic Algorithm (GA), and it is also exploited to build a solution from scratch, in this case, guided by heuristic rules that are evolved automatically by Genetic Programming (GP). We conducted an experimental study to assess the performance of the proposed algorithms and to compare them against a Price-and-Branch (P &B) algorithm taken from the literature. The results show that the greedy algorithm guided by heuristics evolved by GP performs better than GA and that it produces solutions very close to the lower bounds provided by P &B, even in some cases improving the best-known upper bounds.