Unidimensional puzzle-based storage systems

Puzzle-Based Storage Systems (PBS), also known as single-level live-cube systems, are very high-density parts-to-person storage systems for unit loads. The PBS design is based on an automated grid composed of cells capable of sliding loads horizontally and vertically. Each cell in a PBS holds one unit load, which is only moved when the load needs to be retrieved or if it needs to be moved out of the way to gain access to another load. The structure of a PBS is based on the classic 15-puzzle children’s game, where 15 numbered tiles need to be slid in a 4 × 4 grid (15 tiles and an empty position) until all the tiles are placed in numerical order. In PBS, the desired loads are moved along the grid by continuously sliding them to an empty position (i.e. an open cell). Since loads need to be slid into open cells, the open cells are commonly referred to as escorts. In PBS, cells may only be moved in the north/south or east/west directions via an escort.

The literature describes two main PBS designs: pop-up and shuttle. In the pop-up design, each cell is equipped with a bidirectional conveyor for sliding loads in one dimension (e.g. vertically) and a bidirectional pop-up conveyor to achieve movements in the other dimension (e.g. horizontally). A typical example of a pop-up PBS includes roller conveyors with pop-up rollers in each cell. The pop-up rollers provide orthogonal movement with respect to the roller conveyor. On the other hand, the shuttle design uses independent material handling equipment (MHE) to move the loads. The MHE may be dedicated to cells or may work in collaboration to pick-up and move the loads upon request. This study focuses on PBS with the pop-up design. Pop-up designs achieve much faster retrieval speeds at the expense of a more rigid configuration (e.g. fixed grid shape and cell size).

Consider the 4 × 4 PBS grid depicted in Figure 1a with cells identified by their column and row numbers –in this order. Each of the sixteen cells of the grid either holds a load or is an escort. This PBS has a single escort (white) that is initially located at the input/output (I/O) point on the southwest corner with grid coordinates (1,1). The input (I) point is where loads enter the PBS and the output (O) point is where loads exit the PBS. In this example, the input and output points coincide. The requested load is represented by the black square in the grid with coordinates (3,3). The remaining fourteen cells, identified in gray, contain other stored loads. Moving the desired load (black) closer to the I/O requires placing the escort in a cell either immediately west or south of the desired load. Although technically the escort does not physically move (as the escort is an empty cell so there is nothing to move), it is conceptually easier to refer to “moving the escort” when describing the process of moving loads to open a cell. In this example, as illustrated by the arrows in Figure 1a, the escort is to be moved to the cell south of the desired load by moving the loads originally in cells (2,1) and (3,1) simultaneously west and then moving the load in cell (3,2) south. The numerals in Figure 1 identify the sequence in which the cell movements are performed. This type of simultaneous movement is known in the PBS literature as block or tandem movements. Notice that it is not possible to move the load in cell (3,2) south at the same time the load in that cell is moving west due to interference. After moving the desired load south, the escort is now the desired load’s original location with coordinates (3,3), as in Figure 1b. The remaining images in Figure 1 depict the sequence of cell movements required to retrieve the desired load via the I/O point.

Arriving loads access the PBS via a set of predefined input point(s) and depart the PBS through a set of predefined output point(s), which may not coincide. As expected, the I/O point(s) in the PBS must be on the edge of the PBS grid. Unlike most storage systems that have predefined aisles, PBS achieve very high-density by being aisle-less. In general, aisles in storage systems are undesirable as nothing may be stored in them. Aisles in traditional storage systems occupy approximately 35% of all the area available for storage (Gue, 2006). In PBS, the escorts may be conceived as movable aisles.

PBS may be controlled by centralized or decentralized control systems. Centralized control PBS require that each cell is connected to a central computer to make decisions considering all the information in the PBS. On the other hand, decentralized control PBS operate by allowing cells to communicate and negotiate as agents with neighboring cells. Centralized control PBS are able to determine optimal control strategies for PBS, at the expense of demanding intensive computing power with efficient algorithms and requiring interconnectivity with all cells. In contrast, decentralized control systems do not require as much computation power and limit information exchange to be on-demand and with neighboring cells. In general, centralized control PBS need to be hardwired and are limited to simpler scenarios (e.g. low-throughput systems with fewer I/O points), whereas decentralized control PBS allow plug-and-play functionality and are scalable to more complex scenarios (e.g. high-throughput systems with multiple I/O points).

The main implementation challenge for PBS is the investment (capital) cost. It is observed that reducing the number of pop-up conveyors would simultaneously reduce the investment cost and operational complexity of PBS, at the expense of a lower system throughput. Interestingly, the cost ratio between unidimensional and bidimensional cells is approximately 2:5 (K. Furmans, private communication, June 21, 2023). Hence, this study challenges the premise that every cell in a PBS must have a pop-up conveyor. The tradeoff of eliminating a pop-up conveyor is that load movements would be limited to one dimension (horizontally or vertically), which could affect the expected retrieval time for a load. Cells without a pop-up conveyor are hereafter referred to as unidimensional cells since movements are limited to bidirectional travel in only one dimension. A PBS that includes unidimensional cells is henceforth termed unidimensional PBS (UPBS).

If the PBS in Figure 1 had unidimensional cells, the proposed retrieval path might not be feasible. For example, if cell in (3,1) was unidimensional only allowing horizontal moves, then the proposed retrieval path would not be feasible. An alternative path would retrieve the load by using the second row and then move south to reach the I/O. Notice that having cell (3,1) as unidimensional also creates a complication for the escort, which would now have to travel from its original position (1,1) $→$ (2,1) $→(2,2)→(3,2)$ for the first load movement or it may take an alternative (and longer) path via (1,1) $→$ (4,1) $→(4,2)→(3,2)$⁠.

