{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T13:26:59Z","timestamp":1760016419567,"version":"3.38.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T00:00:00Z","timestamp":1718668800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T00:00:00Z","timestamp":1718668800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100016379","name":"Universit\u00e4t Osnabr\u00fcck","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100016379","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["OR Spectrum"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Optimizing retrieval requests in warehouses is essential for maintaining a smooth flow of products. Most studies on warehouse retrieval optimization have considered no more than two input\/output-points for product retrieval. In this paper, we study different variants of a new stacker crane scheduling problem, where pallets have to be retrieved in a warehouse with multiple input\/output-points. The goal is to minimize the total travel time of the stacker crane to perform all retrievals. The problem variants we consider require determining either the pallet retrieval sequence, the assignment of pallets to input\/output-points, or both. We prove NP-hardness results and identify cases that can be solved in strongly polynomial time. Additionally, we propose transformations to the traveling salesman problem, enabling the application of a vast collection of existing solution techniques. Finally, in an extensive computational study, we compare different problem variants, assess their gain of optimization, and experimentally analyze the impact of various instance parameters.<\/jats:p>","DOI":"10.1007\/s00291-024-00775-x","type":"journal-article","created":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T18:12:44Z","timestamp":1718734364000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Retrieval optimization in a warehouse with multiple input\/output-points"],"prefix":"10.1007","volume":"47","author":[{"given":"Jan-Niklas","family":"Buckow","sequence":"first","affiliation":[]},{"given":"Marc","family":"Goerigk","sequence":"additional","affiliation":[]},{"given":"Sigrid","family":"Knust","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,6,18]]},"reference":[{"key":"775_CR1","unstructured":"Applegate D, Bixby R, Chvatal V, et\u00a0al (2006) Concorde TSP solver. https:\/\/www.math.uwaterloo.ca\/tsp\/concorde.html"},{"key":"775_CR2","doi-asserted-by":"publisher","unstructured":"Asadpour A, Goemans M, M\u0105dry A, et\u00a0al (2010) An $${O}(\\log n \/ \\log \\log n)$$-approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of the 2010 annual ACM-SIAM symposium on discrete algorithms, pp 379\u2013389, https:\/\/doi.org\/10.1137\/1.9781611973075.32","DOI":"10.1137\/1.9781611973075.32"},{"issue":"3","key":"775_CR3","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1016\/j.ejor.2016.04.008","volume":"254","author":"N Boysen","year":"2016","unstructured":"Boysen N, Stephan K (2016) A survey on single crane scheduling in automated storage\/retrieval systems. Eur J Oper Res 254(3):691\u2013704. https:\/\/doi.org\/10.1016\/j.ejor.2016.04.008","journal-title":"Eur J Oper Res"},{"key":"775_CR4","doi-asserted-by":"publisher","first-page":"102994","DOI":"10.1016\/j.tre.2022.102994","volume":"169","author":"JN Buckow","year":"2023","unstructured":"Buckow JN, Knust S (2023a) The warehouse reshuffling problem with swap moves. Transp Res Part E Logist Transp Rev 169:102994. https:\/\/doi.org\/10.1016\/j.tre.2022.102994","journal-title":"Transp Res Part E Logist Transp Rev"},{"key":"775_CR5","doi-asserted-by":"publisher","first-page":"100113","DOI":"10.1016\/j.ejtl.2023.100113","volume":"12","author":"JN Buckow","year":"2023","unstructured":"Buckow JN, Knust S (2023b) The warehouse reshuffling problem with swap moves and time limit. EURO J Transp Logis 12:100113. https:\/\/doi.org\/10.1016\/j.ejtl.2023.100113","journal-title":"EURO J Transp Logis"},{"key":"775_CR6","unstructured":"Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Carnegie-Mellon University Pittsburgh Management Sciences Research Group, Tech. rep"},{"issue":"4","key":"775_CR7","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1287\/opre.2.4.393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig G, Fulkerson D, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 2(4):393\u2013410. https:\/\/doi.org\/10.1287\/opre.2.4.393","journal-title":"J Oper Res Soc Am"},{"issue":"5","key":"775_CR8","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.entcs.2011.06.003","volume":"264","author":"B Dezs\u0151","year":"2011","unstructured":"Dezs\u0151 B, J\u00fcttner A, Kov\u00e1cs P (2011) Lemon - an open source C++ graph template library. Electron Notes Theor Comput Sci 264(5):23\u201345. https:\/\/doi.org\/10.1016\/j.entcs.2011.06.003","journal-title":"Electron Notes Theor Comput Sci"},{"key":"775_CR9","unstructured":"Frank A, Korte B, Triesch E, et\u00a0al (1998) On the bipartite travelling salesman problem. Tech. rep., Universit\u00e4t Bonn. Institut f\u00fcr \u00d6konometrie und Operations Research"},{"issue":"2","key":"775_CR10","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/j.ejor.2016.07.060","volume":"257","author":"A Garc\u00eda","year":"2017","unstructured":"Garc\u00eda A, Tejel J (2017) Polynomially solvable cases of the bipartite traveling salesman problem. Eur J Oper Res 257(2):429\u2013438. https:\/\/doi.org\/10.1016\/j.ejor.2016.07.060","journal-title":"Eur J Oper Res"},{"key":"775_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, USA"},{"issue":"2","key":"775_CR12","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/j.ejor.2013.09.038","volume":"235","author":"A Gharehgozli","year":"2014","unstructured":"Gharehgozli A, Yu Y, de Koster R et al (2014a) An exact method for scheduling a yard crane. Eur J Oper Res 235(2):431\u2013447. https:\/\/doi.org\/10.1016\/j.ejor.2013.09.038","journal-title":"Eur J Oper Res"},{"issue":"1","key":"775_CR13","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1287\/trsc.2014.0562","volume":"51","author":"A Gharehgozli","year":"2014","unstructured":"Gharehgozli A, Yu Y, Zhang X et al (2014b) Polynomial time algorithms to minimize total travel time in a two-depot automated storage\/retrieval system. Transp Sci 51(1):19\u201333. https:\/\/doi.org\/10.1287\/trsc.2014.0562","journal-title":"Transp Sci"},{"issue":"3","key":"775_CR14","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1016\/S0377-2217(99)00468-3","volume":"129","author":"F Glover","year":"2001","unstructured":"Glover F, Gutin G, Yeo A et al (2001) Construction heuristics for the asymmetric TSP. Eur J Oper Res 129(3):555\u2013568. https:\/\/doi.org\/10.1016\/S0377-2217(99)00468-3","journal-title":"Eur J Oper Res"},{"issue":"12","key":"775_CR15","doi-asserted-by":"publisher","first-page":"3010","DOI":"10.1016\/j.cor.2013.07.006","volume":"40","author":"M Goerigk","year":"2013","unstructured":"Goerigk M, Gr\u00fcn B, He\u00dfler P (2013) Branch and bound algorithms for the bus evacuation problem. Comput Oper Res 40(12):3010\u20133020. https:\/\/doi.org\/10.1016\/j.cor.2013.07.006","journal-title":"Comput Oper Res"},{"issue":"3","key":"775_CR16","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1006\/jagm.1994.1043","volume":"17","author":"J Hao","year":"1994","unstructured":"Hao J, Orlin J (1994) A faster algorithm for finding the minimum cut in a directed graph. J Algo 17(3):424\u2013446. https:\/\/doi.org\/10.1006\/jagm.1994.1043","journal-title":"J Algo"},{"issue":"6","key":"775_CR17","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0278-6125(95)90066-T","volume":"13","author":"A Keserla","year":"1994","unstructured":"Keserla A, Peters B (1994) Analysis of dual-shuttle automated storage\/retrieval systems. J Manuf Syst 13(6):424\u2013434. https:\/\/doi.org\/10.1016\/0278-6125(95)90066-T","journal-title":"J Manuf Syst"},{"key":"775_CR18","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.dam.2017.09.009","volume":"235","author":"G Kov\u00e1cs","year":"2018","unstructured":"Kov\u00e1cs G, Tuza Z, Vizv\u00e1ri B et al (2018) A note on the polytope of bipartite TSP. Discrete Appl Math 235:92\u2013100. https:\/\/doi.org\/10.1016\/j.dam.2017.09.009","journal-title":"Discrete Appl Math"},{"issue":"1\u20132","key":"775_CR19","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn HW, Yaw B (1955) The Hungarian method for the assignment problem. Naval Res Logist Q 2(1\u20132):83\u201397. https:\/\/doi.org\/10.1002\/nav.3800020109","journal-title":"Naval Res Logist Q"},{"issue":"18","key":"775_CR20","doi-asserted-by":"publisher","first-page":"4599","DOI":"10.1080\/00207540050205532","volume":"38","author":"C Malmborg","year":"2000","unstructured":"Malmborg C (2000) Interleaving models for the analysis of twin shuttle automated storage and retrieval systems. Int J Prod Res 38(18):4599\u20134610. https:\/\/doi.org\/10.1080\/00207540050205532","journal-title":"Int J Prod Res"},{"issue":"1","key":"775_CR21","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s10479-019-03222-1","volume":"296","author":"X Man","year":"2021","unstructured":"Man X, Zheng F, Chu F et al (2021) Bi-objective optimization for a two-depot automated storage\/retrieval system. Ann Oper Res 296(1):243\u2013262. https:\/\/doi.org\/10.1007\/s10479-019-03222-1","journal-title":"Ann Oper Res"},{"issue":"10","key":"775_CR22","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1023\/A:1018592017528","volume":"29","author":"R Meller","year":"1997","unstructured":"Meller R, Mungwattana A (1997) Multi-shuttle automated storage\/retrieval systems. IIE Trans 29(10):925\u2013938. https:\/\/doi.org\/10.1023\/A:1018592017528","journal-title":"IIE Trans"},{"key":"775_CR23","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tre.2014.11.002","volume":"73","author":"J Pazour","year":"2015","unstructured":"Pazour J, Carlo H (2015) Warehouse reshuffling: Insights and optimization. Transp Res Part E Logist Transp Rev 73:207\u2013226. https:\/\/doi.org\/10.1016\/j.tre.2014.11.002","journal-title":"Transp Res Part E Logist Transp Rev"},{"issue":"1","key":"775_CR24","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s13676-012-0010-0","volume":"1","author":"R Roberti","year":"2012","unstructured":"Roberti R, Toth P (2012) Models and algorithms for the asymmetric traveling salesman problem: an experimental comparison. EURO J Transp Logistics 1(1):113\u2013133. https:\/\/doi.org\/10.1007\/s13676-012-0010-0","journal-title":"EURO J Transp Logistics"},{"issue":"2","key":"775_CR25","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/j.ejor.2008.01.038","volume":"194","author":"K Roodbergen","year":"2009","unstructured":"Roodbergen K, Vis I (2009) A survey of literature on automated storage and retrieval systems. Eur J Oper Res 194(2):343\u2013362. https:\/\/doi.org\/10.1016\/j.ejor.2008.01.038","journal-title":"Eur J Oper Res"},{"issue":"5","key":"775_CR26","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1023\/A:1007545122755","volume":"31","author":"J Van den Berg","year":"1999","unstructured":"Van den Berg J, Gademann A (1999) Optimal routing in an automated storage\/retrieval system with dedicated storage. IIE Trans 31(5):407\u2013415. https:\/\/doi.org\/10.1023\/A:1007545122755","journal-title":"IIE Trans"},{"issue":"2","key":"775_CR27","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1287\/trsc.1090.0298","volume":"44","author":"I Vis","year":"2010","unstructured":"Vis I, Carlo H (2010) Sequencing two cooperating automated stacking cranes in a container terminal. Transp Sci 44(2):169\u2013182. https:\/\/doi.org\/10.1287\/trsc.1090.0298","journal-title":"Transp Sci"},{"issue":"2","key":"775_CR28","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1287\/opre.1080.0621","volume":"57","author":"I Vis","year":"2009","unstructured":"Vis I, Roodbergen K (2009) Scheduling of container storage and retrieval. Oper Res 57(2):456\u2013467. https:\/\/doi.org\/10.1287\/opre.1080.0621","journal-title":"Oper Res"},{"issue":"15","key":"775_CR29","doi-asserted-by":"publisher","first-page":"4668","DOI":"10.1080\/00207543.2021.1934590","volume":"60","author":"Y Yu","year":"2022","unstructured":"Yu Y, Liu Y, Yu H (2022) Optimal two-class-based storage policy in an AS\/RS with two depots at opposite ends of the aisle. Int J Prod Res 60(15):4668\u20134692. https:\/\/doi.org\/10.1080\/00207543.2021.1934590","journal-title":"Int J Prod Res"}],"container-title":["OR Spectrum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-024-00775-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00291-024-00775-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-024-00775-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,12]],"date-time":"2025-03-12T09:22:16Z","timestamp":1741771336000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00291-024-00775-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,18]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["775"],"URL":"https:\/\/doi.org\/10.1007\/s00291-024-00775-x","relation":{},"ISSN":["0171-6468","1436-6304"],"issn-type":[{"type":"print","value":"0171-6468"},{"type":"electronic","value":"1436-6304"}],"subject":[],"published":{"date-parts":[[2024,6,18]]},"assertion":[{"value":"22 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 May 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}