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

Title

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

 Author

Goslinga, Daan (TU Delft Electrical Engineering, Mathematics and Computer Science)

Contributor

Yorke-Smith, N. (mentor) ORCID 0000-0002-1814-3515

 Degree granting institution

Delft University of Technology

 Programme

Computer Science

 Date

2022-07-06

 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.

 Subject

3D bin packing
Picnic
genetic algorithm

 To reference this document use:

http://resolver.tudelft.nl/uuid:a128ea27-a231-42b8-9938-fbcb724c7930

 Part of collection

Student theses

 Document type

master thesis

 Rights

© 2022 Daan Goslinga
Files
PDF Thesis_Daan_Goslinga_censored.pdf 19.66 MB
Close viewer