An efficient bin-packing algorithm applied to packing groceries in a fulfillment center

Master Thesis (2019)
Author(s)

M.M. van Aken (TU Delft - Electrical Engineering, Mathematics and Computer Science)

Contributor(s)

Fernando Mário Filho – Mentor (TU Delft - Discrete Mathematics and Optimization)

K.I. Aardal – Graduation committee member (TU Delft - Discrete Mathematics and Optimization)

M.B. Van Gijzen – Graduation committee member (TU Delft - Numerical Analysis)

Frank Gorte – Graduation committee member (Picnic Supermarkets B.V.)

Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright
© 2019 Margot van Aken
More Info
expand_more
Publication Year
2019
Language
English
Copyright
© 2019 Margot van Aken
Graduation Date
08-03-2019
Awarding Institution
Delft University of Technology
Programme
Applied Mathematics
Faculty
Electrical Engineering, Mathematics and Computer Science
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

We have tried to create a bin-packing algorithm that assigns items from a customer-order to totes such that the amount of totes is minimized. Analyzing the bin-packing algorithm that was used before this thesis had been written, taught us that xxx.xx% of the customer-orders was packed non optimal. In this thesis four algorithms are applied to Picnic data. The order in which the algorithms assign items to a tote has major consequences for the solutions. Eight different ways to order the items are combined with each algorithm, resulting in 32 different tote-calculations. Out of those 32 tote-calculations, the Best Fit Algorithm with items ordered in decreasing normalized values generates the best results. Remarkably, ordering items randomly also gives good solutions. This brought us to introducing a new method, where each customer-order is calculated at most eight times, each time shuffling the items before rerunning the algorithm and remembering the better solution. This heuristic is optimal for xxx.xx% of the customer-orders.

Files

License info not available