The research problem addressed in this paper is to determine how to design UPBS (i.e. PBS containing some cells that are limited to movements in the north/south or east/west). This study is a pioneer in considering UPBS. The basic premise in the study is that limiting some grids to unidimensional movement will improve the business case for implementing PBS in terms of the system cost-to-throughput ratio. The remaining of this paper is organized as follows. Section 2 summarizes the relevant academic literature associated with very high-density storage systems. Section 3 presents a mathematical formulation to determine the best path to retrieve a single load using a single escort with a single I/O point for a centralized control UPBS. The optimization problem is solved iteratively to compute the expected optimal retrieval distance for a UPBS design considering a random load and escort location for a 4 × 4 UPBS. UPBS design insights and cost-to-throughput analyses are derived from these results. In addition, mathematical formulations that extend the problem to consider multiple escorts are presented. Section 4 studies a more complex and practical decentralized control UPBS that retrieves simultaneous loads to multiple I/O points using multiple escorts. A simulation study is performed to evaluate different UPBS designs and gain valuable design insights. Lastly, Section 5 presents the conclusions and future work of this study.

This section presents and discusses the pertinent PBS academic literature by discussing: centralized control PBS, decentralized control PBS, and three-dimensional (3D) PBS.

The first mention of a system that resembles PBS was in Gue (2006) as an example of a very high-density (VHD) storage system. The paper emphasizes the importance of effectively using space and characterizes the best layouts for VHD storage systems. Gue and Kim (2007) is the first publication specifically addressing PBS. The authors estimate the minimum number of moves required to retrieve a load to a corner I/O point using a single escort without considering tandem movement. Taylor and Gue (2008) extend the work of Gue and Kim (2007) by quantifying the effects of using different number and location of escorts on the average retrieval time. It is concluded that having more escorts reduces the expected retrieval time of a single load. Gue and Taylor (2014) introduce a type of aisle-less storage concept labeled concentric rings and compare it to the PBS from Gue and Kim (2007) in terms of retrieval time performance. Kota et al. (2015) extend the work of Gue and Kim (2007) by developing closed-form expressions to minimize the time a PBS takes to retrieve a single load that is randomly located using one and two escorts without tandem movement.

Zhang et al. (2013) propose controlling PBS by implementing the analogous of a class-based storage policy with three classes. Mirzaei et al. (2017) study multiple load retrievals in a PBS using a single escort and find that a method that combines loads for tandem retrieval significantly reduced the average retrieval time. Yalcin et al. (2019) optimally develop retrieval plans for a single load using multiple escorts with tandem movements.

Ma et al. (2022) introduce a beam search algorithm to minimize the total number of moves required for the single-load retrieval problem using multiple escorts. Bukchin and Raviv (2022) develop a 0/1 formulation based on a time-expanded-graph (TEG) for single load retrieval problems involving simultaneous block and load movements. Based on experimental results, they suggest that placing the I/O point in the middle of the edge or employing multiple I/O points is advantageous. Bukchin and Raviv (2023) extend the TEG formulation to include multiple simultaneous retrievals as a variation of the multi-commodity network flow problem.

Other authors considered centralized algorithms for shuttle-based PBS: Raviv et al. (2023) propose shuttle-based PBS using autonomous mobile robots (AMRs), and Sgarbossa et al. (2023) present a puzzle-based movable rack system for picking that allows Euclidian travel.

It is observed that most existing models in the scientific literature consider as input parameters some pre-determined repositioning movements that might not be feasible in UPBS. For example, some papers implicitly assume that escorts move progressively between moves via a 3- or 5-move repositioning. These moves may not be feasible in UPBS. On the other hand, TEG-based formulations, such as the ones in Bukchin and Raviv (2022) and Bukchin and Raviv (2023), may be manipulated by excluding some arcs from their network to resemble UPBS. Preliminary work related to the single-escort UPBS formulation presented in Section 3.1 was included in Carlo and Blanco (2023) without stating how to compute the required travel distances, without detailing how the formulation may be utilized to generated UPBS design insights, or how to quantify the throughput-to-cost tradeoffs of UPBS.

All papers described above assume that the PBS operates with a centralized control system. The next sub-section presents papers assuming decentralized control systems, where the information is requested and passed on-demand from one cell to another, rather than collecting all the information on a centralized system.

The main advantage of decentralized control PBS is the ability to develop plug-and-work modules that serve as grid cells. Notice that centralized controls require connecting each cell to a central decision support system. Furmans et al. (2010) describe new plug-and-work material handling systems that operate using decentralized decisions, including a PBS. Mayer and Furmans (2010) and Gue et al. (2014) describe PBS systems consisting of modularized conveyor-units (equivalent to grid cells) that make decentralized decisions to handle loads while avoiding deadlocks. Similar systems are studied by Krühn et al. (2010) and Krühn et al. (2016) in terms of using decentralized controls based on the status of neighboring modules and developing algorithms to detect and avoid deadlocks. Furmans et al. (2013) extend the work of Gue et al. (2014) by introducing an adapted control algorithm to manage a PBS and prevent deadlocks when a conveyor module fails.

Gue and Uludag (2012) and Shekari Ashgzari and Gue (2021) study PBS for picking operations where each cell may contain totes with multiple loads (i.e. mixed totes). Seibold et al. (2013) focus on using PBS to sort goods under different layouts, assuming a constant work in process (WIP), while Sohrt et al. (2014) incorporate time-windows for PBS used for sorting.

