Algorithmic Optimization of Warehouse Box Selection

Abstract

The efficiency of e-commerce logistics chains is heavily influenced by bin selection during the packing process, which can be formulated as a variant of the NP-hard three-dimensional bin packing problem: selecting the smallest possible combination of heterogeneous bins that can fit a given order. This thesis presents the implementation and evaluation of several solving techniques for this problem, with a focus on achieving runtimes suitable for real-world applications. Following a survey of what solutions currently exist in the literature, the four commonly found methods are heuristics, Genetic Algorithms (GAs), Deep Reinforcement Learning (DRL), and Mixed-Integer Linear Programming (MILP) solvers. These are all evaluated throughout this thesis, as well as the CP-SAT solver, which is capable of handling MILP problem formulations. Contrary to common findings within the literature, which consider GAs and DRL methods as state-of-the-art, this thesis shows that when replacing the traditional MILP solvers with CP-SAT, this becomes a viable alternative that can provide increased packing efficiency in a feasible amount of time. Heuristic solutions can also be a suitable option in certain scenarios, for instance, when minimizing computational load is highly prioritized.

This thesis concludes that it is possible to generate solutions to this bin packing problem using CP-SAT within feasible runtimes. While human workers may outperform the solver in some cases, this is primarily due to limitations within the current model. The solver is ready to be implemented if a warehouse meets a few key conditions: items should be well approximated by rectangular prisms, and the input data must be accurate and reliable. Given the NP-hard nature of the problem, performance is better when the number of items remains within normal operational bounds. Additionally, the availability of appropriately sized packing cartons is important. Without this, the benefits of the bin selection automation are significantly reduced.