Batch Picking in Warehouse Logistics: Trading Optimality for Feasibility - Ludwig, Lundholm Hultqvist; Lammers, Mathias (My University, 2022)
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.
Keywords: optimization; algorithms; batch picking; travelling salesman; warehouse; logistics; graphs; benchmarking; complexity