Shirazi and Zolghadr (2021) present an algorithm that allows replenishments from all sides of the PBS grid. Assuming the number of requested loads remains constant, the authors conclude via simulation that depending on the grid size and the number of requested loads, increasing the number of escorts might make the retrieval process more complicated. Alahmad and Ishii (2021) use an A* algorithm to, among other things, demonstrate that square grids perform better than other rectangular shapes. He et al. (2023) use a deep reinforcement algorithm for the multi-load PBS retrieval problem with multiple escorts and randomly placed I/O points.

Other authors have proposed decentralized control for shuttle-based PBS. Alfieri et al. (2012) introduce a version of a shuttle PBS that uses a limited number of Automated Guide Vehicle (AGV) tractors to facilitate rack movements. In their system, the AGVs are not dedicated to the cells, which provide some of the benefits of PBS, without investing too much in automation. Schwab (n.d.) introduces a decentralized control algorithm, LivePath, designed for PBS (referred to as GridFlow systems) operated by AGVs to handle large loads. Instead of relying on path reservations, each AGV determines its next move based solely on the current system state, using a set of priority-based rules to keep the system free of both deadlocks (circular waiting) and livelocks (circular movement). LivePath demonstrated suitable throughput when evaluated against a centralized benchmark, using a mixed-integer programming MIP formulation capable of computing optimal movement sequences for single-AGV scenarios. Trenkle et al. (2013) describe an autonomous system consisting of several individual vehicles that mimic PBS. Gue (2016) propose a PBS for handling containers at a rail-to-rail hub for the Physical Internet (PI or π). Sohrt and Overmeyer (2020) study a routing algorithm designed for decentralized and controlled modular conveyors synchronized through the network, with the aim to reserve routes by exchanging messages. Seibold et al. (2022) present a decentralized controls system based on the principle of logical time.

Furmans and Gue (2018) provide a general framework for material handling modules, which can store relevant information, contributing to decision-making, and then controlling the execution of these decisions.

The PBS concept has been further extended to include a third dimension with up/down movements. Zaerpour et al. (2010) and Zaerpour et al. (2012) are the first to study PBS in three dimensions, called live-cubes, which can be seen as placing several PBS one on top of the other, connected by a lift. Zaerpour et al. (2017a) propose an evaluative framework to compare different live-cubes system configurations, while Zaerpour et al. (2017b) and Zaerpour et al. (2017c) implement a class-based policy for a live-cubes system. Yu and Koster (2012) investigate storage and retrieval sequencing problems in 3D PBS. Hao et al. (2015) develop models for designing 3D compact storage systems. Other studies have focused on automated parking systems (e.g. Wu et al. (2019), Siddique et al. (2021)).

The only published work that implicitly assumes UPBS is Furmans et al. (2013), which modifies the decentralized adapted controls algorithm from Gue et al. (2014) to continue operating even if some north/south or east/west conveyors fail. In this study the system is not designed to be a UPBS, but rather behaves as one when conveyors fail. The authors report, as an example, that based on an agent-based simulation two failed north/south conveyor failures in the same row have a significantly greater impact on the throughput than two north/south conveyor failures in the same column. The main difference between Furmans et al. (2013) and this paper is that they have an algorithm to cope with unreliable conveyors, whereas this study seeks to determine the placement of unidimensional cells in a UPBS. A more detailed literature review on PBS may be found in Blanco (2023).

Consider an $m×n$ UPBS grid operating with a centralized control system. The problem under study seeks to determine the best path to retrieve a predetermined load from its original location in the grid to the I/O point with the least amount of horizontal and vertical load movements. The following modeling assumptions are made:

1. The initial location of the requested load is known

2. There is only one I/O point, located in any location around the edges of the grid

3. The travel distance between locations is known and corresponds to rectilinear travel considering unidimensional cells

4. Each horizontal or vertical movement is of one distance unit (DU)

5. Loads may only move via escorts

The modeling assumptions made are realistic for a PBS if the performance metric is associated with travel distances, as in our case. However, from a temporal perspective it would be important to incorporate the time delay experienced by loads as a consequence of the conveyor pop-up times (i.e. the time it takes pop-up conveyors to be risen or lowered to enable orthogonal movements). For example, the FlexConveyor in Next Intralogistics (n.d.) requires 0.3 s to lift up or lower down (i.e. 0.6 s per complete lift-return cycle). Clearly, from a temporal perspective, the orientation of the PBS becomes relevant and the problem becomes more complicated.

The UPBS retrieval problem may be formulated as a mathematical program. Section 3.1 presents a linear program (LP) formulation for the single-escort problem and Section 3.2 presents a 0/1 formulation for the multi-escort problem.

The following nomenclature is defined for the LP formulation:

Sets

• $N$ = set of all (grid) cell locations, $N={1,…,|N|}$

• $Jk$ = set of neighborhood locations for cell location $k$⁠, $Jk={1,…,|Jk|},k∈N$

Indices

• $i$ = location of the escort at the beginning of a movement, $i∈N$

• $k$ = location of the escort at the end of a movement; which coincides with the location of the load to be retrieved, $k∈N$

• $h,j$ = last cell location visited by the escort before reaching location $k$⁠, $(h,j∈Jk)$

Parameters

• $s$ = initial location of the load to be retrieved, $s∈N$

• $r$ = location of the I/O, $r∈N$

• $dijk$ = minimum distance for the escort to move from location $i∈N$⁠, using intermediate location $j∈N$⁠, to reach the load located at $k∈N$⁠. The intermediate location is necessary to ensure the minimum distance does not include going directly from location $i$ to location $k$⁠, as this would imply that the load is moved backwards in the process.

• $djs$ = minimum distance for the escort to move from its initial location to the load’s initial location $s∈N$ through neighborhood location $j∈N$ in DUs (note the index of the escort’s initial location is suppressed)

Decision variables

