fixed point on the level surface.

###### Proof.

(i) follows from [28, Lemmas 3.7, 3.8].

(ii) follows from [28, Lemma 3.2].

(iii) On the other hand, let
$\widetilde{\mathbf{T}}=h^{-\frac{1}{2}}\frac{\partial}{\partial t}$ in the
standard coordinates $t,x^{i}$ for the exterior of the Schwarzschild
spacetime. Let $G_{E}^{\prime}$ be the reference Riemannian metric with
respect to $t$. One can compute by (ii):

(5.8)
$\langle{\mathbf{T}},\widetilde{\mathbf{T}}\rangle_{G}={\alpha}h^{-1}\langle{\overline{\nabla}}\tau,\frac{\partial}{\partial
t}\rangle_{G}=-{\alpha}h^{-1}P_{\tau}^{-1}=O(x^{-1})$

near $x=0$. From this it is easy to see that (iii) is true.

(iv) The bound of $A$ follows from the [28, Lemma 3.4]. From the proof of this
fact, one can also show that $\nabla^{k}A$ is also uniformly bounded for all
$k\geq 1$.

(v) To prove $|||\,{\overline{\mathrm{Rm}}}|||$ is bounded, we need to prove
that $\,{\overline{\mathrm{Rm}}}$ is bounded when evaluated at an orthonormal
basis $w_{1},w_{2},w_{3},w_{4}$ where $w_{4}={\mathbf{T}}$ and
$w_{1},w_{2},w_{3}$ are tangential to the level surface of $\tau$. Note that
one cannot just appeal to Lemma 2.1 to conclude that
$|||\,{\overline{\mathrm{Rm}}}|||$ is bounded because
$|||\,{\overline{\mathrm{Rm}}}|||_{G_{E}^{\prime}}$ decays like $x^{3}$,
$\,{\overline{\mathrm{Rm}}}$ is a four tensor, and we only have (5.8). Let us
choose $w_{i}$, $1\leq i\leq 3$ as follows. Let $y^{1},y^{2}$ be local
coordinates of $\mathbb{S}^{2}$, and let $\Phi$ be the diffeomorphism in
(5.7):

