Retrieval optimization in a warehouse with multiple input/output-points

Buckow, Jan-Niklas; Goerigk, Marc; Knust, Sigrid Article — Published Version Retrieval optimization in a warehouse with multiple input/ output-points OR Spectrum Provided in Cooperation with: Springer Nature Suggested Citation: Buckow, Jan-Niklas; Goerigk, Marc; Knust, Sigrid (2024) : Retrieval optimization in a warehouse with multiple input/output-points, OR Spectrum, ISSN 1436-6304, Springer, Berlin, Heidelberg, Vol. 47, Iss. 1, pp. 1-34, https://doi.org/10.1007/s00291-024-00775-x This Version is available at: https://hdl.handle.net/10419/323269 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Vol.:(0123456789) OR Spectrum (2025) 47:1–34 https://doi.org/10.1007/s00291-024-00775-x ORIGINAL ARTICLE Retrieval optimization inawarehouse withmultiple input/ output‑points Jan‑NiklasBuckow1· MarcGoerigk2· SigridKnust1 Received: 22 December 2023 / Accepted: 31 May 2024 / Published online: 18 June 2024 © The Author(s) 2024 Abstract 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. Keywords Logistics· Warehouse· Retrieval optimization· Multiple input/outputpoints * Jan-Niklas Buckow [email protected] Marc Goerigk [email protected] Sigrid Knust [email protected] 1 Institute ofComputer Science, Osnabrück University, Wachsbleiche27, 49090Osnabrück, Germany 2 Business Decisions andData Science, University ofPassau, Dr.-Hans-Kapfinger-Straße 30, 94032Passau, Germany 2 J.-N.Buckow et al. 1 Introduction The storage and subsequent retrieval of items in warehouses is crucial for ensuring a smooth flow of products in supply chains. To increase the efficiency, warehouses often use automated storage/retrieval systems (AS/RS), where all incoming items are transferred on uniform pallets. In such storages, there are two types of requests: storage requests and retrieval requests. For a storage request, a pallet is moved by an automatically controlled stacker crane from an input/output-point (I/O-point) to a location within the warehouse. Moreover, for a retrieval request, the stacker crane returns a pallet to an I/O-point. To obtain more details on warehouses with AS/RS, we refer to the survey papers by Boysen and Stephan (2016) as well as Roodbergen and Vis (2009). 1.1 Motivation Our work was initially motivated by a problem setting we encountered at an industrial company operating a high-bay warehouse with AS/RS. Nevertheless, the scope of our findings reaches beyond this specific context. The problem we identified and subsequently studied has broad applicability across a range of settings, even those that do not involve warehouses, as we will illustrate later. For clarity and ease of understanding, we will keep using terminology related to warehouses. At the aforementioned industrial company, we discovered a warehouse with three different I/O-points and the following stacker crane scheduling problem. Initially and finally, the stacker crane is located at a specific depot I/O-point. A given set of retrieval requests has to be processed, where each pallet to be retrieved can be returned to an arbitrary I/O-point. When approaching an I/Opoint, the stacker crane drops the pallet to be retrieved there and picks up a pallet to be stored. It then moves to the next pallet to be retrieved in the warehouse and swaps it with the pallet to be stored currently loaded on the stacker crane (it has an additional buffer location to perform such swaps). Each pallet to be retrieved will be returned to the storage after an employee has removed specific parts from it used in a further production process. Consequently, at each I/O-point, exactly the pallet that was previously retrieved there is available as a storage request. This means that the retrieval requests are automatically synchronized with the number of storage requests waiting at the I/O-points. Therefore, for a processing sequence of retrieval requests and their assignment to I/O-points, the storage requests result implicitly and do not have to be considered explicitly. Moreover, to optimize storage locations based on the retrieval frequencies of the pallets, the company regularly rearranges the assignment of pallets to storage locations, for instance during breaks or at night. The described process is called warehouse reshuffling (Pazour and Carlo 2015; Buckow and Knust 2023a, b), and it ensures that high frequency retrieval requests can be performed fast without considering the selection of storage locations for storage requests. 3 Retrieval optimization inawarehouse withmultiple… The goal is to minimize the makespan, i.e., the total travel time of the stacker crane to perform all retrieval requests of the current shift. However, even if the travel time is the key performance measure in the company’s problem setting, our approaches can also handle other performance measures instead, such as the stacker crane’s energy consumption or its wear and tear. In the following, we hence use the more general term travel costs instead of travel time, highlighting that we simply can use another performance measure without affecting the correctness of our proposed methodology. For example, Fig.1 shows a feasible stacker crane tour processing four pallet retrieval requests in a warehouse with three I/O-points (the leftmost I/O-point serves as depot where the stacker crane tour starts and ends). The numbers indicate the sequence in which the stacker crane traverses the tour. The industrial company mentioned operates a large high-bay racking using a stacker crane equipped with an additional buffer location. This device is designed to swap the pallet currently loaded on the stacker crane with a pallet at a storage location. We know from the stacker crane’s manufacturer that other companies operate similar warehouses. These firms are predominantly engaged in sectors such as the metal industry or the production of windows and doors. Since they handle heavy pallets, it is not feasible to use the stacker crane’s increased capacity to transport two pallets at once. Therefore, pallet swaps are the operating mode of choice in such warehouses (Buckow and Knust 2023b, a). Note that this setting can also be used to model other problems. For example, besides the scenario discussed above, it also applies to warehouses with stacker cranes of capacity one when only retrieval requests have to be performed. This is possible because the stacker crane can simply omit picking up a pallet when reaching an I/O-point, while still visiting pallets and I/O-points alternately in the tour. Furthermore, the described problem can be used to model specific transportation problems outside of warehouses, such as transporting patients to health care facilities. In this scenario, different patients are located in different places and a single ambulance, capable of transporting only one patient at a time, must transport each patient to one of several healthcare facilities. The ambulance starts and ends its tour at a given facility, and the goal is to minimize the time it takes to complete the transport of all patients. This can be modeled by our problem, with the patients corresponding to retrieval requests and the facilities corresponding to I/O-points. Fig. 1 Stacker crane tour processing four pallet retrieval requests. Numbers indicate the order of movements 4 J.-N.Buckow et al. Our problem can also be interpreted as a new variant of the bipartite traveling salesman problem ( TSP ). In the bipartite TSP , two node sets of equal size and travel costs between the nodes are given, and the goal is to find a minimum cost tour that visits each node exactly once, where nodes from the two sets must be visited alternately. For more details on the bipartite TSP , we refer to García and Tejel (2017), Kovács etal (2018) and Frank etal (1998). In the case of our problem, we also aim to find a minimum cost tour that alternately visits pallets and I/O-points. However, in contrast to the bipartite TSP , I/O-points are allowed to be visited any number of times, while each pallet must be visited exactly once. Depending on the real-world scenario to be modeled, each pallet may only be allowed to be retrieved at a specific I/O-point. This is the case, for example, if the pallet has to be processed on a machine that is located in a production hall which can only be reached via a specific I/O-point. Similarly, each pallet may need to be retrieved at a specific I/O-point because there a specific truck is loaded. In addition, a sequence may be given in which the pallets have to be retrieved. For example, the machines in the production process may require the pallets in a specific order. Besides the basic problem scenario described above, we hence also study the problem scenarios that the pallet retrieval sequence and/or the assignment of pallets to I/O-points is fixed. 1.2 Literature review A lot of literature has tackled stacker crane scheduling problems to optimize storage and retrieval requests in warehouses with a single I/O-point (Boysen and Stephan 2016). These problems mainly deal with finding an appropriate sequence in which the storage and retrieval requests are processed by the stacker crane. The stacker crane can thereby be operated in two different ways, namely in a single command cycle or in a dual command cycle. In a single command cycle, the stacker crane performs either a single storage or a single retrieval request. In a dual command cycle, the stacker crane performs a combined storage and retrieval request. First, the stacker crane picks up a pallet to be stored at an I/O-point and brings it to an empty location. Afterwards, the stacker crane moves unloaded to the location of a retrieval request and returns the pallet there to an I/O-point. Some modern warehouses (e.g., the industrial company mentioned above) are equipped with a stacker crane classified as a twin shuttle or sometimes also called dual shuttle (Keserla and Peters 1994; Malmborg 2000; Meller and Mungwattana 1997). Because a twin shuttle has an additional buffer, it can perform swap moves where the stacker crane directly swaps the pallet at a storage location with the pallet currently stored in its buffer (Buckow and Knust (2023b, 2023a)). By using swap moves when performing dual command cycles, the unloaded travel can be completely eliminated by directly swapping the pallet to be stored with the pallet to be retrieved. Moreover, note that the handling effort of the dual command cycles only depends on the retrieval requests when using swap moves, because the pallet retrieval locations are used to store the next pallets. However, recall that in the problem setting of the company mentioned above, they are handling heavy pallets, and it 5 Retrieval optimization inawarehouse withmultiple… is hence not possible to combine two storage and two retrieval requests to one command cycle, even with two pallet positions on the stacker crane. There are few studies on the optimization of storage and retrieval requests in warehouses with more than one I/O-point. Nonetheless, the publications on the stacker crane scheduling problems most similar to ours are summarized in Table1, including a brief description of the problem characteristics, their complexity and the solution methods applied. Other complexity results for related problems are presented byBoysen and Stephan (2016). Van den Berg and Gademann (1999) consider a specialized scenario where the input and the output point are separated locations, i.e., all storage requests start at the input point, and all retrieval requests have to be brought to the output point. They assume that the arrival sequence of the storage requests is fixed, and present a polynomial-time algorithm to solve their problem optimally. Both Vis and Roodbergen (2009) as well as Vis and Carlo (2010) consider a container storage with multiple rows each having two I/O-points. On the one hand, Vis and Roodbergen (2009) study the case with a single stacker crane, and they decompose their problem into single-row blocks where all requests are located on a line. Moreover, they combine a linear assignment and a dynamic programming approach to solve their problem efficiently. On the other hand, Vis and Carlo (2010) extend the described setting to the case with two coorperating stacker cranes, and they developed a simulated annealing heuristic for their problem. In the case of two I/O-points and arbitrary positions of the requests, Gharehgozli etal (2014b) present polynomial-time algorithms to minimize the total travel time of the stacker crane. Man etal (2021) study a bi-objective stacker crane scheduling problem to optimize storage and retrieval requests in a warehouse with two I/Opoints. They consider the two objectives of minimizing the total travel time and the total tardiness. Yu etal (2022) present models for the expected travel time in warehouses with two I/O-points and a class-based storage policy, i.e., the storage is partitioned into different classes where only specific pallets are allowed to be stored in each class. Nevertheless, Yu etal (2022) concentrate on warehouse design, and no algorithms for scheduling storage and retrieval requests are presented. Table 1 Overview of publications with similar stacker crane scheduling problems *BB: Branch-and-bound, DP: Dynamic programming, ECM: 𝜖 -constraint method, H: Heuristics, LAP: Linear assignment problem, PT: Patching techniques, SA: Simulated annealing, TP: Transportation problem Publication Problem characteristics Complexity Methods ∗ Van den Berg and Gademann (1999) Separated input and output point Polynomial TP Vis and Roodbergen (2009) Multiple rows each having two I/Opoints Polynomial LAP, DP Vis and Carlo (2010) Two I/O-points and two stacker cranes – SA Gharehgozli etal (2014b) Two I/O-points; arbitrary request positions Polynomial PT Man etal (2021) Two I/O-points; Bi-objective problem – ECM, H Gharehgozli etal (2014a) Multiple linearly arranged I/O-points NP-hard PT, BB 6 J.-N.Buckow et al. Gharehgozli etal (2014a) consider a yard crane scheduling problem with multiple I/O-points arranged linearly both on the landside and seaside. They prove that their problem is NP-hard, but the proof assumes that storage requests have to be scheduled in addition to retrieval requests. Nonetheless, the complexity status when only scheduling retrieval requests in a warehouse with multiple I/O-points remains unclear. Gharehgozli etal (2014a) formulate their problem as a TSP and introduce a branch-and-bound algorithm that utilizes patching techniques to solve it. However, the approach presented by Gharehgozli etal (2014a) primarily exploits the specific distances in container yards, making it unsuitable for our problem setting. Moreover, their algorithm is not designed to handle the specific case that the retrieval I/Opoints arefixed. 1.3 Contribution In this paper, we study different variants of a new stacker crane scheduling problem, which we call the retrieval optimization problem ( ROP ). In the ROP , we are given a warehouse with multiple I/O-points, and a set of retrieval requests to be processed. The goal of the ROP is to schedule all retrieval requests with minimum total travel costs of the stacker crane. As already described above, the ROP has several applications, including the problem setting of the company, which initially motivated our work. In order to schedule the retrieval requests, we have to determine a sequence in which the pallets are retrieved, and it must be decided which pallet is retrieved at which I/O-point. We also consider different problem variants with a fixed pallet retrieval sequence and/or a fixed assignment of pallets to retrieval I/O-points. Even if there are typically two-dimensional warehouses in practice, our approach is more general and can handle arbitrary costs as long as they are symmetric and fulfill the triangle inequality. In contrast to the existing literature, we consider an arbitrary number of I/O-points, arbitrary positions of the requests, and dual command cycles in connection with swap moves are used to pair storage and retrieval tasks. Since swap moves are used, only the scheduled retrieval requests determine the handling effort. Our results show that the ROP is strongly NP-hard as long as the number of I/Opoints is part of the input and the pallet retrieval sequence has to be determined. In contrast, if the number of I/O-points is fixed or the pallet retrieval sequence is already given, the problem becomes polynomially solvable. Moreover, we present efficient transformations of the ROP to the TSP , which opens a rich arsenal of existing solution approaches in the literature, enabling to effectively solve the ROP . The computational study reveals several managerial implications and insights, such as that the stacker crane’s total travel costs can be reduced considerably by allowing the pallets to be retrieved at arbitrary I/O-points instead of fixing them. The remainder of this paper is structured as follows. First, in Sect.2, we provide a formal definition of the ROP and introduce the used notations. Section3 is devoted to theoretical properties: we prove NP-hardness of two variants of the ROP , consider the case that the number of I/O-points is fixed, and investigate the gain of flexible 7 Retrieval optimization inawarehouse withmultiple… retrieval I/O-points. Next, in order to solve the ROP , we present efficient transformations to the TSP in Sect.4. In Sect.5, we reveal extensive computational results for different problem variants. Finally, Sect.6 concludes the paper. 2 Problem definition The ROP can be stated as follows. In a warehouse,n pallets P={p1,…,pn} have to be retrieved, and there arem different I/O-points Θ={𝜃1,…,𝜃m} , where 𝜃depot ∈Θ denotes the depot I/O-point. Each pallet p∈P and each I/O-point 𝜃∈Θ is associated with a location 𝓁(p) and 𝓁(𝜃) , respectively. For the resulting 𝜇=n+m locations L={𝓁1,…,𝓁𝜇} , we have symmetric travel costs c[𝓁i,𝓁j]=c[𝓁j,𝓁i] , fulfilling the triangle inequality c[𝓁i,𝓁j]≤c[𝓁i,𝓁k]+c[𝓁k,𝓁j] for all locations 𝓁i,𝓁j,𝓁k∈L . To express the travel costs between the locations of pallets p,p�∈P and I/O-points 𝜃,𝜃�∈Θ , we also use the simpler notations c[p,𝜃] , c[𝜃,p] , c[p,p�] , and c[𝜃,𝜃�] instead of c[𝓁(p),𝓁(𝜃)] , c[𝓁(𝜃),𝓁(p)] , c[𝓁(p),𝓁(p�)] , and c[𝓁(𝜃),𝓁(𝜃�)] , respectively. Let Π denote the set of permutations of all palletsP, and 𝜋=(𝜋1,…,𝜋n)∈Π be a specific sequence in which the n pallets are retrieved. Moreover, 𝛼=(𝛼(p1),…,𝛼(pn))∈Θ n represents an assignment of the pallets to I/Opoints (where 𝛼(p)∈Θ denotes the I/O-point at which pallet p∈P is retrieved). The goal of the ROP is to find a pallet retrieval sequence 𝜋∈Π as well as an assignment 𝛼∈Θ n of the pallets to I/O-points such that the total travel costs TTC ∶Π×Θ n → ℝ+ of the resulting stacker crane tour are minimized, i.e., where the objective function is defined as Here, it is assumed that the stacker crane tour starts and ends at the depot I/Opoint 𝜃depot . For a solution S∈Π×Θ n , we denote by 𝜋(S) its pallet sequence, by 𝛼(S) the tuple ( 𝛼 (p1),…, 𝛼 (pn)) , and by c(S)=TTC(𝜋(S),𝛼(S)) its costs. In the stacker crane tour corresponding to a solution S∈Π×Θ n , pallets and I/O-points are visited alternately. It is sufficient to consider only such tours, as the costs cannot decrease by visiting additional locations in between due to the triangle inequality. In particular, we can assume that 𝛼( 𝜋 n)= 𝜃 depot in an optimal solution, as we need to return to the depot I/O-point at the end of the tour. Example 1 Consider the instance of the ROP shown in Fig. 2 with n=3 pallets, m=2 I/O-points, 𝜃depot =𝜃1 , and costs c[𝓁i,𝓁j] as displayed in Fig. 2a. A min (𝜋,𝛼)∈Π×Θ n TTC(𝜋,𝛼), TTC( 𝜋 , 𝛼 )=c[ 𝜃depot , 𝜋1 ]+c[ 𝜋1 , 𝛼 ( 𝜋1 )] + c[ 𝛼 ( 𝜋1 ), 𝜋2 ]+… +c[𝜋n,𝛼(𝜋n)] + c[𝛼(𝜋n),𝜃depot] =c[𝜃depot,𝜋1]+c[𝛼(𝜋n),𝜃depot]+ n ∑ i=2 c[𝛼(𝜋i−1),𝜋i]+ n ∑ i=1 c[𝜋i,𝛼(𝜋i)] . 8 J.-N.Buckow et al. feasible solutionS for this instance with 𝜋(S)=(p1,p2,p3) , 𝛼(S)=(𝜃1,𝜃1,𝜃2) , and total costs c(S)=2+2+2+2+6+1+5=20 is shown in Fig.2b. Note that in solutionS, the stacker crane additionally needs to traverse the arc (𝜃2,𝜃1) in order to return to the depot I/O-point 𝜃1 . A better feasible solution S with 𝜋 (S)=(p 2 ,p 3 ,p 1) , 𝛼 (S)=(𝜃 1 ,𝜃 2 ,𝜃 2) , and c(S)=13 is displayed in Fig.2c. In solution S , the last pallet p1 is already retrieved at the depot I/O-point 𝜃1 , eliminating an additional stacker crane movement. Since the pallet sequence 𝜋 and/or the assignment 𝛼 of pallets to I/O-points may be fixed or not, we consider the following four problem variants: (i) both 𝜋 and 𝛼 are fixed, (ii) the permutation 𝜋 is fixed, whereas the assigned I/O-points 𝛼(p)∈Θ for all pallets p∈P have to be determined, (iii) the assigned I/O-points 𝛼(p)∈Θ for all pallets p∈P are fixed, whereas the permutation 𝜋 has to be determined, or (iv) both the permutation 𝜋 and the assigned I/O-points 𝛼(p)∈Θ for all pallets p∈P have to be determined. In case (i), a solution is already fully determined and there is no room for optimization, as the stacker crane’s tour is fixed due to the known permutation 𝜋 and the known assignment of the pallets p∈P to I/O-points 𝛼(p)∈Θ . Case (ii) is also easy to solve, because the pallet permutation 𝜋 is fixed, and the I/O-points to be assigned can be chosen independently of each other, as they are always approached between two fixed locations. Therefore, for all i=1, …,n−1 , we set the I/O-points to (1) 𝛼( 𝜋 i)=arg min𝜃∈Θ{c[ 𝜋 i, 𝜃 ]+c[ 𝜃 , 𝜋 i+1]}, Fig. 2 Example of the ROP 15 Retrieval optimization inawarehouse withmultiple… we present two transformations of the ROP to the TSP . Our computational results in Sect.5 show that these transformations enable to effectively solve the ROP , outperforming intuitive nearest neighbor heuristics. First, we transform ROPAP to the metric TSP (i.e., the costs in the resulting TSP instance are symmetric and the triangle inequality holds). The key idea is to create a node for each pallet, and only determine a retrieval sequence 𝜋 of the pallets by solving the corresponding TSP instance, while an assignment 𝛼 of pallets to their retrieval I/O-points results implicitly. For each pair of pallets pi,pj∈P , we denote by 𝛽(pi,pj) an I/O-point 𝜃∈Θ that minimizes the cost of retrieving pallet pi if pallet pj is processed directly afterwards, i.e., minimizing the cost c[pi,𝜃]+c[𝜃,pj] . We also call 𝛽(pi,pj) an optimal I/O-point to be placed between pallets pi and pj . Based on this, we next define the set of solutions where an optimal I/O-point 𝛽( 𝜋 i, 𝜋 i+1) is always placed between all successive pallets 𝜋i and 𝜋i+1 ( i=1, …,n−1 ), and the last pallet 𝜋n in the pallet retrieval sequence is retrieved at the depot I/O-point 𝜃depot . For ROPAP , note that each solution S∈Π×Θ n can be transformed into a solution S�∈SAP with costs c(S�)≤c(S) by replacing the current retrieval I/O-points with the corresponding optimal I/Opoints to be placed between all two pairs of pallets in the given pallet retrieval sequence, and retrieving the last pallet at the depot I/O-point 𝜃depot . In order to solve ROPAP , it is therefore sufficient to consider only the solution set SAP , as it contains in particular an optimal solution. A transformation of ROPAP to the metric TSP is formulated in Theorem 6. Moreover, each TSP solution of the transformed instance corresponds to an ROPAP solution SAP ∈SAP with the same total costs. In particular, the set of all corresponding TSP solutions must contain a solution which is optimal for ROPAP . Consequently, it is sufficient to solve ROPAP indirectly by using algorithms for the TSP applied to the transformed instance. Theorem6 There is a polynomial-time transformation of ROPAP to the metric TSP , and we have a bijection between the set SAP of ROPAP solutions and the set STSP of TSP solutions. Moreover, each ROPAP solution SAP ∈SAP has the same total costs as its corresponding TSP solution STSP ∈STSP , i.e., c(SAP)=c(STSP) . Proof We are given an ROPAP instance with n pallets P={p1,…,pn} , m I/Opoints Θ={ 𝜃 1,…, 𝜃 m} , a specific depot I/O-point 𝜃depot ∈Θ , and the corresponding 𝜇=n+m locations L={𝓁1,…,𝓁𝜇} with metric travel costs c[𝓁i,𝓁j] for all 𝓁i,𝓁j∈L . We construct a TSP instance with the complete, undirected graph G=(V,E) having n�=n+1 nodes and edge costs c�[v,w] for all v,w∈V as follows. • We have the node set V={v0,v1,…,vn} , where node v0 corresponds to the depot I/O-point 𝜃depot , and for all i=1, …,n , the node vi corresponds to pallet pi∈P . SAP = {(𝜋,𝛼)∈Π×Θ n∣𝛼(𝜋i)=𝛽(𝜋i,𝜋i+1)for i=1, …,n−1 and 𝛼(𝜋n)=𝜃depot}, 16 J.-N.Buckow et al. • The edge costs between pallet nodes and the depot node remain the same as in the ROPAP instance, i.e., for all i=1, …,n , we have c�[ v 0 ,v i]= c [ 𝜃 depot ,p i]. • The edge costs between two different pallet nodes correspond to the cheapest possible way to place an I/O-point in between, i.e., for all i,j=1, …,n with i≠j , we have The resulting TSP costs are symmetric due to the definition above. Moreover, the original ROPAP costs fulfill the triangle inequality, and as discussed next, this property remains also valid for the resulting TSP costs, i.e., c�[vi,vj]≤c�[vi,vk]+c�[vk,vj] for all different i,j,k=0, …,n . • For i=0 and j,k=1, …,n (similarly the case j=0 and i,k=1, …,n ), we have • For k=0 and i,j=1, …,n , we have • For i,j,k=1, …,n , we have Next, we show that there is a bijection between the set SAP of ROPAP solutions and the set STSP of TSP solutions, and that each TSP solution has the same total costs as its corresponding ROPAP solution. On the one hand, each ROPAP solution SAP ∈SAP can uniquely be described by its pallet retrieval sequence 𝜋 , as the assignment of pallets to I/O-points results implicitly (for all i=1, …,n−1 , pallet 𝜋i is retrieved at I/O-point 𝛽(𝜋i,𝜋i+1) , and the last pallet 𝜋n is retrieved at the depot I/O-point 𝜃depot ). On the other hand, each TSP solution STSP ∈STSP can uniquely be described by its pallet node sequence, as the position of the depot node v0 in the tour can be assumed to be fixed. Therefore, we have |SAP|=|STSP|=n! , and for each ROPAP solution SAP ∈SAP , we can construct a corresponding TSP solution STSP ∈STSP and vice versa, just by considering the pallet retrieval sequence. Moreover, we have c(SAP)=c(STSP) for corresponding solutions, because in both cases, the tour starts and ends at a depot I/O-point or depot node, and the costs between two pallet nodes c� [vi,vj]=min 𝜃∈Θ {c[pi,𝜃]+c[𝜃,pj]} . c� [v0,vj]=c[𝜃depot,pj] ≤c[𝜃depot,pk]+c[pk,𝛽(pk,pj)] + c[𝛽(pk,pj),pj ] =c�[v 0 ,v k ]+c�[v k ,v j ]. c�[ vi,vj ]= c [ pi,𝛽 ( pi,pj )] + c [ 𝛽 ( pi,pj ) ,pj ] ≤c[pi,𝜃depot]+c[𝜃depot,pj] =c�[v i ,v 0 ]+c�[v 0 ,v j ]. c� [vi,vj]=c[pi,𝛽(pi,pj)] + c[𝛽(pi,pj),pj] ≤c[pi,𝛽(pi,pk)] + c[𝛽(pi,pk),pj] ≤c[pi,𝛽(pi,pk)] + c[𝛽(pi,pk),pk]+c[pk,𝛽(pk,pj)] + c[𝛽(pk,pj),pj ] =c�[v i ,v k ]+c�[v k ,v j ]. 17 Retrieval optimization inawarehouse withmultiple… vi,vj∈V⧵{v0} also consider the cost of placing an optimal I/O-point 𝛽(pi,pj) between the two corresponding pallets pi and pj . The corresponding TSP instance of an ROPAP instance can be computed in O(n2 ⋅ m) , as mainly for each pair of two pallets, an optimal I/O-point to be placed between them has to be calculated. Converting an ROPAP solution to the corresponding TSP solution and vice versa can be done in O(n) , since only the pallet retrieval sequence 𝜋 needs to be considered (assuming optimal I/O-points to be placed between the pallets are stored in the previous step). We hence conclude that the transformation can be done in polynomial time. ◻ Example 2 Reconsider the ROPAP instance shown in Fig. 2a with n=3 pallets and m=2 I/O-points. The corresponding TSP instance is shown in Fig. 5a, where we have 𝛽(p1,p2)=𝛽(p2,p1)=𝜃1 , 𝛽(p1,p3)=𝛽(p3,p1)=𝜃2 , and 𝛽(p2,p3)=𝛽(p3,p2)=𝜃2 . For the TSP solution STSP =(v0,v2,v3,v1) with costs c(STSP)=13 , we obtain the corresponding ROPAP solution S shown in Fig.2c with costs c(S)=13 . Since the transformation presented in Theorem6 is polynomial, and we have a bijection between the set SAP of ROPAP solutions and the set STSP of TSP solutions, each approximation algorithm for the metric TSP also yields the same performance guarantee for ROPAP . From Theorem6, it hence follows immediately Corollary1. Corollary 1 There is a 3 2 -approximation for ROPAP . Proof We apply the transformation from Theorem6 to the given ROPAP instance and get the corresponding instance of the metric TSP , which in turn is solved by using the algorithm presented by Christofides (1976). For the resulting TSP solution, we compute the corresponding ROPAP solution of the original instance. This procedure yields the same performance guarantee of 3 2 for ROPAP as the algorithm presented by Christofides (1976) for the metric TSP , since we have a bijection between the set SAP of ROPAP solutions and the set STSP of TSP solutions, and each ROPAP solution SAP ∈SAP has the same total costs as its corresponding TSP solution STSP ∈STSP . Furthermore, the procedure can be applied in polynomial time, because creating the corresponding metric TSP instance can be done in O(n2 ⋅ m) , Fig. 5 Example of the costs c�[vi,vj] of the resulting TSP instances according to the transformations presented in Theorems6 and7 18 J.-N.Buckow et al. and converting the resulting TSP solution into an ROPAP solution can be done in O(n) , as shown in the proof of Theorem6. ◻ In the case of ROPP , only the pallet retrieval sequence has to be determined, and we define SP=Π as the set of all possible solutions. As stated in Theorem7, we present a transformation of ROPP to the asymmetric TSP ( ATSP ) with valid triangle inequality. In addition, for each ATSP solution SATSP ∈SATSP of the transformed instance, we have a corresponding ROPP solution SP∈SP with the same total costs and vice versa. The main idea of this transformation is to create a TSP node for each pallet p∈P , and the cost of moving from palletp to p�∈P considers the cost of moving to the specific I/O-point 𝛼(p) approached in between to retrieve palletp before moving to p′ . Note that the resulting costs are asymmetric, since the fixed retrieval I/O-points 𝛼(p) and 𝛼(p�) may differ. Unlike in the case of ROPAP , there does not seem to be an efficient transformation of ROPP to the symmetric TSP , since the assigned pallet I/O-points are given as input. Nevertheless, each possible pallet retrieval sequence of the ROPP instance can be expressed as an ATSP solution for the corresponding transformed instance, and this solution has the same costs as a solution with the same sequence of the original instance. It is thus also sufficient to solve ROPP indirectly by using algorithms for the TSP applied to the transformed instance. Theorem7 There is a polynomial-time transformation of ROPP to the ATSP fulfilling the triangle inequality, and we have a bijection between the set SP of ROPP solutions and the set SATSP of ATSP solutions. Moreover, each ROPP solution SP∈SP has the same total costs as its corresponding ATSP solution SATSP ∈SATSP , i.e., c(SP)=c(SATSP ) . The proof follows a similar idea as the proof for Theorem6 and is presented inAppendix B. Example 3 Reconsider the ROPP instance shown in Fig.2a with n=3 pallets, m=2 I/O-points, 𝛼(p1)=𝛼(p2)=𝜃1 , and 𝛼(p3)=𝜃2 . The corresponding ATSP instance is shown in Fig. 5b. For the ATSP solution SATSP =(v0,v1,v2,v3) with costs c(SATSP )=20 , we obtain the corresponding ROPP solutionS shown in Fig.2b with costs c(S)=20 . Again, each approximation algorithm for the ATSP fulfilling the triangle inequality also yields the same performance guarantee for ROPP , because the transformation presented in Theorem7 is polynomial, and we have a bijection between the set SP of ROPP solutions and the set SATSP of ATSP solutions where corresponding solutions have the same total costs. For the ATSP fulfilling the triangle inequality, Asadpour etal (2010) presented an approximation algorithm with an O(log n∕log log n) performance guarantee. We therefore immediately conclude Corollary2. 19 Retrieval optimization inawarehouse withmultiple… Corollary 2 There is an approximation algorithm with an O(log n∕log log n) performance guarantee for ROPP . 5 Computational results This section presents extensive computational results for the ROP . First, in Sect.5.1, we describe the test instances used in our experiments. Optimal results determined by a branch-and-cut solver for the ATSP are presented in Sect.5.2, where we analyze the effect of different instance parameters on the solution quality. In Sect.5.3, the results determined by four different heuristics are presented. Finally, Sect.5.4 provides insights on the gain of optimization for different ROP variants. We implemented all algorithms inC++, and our experiments were performed on an Intel Core i9-10920X 3.5GHz machine with 64 Bit Ubuntu 20.04 LTS and 64GB RAM. To solve the TSP instances resulting from the transformations presented in Sect.4, we implemented a branch-and-cut solver using CPLEX20.1 and the graph library LEMON1.3.1 (Dezső etal 2011). Our experiments with the branch-and-cut solver were multi-threaded, allowing for simultaneous use of up to ten cores, and we set a time limit of one hour for each instance. However, for the heuristics, the experiments were single-threaded, and average gaps to the best lower bound values of the corresponding instances are reported. For a given solutionS, the percentage gap is calculated according to the formula 100 ⋅ c(S)−LB LB , whereLB denotes the best lower bound of the corresponding instance obtained by CPLEX. All instances and the raw data of all results can be found at http:// www2. infor matik. uos. de/ kombo pt/ data/ rop/. 5.1 Test data To properly evaluate our solution approaches, we randomly generated instances with various parameters based on data provided by the company we collaborate with. This company operates a high-bay warehouse using AS/RS where around n=100 pallets need to be retrieved during a single shift by using m=3 different I/O-points. Their stacker crane can move independently of each other in horizontal and vertical directions, and hence the travel costs between two locations are based on the Chebyshev metric (i.e., the maximum of the vertical and horizontal costs). To gain deeper insights on the ROP , we also generated instances that are more general than the company’s specific problem setting, allowing to examine the influence of some instance parameters. First, the number of pallets to be retrieved or the number of I/O-points may differ in other problem settings. Moreover, in warehouses without AS/RS, stacker cranes typically cannot move independently in horizontal and vertical directions, and therefore other travel cost measures apply. Besides the Chebyshev metric, other realistic travel cost measures in warehouses include the Euclidean (i.e., the length of the direct connection line) and the Manhattan (i.e., the total horizontal plus vertical costs) metric. For example, in unit-load warehouses with forklifts and rectilinear ordered racks positioned on 20 J.-N.Buckow et al. the ground, travel costs can be accurately modeled by the Manhattan metric. In contrast, for warehouses with human pickers and few items stored on the ground, the Euclidean metric seems to be a suitable choice as nearly the direct connection line between two locations can be traversed. In practice, the ordering of I/O-points may be linear, for example, if they are located at the bottom of a shelf for easy accessibility. However, we know from the company we collaborate with that they plan to build a new warehouse on a hill, and to accommodate the different ground levels, the I/O-points need to be ordered at different heights instead of being located on a line. Additionally, there are warehouses located above production or logistic facilities where the I/O-points may possibly be ordered arbitrarily on the ground, such as a carpet manufacturer mentioned by Gharehgozli etal (2014b). Thus, from a practical perspective, both linear and arbitrary orderings of the I/O-points seem to make sense. Based on the previous discussion, we generated a total of160 instances with four parameters. In line with the notation used above, parametern corresponds to the number of pallets to be retrieved, and parameterm describes the number of I/O-points in the warehouse. The ordering parameter specifies whether the locations corresponding to the I/O-points are chosen randomly or are ordered on a line. The metric parameter describes how the travel costs between two locations are calculated, where we consider the Chebyshev, Manhattan and Euclidean metric, respectively. All locations are randomly chosen within a square area having an edge length of 1 000 and are sampled as integer values. To ensure that the instances can be used not only for ROPAP , but also for ROPA and ROPP , we also randomly sampled an assignment 𝛼 of pallets to I/O-points as well as a pallet retrieval sequence 𝜋 . Depending on the problem variant considered, the values of 𝛼 and 𝜋 may be not required. In these cases they are simply ignored. To investigate the influence of specific parameters and to cover a wide range of problem settings, we grouped the instances into three sets In , Im and ICosts . These instance sets are all based on the company’s problem setting, except that certain parameters are varied. Instance set In varies the number of pallets to be retrieved n∈{20, 50, 100, 200, 500, 1 000} , while assuming m=3 different I/Opoints ordered randomly and travel costs resulting from the Chebyshev metric. Instance set Im varies the number of I/O-points m∈{1, 2, 3, 5, 10, 20} , while assuming n=100 pallets to be retrieved, a random ordering of the I/O-points and travel costs resulting from the Chebyshev metric. Finally, instance set ICosts varies both the ordering and the metric parameter, considering all possible combinations of these two parameters while assuming n=500 and m=3 (note that larger instances are needed to get meaningful differences between varying travel costs). For each specified combination of parameters, ten random instances were created. 5.2 Optimal results In a first experiment, we aimed to determine optimal solutions for both ROPP and ROPAP to examine how different instance parameters affect the difficulty of 21 Retrieval optimization inawarehouse withmultiple… solving these problems. In preliminary experiments, the mathematical model presented inAppendix A turned out to be inappropriate to solve ROPP and ROPAP . In order to still obtain optimal solutions, we hence transformed the ROPP and ROPAP instances into their corresponding TSP instances according to Theorems6 and7, respectively. Unfortunately, hardly any exact solvers are freely available to solve the resulting TSP instances, with the Concorde solver developed by Applegate etal (2006) apparently being the only exception. However, it is limited to handle symmetric TSP instances. Since only transformed ROPAP instances are guaranteed to be symmetric, while transformed ROPP instances may result in asymmetric TSP instances, a general ATSP solver is required to solve all instances properly and to enable a fair comparison between all results. To address this issue, we implemented our own branch-and-cut ATSP solver using CPLEX to solve all resulting TSP instances. Our branch-and-cut solver is based on the well-known two-index formulation originally proposed by Dantzig etal (1954). Further details can be found in survey papers such as the one by Roberti and Toth (2012). Moreover, we separate subtour elimination constraints by calculating minimum cuts with the LEMON library implementation of the algorithm proposed by Hao and Orlin (1994). We conducted tests on our branch-and-cut solver to evaluate the impact of a warm-start, i.e., initializing CPLEX with a given solution determined by a heuristic. In Sect.5.3, we evaluate various heuristics to solve the resulting ATSP instances. The modified KarpSteele patching heuristic presented by Glover etal (2001) proved to be the most effective on our transformed instances, and we therefore use it for the warm-start of our branch-and-cut solver. In all experiments with our branch-and-cut solver, a time limit of one hour per instance was applied. Table2 presents the results of the impact of the warm-start on our branch-andcut solver for all160 instances In∪Im∪ICosts combined. The first column indicates whether a warm-start was applied. The remaining columns show the number of feasible solutions, the number of solutions verified as optimal within the time limit, and the actual average computing times in seconds, distinguished by ROPP and ROPAP . As shown in Table2, more instances were verified as optimally solved and the average computation times were lower for ROPP compared to ROPAP , regardless whether a warm-start was used. Although ROPP may result in asymmetric TSP instances in contrast to ROPAP , they seem to be easier to solve. A plausible explanation is that in ROPP only a pallet retrieval sequence 𝜋 has to be determined, whereas in ROPAP additionally an assignment 𝛼 of the pallets to I/O-points has to Table 2 Impact of the warm-start on the branch-and-cut solver for instances In ∪ Im ∪ ICosts ROPP ROPAP Warm-start #Feas #Opt Avg. time [s] #Feas #Opt Avg. time [s] Without 153 153 374.80 130 128 1256.83 With 160 160 2.67 160 139 791.44 22 J.-N.Buckow et al. be calculated. Since the assignment 𝛼 is already fixed in ROPP , a sequence 𝜋 can be better determined. Note that without a warm-start, not for all160 instances feasible solutions could be found for both ROPP and ROPAP as listed in Table2. This is due to the insufficient solving time available to separate all subtour elimination constraints on these instances. In contrast, when using a warm-start, the solver is guaranteed to find feasible solutions for all instances because it has already been initialized with one. Furthermore, the number of instances verified as optimally solved is much larger with a warm-start for both ROPP and ROPAP , while the average computation times decrease considerably. Even if the gaps reported by CPLEX are at most 2% on any instance solved to feasibility, the compelling positive impact of a warm-start emphasizes the value of considering heuristics for ROPP and ROPAP . Due to the high effectiveness of a warm-start, only results with a warm-start are shown below. In Sect.3.1, we proved that both ROPP and ROPAP are strongly NP-hard. Thus, it can be expected that the instance size, measured by parametersn andm, strongly determines the difficulty of solving these problems. Therefore, we investigated how the number of pallets to be retrieved (parametern) and the number of I/O-points (parameterm) impact the results. Tables3 and4 present the results of our branchand-cut solver for instances In and Im , distinguished by parametersn andm, respectively. For both ROPP and ROPAP and each value ofn orm, the number of instances verified as optimally solved, the maximum percentage gap reported by CPLEX, and Table 3 Results of the branch-and-cut solver for instances In distinguished by parametern ROPP ROPAP n#Opt Max. gap [%] Avg. time [s] #Opt Max. gap [%] Avg. time [s] 20 10 0.0000 0.01 10 0.0000 0.04 50 10 0.0000 0.04 10 0.0000 0.19 100 10 0.0000 0.12 10 0.0000 1.56 200 10 0.0000 0.37 10 0.0000 32.78 500 10 0.0000 3.07 7 0.0044 2351.31 1000 10 0.0000 23.52 2 0.0018 2930.42 Table 4 Results of the branch-and-cut solver for instances Im distinguished by parameterm ROPP ROPAP m#Opt Max. gap [%] Avg. time [s] #Opt Max. gap [%] Avg. time [s] 1 10 0.0000 0.15 10 0.0000 0.16 2 10 0.0000 0.11 10 0.0000 0.67 3 10 0.0000 0.12 10 0.0000 1.56 5 10 0.0000 0.11 10 0.0000 1.90 10 10 0.0000 0.09 10 0.0000 42.43 20 10 0.0000 0.09 8 1.3409 214.90 23 Retrieval optimization inawarehouse withmultiple… the average computing times in seconds are shown. Recall that there are a total of ten instances for each value ofn orm. According to the results shown in Table3, all instances were verified as optimally solved for ROPP , regardless of the value of parametern. In contrast, in the case of ROPAP , the time limit of one hour was insufficient to verify some instances for values of n≥500 . However, the gap reported by CPLEX on any instance is far below 0.01% , indicating that the corresponding solutions are at least nearly optimal. Furthermore, the average computing times increase sharply with rising values ofn for both ROPP and ROPAP . These results validate that the parametern has a major impact on the difficulty of solving the problem, even if the given instances are well solvable. Additionally, the values in Table3 confirm that in practice ROPAP is more difficult to solve than ROPP . As can be seen in Table4, all instances were verified as optimally solved in the case of ROPP , independent of the parameterm. Moreover, for ROPP , the computing times are negligible, being far below one second even for larger values ofm. In contrast, for ROPAP , there is a sharp increase in computing times with rising values ofm. Additionally, while all solutions were verified as optimal in the case of ROPAP for m≤10 , two instances with m=20 could not be verified within the time limit of one hour. However, the gaps reported by CPLEX are at most 1.5% . These results show that the parameterm has a large influence on the difficulty of solving ROPAP , while it appears to have less impact on ROPP . Additionally, ROPAP seems to be much more difficult to solve compared to ROPP . Next, we evaluated the impact of different orderings of the I/O-points and travel cost metrics on the difficulty of solving ROPP and ROPAP . For different orderings and metrics, Table5 shows the number of instances verified as optimally solved and the average computing times in seconds for the instances ICosts , distinguished by ROPP and ROPAP . Instances with a linear ordering appear to be easier to solve than those with a random ordering, particularly for ROPAP . For a random ordering, the metric has little influence on the results for both ROPP and ROPAP . However, if the I/O-points are ordered linearly, there are still few differences in the case of ROPP , while the metric has a considerable impact for ROPAP . With ROPAP , when considering linearly ordered I/O-points, instances with Chebyshev metric take the smallest computing times with just a few seconds, whereas instances with Euclidean and Manhattan metric take more than one thousand seconds on average. Table 5 Results of the branchand-cut solver for instances ICosts distinguished by different metrics and orderings of the I/O-points ROPP ROPAP Ordering Metric #Opt Avg. time [s] #Opt Avg. time [s] Random Chebyshev 10 3.07 7 2351.31 Euclidean 10 3.01 8 1929.82 Manhattan 10 3.48 7 2258.06 Linear Chebyshev 10 2.40 10 2.35 Euclidean 10 3.06 9 1328.35 Manhattan 10 3.18 8 1568.05 24 J.-N.Buckow et al. Due to the special structure of instances with linearly ordered I/O-points, these are easier to solve, mainly because the travel costs between pallets and different I/O-points are more similar. This is particularly the case for the Chebyshev metric, where either the horizontal or vertical direction dominates the distance, enabling to reach several I/O-points from a pallet with the same travel costs. In contrast, with the Euclidean and Manhattan metrics and a linear ordering, there are more differences in travel costs between pallets and I/O-points, as these are never completely dominated by either horizontal or vertical distance. However, the results generally reveal the insight that the ROP can be solved well regardless of the cost metric used or the given order of I/O-points. 5.3 Heuristics In a second experiment, we compared some heuristics to solve ROPP and ROPAP . Despite the previously shown good results of our branch-and-cut solver, recall that its sound performance is largely tied to the warm-start with heuristic solutions. Furthermore, the heuristics we used are not only easier to implement than the branchand-cut solver, but also require much less computational time. First, we implemented an intuitive heuristic that solves ROPP and ROPAP by greedily selecting the next pallets and I/O-points to be visited. For ROPP , starting at the depot I/O-point, in each step we choose a pallet with the smallest travel cost from the current I/O-point until all pallets have been visited. When visiting a pallet, the next I/O-point to be traversed is implicitly determined by the fixed assignment 𝛼 in the case of ROPP . In contrast, for ROPAP , the only difference of the intuitive heuristic is that an I/O-point minimizing the travel costs from the current pallet is chosen as next I/O-point to be traversed. Note that the intuitive heuristics for both ROPP and ROPAP can be seen as a special nearest neighbor heuristic, since in each step, a nearest available location is approached. In our experiment, these intuitive heuristics serve as simple baseline approaches that a warehouse planner might employ. We also implemented three TSP heuristics, which can be applied to ROPP and ROPAP instances transformed according to Theorems6 and7, respectively. • Nearest neighbor (TSP-NN): Starting at the node corresponding to the depot I/O-point, a nearest unvisited node is appended to the tour until all nodes have been visited. • Cheapest insertion (TSP-CI): The solution is initialized with a tour consisting only of the node corresponding to the depot I/O-point. Iteratively, an unvisited node that can be inserted with the cheapest insertion costs is inserted at a cheapest insertion position until all nodes have been visited. • Modified Karp-Steele patching (TSP-MKSP): At first, a minimum-cost cycle cover of all nodes is calculated (we solved the corresponding matching problem by using the network simplex algorithm implemented in the LEMON library). Afterwards, the resulting cycles are iteratively patched until only a single cycle remains by evaluating all possible patching options and applying one with the smallest cost increase (Glover etal 2001). 31 Retrieval optimization inawarehouse withmultiple… The formulation(A1)-(A8) models the general variant ROPAP where both the pallet retrieval sequence 𝜋 and the assignment 𝛼 of pallets to I/O-points have to be determined. In order to use that model also for variant ROPP where 𝜋 has to be determined and 𝛼 is already fixed, the equations(A9) need to be additionally inserted into the model. A similar modification can also be performed for variant ROPA , but we omit specifying it explicitly since the variant can be solved trivially in polynomialtime. B. Proof ofTheorem7 Proof We are given an ROPP instance with n pallets P={p1,…,pn} , m I/Opoints Θ={ 𝜃 1,…, 𝜃 m} , a specific depot I/O-point 𝜃depot ∈Θ , for each pallet p∈P a specific retrieval I/O-point 𝛼(p)∈Θ , and 𝜇=n+m corresponding locations L={𝓁1,…,𝓁𝜇} with metric travel costs c[𝓁i,𝓁j] for all 𝓁i,𝓁j∈L . We construct an ATSP instance with the complete, directed graph G=(V,A) having n�=n+1 nodes and arc costs c�[v,w] for all v,w∈V as follows. • We have the node set V={v0,v1,…,vn} , where node v0 corresponds to the depot I/O-point 𝜃depot , and for all i=1, …,n , the node vi corresponds to pallet pi∈P . • The arcs connecting the depot node with the pallet nodes have the same cost as in the ROPP instance, i.e., for all i=1, …,n , we have c�[v0,vi]=c[ 𝜃 depot,pi] . • The arcs connecting the pallet nodes with the depot node have the cost corresponding to move from the pallet’s specific retrieval I/O-point to the depot I/Opoint, i.e., for all i=1, …,n , we have c�[vi,v0]=c[pi, 𝛼 (pi)] + c[ 𝛼 (pi), 𝜃 depot] . • The arc costs between two different pallet nodes correspond to the costs of retrieving the first pallet at its specific I/O-point and moving forward to the second pallet, i.e., for all i,j=1, …,n with i≠j , we have c�[vi,vj]=c[pi, 𝛼 (pi)] + c[ 𝛼 (pi),pj] . As discussed next, the triangle inequality remains also valid, i.e., c′[vi,vj]≤c′[vi,vk] +c′[vk,vj] for all different i,j,k=0, …,n . • For j=0 and i,k=1, …,n (similarly the case k=0 and i,j=1, …,n ), we have (A7) xjki ∈{0, 1}j,k=1, …,n;i=1, …,m (A8) dk to ,d k from ≥0k=1, …, n (A9) n ∑ k=1 xjki =1j=1, …,n;i=𝛼(j ) 32 J.-N.Buckow et al. • For i=0 and j,k=1, …,n , we have • For i,j,k=1, …,n , we have Next, we prove that there is a bijection between the set SP of ROPP solutions and the set SATSP of ATSP solutions, and that each ATSP solution has the same total costs as its corresponding ROPP solution. On the one hand, each ROPP solution SP∈SP can uniquely be described by its pallet retrieval sequence 𝜋 , as the assignment of pallets to I/O-points is fixed. On the other hand, each ATSP solution SATSP ∈SATSP can uniquely be described by its pallet node sequence, as the position of the depot node v0 in the tour can be assumed to be fixed. We hence have |SP|=|SATSP |=n! , and for each ROPP solution SP∈SP , we can construct a corresponding ATSP solution SATSP ∈SATSP and vice versa, just by considering the pallet retrieval sequence. In addition, c(SP)=c(SATSP ) holds for corresponding solutions, because in both cases, the tour starts and ends at the depot I/O-point or depot node, and the costs between two pallet nodes vi,vj∈V⧵{v0} also consider the cost of placing the retrieval I/O-point 𝛼(pi) between the two corresponding pallets pi and pj . The resulting ATSP instance corresponding to an ROPP instance can be computed in O(n2) , as mainly for each pair of two pallets the travel costs have to be calculated and the corresponding retrieval I/O-points are fixed. Converting an ROPP solution to the corresponding ATSP solution and vice versa can be done in O(n) , since only the pallet retrieval sequence 𝜋 needs to be considered. We hence conclude that the transformation can be done in polynomial time. ◻ Acknowledgements The authors would like to thank the editors and two anonymous referees for their constructive and helpful comments. Funding Open Access funding enabled and organized by Projekt DEAL. Data availability All instances and results can be found at http:// www2. infor matik. uos. de/ kombo pt/ data/ rop/. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long c� [vi,v0]=c[pi,𝛼(pi)] + c[𝛼(pi),𝜃depot] ≤c[pi,𝛼(pi)] + c[𝛼(pi),pk]+c[pk,𝛼(pk)] + c[𝛼(pk),𝜃depot ] =c � [vi,vk]+c � [vk,v0]. c� [v0,vj]=c[𝜃depot,pj] ≤c[𝜃depot,pk]+c[pk,𝛼(pk)] + c[𝛼(pk),pj ] =c�[v 0 ,v k ]+c�[v k ,v j ]. c�[ vi,vj ]= c [ pi,𝛼 ( pi )] + c [ 𝛼 ( pi ) ,pj ] ≤c[pi,𝛼(pi)] + c[𝛼(pi),pk]+c[pk,𝛼(pk)] + c[𝛼(pk),pj ] =c�[v i ,v k ]+c�[v k ,v j ]. 33 Retrieval optimization inawarehouse withmultiple… as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/ licenses/by/4.0/. References Applegate D, Bixby R, Chvatal V, etal (2006) Concorde TSP solver. https:// www. math. uwate rloo. ca/ tsp/ conco rde. html Asadpour A, Goemans M, Mądry A, etal (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–389, https:// doi. org/ 10. 1137/1. 97816 11973 075. 32 Boysen N, Stephan K (2016) A survey on single crane scheduling in automated storage/retrieval systems. Eur J Oper Res 254(3):691–704. https:// doi. org/ 10. 1016/j. ejor. 2016. 04. 008 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 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 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 Dantzig G, Fulkerson D, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 2(4):393–410. https:// doi. org/ 10. 1287/ opre.2. 4. 393 Dezső B, Jüttner A, Kovács P (2011) Lemon - an open source C++ graph template library. Electron Notes Theor Comput Sci 264(5):23–45. https:// doi. org/ 10. 1016/j. entcs. 2011. 06. 003 Frank A, Korte B, Triesch E, etal (1998) On the bipartite travelling salesman problem. Tech. rep., Universität Bonn. Institut für Ökonometrie und Operations Research García A, Tejel J (2017) Polynomially solvable cases of the bipartite traveling salesman problem. Eur J Oper Res 257(2):429–438. https:// doi. org/ 10. 1016/j. ejor. 2016. 07. 060 Garey M, Johnson D (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, USA 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–447. https:// doi. org/ 10. 1016/j. ejor. 2013. 09. 038 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–33. https:// doi. org/ 10. 1287/ trsc. 2014. 0562 Glover F, Gutin G, Yeo A etal (2001) Construction heuristics for the asymmetric TSP. Eur J Oper Res 129(3):555–568. https:// doi. org/ 10. 1016/ S03772217(99) 00468-3 Goerigk M, Grün B, Heßler P (2013) Branch and bound algorithms for the bus evacuation problem. Comput Oper Res 40(12):3010–3020. https:// doi. org/ 10. 1016/j. cor. 2013. 07. 006 Hao J, Orlin J (1994) A faster algorithm for finding the minimum cut in a directed graph. J Algo 17(3):424–446. https:// doi. org/ 10. 1006/ jagm. 1994. 1043 Keserla A, Peters B (1994) Analysis of dual-shuttle automated storage/retrieval systems. J Manuf Syst 13(6):424–434. https:// doi. org/ 10. 1016/ 02786125(95) 90066-T Kovács G, Tuza Z, Vizvári B etal (2018) A note on the polytope of bipartite TSP. Discrete Appl Math 235:92–100. https:// doi. org/ 10. 1016/j. dam. 2017. 09. 009 Kuhn HW, Yaw B (1955) The Hungarian method for the assignment problem. Naval Res Logist Q 2(1– 2):83–97. https:// doi. org/ 10. 1002/ nav. 38000 20109 Malmborg C (2000) Interleaving models for the analysis of twin shuttle automated storage and retrieval systems. Int J Prod Res 38(18):4599–4610. https:// doi. org/ 10. 1080/ 00207 54005 02055 32 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–262. https:// doi. org/ 10. 1007/ s1047901903222-1 34 J.-N.Buckow et al. Meller R, Mungwattana A (1997) Multi-shuttle automated storage/retrieval systems. IIE Trans 29(10):925–938. https:// doi. org/ 10. 1023/A: 10185 92017 528 Pazour J, Carlo H (2015) Warehouse reshuffling: Insights and optimization. Transp Res Part E Logist Transp Rev 73:207–226. https:// doi. org/ 10. 1016/j. tre. 2014. 11. 002 Roberti R, Toth P (2012) Models and algorithms for the asymmetric traveling salesman problem: an experimental comparison. EURO J Transp Logistics 1(1):113–133. https:// doi. org/ 10. 1007/ s136760120010-0 Roodbergen K, Vis I (2009) A survey of literature on automated storage and retrieval systems. Eur J Oper Res 194(2):343–362. https:// doi. org/ 10. 1016/j. ejor. 2008. 01. 038 Van den Berg J, Gademann A (1999) Optimal routing in an automated storage/retrieval system with dedicated storage. IIE Trans 31(5):407–415. https:// doi. org/ 10. 1023/A: 10075 45122 755 Vis I, Carlo H (2010) Sequencing two cooperating automated stacking cranes in a container terminal. Transp Sci 44(2):169–182. https:// doi. org/ 10. 1287/ trsc. 1090. 0298 Vis I, Roodbergen K (2009) Scheduling of container storage and retrieval. Oper Res 57(2):456–467. https:// doi. org/ 10. 1287/ opre. 1080. 0621 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–4692. https:// doi. org/ 10. 1080/ 00207 543. 2021. 19345 90