• $yj$ = Binary variable equal to 1 if escort moves from its initial location to $s∈N$ through location $j∈Js$⁠, zero otherwise. This variable is relaxed in the formulation.

• $xijk$ = Binary variable equal to 1 if escort moves from location $i∈N$ to the load’s location $k∈N$ via intermediate location $j∈Jk$⁠, zero otherwise. This variable is relaxed in the formulation.

(SE)

s.t.

The objective function of the single escort formulation (SE) in (1) minimizes the number of movements from the escort’s initial location to the load’s initial location (the first term in the objective function) and all the escort movements from there on until reaching the I/O. Referencing Figure 1, the first term in the objective function would capture the escort movements from its initial location (1,1) to the loads initial location (3,3). The remaining escort movements would be captured by the second term of the objective function. Since an escort movements eventually lead to a load movement, the objective function records the total number of movements required to retrieve the load. Further, since the horizontal and vertical move velocities are assumed constant, the objective function is associated with the total load retrieval time. Therefore, a lower number of total movements to perform a retrieval implies lower retrieval times, which in turn imply a higher UPBS system throughput, which is what this study ultimately intends to quantify. The formulation can consider the case where cell movement is limited to one at a time (a.k.a. load movement) or can allow tandem movements by manipulating the escort travel distances. Also, the formulation allows the I/O to be located at any grid cell. Constraint set (2) ensures that the escort moves from its initial location exactly once. The initial location of the escort is not explicitly specified but is implicitly included in $djs$⁠. It is noted that if the escort travels to any location via the I/O, the load will end up at the I/O, which concludes the retrieval process. Constraint set (3) ensures the escort repositions for the second load movement, which starts at the escort’s ending location after the first load movement (i.e. the load’s initial location) and ends at the intermediate location used to reach location $s$ in the load’s first movement. Constraint set (4) is a flow conservation constraint that ensures that if the escort moves a load at location $k$⁠, the next escort movement needs to start at $k$ or the load must have been delivered at the I/O (i.e. intermediate location $r$ was visited). Constraint set (5) covers a special case when the load is delivered to the I/O on the first move. Constraint sets (6) and (7) define the decision variables. Intuitively, the decision variables should be binary in (6) and (7); however, since the SE formulation is associated with the min-cost flow problem in a node-arc incidence matrix of a directed graph, as represented in Figure 2, the coefficients associated with the restrictions are known to create a Totally Unimodular (TU) matrix. Hence, the decision variables may be relaxed in the SE formulation.

The next sub-section describes the methodology recommended for determining how to obtain the distances for an UPBS.

The SE formulation in Equations (1–7) assumes that values of $djs$ and $dijk$ are known. These parameters correspond to the minimum distances (measured in number of movements) required to travel within the UPBS. To obtain these parameters a modified version of the Floyd–Warshall (F–W) algorithm [44, p. 251] may be run a priori. The F–W algorithm simultaneously finds the shortest path between all pairs of nodes (⁠$V$⁠) with arcs (⁠$E$⁠) in a network $G(V,E)$ by efficiently solving Dijkstra’s algorithm recursively. The complexity of the F–W algorithm is O(⁠$n3)$⁠.

In this study, the UPBS grid is modeled as a directed graph $GUPBS(V,E)$⁠. The nodes $i∈V$ of the graph represent the grid cell locations and the $(i,j)∈E$ edges determine if a movement between the cell locations is allowed for the UPBS. As shown in Figure 2, in a regular PBS all cells that are not at the edge of the grid will have four neighbors, one in each direction. Non-corner edge cells will have 3 neighbors, and corner cells will have only 2.

Further, since the distance parameter $dijk$ represents the minimum distance to travel in the UPBS network from $i→j→k$ without traversing directly from $i→k$⁠, the F–W algorithm has to be modified. To understand the reasoning behind the required modification, assume that an escort in location 6 of the PBS in Figure 2 will be used to move a load in location 10. Clearly, by performing this movement, the load would travel southward from location 10 to location 6. After this movement, the load would end in location 6 and the escort in location 10. Further, assume the next movement of the load was determined to be once again southward to location 2. Then, to ensure a southward movement of the load, the escort will have to travel from location 10 to location 6, via location 2 (10 $→2→6$⁠). If one allows the escort to travel using arc $(10,6)$ (i.e. the $i→k$ movement that we seek to prohibit), then as the escort travels down, the load travels up back to its original location 10. For this reason, the network in the F–W algorithm needs to be modified to exclude the arc $(i,k)$ when computing $dijk$⁠.

The corresponding network graph for UPBS would also exclude the arcs not allowable for unidimensional cells, as shown in the example in Figure 3. In Figure 3, the bi-dimensional grids are presented in gray and the unidimensional grids only include the allowable move direction. Note that in the UPBS example provided excluded arc $(2,6)$ as grid 2 is unidimensional allowing movement only in the horizontal dimension.

To find $dijk$⁠, the F–W algorithm was run for each $(j,k)$ pair with a special network $G(j,k)(V,E)≐GUPBS(V,E)\(k,j)$ (i.e. the UPBS network excluding arc between $k→j$⁠). As described before, if edge $(k,j)$ is included in the network, there is a possibility that the shortest path from $i→j$ goes through $k$⁠; implying that the escort passes through the load location in order to be positioned, and in the process moves the load backwards away from the I/O. Let the shortest path solution from $i→j$ the F–W algorithm in network $G(j,k)(V,E)$ be $dij(j,k)$⁠. Then,

