An efficient bin-packing algorithm applied to packing groceries in a fulfillment center
M.M. van Aken (TU Delft - Electrical Engineering, Mathematics and Computer Science)
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.)
More Info
expand_more
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.