PackingSolver: a solver for Packing Problems
share
In this article, we introduce PackingSolver, a new solver for two-dimensional two- and three-staged guillotine Packing Problems. It relies on a simple yet powerful anytime tree search algorithm called Memory Bounded A* (MBA*). This algorithm was first introduced in libralesso2020 for the 2018 ROADEF/EURO challenge glass cutting problem (https://www.roadef.org/challenge/2018/en/index.php), for which it had been ranked first during the final phase. In this article, we generalize it for a large variety of Cutting and Packing problems. The resulting program can tackle two-dimensional Bin Packing, Multiple Knapsack, and Strip Packing Problems, with two- or three-staged exact or non-exact guillotine cuts, the orientation of the first cut being imposed or not, and with or without item rotation. Despite its simplicity and genericity, computational experiments show that this approach is competitive compared to the other dedicated algorithms from the literature. It even returns state-of-the-art solutions on several variants. The combination of efficiency, ability to provide good solutions fast, simplicity and versatility makes it particularly suited for industrial applications, which require quickly developing algorithms implementing several business-specific constraints.
READ FULL TEXT