This sub-section uses the SE formulation iteratively to obtain design insights for UPBS. The F–W algorithm modification and the SE formulation were coded in Python, which calls the Gurobi Optimizer v9.1.2® to solve the LP. The experiments consider a 4 × 4 UPBS grid. The PBS grid is mapped with location 0 in the lower left corner with coordinates (1,1), with location numbering increasing to the east, then north. For example, location 1 has coordinates (2,1) and location 4 has coordinates (1,2). The I/O is assumed in location 0. This assumption is consistent with papers, although Bukchin and Raviv (2022) suggest that the I/O should be located in the middle of an edge as it reduces the expected retrieval distance for loads.

The experimental methodology starts assuming the requested load is in location 1. The SE formulation is then solved considering that the escort is in each of the 15 possible locations (16 total cells, minus the load’s initial location). The average of the retrieval distances represents the expected retrieval distance for a PBS, given the requested load is in location 1. For the load in location 1, the expected load retrieval distance (E[RD]) was 2.80 DU, as shown in Table 1. This process was repeated for each possible load location (15 total as the load in the I/O was excluded). A total of 15 × 15 = 225 instances were run. The average of the 225 instances is the average expected load retrieval distance (⁠$E[RD]̅PBS$⁠) for the PBS. Table 1 summarizes the results for the traditional (bidimensional) PBS which serves as a baseline for the number of moves required to retrieve the load. The average expected load retrieval distance for the PBS (⁠$E[RD]̅PBS$⁠) is 9.31 DU.

The experiment continues by considering incorporating one unidimensional cell at a time to the system. Incorporating one unidimensional cell at a time is an iterative greedy approach to find a good (yet not necessarily optimal) solution. Only 12 of the 16 cells are considered as potential unidimensional cells given that corner cells may not be unidimensional because it would be impossible for a single escort to remove a load from a corner in those scenarios. For example, the first potential unidimensional cell to be considered is the one in location 1 (with coordinates (2,1)) in the direction that precludes loads from moving in the east/west dimension. (Recall that the I/O is in location 0.) For this UPBS the average expected load retrieval distance is obtained as before by allowing the escort to be in all other cells. The second potential unidimensional cell is the same cell location (location 1) but limiting the north/south dimension. The third potential unidimensional cell is location 2 with limited dimension east/west. In a 4 × 4 PBS grid there are 12 cells that may be unidimensional (four corners excluded), and the unidimensional cells may be in one of two orientations, so a total of 24 layouts are considered. The average expected optimal retrieval distance for the 24 layouts is compared. The unidimensional cell (and orientation) with the minimum expected optimal retrieval distance is considered the most appropriate one to incorporate as the lowest $E[RD]̅$ will provide the highest UPBS throughput among all possibilities.

Given that the best unidimensional cell is implemented, the experiment continues to explore incorporating a second unidimensional cell. At this point, only 22 unidimensional cells are considered (corners and the first unidimensional cell are excluded) for the second unidimensional cell to implement. After the second (Taha, 2006) unidimensional cell was selected based on their $E[RD]̅$⁠, a third unidimensional cell was identified, and so on. Figure 4 summarizes the results of expected optimal retrieval distance as a function of the number of unidimensional cells incorporated. Figure 4 may be interpreted as, by implementing the best unidimensional cell, the expected retrieval distance increases by 2.53% over the original PBS (which is the baseline). After implementing two unidimensional cells, the average expected retrieval distance increases by 5.30% over the PBS. As stated earlier, the proposed strategy that incorporates one unidimensional cell at a time does not guarantee optimality of the resulting UPBS design as not all possible combinations of unidimensional cell designs are considered. On the other hand, the iterative greedy approach is expected to yield good solutions.

It can be observed from Figure 4 that implementing three (of the possible 12) unidimensional cells increases the expected optimal retrieval distance by less than 10%, when compared to the bidimensional PBS. Considering four unidimensional cells affects the expected optimal retrieval distance by less than 15%. With six unidimensional cells the expected optimal retrieval distance increase exceeds 20%.

Figure 5 depicts the final layout with as many unidimensional cells as possible. The bi-dimensional grids are presented in gray and the unidimensional grids only include the allowable move direction. The boxed number included in the unidimensional cells indicates the stage in which it was incorporated (1 being the first unidimensional cell added). This number also corresponds to the abscissa in Figure 4. The maximum number of unidimensional cells is 8. Adding a ninth unidimensional cell renders an infeasible design as the I/O would be unreachable from some cells. There were instances where two unidimensional cells resulted in the same expected retrieval distance; in those cases, the more intuitive choice was selected by hand. In all these cases it was observed that the unidimensional cell not selected was selected in the next stage.

The UPBS layout in Figure 5 appears to have created north-south corridors in the first and last columns and east-west corridors in the other columns. This layout may be used to guide the design of UPBS considering the tradeoff between cost and expected retrieval distance from Figure 4.

To quantify the cost-to-throughput tradeoff of UPBS, let $cb$ be the fixed cost of each bidimensional cell (or cell module). Assuming a unidimensional: bidimensional cell cost ratio of approximately 2:5, the 4 × 4 grid design with 3 unidimensional cells will cost $1.8cb$ less than the PBS, at the expense of an $E[RD]̅$ increase of by 9.17%, or equivalently, a 8.34% average reduction in system throughput.

When extrapolating the design insights for larger PBS grids one would expect a similar pattern; corner cells bidimensional, non-corner edge cells would be the first to be considered unidimensional, and corridors will be created for loads and escorts to navigate. Figure 6 presents the hypothesized UBPS layout design progression for a single-escort 5 × 5 grid design.

