A Two-Stage 3D Bin Packing Algorithm for Groceries at Online Supermarket Picnic

Abstract

The online supermarket Picnic uses the volume of groceries to pack them into totes and bags. While this generally works well, there are cases in which an article's volume fits into a designated space, but its dimensions do not. To prevent this so-called overflow, Picnic uses a maximum fill rate of 85%, which means that no tote can be filled to more than 85% of its volume. Unfortunately, the use of a maximum fill rate does not guarantee that no overflow occurs at all and workers are sometimes still instructed to perform infeasible packings. To solve this, this thesis proposes a Three-dimensional Bin Packing algorithm (3D-BAGS) which uses the width, height and length of an article to determine whether it can be placed inside a bag. A Biased Random-Key Genetic Algorithm is used to converge to a good packing solution. After which, the same algorithm divides the bags into so-called totes, which are shipped to the customer. 3D-BAGS expands upon the state-of-the-art Three-dimensional Bin Packing algorithms by including bag stretching plus the diagonal rotation and squeezing of articles. Computation time of the current state-of-the-art is reduced by including memoization, priority based multithreading and a different stopping criterion. This thesis shows that the use of 3D-BAGS leads to more accurate packings, while simultaneously lowering the amount of totes needed to ship ambient and chilled groceries. However, 3D-BAGS needs more totes to ship frozen products compared to Picnic's current approach and is also more computationally expensive.