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

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

van Aken, Margot (TU Delft Electrical Engineering, Mathematics and Computer Science)

de Oliveira Filho, F.M. (mentor)
Aardal, K.I. (graduation committee)
van Gijzen, M.B. (graduation committee)
Gorte, Frank (graduation committee)

Delft University of Technology

Applied Mathematics

2019-03-08

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.

Bin-packing
heuristic
groceries

http://resolver.tudelft.nl/uuid:f4ee26b5-b94e-4cd3-9c7a-c281b0c8d8a8

Student theses

master thesis

© 2019 Margot van Aken