For a 5 × 5 UPBS, the first two cells to become unidimensional should be the ones adjacent to the corner cells in the top row, consistent with the empirical results for the 4 × 4 design. Notice that the first unidimensional cell with coordinates (5,4) in Figure 6 barely has an effect on the retrieval of loads. Similarly, incorporating the second unidimensional cell with coordinates (2,5) only limits the retrieval flow of a few loads that now are forced to travel in the horizontal direction. Since cell with coordinates (2,5) becomes unidimensional, there is little value-added in allowing cell (2,4) to have vertical movement. The fourth cell to be unidimensional should be the one with coordinates (5,2) as the last column mainly becomes a vertical corridor. Preferring cell with coordinates (5,2) to the one in (5,3) is to allow the escort to escape the corridor more easily. Figure 6 presents the hypothesized sequence for incorporating unidimensional cells. As in the 4 × 4 case, more unidimensional cells may be incorporated, at the expense of throughput. These design insights may be extrapolated for designing larger single-escort UPBS.

Unfortunately, the LP for the SE formulation cannot be directly extended to the multi-escort problem. Instead, the 0/1 formulation based on a time-expanded graph (TEG) from Bukchin and Raviv (2023) may be modified to consider UPBS. The required modification eliminates from the TEG graph those edges corresponding to unidimensional cells. The formulation already allows individual or tandem movements and has the makespan (equivalent to the load retrieval time for a single-load instance) as a weighted term in the objective function. The modified formulation is not included for practicality. Clearly, the TEG formulation may also be used for the single-escort problem. However, the SE formulation presented is much faster. The main limitation of the TEG formulation is its sensitivity to an input parameter $T$⁠, which is an upper bound on the maximum number of steps to retrieve the load. If $T$ is not large enough, the load would not have enough time to exit the system; if $T$ is too large, the runtime to solve the TEG grows quickly. An alternative to obtain an upper bound for the $T$ parameter in the TEG formulation is to solve the single escort (SE) formulation to determine the number of movements required to retrieve the load.

An alternative linear MIP formulation for the multi-escort problem is presented in Appendix A. The formulation, labeled ME, finds the optimal cell movements to retrieve a load, given that the retrieval path is known. The ME formulation may use the resulting retrieval path from the SE formulation, in which case the solution would not be guaranteed to be globally optimal. However, it would provide a faster solution than the TEG formulation. Unfortunately, experimental results such as the ones from Section 3.3 for the multi-escort problem would require that all combinations of the initial escort locations be considered and the required runtimes become impractical even with two escorts. Since the focus of this paper is on the design of UPBS, no experiments were performed to compare the two alternatives for solving the single-load multi-escort UPBS.

In general, UPBS should be designed assuming multiple escorts, as they are simply unused storage capacity. Therefore, the number of escorts in the UPBS is expected to change over time. It is hypothesized that UPBS designs based on insights from the single-escort case should to be effective for multi-escort UPBS. In theory, for multi-escort UPBS, the escorts may collaborate to retrieve a load from a unidimensional corner cell. However, no UPBS should have unidimensional corner cells as it might become inoperable when storage capacity is at maximum (i.e. a single escort is left). Interestingly, if multiple loads are retrieved simultaneously, then the distribution of escorts to retrieval loads becomes an important factor. Results from Mirzaei et al. (2017) suggest that retrieving multiple loads in tandem is effective. Also, results from Bukchin and Raviv (2022) suggest that retrieval times for retrieving a single load with multiple loads improve up to the fourth escort – beyond that it becomes negligible. Therefore, it is possible that the optimal retrieval strategy evenly distributes escorts among retrieval loads and then seek to merge them at some point in the retrieval path so all escorts may collaborate to retrieve them in tandem. Interestingly, the UPBS design proposed in Section 3.3 based on empirical results tends to create corridors, which should serve as merging points to retrieve loads in tandem.

In practice, PBS store and retrieve multiple loads in parallel using multiple escorts and I/O points. Although the TEG model from Bukchin and Raviv (2023) may be modified to allow simultaneous retrievals, obtaining design insights using the model is limited given the complexity of the experiments.

Fortunately, Krühn et al. (2016) provide a decentralized control algorithm to simultaneously replenish and retrieve multiple loads in a PBS using multiple escorts and I/O points in a manner that avoids deadlocks even when some PBS cells conveyors fail (i.e. unreliable conveyors). This section will use their algorithm to develop managerial insights for the design of UPBS. Unfortunately, Furmans et al. (2013) does not provide enough information to validate a simulation using their algorithm. However, their approach is a straightforward extension of the decentralized algorithm used in Gue et al. (2014), which does provide empirical results that may be used to validate a simulation of their approach. Hence, the method employed is to replicate the decentralized algorithm in Gue et al. (2014) and validate it against their results. At that point, the decentralized algorithm can be easily extended following the description in Furmans et al. (2013).

In general, Gue et al. (2014) proposes a decentralized algorithm that requires at least one escort per row. The PBS input points are the row of cells at the top of the grid and the output points are the row of cells at the bottom of the grid. The algorithm allows multiple requests at the same time and assumes that exiting loads are immediately replenished with a new load that needs to move to the row of origin of the retrieved load. Furmans et al. (2013) extend this work by considering that some cells fail in a particular dimension for a random amount of time, until they are repaired. Their algorithm maintains the PBS running without deadlocks until repairs occur.

Our implementation of the decentralized algorithm in Gue et al. (2014) was done in Python using the Mesa package. The resulting code was validated visually and pushed to the limit in terms of required throughput to confirm that the algorithm avoids deadlocks as suggested by the authors. At that point, experiments were conducted with the following modeling assumptions:

1. The PBS grid dimensions are 12 $×$ (12+ $k$⁠) cells

2. Once a load is requested, it must travel to any cell in the bottom row of the PBS (i.e. an output point), where it will immediately exit the PBS.

