The public defence of the thesis takes place on Thursday November 7th, 2024 at 13:00.

Thesis title: Order-Picking Optimization as a Service

Author: Johan Oxenstierna, Department of Computer Science, Lund University

Faculty opponent: Associate Professor Kenn Steger-Jensen, Aalborg University, Denmark

Examination Committee:

• Professor Ulrich Berger, Brandenburg University of Technology, Germany
• Associate Professor Tarun Agrawal, Chalmers University of Technology
• Professor Veronica Lesch, Baden-Wuerttemberg Cooperative State University, Germany
• Deputy: Associate Professor Yiannis Karayiannidis, Department of Automatic Control, Lund University

Session chair: Professor Johan Marklund, Lund University

Supervisors:

• Professor Volker Krueger, Lund University
• Professor Jacek Malec, Lund University

Location: E:1406, E-building, Klas Anshelms väg 10 / John Ericssons väg 2, Lund, Sweden

For download: Follow this link to download the pdf: https://portal.research.lu.se/sv/publications/order-picking-optimization-as-a-service

Abstract

Order-picking is one of the costliest processes in warehouses and we investigate how it can be optimized using Software as a Service (SaaS). First, we describe three specific order-picking optimization problems: The Picker Routing Problem (PRP), the Order Batching Problem (OBP) and the Storage Location Assignment Problem (SLAP). The PRP is a type of Traveling Salesman Problem (TSP) where we find a minimal-cost path for a vehicle assigned to pick a given set of products in the warehouse. The OBP is a type of Vehicle Routing Problem (VRP) where products are partitioned among a fleet of vehicles. We compute cost in the OBP by optimizing the PRP for each vehicle. In the SLAP, we assign or reassign storage locations of products such that costs in PRPs and/or OBPs are minimized. There are several choices regarding features and constraints for these problems, including digitization of warehouse rack layouts, zones, depot locations, dynamicity, product and vehicle characteristics, traffic rules and cost functions. In related work, there is little consensus on how to choose, classify and judge the importance of such features, leading to a lack of standards on data-driven benchmarking and experiment reproducibility. Before we propose optimization methods, we therefore examine choices and preprocessing of features to promote standardization. For our optimizers, we use heuristics and meta-heuristics. There exist publicly available heuristic solvers for the PRP capable of obtaining optimal solutions in a short CPU-time, but for the OBP and SLAP, optimal solutions often require an excessive amount of CPU-time. Consequently, we propose SaaS-suitable optimization techniques that balance between CPU-time, memory usage and cost minimization. We mainly rely on Monte Carlo methods, including Metropolis sampling and Nested Annealing, Sequential Minimal Distance (SMD), restart heuristics, cost approximation using the Quadratic Assignment Problem (QAP) and sub-optimal PRP optimization. Results show that costs found at early stages in optimization are often difficult to improve on, and that performance is sensitive to small changes in parameters and implementation in ways that are often difficult to foresee. For a SaaS which aims to provide optimization for multiple order-picking usecases, we therefore suggest a flexible workflow where various optimization methods are trialled and compared in sandbox environments. Data and results are shared in public repositories.