(5.9) $\left\\{\begin{array}[]{ll}e_{A}=:\Phi_{*}(\frac{\partial}{\partial
y^{A}})=-P_{A}\partial_{v}+\partial_{A},A=1,2;\\\
e_{3}=:\Phi_{*}(\frac{\partial}{\partial
x})=-P_{x}\partial_{v}+\partial_{x};\\\
e_{4}=:\Phi_{*}(\frac{\partial}{\partial\tau})=-P_{\tau}\partial_{v}.\end{array}\right.$

Then $e_{1},e_{2},e_{3}$ are tangential to the level set of $\tau$. We have

(5.10) $\left\\{\begin{array}[]{ll}\langle
e_{A},\widetilde{\mathbf{T}}\rangle=-P_{A}h^{\frac{1}{2}}&\hbox{$A=1,2$;}\\\
\langle e_{3},\widetilde{\mathbf{T}}\rangle=-P_{x}h^{\frac{1}{2}}.\\\
\end{array}\right.$

Since $\langle e_{i},e_{i}\rangle=P_{i}^{2}+r^{2}=P_{i}^{2}+x^{-2}$, for
$i=1,2,3$ we have

$|||e_{i}|||_{G_{E}^{\prime}}^{2}=\langle e_{i},e_{i}\rangle+2(\langle
e_{i},\widetilde{\mathbf{T}}\rangle)^{2}\leq Cx^{-2}.$

We may obtain orthonormal basis $w_{i}$ from $e_{i}$ so that
$w_{i}=xc_{ij}e_{j}$, with $c_{ij}$ being bounded, see [28, Lemma 3.1].
$|||w_{i}|||_{G_{E}^{\prime}}\leq C$ for some constant $C$. From (5.8), we
also have $|||w_{4}|||_{G_{E}^{\prime}}=|||{\mathbf{T}}|||_{G_{E}}\leq
Cx^{-1}$. To summarise:

(5.11) $\left\\{\begin{array}[]{ll}|||w_{i}|||_{G_{E}^{\prime}}\leq
C,&\hbox{for $1\leq i\leq 3$;}\\\ |||w_{4}|||_{G_{E}^{\prime}}\leq
Cx^{-1},\end{array}\right.$

for some constant $C>0$, provided $s_{0}$ is small enough. Now we are ready to
estimate $|||\,{\overline{\mathrm{Rm}}}|||$. Since
$\,{\overline{\mathrm{R}}}(w_{4},w_{4},\cdot,\cdot)=0$, by (5.11), we have

$|\,{\overline{\mathrm{R}}}(w_{a},w_{b},w_{c},w_{d})|\leq|||\,{\overline{\mathrm{Rm}}}|||_{G_{E}^{\prime}}|||w_{a}|||\,|||w_{b}|||\,|||w_{c}|||\,|||w_{c}|||\leq
Cx.$

because $|||\,{\overline{\mathrm{R}}}|||_{G_{E}^{\prime}}\leq Cx^{3}$.
Therefore, $|||\,{\overline{\mathrm{Rm}}}|||\leq Cx$. Similarly, one can
conclude that $|||{\overline{\nabla}}^{k}\,{\overline{\mathrm{Rm}}}|||\leq
Cx.$

(vi) By [23, Lemma 2.1], The fact that $|H-\frac{1}{\tau}|=O(x^{2})=O(r^{-2})$
follows from [23, Theorem 2.1] and the definition of $P$. Since
$\tau$=constant can be written as a spacelike graph over $\mathbf{x}$ in the
standard coordinates $t,x^{i}$, as before one can see the last assertion is
true. ∎

##  Appendix A Hölder spaces

We begin by explicitly defining the local Hölder norms used in the definition
parabolic Hölder spaces. Let $\Omega$ be an open set in $\mathbb{R}^{m}$. Let
$k\geq 0$ be an integer and $0<\sigma<1$, for $s_{0}>0$, the
$C^{2k+\sigma,k+\frac{\sigma}{2}}$ norm on
$\Omega_{s_{0}}=\Omega\times[0,s_{0}]$ for functions $f(\mathbf{x},s)$ is
defined as:

$\begin{split}||f||_{2k+\sigma,k+\frac{\sigma}{2};\Omega_{s_{0}}}=&\sum_{|{\alpha}|+2r=0}^{2k}\sup_{\Omega}\left|\partial^{r}_{s}\partial^{\alpha}f\right|\\\
&+\sum_{|{\alpha}|+2r=2k}\sup_{(\mathbf{x},s)\neq(\mathbf{x}^{\prime},s^{\prime})\in\Omega_{s_{0}}}\frac{\left|\partial^{r}_{s}\partial^{\alpha}f(\mathbf{x},s)-\partial^{r}_{s}\partial^{\alpha}f(\mathbf{x}^{\prime},s^{\prime})\right|}{|\mathbf{x}-\mathbf{x}^{\prime}|^{\sigma}+|s-s^{\prime}|^{\frac{\sigma}{2}}}\end{split}$

where

$\partial^{r}_{s}\partial^{\alpha}u=\frac{\partial^{r+|{\alpha}|}u}{\partial
s^{r}\partial x^{\alpha}}$

and ${\alpha}$ is a multi-index. If there is no confusion on the domain of
definition of $f$, we will simply write the norm as
$||f||_{2k+\sigma,k+\frac{\sigma}{2}}$.

##  Appendix B A convergence lemma

Let $U$ be a coordinate neighborhood of a Lorentz manifold with time function
$\tau$, ${\overline{\nabla}}\tau$ is past directed, so that $U$ is given by

$U=(-2,2)\times B(2)=\\{(x^{0},x^{i},\dots,x^{n})||x^{a}|<2,0\leq a\leq n\\}$

where $\tau=x^{0}$. Let

$V=(-1,1)\times B(1)=\\{(x^{0},x^{i},\dots,x^{n})||x^{a}|<1,0\leq a\leq n\\}$

Moreover the metric is of the form
$G=-{\alpha}^{2}d\tau^{2}+g_{ij}dx^{i}dx^{j}$, which is zero shift. Assume the
lapse function ${\alpha}$ is uniformly bounded from above and below. We also
assume that $g_{ij}$ is uniformly equivalent to the Euclidean metric
$\delta_{ij}$.

######  Lemma B.1.

Let $M_{k}$ be a sequence of spacelike surfaces so that

  1. (i)

$M_{k}\cap U$ is connected, $\partial M_{k}\cap U=\emptyset$;

  2. (ii)

the mean curvature $H_{k}$ of $M_{k}$ together with all its derivatives are
bounded; and

  3. (iii)

the tilt factor $\kappa_{k}$ of $M_{k}$ with respect to $\tau$ are uniformly
bounded.

If there is a limit point $p$ of $M_{k}$ inside $V$, then there is a
subsequence of $M_{k}$, still denoted by $M_{k}$ and a spacelike hypersurface
$M_{\infty}$ inside $V$ so that $d_{h}(M_{k},M_{\infty})\to 0$ in every
compact subsets of $V$. Moreover, the mean curvature $H_{\infty}$ is such that
$\lim_{k\to\infty}H_{k}=H_{\infty}$.

###### Proof.

First we may assume that $H_{k}\to H_{\infty}$ in $C^{\infty}$ norm in any
compact set of $U$. Since $U$ is simply connected, $M_{k}$ is achronal [25,
p.427]. Hence each $M_{k}$ is a graph. Namely, for each $k$, there is a
connected open set $W_{k}\subset U$ and a smooth function $u_{k}$ such that

$M_{k}=\\{(u_{k}(\mathbf{x}),\mathbf{x})|\ \mathbf{x}\in W_{k}\\}$

where $\mathbf{x}=(x^{1},\cdots,x^{n})$. Since $M_{k}$ is spacelike, there is
$C_{1}>0$ such that $|Du_{k}|\leq C_{1}$ for all $k$, where $Du_{k}$ is the
gradient with respect to the Euclidean metric. Hence there is $\delta>0$
independent of $\mathbf{x}$ such that if $(u_{k}(\mathbf{x}),\mathbf{x})\in
M_{k}\cap V$, with $|u_{k}(\mathbf{x})|\leq 1-\eta$ for some $\eta>0$. Then
$B_{\mathbf{x}}(\delta)\subset B_{\mathbf{x}}(2\delta)\subset W_{k}$ and
$|u_{k}(\mathbf{y})|<1$ for $\mathbf{y}\in B_{\mathbf{x}}(\delta).$ Here
$B_{\mathbf{x}}(\delta)=\\{\mathbf{y}|\ |y^{i}-x^{i}|<\delta,1\leq i\leq
n\\}$. Since the tilt factors of $M_{k}$ are uniformly bounded and $H_{k}\to
H_{\infty}$, the equation satisfies by $u_{k}$ is uniformly elliptic in
$B_{\mathbf{x}}(\delta)$. Hence if $p$ is a limit point of $M_{k}$ inside $V$,
passing to a subsequence, $u_{k}$ will converges in $C^{\infty}$ norm on
compact sets of $B_{\mathbf{x}}(\delta)$ where $\mathbf{x}$ is the projection
of $p$ to $B(2)$. From this it is easy to see the lemma is true. ∎

## References

  * [1] Andersson, L. ; Iriondo, M. S., Existence of constant mean curvature hypersurfaces in asymptotically flat spacetimes, Ann. Global Anal. Geom. 17 (1999), no. 6, 503–538.
  * [2] Andrews, B.; Chow, B.; Guenther, C.; Langford, M., Extrinsic geometric flows. Graduate Studies in Mathematics, 206. American Mathematical Society, Providence, RI, [2020], ©2020. xxviii+759 pp. ISBN: 978-1-4704-5596-5
  * [3] Bartnik, R., Existence of maximal surfaces in asymptotically flat spacetimes, Comm. Math. Phys. 94 (1984), no. 2, 155–175.
  * [4] Bartnik, R., Regularity of variational maximal surfaces, Acta Math. 161 (1988), no. 3–4, 145–181.
  * [5] Bartnik, R.; Simon, L., Space-like hypersurfaces with prescribed boundary values and mean curvature, Commun. Math. Phys. 87 (1982) 131–152.
  * [6] Chau, A.; Chen, J.;, He,W., Lagrangian Mean Curvature flowfor entire Lipschitz graphs, Calc. Var. 44 (2012), 199–220.
  * [7] Chau, A.; Tam, L.-F., On a modified parabolic complex Monge-Ampère equation with applications, Math. Z. 269 (2011), no. 3-4, 777–800.
  * [8] Ecker, K., On mean curvature flow of spacelike hypersurfaces in asymptotically flat spacetimes, J. Austral. Math. Soc. Ser. A 55 (1993), no. 1, 41–59.
  * [9] Ecker, K., Interior estimates and longtime solutions for mean curvature flow of noncompact spacelike hypersurfaces in Minkowski space, J. Differential Geom 46 (1997), no. 3, 481–498.
  * [10] Ecker, K.; Huisken, G., Parabolic methods for the construction of spacelike slices of prescribed mean curvature in cosmological spacetimes Comm. Math. Phys. 135 (1991), no. 3, 595–613.
  * [11] A. Friedman, A., Partial differential equations of parabolic type, Englewood Cliffs, N.J., : Prentice-Hall (1964).
  * [12] Gentile, G.; Vertman, B.,Prescribed mean curvature flow of non-compact space-like Cauchy hypersurfaces, Ann. Global Anal. Geom. 64 (2023), no. 2, Paper No. 11, 45 pp.
  * [13] Gerhardt, C., Hypersurfaces of prescribed mean curvature in Lorentzian manifolds, Math. Z. 235 (2000), no. 1, 83–97.
  * [14] Gerhardt, C., H-surfaces in Lorentzian manifolds, Comm. Math. Phys. 89 (1983), no. 4, 523–553.
  * [15] Gerhardt, C., H-surfaces in Lorentzian manifolds, Comm. Math. Phys.  89 (1983), no. 4, 523–553. 2
  * [16] Gilbarg, D; Trudinger, N.S., Elliptic partial differential equations of second order, 2nd ed., rev. 3rd printing. Berlin ; New York : Springer c1998.
  * [17] Hamilton, R.S., Three-manifolds with positive Ricci curvature, J. Differ. Geom. 17(1982), 255–306.
  * [18] Hamilton, R. S., A compactness property for solutions of the Ricci flow, Amer. J. Math. 117 (1995), no. 3, 545–572.
  * [19] Hawking, S.; Ellis, G., The large-scale structure of spacetime, Cambridge: Cambridge University Press 1973.
  * [20] Husiken, G.,Flow by mean curvature of convex surfaces into spheres, J. Differential Geom. 20 (1984), no. 1, 237–266.
  * [21] Husiken, G.,The volume preserving mean curvature flow, J. Reine Angew. Math. 382 (1987), 35–48.
  * [22] Kröcke, K.; Petersen, O.L.; Lubbe, F.; Marxen, T.; Maurer, W.; Meiser, W.; Schnürer, O.C.; Szabó.Á; Vertman, B., Mean curvature flow in asymptotically flat product spacetimes, J. Geom. Anal. 31(6), 5451–5479 (2021)
  * [23] Li, C.; Shi, Y.-G.; Tam, L.-F., Boundary behaviors of spacelike constant mean curvature surfaces in Schwarzschild spacetime, arXiv:2202.00926.
  * [24] Lieberman, G. M.,Second order parabolic differential equations, World Scientific Publishing Co., Inc., River Edge, NJ, 1996.
  * [25] O’Neill, B., Semi-Riemannian geometry : with applications to relativity, New York : Academic Press 1983.
  * [26] Shi, W.-X., Ricci Flow and the uniformization on complete non compact Kähler manifolds, J. of Differential Geometry 45 (1997), 94-220.
  * [27] Tam, L.-F.,Exhaustion functions on complete manifolds, Recent advances in geometric analysis, 211–215, Adv. Lect. Math. (ALM), 11, Int. Press, Somerville, MA, 2010.
  * [28] Tam, L.-F.,Spacelike CMC surfaces near null infinity of the Schwarzschild spacetime, arXiv:2306.03353
  * [29] Treibergs, A. E., Entire spacelike hypersurfaces of constant mean curvature in Minkowski space, Invent. Math. 66 (1982), no. 1, 39–56.


# A Novel Framework for Automated Warehouse Layout Generation

Atefeh Shahroudnejad
Amii (Alberta Machine Intelligence Institute)
<EMAIL_ADDRESS>
&Payam Mousavi
Amii (Alberta Machine Intelligence Institute)
<EMAIL_ADDRESS>
&Oleksii Perepelytsia
Routeique Inc
<EMAIL_ADDRESS>
&Sahir
Amii (Alberta Machine Intelligence Institute)
<EMAIL_ADDRESS>
&David Staszak
Amii (Alberta Machine Intelligence Institute)
<EMAIL_ADDRESS>
&Matthew E. Taylor
Amii (Alberta Machine Intelligence Institute)
University of Alberta
<EMAIL_ADDRESS>
&Brent Bawel Routeique Inc
<EMAIL_ADDRESS>
Corresponding author

###### Abstract

Optimizing warehouse layouts is crucial due to its significant impact on
efficiency and productivity. We present an AI-driven framework for automated
warehouse layout generation. This framework employs constrained beam search to
derive optimal layouts within given spatial parameters, adhering to all
functional requirements. The feasibility of the generated layouts is verified
based on criteria such as item accessibility, required minimum clearances, and
aisle connectivity. A scoring function is then used to evaluate the feasible
layouts considering the number of storage locations, access points, and
accessibility costs. We demonstrate our method’s ability to produce feasible,
optimal layouts for a variety of warehouse dimensions and shapes, diverse door
placements, and interconnections. This approach, currently being prepared for
deployment, will enable human designers to rapidly explore and confirm
options, facilitating the selection of the most appropriate layout for their
use-case.

_Keywords_ AI $\cdot$ Constrained Optimization $\cdot$ Automation $\cdot$
Warehouse Design $\cdot$ Logistics

##  1 Introduction

The main goal of Warehouse Management Systems (WMS) is running operations as
efficiently as possible to improve profitability through increasing
productivity, reducing labor costs, and ultimately increasing customer
satisfaction. One of the key components of a WMS is optimal space utilization.
It reduces the need for a larger capacity warehouse by maximizing inventory
storage and minimizing wasted or underutilized areas. Moreover, warehouse
configuration has a direct impact on all warehouse operations, especially the
worker routing and picking processes. Efficient warehouse configurations
(i.e., layouts) can enhance the order fulfillment process by eliminating
unnecessary movement and related errors, resulting in time and cost savings
Mohamud et al. (2023); Richards (2017). However, the vast majority of
warehouses worldwide still continue to rely on manual management or basic
automation Albert et al. (2023). There are a range of traditional and non-
traditional manual layout designs that have been proposed over the years to
speed up warehouse operations and minimize operating costs Gue and Meller
(2009); Bortolini et al. (2020); Kocaman et al. (2021); Zhang et al. (2021).
Although manually-designed layouts might be feasible for small warehouses with
limited options, for larger scales, they are a less efficient use of warehouse
designer time and more prone to human error. Hence, an automated process for
candidate layout generation would be beneficial to all stakeholders. Moreover,
an automated warehouse layout process would allow users to change
specifications over time to meet shifting product demand and facilitate the
expansion or restructuring of the warehouse while preserving efficiency and
productivity.

To automatically generate optimal candidate layouts, we must first establish
clear criteria for what constitutes an optimal layout; In this work, we define
a layout to be optimal if it maximizes space usage (i.e., storage capacity)
given a required number of accessible storage points (i.e., pick faces), a
required number of longer-term storage points (locations incurring an
accessibility penalty) and the physical and functional constraints of the
space. We aim to design layouts that account for different user preferences
among the competing priorities of maximizing storage and accessibility.
Therefore, there is generally more than one optimal layout, given the multi-
objective nature of the problem. Hence, we must solve a constrained
optimization problem that maximizes storage capacity and number of pick faces
while satisfying a set of constraints. It is worth mentioning that this
problem differs from general floor planning, which is a partitioning problem
with a given list of rooms and their adjacency, size, and position
constraints. Thus, the approaches do not quite apply to our problem.

Unlike automatic floor plan generation Medjdoub and Yannou (2000); Che et al.
(2017); Wu et al. (2018); Hu et al. (2020); Laignel et al. (2021); Morisset de
Pérdigo (2021), automatic warehouse layout generation has not been fully
explored in the literature. In warehouse environments, there are additional
challenges not included in those analyses, such as industrial constraints,
changing preferences, and real impact on warehousing operational activities.
Prior attempts to automate warehouse layout design have focused on using
mathematical optimization methods Yener and Yazgan (2019). For example, Zhang
and Lai (2006) formulate the problem as an Integer Linear Program (ILP) with
the combination of path relinking and a Genetic Algorithm (GA). Gu Gu (2005)
uses Generalized Benders Decomposition (GBD) to find the optimal solution.
Mathematical approaches have some limitations, such as modeling complexity,
lack of flexibility in case of any changes in the requirements, and large
computational costs.

We propose a new framework to address the gap in the existing literature and
to build a tool applicable to real-world scenarios. We present an interactive
and iterative tool that allows warehouse designers to impose operational
constraints or preferences and evaluate the optimality using objective
measures such as capacity and accessibility. This leads the users to an
informed decision on the final configuration based on the existing demands and
solves a constrained optimization problem that maximizes storage capacity and
number of pick faces while satisfying given warehouse constraints.

##  2 Methodology

We aim to create warehouse layouts that balance various factors such as
storage capacity, sufficient number of access points, ease of navigation, and
average projected throughput during item retrieval. After generating a range
of candidate layouts, an experienced warehouse designer can select from the
candidates or further refine them. For any candidate chosen in this
interactive selection process, the layout would then undergo a thorough
validation by an on-site team prior to implementation.

We propose a novel candidate layout generation algorithm (see Algorithm 1) to
generate optimal layouts based on tree search. A given space is specified by a
discrete two-dimensional grid of cells with several masks marking the
positions of walls $M_{walls}$ and door connections $M_{door\\_connections}$.
Figure 1 shows a running example of a sample space from our industry partner.
Each unit cell in the grid is colored based on what category it belongs to:
walls, door connections, aisles, storage, or pick face. The grid is
initialized with all cells fully occupied $L_{\text{\it{full}}}$. The tree
search then explores the space of possible layouts by systematically carving
new aisles. Invalid nodes (i.e., layouts violating any constraints) are
filtered in the Layout Filtering step (explained in Section 2.2). The valid
layouts are scored using a custom scoring function, and those with the highest
score are designated as optimal. As discussed before, there are typically
multiple optimal (and viable) layouts for consideration by the customer. In
Figure 1, each colored path represents a route that leads to the best possible
solution for a particular setting.

Algorithm 1 Candidate Layout Generation (beam size =1)

1:Inputs: $M_{\text{\it{walls}}},M_{\text{\it{door\\_connections}}}$ //input
masks

2:Initialize: Start from the full space : $L_{\text{\it{full}}}$

3:$Q\leftarrow\text{\it{Queue}}()$ //create an empty queue

4:$Q.\text{\it{push}}(L_{\text{\it{full}}})$

5:$L_{\text{\it{optimal}}}\leftarrow L_{\text{\it{full}}}$

6:while not $Q.\text{\it{empty}}()$ do

7: $L\leftarrow Q.\text{\it{pop}}()$

8: Generate all children by carving aisles horizontally and vertically for all
block stores in $L$

9: if $L==L_{\text{\it{\text{\it{full}}}}}$ then // first level

10: score valid children

11: if highest score $>L_{\text{\it{optimal}}}$ score then

12: $L_{\text{\it{optimal}}}\leftarrow$ valid children with highest score

13: $Q.\text{\it{push}}($all children$)$

14: break

15: for All children ($c_{1},\ldots,c_{n}$) do

16: if $c_{i}$ is valid then //filtering step

17: Score $c_{i}$

18: if children highest score $>=L$ score then

19: $Q.\text{\it{push}}($children with highest score$)$

20: if children highest score $>L_{optimal}$ score then

21: $L_{\text{\it{optimal}}}\leftarrow$children with highest score

22:return $L_{\text{\it{optimal}}}$

###  2.1 Tree Search

Due to the time-intensive nature and memory constraints of exhaustive tree
search at scale, we employ beam search for exploring the tree. Beam search is
a heuristic Breadth-First Search (BFS) algorithm that helps to make local
decisions and limit the search space. In the default setting (beam size:
$b=1$), for each node in the tree: (i) all children are generated by carving
new possible horizontal or vertical aisles in each block store111A group of
contiguous storage cells is called a block store.; (ii) child nodes at the
first level are always expanded (to promote diversity of solutions). For
deeper levels, only valid child nodes are expanded; and (iii) all valid
children are scored and the most promising child (the one with the highest
score), is selected for further expansion. The remaining child nodes are
pruned. This process continues until there are no more child nodes left for
expansion in the tree. This indicates that the terminal state has been reached
and the layouts with the highest score are taken to be optimal. For larger
beam sizes ($b>1$) however, $b$ top-scored children are selected at each
level.

###  2.2 Layout Filtering

To ensure that only viable and efficient layouts are selected, we sift through
all generated children layouts and reject those that violate any functional or
efficiency constraints as defined below:

Functional constraints:

  * •

Aisles that are connected to pick faces can not be narrower than the specified
aisle width,

  * •

All aisles need to be reachable by all doors into the warehouse space,

  * •

No item is allowed to be placed in doorways or areas marked as “reserved,” and

  * •

No pillar can block an aisle.

Efficiency constraints:

  * •

Aisles wider than the minimum required size are not allowed as they waste
space,

  * •

Two-sided access block stores should contain at least two rows, and

  * •

Each block store should contain more than one item as it is never efficient or
desirable to store a single item at a given location.

Figure 1: Running example of beam search ($b=1$) for a sample space from our
industry partner with specified door connections and aisle width = 3. At the
initial state, all free spaces are assigned as storage spaces. At the first
level, all possible unique children are generated by carving aisles with
sliding horizontal and vertical aisles across all block stores. Depending on
the particular $\alpha-\theta$ combination specified, a different
configuration is found as the best solution for that setting. This carving
process is undertaken again on the chosen configuration in subsequent levels
until a terminal state is found. In the figure, each colored path represents a
route that leads to the best possible solution for a particular
$\alpha-\theta$ combination. For each of these solutions, the $\alpha$,
$\theta$, number of pick faces and number of storage are shown. Space
specifications:  Walls,  Door connections,  Aisles,  Storage,  Pick face.

###  2.3 Layout Scoring

Candidate solutions are evaluated and the underperforming tree nodes are
pruned. The scoring function is a critical component used as a heuristic in
the tree search. A misspecified score will be detrimental to the node
expansion of the tree search resulting in sub-optimal solutions. We introduce
a scoring function, Eq. (1), which not only enables trade-offs between
important performance factors (e.g., storage and accessibility) but also
facilitates diverse layout generation. We use normalization and define the
term weights carefully in the scoring formula to ensure the layout assessment
is accurate and unbiased.

$\text{\it{Score}}=\alpha T_{s}+\beta T_{pf}+c_{1}T_{o},$ (1)

The scoring function is a weighted combination of three terms, namely, the
normalized storage capacity $T_{s}$, the normalized number of pick faces
$T_{pf}$, and the normalized number of block stores in a specific orientation
(vertical or horizontal) $T_{o}$. The coefficients $\alpha$ and $\beta$
specify the relative importance of the first two terms, while the coefficient
$c_{1}$ is a fixed hyperparameter selected empirically (more details later).

The normalized storage capacity $T_{s}$ is defined as,

$T_{s}=\frac{N_{s}-c_{2}\theta P_{a}}{\text{\it{Total open area}}},$ (2)

where $N_{s}$ is the storage capacity; $\theta$ is a weighting coefficient;
$c_{1}$ and $c_{2}$ are hyperparameters (discussed in more details later), and
$P_{a}$ is an accessibility penalty defined as,

$P_{a}:=\sum_{BS_{i}}\omega_{i}\max_{j\in BS_{i}}(h_{j}-1)^{2},$ (3)

with $\omega$, and $h$ corresponding to the width and item heights of a block
store $BS$. The penalty is related to the number of items that need to be
removed to access the deepest row in a block store. The chosen quadratic
scaling has desirable symmetry properties ensuring that higher depths are
appropriately penalized.

The second term in Eq. (1), $T_{pf}$, the normalized number of pick faces is
defined as,

$T_{pf}=N_{pf}/N_{s},$ (4)

where $N_{pf}$ is the number of pick faces.

Finally, the third term in Eq. (1), $T_{o}$ represents the normalized number
of block stores in a specific orientation (vertical or horizontal) if that
orientation is opposite to the space orientation. Without using this term,
block stores tend to be aligned with the space orientation. However, sometimes
the opposite orientation is preferable due to the location of the staging
area222Staging area is where items are loaded to or unloaded from the
warehouse.. $T_{o}$ provides a control to allow the dominated layout
orientations thereby promoting more diversity in the results.

The weighting coefficients, $\alpha$, $\beta$, and $\theta$, adjust the
balance between the different terms. The term $\alpha\in\\{0.1,\dotsc,1\\}$
controls the balance between storage capacity and number of pick faces,
$\beta=\min(0.1,1-\alpha)$, and $\theta\in\\{0.1,\dotsc,\alpha/2\\}$ are
defined based on $\alpha$. The term $\theta$ controls the accessibility
penalty $P_{a}$. The maximum of $\theta$ is set based on $\alpha$ to avoid
over-penalizing. Hyperparameters $c_{1}=0.01$ and $c_{2}=0.1$ are set
empirically to scale the corresponding terms.

Each combination of $\alpha$ and $\theta$ represents a particular preference
for the properties of the generated optimal layout discovered by the tree
search. The process for selecting the final layout involves the warehouse
designer, and is discussed in more details in Section 3.

###  2.4 Connectivity Score

In addition to the scoring function presented above, we define another score
term, connectivity to estimate the likely relative throughput expected from
different candidate layouts. Note that the exact throughput cannot be known a
priori as it will depend on specific product assignment and order lists. Our
estimates here are used only to determine the ranking order of different
candidates as a tool to select among several optimal candidates generated
above. The connectivity score is defined as the average cumulative ratios of
shortest distances to the Manhattan distances Black (2006) for pairs of pick
faces:

$\mathcal{C}=\frac{1}{N_{pf}}\sum_{i\leq
j}\frac{1}{D_{i,j}^{\text{\it{Shortest}}}/D_{i,j}^{\text{\it{Manhattan}}}},$
(5)

where $N_{pf}$ is the number of pick faces, and $D_{i,j}$ is the distance
(i.e., shortest or Manhattan) between two pick face locations.

This is based on the intuition that for a high-throughput (i.e., more
connected) layout, the shortest distances (between pairs of pick faces) will
on average be closer in value to the Manhattan distance. This function has the
additional desired property that it is normalized to one, facilitating simple
direct comparisons between different layouts. Note that we decided not to
include connectivity as an independent scoring term in Eq. (1) to simplify the
process and minimize instabilities in the search.

Figure 2: Pareto visualization for a medium-sized space from our industry
partner with specified door connections and aisle width = 3. The pink dashed
line shows the Pareto front. Zoomed layouts correspond to the data points on
the Pareto front. The red star at the bottom shows the manually-designed
layout which has been specified by the red dashed border. Space specifications
include the following:  Walls,  Door connections,  Aisles,  Storage,  Pick
face.

###  2.5 Post-Refinement

The objective of the post-refinement step is to apply any additional
constraints to arrive at the final layouts. While every application will
require some customization by the on-site team often these constraints and
requirements can be codified to save time. In one application, the pallet
racking system only allowed even numbers of racking units along the total
block store (due to how the racking infrastructure was constructed). In
another application, clear paths were necessary to access pillars that
contained fire safety equipment. In both cases, the flexibility of our
algorithm allowed for these constraints to be programmatically applied as a
final step, only passing layouts that fulfilled the criteria.

###  2.6 Implementation Details

Our method is adjustable to larger beam sizes. By increasing the beam size,
the search space is expanded as more children are explored at a time. However,
it also increases the exploration time. Therefore, we use multiprocessing to
expedite the search process, especially for larger beam sizes. We used eight
CPU cores with 16GB of memory to run experiments. For a medium-sized space
($50\times 55$), the average processing time for generating the Pareto plot
(e.g., Figure 2) is 85s.

##  3 Results

To generate all possible optimal layouts for a given space, the layout
generation process is run separately for all combinations of $\alpha$ and
$\theta$ in their defined ranges. Drawing from the pool of generated optimal
layouts, we create a Pareto plot that visualizes possibilities with respect to
the storage capacity and number of pick faces. The Pareto plot is used as an
interactive decision-making tool. Figure 2 shows the Pareto plot for a medium-
sized space from our industry partner. The Pareto front comprises optimal
layouts that dominate the other candidates by striking a better trade-off
between the storage capacity and number of pick faces. The Pareto front is
downward sloping, illustrating that the storage capacity decreases with
increasing number of pick faces. When two candidate layouts have the same
score in the same $\alpha-\theta$ setting, the connectivity score comes into
play and decides which one is likely to lead to a higher-throughput design.

In Figure 2, we compare the auto-generated optimal layouts in the Pareto plot
with the existing manually-designed layout (indicated by the red star added to
the plot). We observe notable improvements across both number of pick faces
and storage capacity.

We closely collaborated with expert warehouse designers to validate the
quality of the generated layouts and compare the results with manually-
generated versions. The designers reported that the process was user-friendly
and served as an effective collaborative tool, significantly streamlining
their efforts to achieve good layouts.

##  4 Discussion

Warehouse layout design plays a vital role in warehouse operations
performance. We proposed a novel automated optimal layout candidate generation
framework using beam search that satisfies a set of constraints. We also
introduced a new scoring function that handles a balance between storage
capacity, number of access points, and accessibility cost. Our method can
generate a wide variety of candidate layouts for different ranges of picking
and storage areas and we demonstrated this in various spaces of two real-world
warehouses. The simplicity of the method makes it easily adaptable to any
changes in user specifications and requirements.

Despite all these strengths, our approach is not without limitations. One
limitation is that we were unable to measure the throughput of the layouts and
compare their performances comprehensively. Throughput depends on order lists
and item allocation, which would add a layer of complexity that is beyond the
scope of this work. As throughput is the ultimate measure of effectiveness,
not being able to account for these factors restricts our ability to fully
evaluate the efficiency of the different layouts. Despite this limitation, the
proposed solution was tested on 9 available physical spaces through the
partnership between Amii and Routeique. In the experiments, the framework
generalized well to both large and small spaces as well as those with non-
rectangular shapes and the expert warehouse designers verified the feasibility
and quality of the generated layouts.

Finally, we did not incorporate some relevant constraints, for example varying
heights of rows, and larger-sized doorways/entryways. However, we found that
it was relatively straightforward to programmatically add those additional
constraints for the unique artifacts found in spaces such as fire
extinguishers (see Section 2.5). While it is challenging to comprehensively
anticipate and account for all unique elements found in specific real-world
scenarios, our method is flexible and could incorporate the majority of such
constraints.

In the future, we will continue to validate and refine our tool in more
diverse settings and in different warehouses. Feedback from a larger number of
warehouse designers will guide the direction of future development.

## Acknowledgments

We thank Mara Cairo, Bevin Eldaphonse, and the Routeique team, especially Mike
Allan for their valuable support during this project. We also thank our
reviewers for their constructive feedback, which helped us to improve the
quality of this work.

## References

  * Mohamud et al. [2023] Ibrahim Hassan Mohamud, Md Abdul Kafi, Syairah Aimi Shahron, Nizamuddin Zainuddin, and Suria Musa.  The role of warehouse layout and operations in warehouse efficiency: A literature review.  _Journal Européen des Systèmes Automatisés_ , 56(1), 2023.
  * Richards [2017] Gwynne Richards.  _Warehouse management: a complete guide to improving efficiency and minimizing costs in the modern warehouse_.  Kogan Page Publishers, 2017.
  * Albert et al. [2023] Pierre-William Albert, Mikael Rönnqvist, and Nadia Lehoux.  Trends and new practical applications for warehouse allocation and layout design: a literature review.  _SN Applied Sciences_ , 5(12):378, 2023.
  * Gue and Meller [2009] Kevin R Gue and Russell D Meller.  Aisle configurations for unit-load warehouses.  _IIE transactions_ , 41(3):171–182, 2009.
  * Bortolini et al. [2020] Marco Bortolini, Francesco Gabriele Galizia, Mauro Gamberi, and Francesco Gualano.  Integration of single and dual command operations in non-traditional warehouse design.  _The international journal of advanced manufacturing technology_ , 111(9):2461–2473, 2020.
  * Kocaman et al. [2021] Yeliz Kocaman, Ömer Öztürkoğlu, and Şevkinaz Gümüşoğlu.  Aisle designs in unit-load warehouses with different flow policies of multiple pickup and deposit points.  _Central European Journal of Operations Research_ , 29:323–355, 2021.
  * Zhang et al. [2021] ZY Zhang, Y Liang, YP Hou, and Q Wang.  Designing a warehouse internal layout using a parabolic aisles based method.  _Advances in Production Engineering & Management_, 16(2):223–239, 2021.
  * Medjdoub and Yannou [2000] Benachir Medjdoub and Bernard Yannou.  Separating topology and geometry in space planning.  _Computer-aided design_ , 32(1):39–61, 2000.
  * Che et al. [2017] Ada Che, Yipei Zhang, and Jianguang Feng.  Bi-objective optimization for multi-floor facility layout problem with fixed inner configuration and room adjacency constraints.  _Computers & Industrial Engineering_, 105:265–276, 2017.
  * Wu et al. [2018] Wenming Wu, Lubin Fan, Ligang Liu, and Peter Wonka.  Miqp-based layout design for building interiors.  In _Computer Graphics Forum_ , volume 37, pages 511–521. Wiley Online Library, 2018.
  * Hu et al. [2020] Ruizhen Hu, Zeyu Huang, Yuhan Tang, Oliver Van Kaick, Hao Zhang, and Hui Huang.  Graph2plan: Learning floorplan generation from layout graphs.  _ACM Transactions on Graphics (TOG)_ , 39(4):118–1, 2020.
  * Laignel et al. [2021] Graziella Laignel, Nicolas Pozin, Xavier Geffrier, Loukas Delevaux, Florian Brun, and Bastien Dolla.  Floor plan generation through a mixed constraint programming-genetic optimization approach.  _Automation in Construction_ , 123:103491, 2021.
  * Morisset de Pérdigo [2021] JR Morisset de Pérdigo.  Floor plan generation as an optimization problem.  Master’s thesis, 2021.
  * Yener and Yazgan [2019] Furkan Yener and Harun Resit Yazgan.  Optimal warehouse design: Literature review and case study application.  _Computers & industrial engineering_, 129:1–13, 2019.
  * Zhang and Lai [2006] GQ Zhang and KK Lai.  Combining path relinking and genetic algorithms for the multiple-level warehouse layout problem.  _European Journal of Operational Research_ , 169(2):413–425, 2006.
  * Gu [2005] Jinxiang Gu.  _The forward reserve warehouse sizing and dimensioning problem_.  Georgia Institute of Technology, 2005.
  * Black [2006] Paul E Black.  Manhattan distance"" dictionary of algorithms and data structures.  _http://xlinux. nist. gov/dads//_ , 2006.