3. The northernmost row of the PBS corresponds to the replenishment row. Once a load exits the system, a new replenishment load is immediately created and assigned to the input point with an available escort, and if none is available, the replenishment load is assigned to a random input point.

4. Replenishment loads are to be stored in the row of origin of the corresponding retrieval request.

5. When initiating a retrieval request, the system selects randomly from among loads not currently requested, which can already be in their assigned (home) row or still in transit to their home from the input point.

The Python code runs for 5,760 time steps (corresponding to an 8-h-shift and a 5 s per time step cycle time), considering a warm-up period of 200 steps and 30 replications of each run, as done in the experiments of Gue et al. (2014). Figure 7 presents the average throughput of the PBS considering 1, 2, and 3 escorts per row (labeled $k$ to use their notation) under different number of active requested loads (i.e. average WIP per their notation).

Figure 7 closely resembles the results from Figure 8 in Gue et al. (2014) for the same experiments. There is a slight deviation between our results and the results from Gue et al. (2014) when the WIP exceeds 110 active loads, corresponding to 76.39% of the total loads being simultaneously requested. It is suspected that the discrepancy corresponds to an interpretation of how to assign input points to replenishment loads. Since the discrepancy favors our implementation, the matter was not investigated further. It is concluded that the Python implementation validates against the AnyLogic simulation results from Gue et al. (2014). The Python implementation was then extended to include the modifications described in Furmans et al. (2013). The only difference from the implementation from Furmans et al. (2013) is that they assume the unreliable cells fail randomly, whereas in our model, the cells may be unidimensional by design. Henceforth, the Python simulation is referred to as the UPBS simulation.

The UPBS simulation was run iteratively to evaluate different UPBS designs. The experiments consider a 12 × 13 UPBS grid with $k$ = 1 escorts per row (i.e. 12 escorts in total). Higher level of escorts per row were not considered as PBS are designed for very high-density. Gue and Kim (2007) suggest that PBS become required for storage densities above 90%. The WIP levels (i.e. the number of active requested loads) considered were 1, 10, 20, and 30.

Given that the input points are on the top row and output points are on the bottom row, it was observed that eliminating north-south movements for any cell is highly disadvantageous compared to eliminating east-west movements. Hence, only eliminating east-west movement capability was considered (i.e. unidimensional cells only include north-south movements) in the experiments.

Initially, a traditional (bidimensional) PBS design was run with the UPBS simulation to establish a baseline in terms of the number of horizontal movements (i.e. horizontal movements of requested or non-requested loads) that move through each cell. The average number of times (based on 30 runs performed) a load moves horizontally through each cell is presented as a heatmap for different WIP levels in Figure 8. The heatmaps serve as a visualization tool to identify the cells with more horizontal movements (red) and those with less (green). Cells with heatmap gradient of green are considered good candidates for unidimensional cells.

For example, Figure 8b (⁠$k$ = 1 and WIP = 10) suggests that the cell with an average number of horizontal movements of 1,392 (cell location (1, 12)) is the best candidate to implement as a unidimensional cell. Notice that this implies that this cell is the least used. Once the best unidimensional cell was implemented, the experiment continued by exploring the implementation of a second unidimensional cell (assuming the UPBS now included the previously implemented unidimensional cell). Therefore, only 155 (155 = 12 $×$ 13$−$ 1) unidimensional cells are considered (the first unidimensional cell implemented is excluded). Once the second unidimensional cell is selected, a third unidimensional cell is identified, and so on.

Given the order in which unidimensional cells were incorporated, it was possible to identify a pattern. Once a unidimensional cell was incorporated, the remainder of the cells in that row became unidimensional. This result was corroborated empirically through multiple experiments. Hence, the experiment continues by implementing one unidimensional row at a time for each WIP level until the system throughput percent difference compared to the bidimensional PBS exceeded 10%. Table 2 summarizes the results of the system throughput as a function of the number of unidimensional rows incorporated for each WIP level. Figure 9 can be interpreted as, for WIP = 1, implementing the best unidimensional row, the throughput increases by 5.69% with respect to the original PBS. After implementing two unidimensional rows, the throughput increases by 7.77% over the PBS. With the addition of three and four unidimensional rows the throughput increases in the proportion corresponding to 9.82% over the original PBS.

Results indicating that implementing UPBS cells increases throughput is counterintuitive. The reason for the throughput increase is the gridlock prevention strategy from the decentralized algorithm from Furmans et al. (2013) as the algorithm “sacrifices” loads immediately south of the requested load under some circumstances to prevent gridlocks by creating an escort at the bottom of the column. In the simulation, the sacrificed load is not included in the throughput calculations and the load is immediately replenished to the system through the input point. However, the efficiency of a sacrifice load in generating escorts in the proper column (notice that east/west movements might be limited) results in an increase of throughput. Technically, the simulation results suggest that it is very efficient in terms of throughput to remove all loads south of the requested load and send them back to the system as replenishment. Without the arbitrary 10% throughput increase threshold, the system is expected to continue incorporating unidimensional cells until the entire system is unidimensional, at which point the UPBS will resemble an automatic dispenser. In practice, this strategy would be limited by the conveyor load capacity going from the output to the input points as it would eventually block the system.

It can be observed from Table 2 and Figure 9 that for a WIP = 10 implementing the best unidimensional row out of the possible 156 possible cells increases the throughput by less than 5% when compared to the bidimensional PBS. That is, by implementing 8.33% of the potential unidimensional cells, the throughput increases, on average, by 4.54%. Considering two unidimensional rows increased throughput by less than 4%. With five unidimensional rows, the throughput increases by 9.5%.

