Batch Picking in Warehouse Logistics: Trading Optimality for Feasibility
Typ
Examensarbete för masterexamen
Program
Publicerad
2022
Författare
Ludwig, Lundholm Hultqvist
Lammers, Mathias
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
A significant cost in warehouse logistics is the act of traversing the warehouse to
collect orders, where a commonly applied heuristic to reduce this cost is picking
several orders at once. Partitioning the full order set into optimal batches is known
as the batch picking problem, which also involves solving the travelling salesman
problem. The travelling salesman problem is famously known as NP-hard, making
it most likely infeasible to optimally solve larger instances of the batch picking
problem in practice. This thesis, in collaboration with Ongoing Warehouse, aims to
study different algorithms to find close-to-optimal solutions while still being viable
in real-world applications.
For the evaluation to be as realistic as possible, the layout of a physical warehouse
was used as a model. This, in addition to multiple order sets and the item placements
used in the aformentioned warehouse, was supplied by Ongoing Warehouse. Various
algorithms for partitioning the order sets and providing necessary traversal paths
were implemented in C# and benchmarked with the use of the external library
BenchmarkDotNet, where the distance of the paths, memory usage and required
time were chosen as the evaluation metrics. The benchmarking results indicated
that partitioning the order set based on proximity and solving the traversal path
with conventional linear programming can be used for reducing the total traversal
distance, while still remaining feasible in practice.
Beskrivning
Ämne/nyckelord
optimization , algorithms , batch picking , travelling salesman , warehouse , logistics , graphs , benchmarking , complexity