Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Order Picking Optimization as a Service

Oxenstierna, Johan LU orcid (2024)
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Assoc. Prof. Steger-Jensen, Kenn, Aalborg University, Denmark.
organization
publishing date
type
Thesis
publication status
published
subject
pages
209 pages
publisher
Computer Science, Lund University
defense location
Lecture Hall E:1406, building E, Klas Anshelms väg 10, Faculty of Engineering LTH, Lund University, Lund. The dissertation will be live streamed, but part of the premises is to be excluded from the live stream.
defense date
2024-11-07 13:00:00
ISBN
978-91-8104-216-0
978-91-8104-215-3
language
English
LU publication?
yes
id
7bc88992-a7aa-4b74-b40a-0eefb2d742c7
date added to LUP
2024-10-14 10:24:10
date last changed
2025-04-04 15:28:57
@phdthesis{7bc88992-a7aa-4b74-b40a-0eefb2d742c7,
  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.}},
  author       = {{Oxenstierna, Johan}},
  isbn         = {{978-91-8104-216-0}},
  language     = {{eng}},
  month        = {{11}},
  publisher    = {{Computer Science, Lund University}},
  school       = {{Lund University}},
  title        = {{Order Picking Optimization as a Service}},
  url          = {{https://lup.lub.lu.se/search/files/197379847/orderPickingOptimizationAsAService.pdf}},
  year         = {{2024}},
}