Figure 10 depicts the heatmap for the final UPBS design with as many unidimensional rows as possible for $k$ = 1 and different WIP levels. The unidimensional grids presented (white with the number 0) only allow north/south movements. The number included to the left of each unidimensional row indicates the stage in which they were incorporated (1 being the first unidimensional cell row). This number also corresponds to the abscissa in Figure 9. The maximum number of unidimensional cells depends on the WIP level. Note that in Figure 9, the stage in which the percentage difference in throughput increased by 10% or more was included for each WIP level, so in the final heatmap layouts (Figure 10) this iteration is not considered.

The pattern for selecting unidimensional cells in Figure 10a is evident – i.e. sequential from the top and full rows become unidimensional. The UPBS layouts in Figure 10b seem to have created horizontal corridors between unidimensional rows to facilitate north-south movements. For WIP = 20 (in Figure 10c) the only unidimensional rows that may be incorporated and still remain under the threshold value of 10% is the third and then the first from the top. Interesting, this leaves a horizontal corridor in the second row from the top to favor replenishments. Clearly, the quantity of replenishments is directly proportional to the WIP levels. Hence, the horizontal corridor between unidimensional rows intuitively makes sense to position inbound loads. Lastly, for WIP = 30 two rows were left as corridors between unidimensional rows. The logical argument for WIP = 20 also intuitively justifies the result. We can safely state that for higher WIP levels, the first unidimensional row would be among the first 4 rows from the top. Clearly, the number of unidimensional rows depends on the trade-off between cost and throughput.

This study considers PBS where some cells are limited to horizontal or vertical movements (i.e. unidimensional cells). PBS with some unidimensional cells is referred to as UPBS. This study presents a LP formulation to find the optimal load retrieval path using a single escort in a UPBS. The LP is solved recursively to determine the expected optimal retrieval distance for a layout considering a random load and escort location for a 4 × 4 PBS. The unidimensional cell with the least impact on the expected optimal retrieval distance is incorporated into the design, and the process is repeated to progressively determine the next unidimensional cells to incorporate. The maximum number of unidimensional cells that could be implemented was 8 cells. At that point, no more unidimensional cells may be added as some cells became unreachable by the escort. It is concluded that a layout including 3 unidimensional cells (25% of the candidate unidimensional cells) affected the expected optimal retrieval distance by less than 10%, compared to the bidimensional PBS. Adding four unidimensional cells (33% of the candidate unidimensional cells) affected the expected optimal retrieval distance by less than 15%. Considering six unidimensional cells further increased the expected optimal retrieval distance by less than 20%. As an example of the cost-to-throughput tradeoff, a PBS with 3 unidimensional cells would have a cost reduction, compared to the bidimensional PBS, of 1.8 times the capital cost of a bidimensional cell, at the expense of an 8.34% average reduction in throughput. It is argued that multi-escort UPBS designs should be similar to the ones empirically produced for single-escort UPBS.

A modification from the TEG-based formulation in Bukchin and Raviv (2023) and a new MIP formulation that assumes the path of the load is known were presented for the multi escort problem to retrieve a single load. It is argued that the MIP formulation and the single-escort LP may be used to determine a lower bound for the critical $T$ parameter in the TEG formulation from Bukchin and Raviv (2023). Unfortunately, both models were deemed too complex to provide UPBS design insights. Instead, the decentralized PBS algorithm from Furmans et al. (2013) was modified to design UPBS considering simultaneous retrievals, multiple escorts, and multiple I/O points. Upon proper validation of the algorithm, a simulation was used to evaluate UPBS by evaluating the average number of horizontal movements in each cell under different WIP levels for a 12 × 13 UPBS. The unidimensional cell with the least impact on the throughput was incorporated into the design, and the process is repeated to progressively determine the next unidimensional cell to incorporate. It was observed that if one cell becomes unidimensional, the remaining cells of that row became unidimensional before cells in other rows. The maximum number of unidimensional cells depends on the WIP level. It is concluded that for a low WIP level of 1, it is possible to design UPBS with 33.33% unidimensional cells, while increasing the throughput by 9.82%. The counterintuitive result that throughput increased by incorporating unidimensional cells is attributed to the decentralized algorithm which is designed to “sacrifice” loads under the requested loads as part of its deadlock prevention protocol. For a medium WIP level of 10, a layout including one row of unidimensional cells increased the throughput by less than 5% when compared to the bidimensional PBS. Considering two unidimensional rows increased the throughput by less than 4%. With five unidimensional rows, the throughput increased by 9.3%. For a WIP level of 20, incorporating one unidimensional row increases throughput by 7.47%.

By incorporating one unidimensional cell at a time, the paper uses an iterative greedy approach to finding a good (yet not necessarily optimal) solution. However, experimental results suggest that the UPBS designs obtained have a reasonable tradeoff between capital investment cost and throughput. Hence, UPBS may help develop a business case for the PBS technology.

Future work on single-load retrieval may explore the effect of alternative I/O locations on the UPBS design. For instance, placing the I/O in the middle of an edge, as suggested in Bukchin and Raviv (2022), may improve performance and yield interesting symmetric UPBS designs. Alternatively, studying UPBS designs with input and output points on opposite sides of the grid, as in staging applications, could provide interesting design insights and applications.

For multiple-load retrievals, future work should consider developing a decentralized control algorithm specifically for UPBS to reduce reliance on sacrifice moves as a deadlock prevention strategy. In general, sacrifice moves should be explicitly modeled to better understand their impact on the system input points when they reenter the UPBS. Lastly, future research may incorporate UPBS designs for multidimensional PBS (i.e. live-cube storage) or incorporate additional performance metrics into the objective function.

This work was supported in part by the National Science Foundation under Grant No. HRD-2008186. The authors are grateful to Dr. Kevin Gue for proposing the research problem.

The supplementary material for this article can be found online.