Hoppa till huvudinnehåll

2019 och senare



Pre-seminar Johan Oxenstierna

Tid: 2024-04-22 11:00 till 12:00 Föreläsning

Johan Oxenstierna will have his PhD Pre-seminar on 22 April 2024 in E:2116.

Abstract: Order-picking is one of the costliest processes in warehouses. In this PhD research, 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 versions of these problems and choices regarding features and constraints, 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 each of the features. This leads 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 which are 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 CPUtime, memory usage and cost minimization. We mainly rely on Monte Carlo methods, including Metropolis sampling and Nested Annealing, Sequential Minimal Distance (SMD) and restart heuristics, and cost approximation using the Quadratic Assignment Problem (QAP) and suboptimal
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 trialed and compared in sandbox environments. Data and results are shared in public repositories.
The reported work has been published in 6 conference papers and 1 Springer Nature paper, with a second Springer Nature paper accepted.

Very welcome!

Om händelsen
Tid: 2024-04-22 11:00 till 12:00


johan [dot] oxenstierna [at] cs [dot] lth [dot] se

Sidansvarig: peter.moller@cs.lth.se | 2024-03-18