Storage Assignment Using Nested Metropolis Sampling and Approximations of Order Batching Travel Costs
Oxenstierna, Johan LU
; Malec, Jacek
LU
and Krueger, Volker
LU
(2024)
In SN Computer Science
5(5).
- Abstract
The Storage Location Assignment Problem (SLAP) is of central importance in warehouse operations. An important research challenge lies in generalizing the SLAP such that it is not tied to certain order-picking methodologies, constraints, or warehouse layouts. We propose the OBP-based SLAP, where the quality of a location assignment is obtained by optimizing an Order Batching Problem (OBP). For the optimization of the OBP-based SLAP, we propose a nested Metropolis algorithm. The algorithm includes an OBP-optimizer to obtain the cost of an assignment, as well as a filter which approximates OBP costs using a model based on the Quadratic Assignment Problem (QAP). In experiments, we tune two key parameters in the QAP model, and test whether... (More)
The Storage Location Assignment Problem (SLAP) is of central importance in warehouse operations. An important research challenge lies in generalizing the SLAP such that it is not tied to certain order-picking methodologies, constraints, or warehouse layouts. We propose the OBP-based SLAP, where the quality of a location assignment is obtained by optimizing an Order Batching Problem (OBP). For the optimization of the OBP-based SLAP, we propose a nested Metropolis algorithm. The algorithm includes an OBP-optimizer to obtain the cost of an assignment, as well as a filter which approximates OBP costs using a model based on the Quadratic Assignment Problem (QAP). In experiments, we tune two key parameters in the QAP model, and test whether its predictive quality warrants its use within the SLAP optimizer. Results show that the QAP model’s per-sample accuracy is only marginally better than a random baseline, but that it delivers predictions much faster than the OBP optimizer, implying that it can be used as an effective filter. We then run the SLAP optimizer with and without using the QAP model on industrial data. We observe a cost improvement of around 23% over 1 h with the QAP model, and 17% without it. We share results for public instances on the TSPLIB format.
(Less)
- author
- Oxenstierna, Johan
LU
; Malec, Jacek
LU
and Krueger, Volker
LU
- organization
- publishing date
- 2024-06
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Metropolis algorithm, Order batching problem, Quadratic assignment problem, Storage location assignment problem, Warehousing
- in
- SN Computer Science
- volume
- 5
- issue
- 5
- article number
- 477
- publisher
- Springer Nature
- external identifiers
-
- scopus:85191065266
- ISSN
- 2662-995X
- DOI
- 10.1007/s42979-024-02711-w
- language
- English
- LU publication?
- yes
- id
- 521004d3-d511-4786-bfa5-8d581c06b087
- date added to LUP
- 2024-05-07 15:31:05
- date last changed
- 2024-05-07 15:32:23
@article{521004d3-d511-4786-bfa5-8d581c06b087,
abstract = {{<p>The Storage Location Assignment Problem (SLAP) is of central importance in warehouse operations. An important research challenge lies in generalizing the SLAP such that it is not tied to certain order-picking methodologies, constraints, or warehouse layouts. We propose the OBP-based SLAP, where the quality of a location assignment is obtained by optimizing an Order Batching Problem (OBP). For the optimization of the OBP-based SLAP, we propose a nested Metropolis algorithm. The algorithm includes an OBP-optimizer to obtain the cost of an assignment, as well as a filter which approximates OBP costs using a model based on the Quadratic Assignment Problem (QAP). In experiments, we tune two key parameters in the QAP model, and test whether its predictive quality warrants its use within the SLAP optimizer. Results show that the QAP model’s per-sample accuracy is only marginally better than a random baseline, but that it delivers predictions much faster than the OBP optimizer, implying that it can be used as an effective filter. We then run the SLAP optimizer with and without using the QAP model on industrial data. We observe a cost improvement of around 23% over 1 h with the QAP model, and 17% without it. We share results for public instances on the TSPLIB format.</p>}},
author = {{Oxenstierna, Johan and Malec, Jacek and Krueger, Volker}},
issn = {{2662-995X}},
keywords = {{Metropolis algorithm; Order batching problem; Quadratic assignment problem; Storage location assignment problem; Warehousing}},
language = {{eng}},
number = {{5}},
publisher = {{Springer Nature}},
series = {{SN Computer Science}},
title = {{Storage Assignment Using Nested Metropolis Sampling and Approximations of Order Batching Travel Costs}},
url = {{http://dx.doi.org/10.1007/s42979-024-02711-w}},
doi = {{10.1007/s42979-024-02711-w}},
volume = {{5}},
year = {{2024}},
}