Optimization of the Storage Location Assignment Problem using nested annealing

Johan Oxenstierna; Louis Janse van Rensburg; Peter J. Stuckey; Volker Krueger

doi:10.1007/978-3-031-49662-2_12

Optimization of the Storage Location Assignment Problem using nested annealing

Johan Oxenstierna, Louis Janse van Rensburg, Peter J. Stuckey, Volker Krueger

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

Abstract

The Storage Location Assignment Problem (SLAP) has a significant impact on the efficiency of warehouse operations. We propose a multi-phase optimizer for the SLAP, where the quality of an assignment is based on distance estimates of future-forecasted order-picking. Candidate assignments are first sampled using a Markov Chain accept/reject method. Order-picking Traveling Salesman Problems (TSPs) are then modified according to the assignments and solved. The model is graph-based and generalizes to any obstacle layout in two dimensions. We investigate whether optimization speed-ups are possible using methods such as cost approximation, rejection of samples with low approximate cost and restarts from local minima. Results demonstrate that these methods improve performance, with total travel-cost reductions of up to 30% within 8 h of CPU-time. We share a public repository with SLAP instances and corresponding benchmark results on the generalizable TSPLIB format.

Original language	English
Title of host publication	11th International Conference, ICORES 2022, Virtual Event, February 3–5, 2022, and 12th International Conference, ICORES 2023, Lisbon, Portugal, February 19–21, 2023 Revised Selected Papers
Editors	Federico Liberatore, Slawo Wesolkowski, Marc Demange, Greg H. Parlier
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	220-244
Number of pages	25
ISBN (Electronic)	9783031496622
ISBN (Print)	9783031496615
DOIs	https://doi.org/10.1007/978-3-031-49662-2_12
Publication status	Published - 2024
Event	International Conference on Operations Research and Enterprise Systems 2023 - Lisbon, Portugal Duration: 19 Feb 2023 → 21 Feb 2023 Conference number: 12th https://link.springer.com/book/10.1007/978-3-031-49662-2 (Proceedings) https://icores.scitevents.org/?y=2023 (Website)

Publication series

Name	Communications in Computer and Information Science
Publisher	Springer
Volume	1985
ISSN (Print)	1865-0929
ISSN (Electronic)	1865-0937

Conference

Conference	International Conference on Operations Research and Enterprise Systems 2023
Abbreviated title	ICORES 2023
Country/Territory	Portugal
City	Lisbon
Period	19/02/23 → 21/02/23
Internet address	https://link.springer.com/book/10.1007/978-3-031-49662-2 (Proceedings) https://icores.scitevents.org/?y=2023 (Website)

Keywords

Hamming distances
Nested annealing
Storage location assignment problem

Access to Document

10.1007/978-3-031-49662-2_12

Cite this

Oxenstierna, J., van Rensburg, L. J., Stuckey, P. J., & Krueger, V. (2024). Optimization of the Storage Location Assignment Problem using nested annealing. In F. Liberatore, S. Wesolkowski, M. Demange, & G. H. Parlier (Eds.), 11th International Conference, ICORES 2022, Virtual Event, February 3–5, 2022, and 12th International Conference, ICORES 2023, Lisbon, Portugal, February 19–21, 2023 Revised Selected Papers (pp. 220-244). (Communications in Computer and Information Science; Vol. 1985). Springer. https://doi.org/10.1007/978-3-031-49662-2_12

Oxenstierna, Johan ; van Rensburg, Louis Janse ; Stuckey, Peter J. et al. / Optimization of the Storage Location Assignment Problem using nested annealing. 11th International Conference, ICORES 2022, Virtual Event, February 3–5, 2022, and 12th International Conference, ICORES 2023, Lisbon, Portugal, February 19–21, 2023 Revised Selected Papers. editor / Federico Liberatore ; Slawo Wesolkowski ; Marc Demange ; Greg H. Parlier. Cham Switzerland : Springer, 2024. pp. 220-244 (Communications in Computer and Information Science).

@inproceedings{bc53e395167b456eb0f2736aa9a7a656,

title = "Optimization of the Storage Location Assignment Problem using nested annealing",

abstract = "The Storage Location Assignment Problem (SLAP) has a significant impact on the efficiency of warehouse operations. We propose a multi-phase optimizer for the SLAP, where the quality of an assignment is based on distance estimates of future-forecasted order-picking. Candidate assignments are first sampled using a Markov Chain accept/reject method. Order-picking Traveling Salesman Problems (TSPs) are then modified according to the assignments and solved. The model is graph-based and generalizes to any obstacle layout in two dimensions. We investigate whether optimization speed-ups are possible using methods such as cost approximation, rejection of samples with low approximate cost and restarts from local minima. Results demonstrate that these methods improve performance, with total travel-cost reductions of up to 30% within 8 h of CPU-time. We share a public repository with SLAP instances and corresponding benchmark results on the generalizable TSPLIB format.",

keywords = "Hamming distances, Nested annealing, Storage location assignment problem",

author = "Johan Oxenstierna and {van Rensburg}, {Louis Janse} and Stuckey, {Peter J.} and Volker Krueger",

note = "Publisher Copyright: {\textcopyright} 2024, The Author(s), under exclusive license to Springer Nature Switzerland AG.; International Conference on Operations Research and Enterprise Systems 2023, ICORES 2023 ; Conference date: 19-02-2023 Through 21-02-2023",

year = "2024",

doi = "10.1007/978-3-031-49662-2_12",

language = "English",

isbn = "9783031496615",

series = "Communications in Computer and Information Science",

publisher = "Springer",

pages = "220--244",

editor = "Federico Liberatore and Slawo Wesolkowski and Marc Demange and Parlier, {Greg H.}",

booktitle = "11th International Conference, ICORES 2022, Virtual Event, February 3–5, 2022, and 12th International Conference, ICORES 2023, Lisbon, Portugal, February 19–21, 2023 Revised Selected Papers",

url = "https://link.springer.com/book/10.1007/978-3-031-49662-2, https://icores.scitevents.org/?y=2023",

}

Oxenstierna, J, van Rensburg, LJ, Stuckey, PJ & Krueger, V 2024, Optimization of the Storage Location Assignment Problem using nested annealing. in F Liberatore, S Wesolkowski, M Demange & GH Parlier (eds), 11th International Conference, ICORES 2022, Virtual Event, February 3–5, 2022, and 12th International Conference, ICORES 2023, Lisbon, Portugal, February 19–21, 2023 Revised Selected Papers. Communications in Computer and Information Science, vol. 1985, Springer, Cham Switzerland, pp. 220-244, International Conference on Operations Research and Enterprise Systems 2023, Lisbon, Portugal, 19/02/23. https://doi.org/10.1007/978-3-031-49662-2_12

Optimization of the Storage Location Assignment Problem using nested annealing. / Oxenstierna, Johan; van Rensburg, Louis Janse; Stuckey, Peter J. et al.
11th International Conference, ICORES 2022, Virtual Event, February 3–5, 2022, and 12th International Conference, ICORES 2023, Lisbon, Portugal, February 19–21, 2023 Revised Selected Papers. ed. / Federico Liberatore; Slawo Wesolkowski; Marc Demange; Greg H. Parlier. Cham Switzerland: Springer, 2024. p. 220-244 (Communications in Computer and Information Science; Vol. 1985).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Optimization of the Storage Location Assignment Problem using nested annealing

AU - Oxenstierna, Johan

AU - van Rensburg, Louis Janse

AU - Stuckey, Peter J.

AU - Krueger, Volker

N1 - Conference code: 12th

PY - 2024

Y1 - 2024

N2 - The Storage Location Assignment Problem (SLAP) has a significant impact on the efficiency of warehouse operations. We propose a multi-phase optimizer for the SLAP, where the quality of an assignment is based on distance estimates of future-forecasted order-picking. Candidate assignments are first sampled using a Markov Chain accept/reject method. Order-picking Traveling Salesman Problems (TSPs) are then modified according to the assignments and solved. The model is graph-based and generalizes to any obstacle layout in two dimensions. We investigate whether optimization speed-ups are possible using methods such as cost approximation, rejection of samples with low approximate cost and restarts from local minima. Results demonstrate that these methods improve performance, with total travel-cost reductions of up to 30% within 8 h of CPU-time. We share a public repository with SLAP instances and corresponding benchmark results on the generalizable TSPLIB format.

AB - The Storage Location Assignment Problem (SLAP) has a significant impact on the efficiency of warehouse operations. We propose a multi-phase optimizer for the SLAP, where the quality of an assignment is based on distance estimates of future-forecasted order-picking. Candidate assignments are first sampled using a Markov Chain accept/reject method. Order-picking Traveling Salesman Problems (TSPs) are then modified according to the assignments and solved. The model is graph-based and generalizes to any obstacle layout in two dimensions. We investigate whether optimization speed-ups are possible using methods such as cost approximation, rejection of samples with low approximate cost and restarts from local minima. Results demonstrate that these methods improve performance, with total travel-cost reductions of up to 30% within 8 h of CPU-time. We share a public repository with SLAP instances and corresponding benchmark results on the generalizable TSPLIB format.

KW - Hamming distances

KW - Nested annealing

KW - Storage location assignment problem

UR - http://www.scopus.com/inward/record.url?scp=85180554905&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-49662-2_12

DO - 10.1007/978-3-031-49662-2_12

M3 - Conference Paper

AN - SCOPUS:85180554905

SN - 9783031496615

T3 - Communications in Computer and Information Science

SP - 220

EP - 244

BT - 11th International Conference, ICORES 2022, Virtual Event, February 3–5, 2022, and 12th International Conference, ICORES 2023, Lisbon, Portugal, February 19–21, 2023 Revised Selected Papers

A2 - Liberatore, Federico

A2 - Wesolkowski, Slawo

A2 - Demange, Marc

A2 - Parlier, Greg H.

PB - Springer

CY - Cham Switzerland

T2 - International Conference on Operations Research and Enterprise Systems 2023

Y2 - 19 February 2023 through 21 February 2023

ER -

Oxenstierna J, van Rensburg LJ, Stuckey PJ, Krueger V. Optimization of the Storage Location Assignment Problem using nested annealing. In Liberatore F, Wesolkowski S, Demange M, Parlier GH, editors, 11th International Conference, ICORES 2022, Virtual Event, February 3–5, 2022, and 12th International Conference, ICORES 2023, Lisbon, Portugal, February 19–21, 2023 Revised Selected Papers. Cham Switzerland: Springer. 2024. p. 220-244. (Communications in Computer and Information Science). doi: 10.1007/978-3-031-49662-2_12