category: literaturenote citekey: thomasbranchcutalgorithmoptimal2025 title: A Branch-and-Cut Algorithm for the Optimal Design of Parking Lots with One-way and Two-way Lanes authors: "Thomas, Helen; Rambha, Tarun" year: 2025 date: 2025-00-00 2025 url: "https://arxiv.org/abs/2506.09961v1" zotero_key: 3CMWGPWZ zotero_storage: 3BVIMXWM collections: transpordi_planeerimine folder: 001_artiklid firstAuthor: "Thomas, Helen"

status: converted

A Branch-and-Cut Algorithm for the Optimal Design of Parking Lots with One-way and Two-way Lanes

Helen Thomas*¹ and Tarun Rambha*^Q1,2

¹Department of Civil Engineering, Indian Institute of Science (IISc), Bengaluru, India ²Centre for infrastructure, Sustainable Transportation, and Urban Planning (CiSTUP), Indian Institute of Science (IISc), Bengaluru, India

Abstract

We address the problem of maximizing the number of stalls in parking lots where vehicles park perpendicular to the driveways. Building on recent research, we first formulate a mixed integer program to maximize the number of parking stalls using a flow-based approach. Parking lots are rasterized into a grid, and the proposed MIP model optimizes them in a generic manner, adapting to the grid resolution and stall size without the need for custom formulations. The constraints ensure the connectivity of parking stalls and driveways to the entrance/exit. This formulation is then extended to the case of one-way driving lanes. We also propose valid inequalities and a branch-and-cut algorithm for the one-way and two-way lane configurations. This approach eliminates flow variables, big-M type constraints, and improves solution times for medium-sized instances. The effectiveness of the suggested models is showcased on 325 parking lots in New York City. For instances in which the flow version could be solved in 15 minutes, the branch-and-cut algorithm improved the median runtimes by 87.43% for the one-way case and by 79.36% for the two-way case and resulted in better optimality gaps for the other instances, compared to the baseline flow-based formulation. Similar advantages were observed when run with a time budget of two hours. One-way configurations accommodated up to 18.63% more vehicles on average than their twoway counterparts across all the instances. Modifications to the proposed formulations that consider the turning characteristics of vehicles and the presence of multiple entrances and exits are also examined.

Keywords: parking lot optimization; mixed integer programming; cutting planes; branch-and-cut

1 Introduction

In most cities, land for parking near central business districts and other high-demand points of interest is usually limited, making parking scarce and expensive. For example, owning a parking space in parts of New York City can cost a staggering six-digit figure (Toy, 2007; Hughes, 2019). Such problems are not only acute for cars but also for other vehicles, such as buses, which need to park at depots located in dense parts of cities (to avoid deadheading), and commercial heavy vehicles serving urban freight. Optimizing the capacity of commercial parking lots can also significantly improve the revenue of operators. Data from Statista suggests that the estimated revenue from parking lots in New York in 2024 is approximately 1.37 million USD. Thus, it is essential to maximize the limited space available for parking, particularly for small and medium-sized lots that tend to reach their capacity frequently. Furthermore, the shapes of parking lots can be irregular and may contain obstacles, making it difficult to design these layouts manually. Stephan et al. (2021), using data from 177 real-world parking lots in Jena, Germany, found that manually designed lots typically have 25% less capacity than those discovered using optimization. Therefore, the design of parking lots involves several key decisions, which will be the focus of our paper. Where should parking stalls and driveways be located in lots with one-way or two-way driving lanes? How can we solve these optimization problems faster using exact methods? Can the layouts be adjusted to handle constraints that arise from turn restrictions and multiple entrances and exits? In the following subsections, we summarize related studies, highlight their gaps, and outline the contributions of our work.

1.1 Background

In many urban areas, drivers are often forced to park far from their destinations or spend considerable time searching for empty parking stalls, causing congestion. A study by Hampshire and Shoup (2018) estimated that the percentage

^(*) Both authors contributed equally to this manuscript. (Q tarunrambha@iisc.ac.in) Corresponding author

of vehicles cruising for parking is about 15% in Stuttgart. This share varies widely across cities but is usually a significant fraction of the total traffic (Shoup, 2006; Lee et al., 2017). Several parking solutions have been explored in the literature, including measuring parking availability (Cai et al., 2019; Arora et al., 2019), optimizing parking search times (Tang et al., 2014; Brooke et al., 2014), and implementing policy measures (Yan et al., 2019). The reader can find in-depth surveys on intelligent parking systems in Lin et al. (2017) and Diaz Og´as et al. (2020). At the parking lot level, recent research focuses on optimizing stalls for automated parking systems (Wu et al., 2019; Chen et al., 2020; Azevedo et al., 2020; Siddique et al., 2021; Sch¨orner et al., 2021; Wang et al., 2021). Problems of similar flavor appear in the planning and organization of automated warehouses and puzzle-based storage systems (Flake and Baum, 2002; Gue and Kim, 2007; Azadeh et al., 2019; Bukchin and Raviv, 2022; Rosenfeld, 2022; Raviv et al., 2023). In this research, we focus on the problem of parking cars in a lot, but many of the methods and ideas can be trivially extended to other settings.

A crucial aspect of lot design involves determining the optimal configuration of parking stalls or fields. Iranpour and Tung (1989) made one of the earliest attempts to solve this problem using a set of nonlinear equations to maximize capacity. They introduced the concept of an ease factor, which reflected the ease/difficulty associated with parking maneuvers and helped select the optimal layout among multiple solutions with equal parking capacity. Abdelfatah and Taha (2014) used Mixed Integer Programming (MIP) models and the LINDO solver to design optimal parking layouts at different angles. The total number of parking stalls was maximized by deciding how many and what types (based on the dimensions and angle of parking used) of rows of parking bays could be accommodated within the given parking lot.

The above studies are limited to the design of rectangular parking lots. Most existing works do not model obstructions such as building elements, trees, sidewalks, and street lights, and these practical constraints demand better optimization. Stephan et al. (2021) addressed such issues using a MIP and proposed heuristics to maximize the capacity of perpendicular parking lots. Their study rasterized a given ground plot into three different resolutions. Forbes and Harris (2022) suggested using cutting planes to reduce the time required to solve a similar MIP.

Figure 1: Solutions for different parking and driving configurations for the example layout used in Stephan et al. (2021). The parking stalls/fields are green and blue, depending on their orientation (not relevant for square fields). Driving fields are indicated in gray. The red cells are areas blocked due to obstructions. Entrance/Exit fields are marked in purple. White cells remain unused.

1.2 Gaps and contributions

The results of field studies that consider the capacity and maneuverability of vehicles can be used as guidelines for parking design. However, manually designing layouts that utilize space effectively, especially in irregularly shaped lots, is difficult and necessitates optimization. While a few automated solutions exist in the literature, they are restricted by driveway configurations, size and shape of parking fields, etc.

This work addresses the problem of designing parking stalls and driveways within a given plot, which could be on land, a single level of a multi-floor parking facility, or a warehouse. We extend and improve the MIP formulations of Stephan et al. (2021) and Forbes and Harris (2022) that maximize the number of parking stalls oriented perpendicular to the driving lanes for two-way and one-way driving configurations (see, for example, Figures 1a and 1c). The MIP formulations presented in this paper are generic. They solve the problem for various vehicle sizes (e.g., passenger cars or unstacked cargo crates/containers in a yard or warehouse, as long as the stall size is the same throughout the lot) and model different resolutions using a single formulation. For example, in the right panel of Figure 1b, one can generate a coarser problem instance by combining 2 × 2 units of red cells to generate the blocked fields in Figure 1a. Similarly, 2 × 2 red-cell units in Figure 1a are grouped to create the blocked cells in the left panel of Figure 1b. Figures in 1d show examples of our model output for the same grid resolution as Figure 1a but with different parking/driving field sizes. The dots inside the cells denote the anchors for the driving and parking fields, which will be described shortly. The right panels of Figures 1b and 1d show upper-bound solutions, as they were terminated after reaching a time limit. The constraints in these formulations ensure that each cell in a rasterized parking lot is used for a single purpose, all parking stalls are connected to the driveways, and the driveways are accessible from the entrance/exit. The main contributions of this research are summarized below:

We extend existing MIP models to one-way lane configurations, modeling the direction of vehicle movement and adding constraints that connect the driveways to both the entrance and exit while avoiding dead ends.
We propose a family of valid inequalities that can be added to the model upfront to generate solutions with a small number of connected driving field components. Empirically, these inequalities significantly improve computation times for the two-way case. We also develop a branch-and-cut algorithm in which feasibility cuts are dynamically added to ensure driveway connectivity, eliminating flow variables and big-M constraints.
We demonstrate computational savings using 325 medium-sized instances (up to half the size of a football field) from New York City. For two-way (one-way) configurations, flow-based formulations optimally solved 187 (149) of the 325 instances within a time limit of 15 min for each instance. On the other hand, our branch-and-cut algorithm solved 245 (288) instances optimally with median runtimes that were 79.36% (87.43%) faster when both methods found optimal solutions. One-way configurations led to an overall increase in the number of stalls by 18.63% compared to lots with two-way driveways.

The remainder of this paper is organized as follows. Section 2 describes a generalized MIP formulation with two-way driving lanes. We discuss extensions to the one-way case in Section 3. Section 4 suggests valid inequalities for the problem and a branch-and-cut algorithm that dynamically generates feasibility cuts. Section 5 demonstrates the advantages of the proposed formulations using open data from New York City. Finally, Section 6 summarizes the findings in this paper along with a discussion on possible extensions. Due to space limitations, we illustrate additional constraints that handle turning radius limitations of vehicles and multiple entrances and exits in Appendix A.

2 A generalized MIP formulation

2.1 Problem setup

This section describes a MIP formulation for the case where parking stalls are perpendicular to driveway lanes, and the driveway lanes are two-way streets. We first rasterize a given plot into a grid of squares or cells. A field is assumed to be a square or rectangular unit comprising multiple cells. Let the number of rows and columns in the grid be µ and ν, respectively. The set of all cells in the parking lot is designated as L = {(i, j) : i ∈ {0, . . . , µ−1}, j ∈ {0, . . . , ν−1}}. As assumed in the literature, we suppose that the lot may have obstacles such as buildings, trees, utility poles, and structural columns (in the case of indoor parking). The set of such blocked cells is denoted as B.

A parking field is assumed to have a width of ω cells and a length of ℓ cells and can be oriented along the lateral (east-west) direction or the longitudinal (north-south) direction. We use angles 0◦ and 90◦ to distinguish between these orientations. The east-west and 0◦ nomenclature is used only to indicate the orientation with reference to the grid but not the driving lanes or geographic directions. They are not to be confused with parallel parking. Parking is assumed to be orthogonal to the driving lanes throughout this work. The binary decision variables that indicate the presence/absence of 0◦ and 90◦ parking fields anchored at cell (i, j) are x ij and x 90 ij , respectively. We simply refer to them as parking fields at (i, j), although they may contain other cells in the lot depending on ω and ℓ. The choice of the anchor within a parking field is simply a convention and can be set to any other cell in the field. Changing the anchor alters the model implementation but does not affect the formulation or the solution. The MIP formulations can also be written using all parking fields that can be anchored at a specific cell, without separate variables for the 0 ◦ and 90◦ parking fields. The variable x ij takes a value of one if an east-west parking field is anchored at (i, j) and includes cells of the form (i + k, j + l), where k ∈ {0, . . . , ω − 1} and l ∈ {0, . . . , ℓ − 1} (see the green rectangle in Figure 2a). Similarly, if x 90 ij is one, then a parking space anchored at (i, j) is created in the north-south direction with cells of the form (i + k, j + l), where k ∈ {0, . . . , ℓ − 1} and l ∈ {0, . . . , ω − 1} (see the blue rectangle in Figure 2a).

The driving fields, on the other hand, are always squares of width δ cells, where δ ≥ ω to provide sufficient space for the vehicles to drive and park. A driving field at (i, j) is assumed to contain cells (i+k, j+l), where k, l ∈ {0, . . . , δ−1} and are determined using binary decision variables yij (e.g., the gray square in Figure 2a). For two-way settings, assumed throughout this section, we require δ ≥ 2ω. Sometimes, parking lots may contain a street accessed by through traffic. We retain such existing driveways while optimizing the layout. The set of anchor points of the existing driving fields is indicated by Q. The decision variable yij is set to one for a driving field anchored at (i, j).

Figure 2: Decision variables of the integer program. The example here assumes parking fields with ω = 2 and ℓ = 3 and square driving fields with δ = 4. Blocked cells are shown in red.

We assume a single entrance/exit using a driving field anchored at (p, q). In a two-way lane configuration, the same cell is used to exit the lot and is sometimes simply referred to as the entrance. The entrance cell to the parking lot is assumed to be known/predetermined, and the corresponding y variable value is set to one. The entrance cell can also be inside the lot to model indoor parking garages with ramp access. We identify subsets of L in which x ij , x 90 ij , and yij are valid, i.e., they can potentially take a value of one at these cells, and name them P , P ⁹⁰, and D, respectively (see Figures 2b, 2c, and 2d). Note that blocked cells can prohibit other nearby cells from being a parking or a driving field.

Symbol	Description
Sets
L	Rasterized cells in the parking lot
B	Blocked cells
Q	Anchor cells of existing drive fields
0 P	Cells at which 0◦ parking fields are valid
90 P	Cells at which 90◦ parking fields are valid
D	Cells at which driving fields are valid
N0 ij	Driving fields that neighbor a 0◦ parking field at (i, j)
N90 ij	Driving fields that neighbor a 90◦ parking field at (i, j)
0 P ij 90 P ij	Anchors of 0◦ parking fields that contain cell (i, j) Anchors of 90◦ parking fields that contain cell (i, j)

Dij	Driving fields that contain cell (i, j)
G	A grid graph of cells in D as nodes and arcs connecting cells that share a side
A	Arcs connecting the cells in the grid
Dij	Cells at the head end of arcs emanating from (i, j)
−1 D ij	Cells at the tail end of arcs incoming to (i, j)
Parameters
µ	Number of rows in the rasterized parking lot
ν	Number of columns in the rasterized parking lot
ω	Width of the parking field in terms of the number of cells
ℓ	Length of the parking field in terms of the number of cells
δ	Width of the driving field in terms of the number of cells
(p, q)	Anchor cell of the entrance/exit driving field
Variables
0 x ij	Binary 0◦ park variable with cell (i, j) as an anchor
90 x ij	Binary 90◦ park variable with cell (i, j) as an anchor
yij	Binary drive variable with cell (i, j) as an anchor
fij,kl	Flow from cell (i, j) to cell (k, l)

Stephan et al. (2021) formulated the problem of designing parking lots with two-way driveways as a MIP using three main types of constraints: (1) Single-purpose constraints – which require each cell to have at most one purpose, i.e., parking, driving, or being left empty, (2) Accessibility constraints – every parking field should be connected to a driving field, and (3) Driveway connectivity constraints – the driving fields must be connected to the entrances/exits. The objective is to maximize the number of parking stalls. They, however, create different models for different resolutions. In the following subsections, we discuss a generalized version.

2.2 Single-purpose constraints

Let the set of 0◦ and 90◦ parking fields that contain a cell (i, j) be represented by P ij and P 90 ij , respectively. Likewise, let Dij denote the set of driving fields that contain cell (i, j). Figure 3 shows an example of the different fields containing a cell (i, j). We do not assume any blocked fields in this example. If there are blocked cells, only the valid fields that contain the cell (i, j) are included in P ij , P 90 ij , and Dij .

Figure 3: Sets of parking and driving fields containing the yellow cell (6, 7)

Cells in the parking lot that are not blocked can be used for parking or driving or be left unused. Constraints (1) and (2) capture this feature. The term ¹ |Dij | P (k,l)∈Dij ykl in the left-hand side allows for overlapping of driving fields as multiple driving fields can contain a cell (i, j).

$$\sum{(k,l)\in\mathcal{P}{i,l}^{0,i}} x{kl}^{0} + \sum{(k,l)\in\mathcal{P}{i,l}^{0,i}} x{kl}^{90} \le 1 \qquad \qquad \forall (i,j) \in L \setminus B, \ |\mathcal{D}_{ij}| = 0 \tag{1}$$

$$\sum{(k,l)\in\mathcal{P}{i,i}^{0}} x{kl}^{0} + \sum{(k,l)\in\mathcal{P}{i,i}^{00}} x{kl}^{90} + \frac{1}{|\mathcal{D}{ij}|} \sum{(k,l)\in\mathcal{D}{i,j}} y{kl} \le 1 \qquad \forall (i,j)\in L\setminus B, |\mathcal{D}_{ij}| > 0$$ (2)

Constraint (2) can be written in a disaggregate form, which can tighten the LP relaxations of the problem. This new version (3) also captures (1) since the first term on the left-hand side does not contain the y variable if |Dij | = 0.

$$y{mn} + \sum{(k,l) \in \mathcal{P}{ij}^0} x{kl}^0 + \sum{(k,l) \in \mathcal{P}{ij}^{00}} x{kl}^{90} \le 1 \qquad \forall (m,n) \in \mathcal{D}{ij}, (i,j) \in L \setminus B$$ (3)

2.3 Accessibility constraints

Each parking field must be accessible from at least one side by a driving field, allowing vehicles to maneuver into the parking stall. Hence, we impose constraints (4) and (5). These constraints ensure that the park field variables can be set to one only if at least one adjacent driving field is active. We assume that neighbor sets N⁰ ij and N⁹⁰ ij are constructed using fields that entirely overlap with the shorter edges of a parking field at (i, j). Recall that, as previously assumed, the width of the driving fields is equal to or greater than twice the width of the parking fields.

Figure 4: Driving field neighbors of parking field at (6, 6) (in left and center panels) and the need for additional constraints on the driving fields (right). The entrance field is anchored at (0, 5).

Figures 4a and 4b show the neighbors of two sample parking fields. The set of driving anchors that allow access to the 0◦ parking field at (6, 6) is shown using gray cells N⁰ ⁶,⁶ = {(4, 2),(5, 2),(6, 2),(4, 9),(5, 9),(6, 9)}. Similarly, N⁹⁰ ⁶,⁶ = {(2, 4),(2, 5),(2, 6),(9, 4),(9, 5),(9, 6)} contains driving anchors that help reach the 90◦ parking field at (6, 6).

$$x{ij}^0 \le \sum{(k,l) \in N{i}^0} y{kl} \qquad \forall (i,j) \in P^0 \tag{4}$$

$$x{ij}^{90} \le \sum{(k,l) \in Ni^{90}} y{kl} \qquad \forall (i,j) \in P^{90}$$ (5)

However, the above constraints are insufficient since they do not require connecting the driving fields. For example, consider Figure 4c, which shows a feasible solution that satisfies constraints (3)–(5). In this example, each parking field is accessible by a driving field, but the driving fields are not connected to the entrance.

2.4 Driveway connectivity constraints

To connect the driving fields, we generate a grid-like directed graph G = (D, A), using the cells in D as nodes and the arcs A to connect adjacent cells. Constraint (6) generates a unit flow at cells where a driving field is anchored. Flows are routed to the entrance node using constraint (7). These flow-conservation constraints ensure that all active driving cells are connected to the entrance location. Additionally, we set the upper bounds on the flow variables using (8) and (9) so that positive flows are not generated in and out of a non-driving cell. A safe choice for M is |D| − 1.

$$\sum{(k,l)\in D{ij}} f{ij,kl} - \sum{(k,l)\in D{i,l}^{-1}} f{kl,ij} = y_{ij} \qquad \forall (i,j)\in D\setminus {(p,q)}$$ (6)

$$\sum{(i,j)\in D{pq}^{-1}} f{ij,pq} = \sum{(i,j)\in D} y_{ij} - 1 \tag{7}$$

$$f{ij,kl} \le My{ij} \qquad \forall ((i,j),(k,l)) \in A \tag{8}$$

$$f{ij,kl} \le My{kl} \qquad \forall ((i,j),(k,l)) \in A \tag{9}$$

Figure 5 shows an optimal solution with driveway connectivity constraints (6)–(9). The left panel contains the lot configuration for this instance, and the links with positive flow are shown in the graph on the right.

Figure 5: Driving fields must be connected to the entrance

We can thus write the complete MIP formulation for the parking lot optimization problem as

$$\max \sum{(i,j) \in P^0} x{ij}^0 + \sum{(i,j) \in P^{00}} x{ij}^{90} \tag{10}$$

s.t. (3)–(9)

$$y_{ij} = 1 \qquad \forall (i,j) \in Q \cup {(p,q)}$$ (11)

$$x_{ij}^{0} \in {0, 1}$$ $\forall (i, j) \in P^{0}$ (12)

$$x_{ij}^{90} \in {0, 1}$$ $\forall (i, j) \in P^{90}$ (13)

$$y_{ij} \in {0, 1} \qquad \qquad \forall (i, j) \in D \tag{14}$$

$$f_{ij,kl} \ge 0 \qquad \forall ((i,j),(k,l)) \in A \tag{15}$$

The flow variables are continuous in (15), but they take integral values at the optimal solution. This property follows from the total unimodularity of the coefficient matrix for any feasible combination of x and y variables. All arc flows emerging from the entrance cell are zeros, i.e., fpq,ij = 0 ∀ (i, j) ∈ Dpq. One can verify this by adding (6) for all cells (i, j) ∈ D \ {(p, q)}, and subtracting (7) from it. We also formulated and tested a multi-commodity version in which arc flows are disaggregated by valid driving cells. However, this approach significantly increased the number of variables and constraints, making it considerably slower to solve.

3 One-way parking lot configuration

Many parking lots are designed with one-way driving lanes to help accommodate more vehicles. This section considers such a variant and describes the model for a single entrance (p, q) and a single exit, denoted as (r, s). Any two distinct valid driving cells may serve as the entrance and exit cells. The driveways should allow vehicles entering to access all parking fields and enable them to return to the exit. Since driveways are one-way, we require δ ≥ ω.

(a) Lot and flow solution with only f variables (b) Lot and flow solution with only g variables

Figure 6: Modifications to driveway connectivity constraints for the single-lane one-way configuration. The entrance and exit cells are at (0,5) and (0,7), shown using dark and light purple nodes, respectively.

In Section 2.4, every driveway anchor cell except the entrance generates one unit of flow in (6), which are all guided to the entrance cell using (7). The entrance and exit locations are adjacent, and the driveways are two-way streets. However, imposing these constraints for the one-way case generates layouts that reach the entrance and exit but are not truly one-way streets, as shown in Figure 6a. The f variables ensure that all active driving cells are connected to the entrance, but not all are reachable from the exit. Note that the grid of valid driving cells differs from the previous grid since the driving fields are smaller.

3.1 Exit connectivity constraints

The previously described flow formulation can be viewed as a multi-origin single-destination problem. To connect parking fields to the exit, we additionally use single-origin multi-destination flow variables gij,kl for every arc ((i, j),(k, l)) ∈ A, representing the flow of another type/commodity. The exit cell sends out flow equal to one unit less than the total number of active driving field anchors in the grid, and using the g variables, one unit is delivered at each driving cell as shown in (16). Every active driving cell, apart from the exit cell, draws one unit of flow of this type according to (17). Constraints (18) and (19) set bounds on flow variables similar to (8) and (9), ensuring that only active driving fields are connected to the exit. Finally, (20) restricts the flows to be non-negative.

$$\sum{(i,j)\in D{rs}} g{rs,ij} = \sum{(i,j)\in D} y_{ij} - 1 \tag{16}$$

$$\sum{(k,l)\in D{i,1}^{-1}} g{kl,ij} - \sum{(k,l)\in D{ij}} g{ij,kl} = y_{ij} \qquad \forall (i,j)\in D\setminus {(r,s)}$$ (17)

$$g{ij,kl} \le M y{ij} \qquad \forall ((i,j),(k,l)) \in A \tag{18}$$

$$g{ij,kl} \le My{kl} \qquad \forall ((i,j),(k,l)) \in A \tag{19}$$

$$g_{ij,kl} \ge 0 \qquad \qquad \forall ((i,j),(k,l)) \in A \tag{20}$$

Figure 7: Parking lot and flow solutions with both f and g variables

A formulation with only the g variables will connect the entrances and exits but may still not produce one-way layouts, as seen from the parking lot and the flow solution in Figure 6b. Since we need connectivity from the entrance to the parking stalls and back to the exit, we include both types of driveway connectivity constraints involving f and g variables. However, this modification does not solve the problem, as seen in the outcome shown in Figure 7.

Note that the total outgoing flows from a valid driving cell (i, j) that is not the entrance or exit equals the sum of the incoming flows. Mathematically,

$$\sum{(k,l)\in D{ij}} (f{ij,kl} + g{ij,kl}) = \sum{(k,l)\in D{ij}^{-1}} (f{kl,ij} + g{kl,ij}) \qquad \forall (i,j)\in D\setminus ({p,q}\cup {r,s})$$ (21)

This is a direct consequence of (6) and (17). Apart from this equality, no constraints link f and g, particularly those that induce one-way restrictions.

3.2 Directionality constraints and dead ends

In the two-way case, one can take a U-turn and move in the reverse direction at dead ends. However, this feature must be restricted in the case of one-way driveways. In the flow solutions in Figures 6 and 7, many dead ends exist, and several arcs carry flow in both directions to ensure connectivity to the entrance or exit. Having arc flows in both directions poses ambiguities in fixing driveway directions and leads to infeasible one-way layouts. To navigate in such a layout, the vehicle must use the same driveway link in both directions, requiring them to take U-turns, which is impossible with one-way driveways. To prevent such solutions, we first define new binary decision variables zij,kl for each arc ((i, j),(k, l)) ∈ A that keep track whether the arc carries non-zero flows and sets the direction of vehicular movement. Bounds on zij,kl with respect to commodity flows can be set as shown in (22) and (23).

$$z{ij,kl} \le f{ij,kl} \le M z_{ij,kl} \qquad \forall ((i,j),(k,l)) \in A$$ (22)

$$z{ij,kl} \le g{ij,kl} \le M z_{ij,kl} \qquad \forall ((i,j),(k,l)) \in A \tag{23}$$

Constraint (22) ensures that zij,kl is zero if fij,kl is zero, and zij,kl is one if fij,kl > 0. Similar relations hold for the g variables. We can observe from (22) and (23) that it is not possible to have arcs with positive f values and zero g values, and vice versa. Thus, both f and g variables on an arc are positive (and consequently, the z variable is one), or all three variables are zero. The zij,kl variable cannot be one if it is not connected to active driving fields at either end. Hence, we can relate the z and y variables using (24) and (25). As before, we set M to |D| − 1. Note that these constraints along with (22) and (23) render bounds on f and g variables (8), (9), (18), and (19) redundant.

$$z{ij,kl} \le y{ij} \qquad \forall ((i,j),(k,l)) \in A \tag{24}$$

$$z{ij,kl} \le y{kl} \qquad \forall ((i,j),(k,l)) \in A \tag{25}$$

As seen in (21), if a driving cell that is not the entrance or the exit has inflow (with respect to both f and g variables), it must also have some outflow. To enforce one-way restrictions and avoid inflows and outflows between a given set of adjacent driving cells, we ensure that flow can occur only along one of the two possible arcs connecting them.

$$z{ij,kl} + z{kl,ij} \le 1 \qquad \forall ((i,j),(k,l)) \in A \tag{26}$$

Due to the above constraint, the driving layouts will also not contain dead ends or cul-de-sacs. In case there exists a driving cell that is a leaf node or a dead end, connectivity to both the entrance and exit requires an outgoing and an incoming arc, which would violate (26).

Similar to the two-way case, adding (17) for all (i, j) ∈ D \ {(r, s)} and comparing it with (16) implies gij,rs = 0 ∀ (i, j) ∈ D⁻¹ rs . Since the two-commodity flows can be either zero or positive on any arc, fij,rs = 0 ∀ (i, j) ∈ D⁻¹ rs and gpq,ij = 0 ∀ (i, j) ∈ Dpq. In other words, there are no outgoing flows from the entrance and no incoming flows to the exit. The complete formulation for the one-way driveway case can thus be written as follows. Figure 8 illustrates an optimal solution for this formulation.

$$\max \sum{(i,j) \in P^{0}} x{ij}^{0} + \sum{(i,j) \in P^{90}} x{ij}^{90}$$ s.t. (3)-(7), (12)-(17), (20), (22)-(26) $$y_{ij} = 1 \qquad \forall (i,j) \in Q \cup {(p,q),(r,s)}$$

$$z_{ij,kl} \in {0,1} \qquad \forall ((i,j),(k,l)) \in A \qquad (28)$$

Notice that while the lot appears navigable by vehicles of dimensions ω = 2 and ℓ = 3, the orientation of the direction variables at few locations, e.g., at cells (8,9), (8,10), (9,9), and (9,10), would force sharp turns that are impossible (unless the problem setting involves multiple smaller vehicles packed within each field or robots in a warehouse that can slide laterally). Turning can also be an issue in two-way parking layouts produced by the optimization models in Section 2 since the lanes are not clearly delimitated. We try to address these concerns in a generic manner through additional constraints in Appendix A for both two-way and one-way lanes. However, for the rest of the paper, we ignore the issues associated with turning since we focus on the R2 resolution (Stephan et al., 2021) with ω = 1, ℓ = 2, and δ = 2 for two-way lanes and δ = 1 for the one-way case where such concerns are less pronounced.

4 A branch-and-cut algorithm

The formulations discussed so far work well for small instances but are slow to converge for medium-scale problems. One reason is that the forcing constraints, which relate the flow variables to the driving or direction variables, lead to poor LP relaxations. Forbes and Harris (2022) suggested a cutting-plane method that avoids flow variables and thus the constant M. We build on this idea by first reformulating the problem using only binary parking and driving variables and strengthening the corresponding inequalities. We then devise a method in which a limited number of

(a) Parking lot layout (b) Driveway direction variables

Figure 8: Optimal solution to a single-lane one-way configuration

these cuts are added upfront, and the rest are generated dynamically within a branch-and-cut framework. Although the facet-defining properties are not explored in this study, the empirical performance of this approach is encouraging. The proposed method differs slightly for the one-way and two-way scenarios. We first explain the method for the two-way driving configuration in Section 4.1 and discuss the one-way case in Section 4.2.

4.1 Two-way driveways

An alternative formulation can be developed for the parking lot design problem by replacing the flow variables with modified driveway connectivity constraints of the form (30), which we will call connectivity cut constraints. This constraint ensures that a driving field can take a value of one only if at least one of the driving fields within specific vertex cut sets is active. A vertex cut set or a vertex separator is a subset of vertices in G which, when removed, partitions the graph into disconnected components with the entrance in one of them. For ease of exposition, assume that the vertex cut set partitions the graph into exactly two components. If more than two components are generated, smaller vertex cut sets can be created to separate the graph into two components, with the entrance/exit in one of them. Let Vpq be a collection of all vertex cut sets that separate the entrance/exit (p, q). We denote the partitions created by a vertex separator as a tuple (Vpq, V, V ′ pq), where V ∈ Vpq, Vpq is the component that contains the entrance/exit (p, q), and V ′ pq = D \ (Vpq ∪ V ). Thus, if the right-hand side of (30) is zero for a cut set V , then it forces all driving fields in V ′ pq to be inactive. However, the problem with this formulation is that the number of constraints grows exponentially with the size of D because the number of vertex cut sets can be extremely large.

$$\max \sum{(i,j)\in P^0} x{ij}^0 + \sum{(i,j)\in P^{00}} x{ij}^{90}$$ s.t. (3)-(5), (11)-(14) $$y{ij} \leq \sum y{kl} \qquad \forall (i,j) \in V'{pq}, V \in \mathcal{V}{pq}$$ (30)

4.1.1 Valid inequalities

(k,l)∈V

If the drive variables in a cut set are zero, it constrains the drive variables in the partition without the entrance to be zero due to (30). In addition, some of the parking variables can also be forced to be inactive. Specifically, all parking fields whose drive field neighbors lie exclusively in V ′ pq ∪ V would become inaccessible. To strengthen the connectivity cut constraints based on this observation, consider a cut set V and define the following sets. For a given cell (i, j) ∈ D and a set S ⊂ D, let P 0 ij (S) be the set of 0◦ parking fields containing (i, j) and whose driving field neighbors lie completely within S. Mathematically, P ij (S) = {(k, l) ∈ P⁰ ij : N⁰ kl ⊆ S}. Likewise, define P 90 ij (S) = {(k, l) ∈ P⁹⁰ ij : N⁹⁰ kl ⊆ S} and Dij (S) = Dij ∩ S. With these new sets, we can strengthen (30) as follows. Notice that the left-hand side of (31) is similar to that of the single-purpose constraint (3).

$$y{mn} + \sum{(k,l) \in \mathcal{P}{ij}^{0}(V'{pq} \cup V)} x{kl}^{0} + \sum{(k,l) \in \mathcal{P}{ij}^{00}(V'{pq} \cup V)} x{kl}^{90} \le \sum{(k,l) \in V} y{kl} \qquad \forall (i,j) \in V'{pq}, (m,n) \in \mathcal{D}{ij}(V'{pq})$$ (31)

The exponential number of constraints needed for enforcing connectivity are like the sub-tour elimination constraints of the traveling salesperson problem. To tackle this challenge, we employ three strategies. (1) We propose a family

Figure 9: Illustration of forward hop inequalities. The gray driving field (5, 3) is active only if accessible through its d-hop neighbors (pink). Inequalities can be strengthened by adding additional parking variables (green and blue). Yellow and orange nodes are neighbors of parking fields in the inequality, and the purple node is the entrance.

of valid inequalities added in advance. (2) To avoid slowing down the LP relaxations, we limit the number of these inequalities by only considering (m, n) = (i, j) instead of all (m, n) ∈ Dij (V ′ pq). (3) The model with these limited valid inequalities typically produces disconnected layouts, but the number of driving-field components is usually small. We propose a simple and effective procedure for generating feasibility cuts that reject such invalid integer solutions and iteratively add them to the branch-and-cut scheme when a violation is found. For the constraints added upfront, we describe a simple family of connectivity cut constraints, which we call bidirectional hop inequalities. These are added to the model as regular or lazy constraints and provide adequate restrictions to obtain reasonable upper bounds. We will use the example layout from the previous section to illustrate these methods but with the R2 resolution.

Forward hop inequalities: Finding vertex cuts for a given driving cell (i, j) that are a certain hop distance away is one way to generate connectivity cuts. Figure 9 illustrates vertex cut sets with pink nodes for the valid driving cell (5, 3), marked in gray, at distances ranging from d = 1 to 6 hops. The central node (5, 3) and its neighbors are colored based on the variables included in (31): gray for drive variables, green for 0◦ variables, and blue for 90◦ variables. Nodes with multiple colors represent all the corresponding variables that can be added to the valid inequality. The yellow and orange nodes denote the neighbors of the park variables on the left-hand side of (31). Initially, for a hop distance of one, only the drive variable is included on the left-hand side (see the d = 1 case). If all immediate neighbors of (5, 3) are inactive, connectivity to the entrance or exit from the gray cell cannot be ensured. In other words, at least one pink node has to be active to access the central driving field. Hence, we can add a cut y(5,3) ≤ y(5,2) +y(4,3) +y(5,4) +y(6,3). Additional park field variables may be added to the left-hand side for vertex cut sets with higher hop distances. For example, for a hop distance of 3, it is not possible to have a 0◦ park field at (5, 2) and (5, 3) if all pink cell drive variables are inactive. Similarly, the 90◦ park variable at (5, 3) can be included on the valid inequality's left-hand side. This is because their neighboring driving anchors from which they can be accessed are part of the vertex separator or entirely within the component not containing the entrance/exit. If a neighbor of a parking field is in the component containing the entrance/exit, the parking field remains accessible even if all driving cells in the vertex cut set are inactive. For a hop limit of 5 and 6, note that the vertex cut set creates more than one component. In these cases, as shown in the figure, the vertex separator is updated to only include essential drive field variables that separate the entrance/exit component from the cell (5, 3) for a tighter cut.

Let H^d ij be the set of nodes d hops from a driving field (i, j), and let πij be the shortest hop distance from (i, j) to the entrance (p, q). For a driving field (i, j), we write valid inequalities for hop distances up to πij . We set V = H^d and add a single constraint for cell (i, j), from which H^d ij is derived, instead of each cell in (H^d ij ) ′ pq. This minimizes

Figure 10: Pink nodes show vertex separators generated at different hop distances from the entrance (purple). Driving (gray) and parking fields (green and blue) can be included in the valid inequality if the neighbors (yellow and orange) are not in the component containing the entrance.

the number of lazy constraints, preventing LP relaxation slowdowns, and because other hop vertex separators are anyway generated for cells in (H^d ij ) ′ pq. Specifically, we include the following constraint in our formulation.

$$y{ij} + \sum{(k,l) \in \mathcal{P}{ij}^0(V{pq}' \cup V)} x{kl}^0 + \sum{(k,l) \in \mathcal{P}{ij}^{00}(V{pq}' \cup V)} x{kl}^{90} \le \sum{(k,l) \in V} y{kl} \quad \forall (i,j) \in D \setminus {(p,q)}, d \in {1,\dots,\pi{ij}}, V = H_{ij}^d \quad (32)$$

Intuitively, using these inequalities for different hop distances increases the likelihood of maintaining connectivity all the way to the entrance of the parking lot. Although for larger hop distances, there is a greater chance of including more decision variables on the left-hand side, it may also increase drive variables on the right-hand side, potentially reducing the constraint's effectiveness. Therefore, in our experiments, we add these inequalities as regular constraints for lower hop distances or when the right-hand side has fewer variables. The remaining hop inequalities are incorporated as lazy constraints.

Reverse hop inequalities: To help with connectivity closer to the entrance, we also use a reverse version of hop inequalities by considering vertex cut sets that are a certain hop distance away from the entrance cell. Specifically, we set V = H^d pq in (31), which consists of cells that are d hops away from the entrance (p, q), where d = {1, 2, . . . , πmax} and πmax is the maximum hop distance from the entrance to other cells in D. As illustrated in Figure 10, with increased hop distance, the vertex cut is closer to the central node, thereby reducing the odds of including additional decision variables on the left-hand side. If removing a vertex cut set creates more than one disconnected component, as previously described, we create multiple vertex cut sets from it, ensuring that each vertex cut set produces exactly two components of the graph. Then, we enforce the reverse hop inequality. An example instance that satisfies these bidirectional hop inequalities is shown in Figure 11a. The driveways are not connected, but there are only a small number of disconnected components. We also generated other families of vertex cut sets using rows and columns of the grid or through successive application of minimum cardinality vertex separators. However, they were found to be less effective than bidirectional hop inequalities.

4.1.2 Avoiding infeasible solutions

The integer feasible solutions with the earlier inequalities may be disconnected. Hence, we discard them using a series of vertex contractions and minimum cardinality vertex-cut problems to dynamically generate more connectivity cut constraints. Consider an integer feasible solution with disconnected driveways and active driving fields represented by Dint. First, we identify the set of connected components of Dint, denoted by C(Dint). Let the component containing the entrance be represented as Dint pq . We then pick a component C ∈ C(Dint) \ Dint pq and perform two sets of node contractions. (1) We contract the nodes in the set {(i, j) : (i, j) ∈ Dint pq ∪ (C(Dint) \ C)} to create a super-source. (2) We also contract the nodes in C to create a super-sink.

Finally, we solve a minimum cardinality vertex-cut problem between the super-source and the super-sink, to get a vertex cut set, say, V . We can then write connectivity cut constraints to avoid the current solution using (33) for all cells in C. This process is then repeated for every component C ∈ C(Dint) \ Dint pq .

$$y{ij} + \sum{(k,l) \in \mathcal{P}{ij}^{0}(V'{pq} \cup V)} x{kl}^{0} + \sum{(k,l) \in \mathcal{P}{ij}^{00}(V'{pq} \cup V)} x{kl}^{90} \le \sum{(k,l) \in V} y_{kl} \qquad \forall (i,j) \in C$$

$$(33)$$

Note that node contractions are necessary before finding the vertex cut set. Otherwise, we might find a cut set that contains active driving nodes from one of the other components. Consequently, we would not discard the current solution because the right-hand side of (33) would be greater than or equal to one. Figure 11 shows the steps in discovering these feasibility cuts. The infeasible layout has three connected components. The nodes in Dint pq are indicated in purple in Figure 11b. The other driveway components in C(Dint) are colored gray. We contract the union of all purple nodes and the bottom component of the driveway graph to create a super-source and contract the middle component to generate a super-sink. The resulting vertex cut set between them is shown in the left panel of Figure 11c. A similar process is repeated by contracting the purple nodes and the nodes in the middle component. The super-source and the contracted super-sink are then used to find a minimum vertex cut set, which is shown using the pink nodes in Figure 11c. As seen in the case of hop inequalities, it is sometimes possible to get a vertex separator that splits the contracted graphs into more than two components. In such cases, to make the cuts tighter, we shrink the vertex separator by only including the nodes that separate the entrance from the elements in C. Note that just one of the above-mentioned cuts is sufficient to avoid the current solution. However, adding multiple constraints and letting the solver decide where else to apply them can tighten the LP relaxation along the branch-and-bound tree.

Figure 11: Generating vertex cut sets within the branch-and-cut algorithm

4.2 One-way driveways

The branch-and-cut algorithm can also be designed for the problem of parking with one-way streets using only binary variables. The connectivity cut inequalities discussed earlier are also valid for this variant and ensure that each driving field is connected to the entrance (p, q) and the exit (r, s). For example, a solution in Figure 12 with ω = δ = 1, and ℓ = 2, satisfies the bidirectional hop constraints and restrictions on the z variables that determine the directions of the driveways. However, this is not a feasible one-way configuration, as reaching the exit requires us to backtrack along the path from the entrance. Note that there is always an optimal solution that does not use a direct connection between the entrance and exit cells, e.g., (0,5) to (0,6); therefore, these arcs can be removed from the graph G.

The primary issue is that the previously defined connectivity cut constraints operate in an undirected sense. To fix this limitation, we redefine them using edge separators or edge cut sets that partition the graph of driving fields into two strongly connected components: W ∈ Wij , which contains a valid driving cell (i, j) and its complement W′ . The set Wij represents all possible subsets of valid drive cells that contain (i, j), each of which has nodes that are strongly connected. Constraints (35) and (36) force the driving field variables in W′ to zero if they cannot access the entrance or cannot be reached by the exit. This situation can arise when the z variables for specific edge sets between the two components W and W′ are inactive. The modified feasibility cuts can also be strengthened by including specific

(a) Layout with bidirectional hop inequalities (b) Direction variables z

Figure 12: Infeasible solutions from the two-way branch-and-cut approach for the one-way scenario

parking field variables on the left-hand side whenever possible.

$$\max \sum{(i,j)\in P^0} x{ij}^0 + \sum{(i,j)\in P^{90}} x{ij}^{90} \tag{34}$$

s.t. (3)–(5),(12)–(14),(24)–(28)

$$y{mn} \le \sum{(i,j)\in W',(k,l)\in W} z{ij,kl} \qquad \forall W \in \mathcal{W}{pq},(m,n) \in W'$$ (35)

$$y{mn} \le \sum{(i,j) \in W, (k,l) \in W'} z{ij,kl} \qquad \forall W \in \mathcal{W}{rs}, (m,n) \in W'$$ (36)

4.2.1 Valid inequalities

As noted in the previous section, the number of feasibility cuts grows exponentially for the one-way case, and this is also true for the new connectivity cut constraints. We take a similar approach as before, generating a limited number of valid inequalities added as regular and lazy constraints.

Bidirectional hop constraints: The constraints from Section 4.1.1 are also valid for the one-way scenario. One could introduce two types of valid inequalities, where hop distances are calculated with respect to both the entrance and exit. However, this led to too many constraints and showed marginal differences in runtimes. Hence, we only included bidirectional hop inequalities with respect to the entrance cell.

Dead end prevention constraints: In the flow formulation version discussed in Section 3.2, constraints involving the lane direction variables z and the flow variables f and g prevented dead ends. Alternatively, it is possible to write valid inequalities that eliminate dead ends without using the flow variables. This can be done (1) purely using drive field variables y or (2) using both y and z variables.

For constraints with only y variables, a valid driving cell with a single neighbor cannot anchor an active driving field (see (37)). In other situations, an active driving cell must have at least two active neighbors to prevent dead ends. The logic for this constraint is captured in (38).

$$y{ij} = 0 \qquad \forall (i,j) \in D, |D{ij}| = 1 \tag{37}$$

$$\sum{(k,l)\in D{ij}} y{kl} \ge 2y{ij} \qquad \forall (i,j) \in D \setminus {(p,q) \cup (r,s)}, |D_{ij}| > 1$$ (38)

Additionally, we can also enforce (39) and (40). These constraints ensure at least one active outgoing and incoming arc for all active drive cells, excluding the entrance and exit cells.

$$\sum{(k,l)\in D{ij}} z{ij,kl} \ge y{ij} \qquad \forall (i,j)\in D\setminus{(p,q)}$$ (39)

$$\sum{(k,l)\in D^{-1}\atop i} z{kl,ij} \ge y_{ij} \qquad \forall (i,j)\in D\setminus {(r,s)}$$

$$(40)$$

4.2.2 Avoiding infeasible solutions

Adding the above inequalities can still result in layouts with few disconnected components (e.g., see Figure 13a). We generate violated constraints and add them to the branch-and-bound process as a remedy. This step is done separately for the entrance and exit. As before, let Dint indicate the driving cells currently active in the infeasible solution. We let Dint pq denote the driving cells that have a directed path to the entrance cell and Dint rs be the set of active driving cells that can be reached via directed paths from the exit. These sets are shown using the dark and light purple nodes in Figures 13b and 13c, respectively.

Figure 13: Generating edge cut sets within the branch-and-cut algorithm

To ensure the connectivity of driveways to the entrance, if |Dint pq | < |Dint|, we first assign weights to the arcs in G. Arcs connecting active drive cells, i.e., the ones for which the z variables are one, are assigned a weight M. Every other arc is assigned a weight of one. We then create a new super-source and connect arcs from it to all vertices in Dint pq . Similarly, we connect all other active driving cells Dint \ Dint pq to a newly created super-sink. The arcs incident to the super-source and super-sink are also assigned a weight of M. In Figure 13b, the purple and gray nodes at the top left and bottom right represent the super-source and super-sink, respectively.

We then solve a minimum weighted edge cut problem between these nodes to find partitions W′ pq and Wpq that separate Dint \ Dint pq and Dint pq , respectively. By assigning a weight of one to arcs with inactive z variables and large weights to the rest, this edge cut set has minimum cardinality (see the pink arcs in the example). Consequently, the resulting feasibility cut will feature fewer terms on the right-hand side, enhancing its effectiveness. The number of arcs in A is a good choice for M. Note that Dint \ Dint pq can have more than one connected component, as seen in Figure 13b. In such situations, multiple edge cut sets can be generated to separate each component from the rest, but this would require more computational effort. The partitions and edge cut set generate a feasibility cut, which can be strengthened with parking variables as shown in (41).

$$y{mn} + \sum{(k,l) \in \mathcal{P}{ij}^{0}(W{pq}^{\prime})} x{kl}^{0} + \sum{(k,l) \in \mathcal{P}{ij}^{90}(W{pq}^{\prime})} x{kl}^{90} \leq \sum{(i,j) \in W{pq}^{\prime},(k,l) \in W{pq}} z{ij,kl} \qquad \forall (m,n) \in D^{int} \setminus D{pq}^{int}$$ (41)

We follow a similar approach to connect the exit to valid driving cells. We first check if |Dint rs | < |Dint|. If so, a new super-source is created and is linked to all active driving cells in Dint \ Dint rs . We then link all driving cells that can be accessed from the exit Dint rs to a new super-sink. As before, arc weights are set to one when the z variables are inactive and to M for others to find a minimum weighted edge cut. Figure 13c shows an example of this procedure. The gray node at the bottom right and the purple node at the top left depict the super-source and super-sink, respectively. The resulting edge cut set is shown in pink. Let the partitions that separate Dint rs and Dint \ Dint rs be denoted as Wrs and W′ rs, respectively. Using this notation, adding (42) to the branch-and-bound algorithm will help discard the current infeasible solution.

$$y{mn} + \sum{(k,l) \in \mathcal{P}{ij}^0(W'{rs})} x{kl}^0 + \sum{(k,l) \in \mathcal{P}{ij}^{00}(W'{rs})} x{kl}^{90} \le \sum{(i,j) \in W{rs}, (k,l) \in W'{rs}} z{ij,kl} \qquad \forall (m,n) \in D^{int} \setminus D{rs}^{int}$$ (42)

5 Experiments

5.1 Dataset

We tested the performance of the MIP models for 325 real-world parking lots from New York City (NYC) Open Data. These lots correspond to open-air street parking facilities in lower and midtown Manhattan and parts of Brooklyn and Queens and have areas ranging from 6011 sq ft to 28436 sq ft (roughly up to half the size of a football field). The chosen lots have IDs in the 125 and 215 series, and their locations are illustrated in different colors in Figure 14a. The area distribution is shown in Figure 14b. Although data on the exact number of stalls in these parking lots is unavailable, we study the utility of models from a computational standpoint and analyze the differences between two-way and one-way layouts. Experiments on exact methods in (Stephan et al., 2021) were run on layouts in the range 6458–19375 sq ft, although heuristics were tested on larger instances in their paper.

Figure 14: Real-world instances of open street parking lots from New York City

Each parking lot is a polygon with corners specified as latitudes and longitudes. Access to the parking lot is found by scanning a circular area (of suitable radius) around the lot using OpenStreetMap (OSM) to get the driving streets in its vicinity. The entrance to the parking lot is then set as one of the edges of the polygon closest to the nearby streets. We designate a parking lot's entrance and exit points to be next to each other. For example, Figure 15a shows a satellite image of a parking lot, and its corresponding polygon is shown in Figure 15b. The closest street is then used to set the entrance in the rasterized grid (see the purple segment in Figure 15c).

Figure 15: Processing a parking lot instance

For rasterization, we considered 3 m wide driveways. The size of the parking stalls was set to 6 m × 3 m, i.e., a parking field occupies two cells. At the polygon's boundaries, we can apply a threshold-based rule for including a cell in the parking lot depending on the fraction of its area contained within the polygon. For the experiments in this section, any cell that overlaps with the polygon is assumed to be part of the parking lot, and the other cells are marked as blocked cells. The final grid with R2 resolution is shown in Figure 15d.

All experiments were conducted on a Dell Precision workstation having a 32-core AMD Ryzen Threadripper Pro

7975WX CPU @ 4.0 GHz and 256 GB of RAM. The algorithms were coded in Python 3.10 with CPLEX 22.1.1, utilizing the callback functionality for the branch-and-cut algorithm and NetworkX for finding bidirectional hops and vertex and edge cut sets. A time limit of 900 s is set for each instance. Experiments were also conducted on a subset of instances with a time budget of two hours. Additional details supporting the main results, along with a comparison of the benefits of including the bidirectional hop inequalities in the branch-and-cut method, are provided in Appendix B.

5.2 Computational performance

Analysis of one-way and two-way driving layout solutions: Figure 16a shows the best lower bounds of the three formulations—flow-based model discussed in Sections 2 and 3 (which is the baseline model), flow-based model with valid inequalities (bidirectional hop and dead end constraints), and a branch-and-cut version—for the one-way and two-way configurations. While many of these instances are solved optimally, others are terminated due to the time limit with an optimality gap. A total of 13291 stalls are discovered for the two-way version. An additional 2476 stalls can be accommodated if the drive layouts are one-way, which is an 18.63% increase. The difference in the number of stalls between the one-way and two-way configurations is relatively less for smaller lots. However, it grows significantly with the parking lot area. The absolute difference between the upper and lower bounds is shown in Figure 16b. Out of 325 instances, the gap is zero for 245 two-way and 288 one-way instances. The absolute optimality gap in the two-way models was generally higher than in the one-way version when the time limits were reached.

Figure 16: Comparison between one-way and two-way solutions

Two-way layouts: We analyzed the computational performance of the three formulations for the two-way case by grouping all instances into two categories: (I) 187 instances in which all methods discover optimal solutions within 15 minutes and (II) 138 instances that are timed out for at least one method (which in this case was always the flow formulation). See Table 2 for a summary. Note that the average of 100.97 s for the flow formulation is significantly higher than the median since some instances take longer to solve, but the optimal solution is found within 15 min. Hence, we will make comparisons with reference to the median values. For the first group, the bidirectional hop inequalities in the flow-based formulation significantly reduce the median runtimes by 74.70%. A further reduction of 18.40% is noticed when using the branch-and-cut algorithm. For the slightly harder Group II instances, we compare the integer lower bounds, best LP relaxation upper bounds, and the relative gap (expressed as a ratio). The branchand-cut method could solve 58 of these instances optimally. Overall, the flow model with valid inequalities performed better, and across all instances in Group II, the flow model discovered 7724 stalls, the flow version with VIs found 7889 stalls, and the branch-and-cut method yielded 7811 parking stalls.

One-way layouts: For the one-way case, we again classified the instances into two groups: (I) 149 instances in which all three methods terminate within 15 min and (II) 176 instances in which at least one of the three methods has a non-zero gap. Unlike the two-way case, some of the instances in group II terminated with zero gaps when using the flow formulation. Surprisingly, the flow version with valid inequalities did not improve the runtimes and the gaps. Compared to the flow formulations in Group I, the branch-and-cut algorithm was 87.43% faster with respect to the median times. Across all instances in Group II, the flow formulations with and without valid inequalities discovered 9715 and 9830 parking stalls, respectively, whereas the branch-and-cut found 10434 stalls. Of the 176 instances in Group II, the branch-and-cut method found an optimal solution in 139 instances, which is also reflected in the average and median gap values.

Table 2: Summary statistics for the two-way and one-way experiments. All times are in seconds. LB and UB indicate lower bounds and upper bounds, respectively.

| | | Two-Way | | | One-Way | | | | | | | |----------|-------------------|---------|---------|--------|----------|-----------------|-------------------|---------|--------|--|--| | Group | Statistics | | Average | Median | Group | Statistics | | Average | Median | | | | | Objective value | | 28.68 | 28 | | Objective value | | 35.71 | 35 | | | | | Time (Flow) | | 100.97 | 12.76 | | Time (Flow) | | 111.44 | 43.23 | | | | I (187) | Time (Flow & VIs) | | 7.12 | 3.23 | I (149) | | Time (Flow & VIs) | | 47.31 | | | | | Time (BnC) | | 5.34 | 2.63 | | Time in s (BnC) | | 12.19 | 5.43 | | | | | Flow | LB | 55.97 | 55 | | | LB | 55.20 | 55 | | | | | | UB | 69.22 | 66.03 | | Flow | UB | 65.13 | 62.88 | | | | | | Gap | 0.22 | 0.20 | | | Gap | 0.19 | 0.12 | | | | | Flow & VIs | LB | 57.17 | 56 | | | LB | 55.85 | 55 | | | | | | UB | 65.16 | 61.90 | | Flow & VIs | UB | 65.81 | 63.99 | | | | II (138) | | Gap | 0.12 | 0.12 | II (176) | | Gap | 0.32 | 0.12 | | | | | BnC | LB | 56.60 | 55 | | | LB | 59.28 | 58 | | | | | | UB | 63.77 | 60.00 | | BnC | UB | 60.85 | 58 | | | | | | Gap | 0.10 | 0.08 | | | Gap | 0.02 | 0 | | |

Extended analysis: We also tested the performance of all three formulations for both driving layout configurations with a longer time limit of two hours. These experiments demonstrated that the trends in the computational times and gaps hold when run for longer periods. We choose lots with areas closest to the median area values of the instances in the 14 bins shown in Figure 14b. The results of these trials are shown in Tables 3 and 4 for the two-way and one-way cases, respectively. The bold LB values represent the best solution among the three formulations. The number of user cuts dynamically generated within the branch-and-cut method is indicated in the last column. The restrictions imposed by the added inequalities help reduce the upper bounds to a relatively greater degree. Needless to say, in the other cases, the branch-and-cut algorithm reached optimality more quickly. The flow-based formulation did not "catch up" with respect to the bounds, and including the valid inequalities helped discover better lower bounds. The branch-and-cut method yielded the tightest upper bounds among all three formulations.

Table 3: Runtimes (in seconds) and gaps of the two-way parking lot formulations

		Flow				Flow with VIs		Branch-and-cut
Instance ID	Time	LB	UB	Gap	Time	LB	UB	Gap	Time	LB	UB	Gap	Cuts
125-068	1.6	20	20	0	0.7	20	20	0	0.5	20	20	0	12
125-140	4.5	26	26	0	2.4	26	26	0	1.4	26	26	0	85
125-299	51.3	33	33	0	12.9	33	33	0	10.5	33	33	0	500
125-425	785.8	41	41	0	9.4	41	41	0	7.6	41	41	0	442
125-116	2524.6	38	38	0	69.2	38	38	0	60.4	38	38	0	421
125-026	7200.1	46	48.54	0.06	63.4	46	46	0	43.7	46	46	0	2518
125-269	7200.8	56	60.24	0.08	4460.5	56	56	0	2850.3	56	56	0	8462
125-158	7200.4	64	73.24	0.14	6562.6	64	64	0	1265.5	64	64	0	2578
125-355	7200.6	68	78.44	0.15	7207.9	68	71.75	0.06	3851.9	68	68	0	6780
125-372	7200.4	70	88.17	0.26	7213.5	73	84.04	0.15	7215.0	72	81.28	0.13	14826
215-145	7200.4	70	88.21	0.26	7211.9	70	83.05	0.19	7216.2	71	80.69	0.14	21274
125-094	7200.4	84	104.58	0.24	7214.0	85	101.65	0.20	7217.0	80	101.48	0.27	47929
125-407	7200.3	82	106.48	0.30	7212.4	87	102.85	0.18	7215.0	80	100.57	0.26	23286
125-112	7200.4	92	119.28	0.30	7215.9	93	115.30	0.24	7221.3	87	113.96	0.31	52962

In the one-way case, the branch-and-cut algorithm discovered the same or more parking lots and terminated with a smaller gap when the time limit was reached, except for one case. As noted earlier, the branch-and-cut method proved more powerful for the one-way scenario than the two-way case and was exceedingly fast in generating optimal solutions. In some instances, optimal solutions were generated in minutes, whereas flow-based formulations could not find or certify optimality even after two hours due to poor upper bounds. Figures 17 and 18 show sample parking lot solutions for some of the instances from these experiments.

Table 4: Runtimes (in seconds) and gaps of the one-way parking lot formulations

| | | | Flow | | | | Flow with VIs | | Branch-and-cut | | | | | | |-------------|--------|-----|--------|------|--------|-----|---------------|------|----------------|-----|--------|------|-------|--| | Instance ID | Time | LB | UB | Gap | Time | LB | UB | Gap | Time | LB | UB | Gap | Cuts | | | 125-068 | 9.0 | 24 | 24 | 0 | 4.4 | 24 | 24 | 0 | 2.2 | 24 | 24 | 0 | 938 | | | 125-140 | 77.2 | 30 | 30 | 0 | 44.0 | 30 | 30 | 0 | 4.7 | 30 | 30 | 0 | 1532 | | | 125-299 | 126.4 | 39 | 39 | 0 | 170.3 | 39 | 39 | 0 | 28.4 | 39 | 39 | 0 | 2880 | | | 125-425 | 7200.1 | 42 | 47.41 | 0.13 | 7206.5 | 42 | 48.77 | 0.16 | 33.1 | 44 | 44 | 0 | 3860 | | | 125-116 | 1340.0 | 46 | 46 | 0 | 3592.6 | 46 | 46 | 0 | 51.7 | 46 | 46 | 0 | 6374 | | | 125-026 | 1560.6 | 56 | 56 | 0 | 6614.3 | 56 | 56 | 0 | 38.3 | 56 | 56 | 0 | 6720 | | | 125-269 | 3223.6 | 64 | 64 | 0 | 7203.9 | 64 | 66 | 0 | 369.5 | 64 | 64 | 0 | 9055 | | | 125-158 | 7200.2 | 78 | 80.18 | 0.03 | 7209.9 | 78 | 80.58 | 0.03 | 159.0 | 78 | 78 | 0 | 16143 | | | 125-355 | 7200.2 | 83 | 84.83 | 0.02 | 7214.6 | 83 | 84.88 | 0.02 | 146.0 | 83 | 83 | 0 | 10198 | | | 125-372 | 7200.2 | 88 | 94.29 | 0.07 | 7221.2 | 88 | 95.99 | 0.09 | 2146.6 | 89 | 89 | 0 | 21389 | | | 215-145 | 7200.4 | 82 | 96.40 | 0.18 | 7216.8 | 88 | 96.44 | 0.10 | 5166.2 | 89 | 89 | 0 | 50973 | | | 125-094 | 7200.4 | 104 | 108.06 | 0.04 | 7218.3 | 101 | 110.08 | 0.09 | 7217.2 | 103 | 107.60 | 0.04 | 22696 | | | 125-407 | 7200.5 | 95 | 112.03 | 0.18 | 7216.4 | 101 | 112.13 | 0.11 | 7217.9 | 103 | 111.28 | 0.08 | 64819 | | | 125-112 | 7204.6 | 103 | 123.46 | 0.20 | 7219.8 | 112 | 124.34 | 0.11 | 7222.2 | 113 | 122.68 | 0.09 | 35412 | |

Figure 17: Sample parking lots for the two-way driveway configuration

Figure 18: Sample parking lots for the one-way driveway configuration

6 Conclusion

This paper proposed alternative integer programming formulations to optimize the number of stalls in a parking lot. We divided the lot into a grid where each cell is associated with variables that determine whether it is designated for parking, driving, or left empty. The constraints ensure that each cell is used for a single purpose and that parking fields are connected using driveways. For one-way driveways, we included additional flow and directionality variables to help decide the flow of traffic on the grid and prevent dead ends. In the one-way and two-way cases, the flow variables appear in forcing constraints with big-M terms, leading to poorer runtimes when using an off-the-shelf solver. We reformulated these problems by defining connectivity cut constraints to link driveways to entrances and exits. A simple family of valid inequalities was proposed using neighbors at different hop distances from a central cell and from the entrance/exit. These constraints resulted in layouts with few disconnected driveway components. We repaired such solutions by generating additional constraints using minimum-cardinality vertex or edge cut sets during the branch-and-bound process. Our experiments on 325 NYC parking layouts highlighted the advantages of the valid inequalities and the branch-and-cut method. The branch-and-cut algorithm's median runtimes were significantly faster than the baseline flow-based formulation.

There are several potential directions for future research. While we focused on maximizing the number of parking stalls, evaluating different layouts from a traffic perspective can provide a comprehensive approach to parking lot design. In addition, parking lots are often heterogeneous and accommodate various vehicle sizes, with parallel and angled parking options. Requirements for differently-abled parking and electric vehicle charging can add practical value. From a computational perspective, while LP relaxations improve with added cuts, these cuts are added only for integer feasible solutions and not at other tree nodes. Adding cuts at other nodes can quickly prune less promising search space regions, but would require a fast maximum separation subroutine. One could also explore branching rules that fix a block of parking field variables or partitioning techniques that divide a lot into smaller regions. Discovering other valid inequalities and analyzing their mathematical properties can also significantly improve model formulations.

Appendix A Practical considerations

Turn restrictions for two-ways: The two-way formulations discussed so far ensure the connectivity and accessibility of parking lots and driving fields. However, the driving fields are not translated into the actual lane design. This is challenging to accomplish purely with the drive field or flow variables. The lack of designated lanes makes it tricky to anticipate vehicle paths to parking stalls and identify the issues they might encounter while turning. Stephan et al. (2021) proposed additional restrictions using the drive and flow variables, which provide sufficient spaces for vehicles to turn. We can include similar constraints using only the drive variables to make the method amenable to the branch-and-cut framework. Developing a fully generalized model that works in all cases seems challenging, as it largely depends on the required level of maneuverability. For example, tight turns might be sufficient for long-term parking or when using robotic units. This section provides some ways to 'polish' the driveway layouts. These modifications mainly attempt to (1) keep the angle of turns at 90◦ and the width of the driveways uniform and (2) avoid sharp turns. These adjustments become particularly crucial when the rasterization is coarse. For this section, we denote yij and zij,kl more elaborately as y(i,j) and z(i,j),(k,l) to avoid confusion over the indices in the examples.

(a) An indistinct perpendicular turn and a sharp turn (b) Layouts without and with turn restrictions

Figure 19: Imposing turn restrictions for two-way configurations

Since driving fields can overlap, instances shown in Figure 19a can occur (here δ = 4), where the perpendicular turns are indistinct, leading to non-uniform driving lanes or the layouts may feature sharp turns, where drivers take consecutive right and left turns, complicating maneuvering. (We may want to permit the latter if we want to approximate curved driving sections using finer rasterization.) With additional restrictions, the number of stalls is reduced by one, but the driveways have uniform widths and well-defined turns. One solution to circumvent such issues is to prohibit overlapping driving fields. This can be modeled by defining arcs in G that connect every node to other nodes that are δ hops away in longitudinal (north-south) and lateral (east-west) directions. However, such an approach would significantly reduce parking stalls, as driving lanes can only be created in lengths that are multiples of δ. Instead, we could restrict combinations of driving fields from being active. The example in Figure 19b depicts a layout without and with these restrictions. This parking lot solution is based on the R2 resolution and has a drive field width δ = 2.

Figure 20: Restrictions for handling turn-related issues

In this approach, a turn is characterized by three active driving cells in a 2 × 2 field. Four possibilities can occur, as shown using the anchors in the example in Figure 20, where δ = 4. To avoid indistinct perpendicular turns and keep the width of the driveway uniform, we can prevent cells in the teal 3 × 3 (which in the general case would be (δ − 1) × (δ − 1)) from being active if the three cells around its corner that are anchors of driving fields are active.

Figure 21: Combinations of direction variables that are avoided for δ = 2. Black arcs represent active z variables, and teal arcs are restricted to be inactive.

For example, in the panel on the left, we set constraints of the form y(i+k,j+k) + y(i+1,j) + y(i,j) + y(i,j+1) ≤ 3 where k ∈ {1, . . . , δ − 1}, which forces at most three of these y variables to be active. Similar constraints can be written in the other cases shown in the figure. In addition, if we want to prevent sharp turns, one could add such constraints using the cells shown in dark teal. They would prevent zig-zag driveways and can also be extended to include more cells to control where exactly the next turn is allowed. In the example from the left-most panel, these constraints would be of the form y(i+1,j−1) + y(i+1,j) + y(i,j) + y(i,j+1) ≤ 3 and y(i−1,j+1) + y(i+1,j) + y(i,j) + y(i,j+1) ≤ 3.

Turn restrictions for one-ways: For one-way configurations, the presence of the direction variables z gives us relatively more control over the turning restrictions. To avoid overlapping driving fields with opposite moving traffic, we first restrict combinations of direction variables as shown in Figure 21a, where δ = 2. More generally, if a direction variable z(i,j),(i+1,j) is active, we require variables in the opposite direction z(i+1,j+k),(i,j+k) to be inactive for k ∈ {1, . . . , δ − 1}. Likewise, if z(i,j),(i,j+1) is active, then z(i+k,j+1),(i+k,j) must be inactive for the same set of k values. These constraints can simply be enforced using an upper bound of one on the sum of pairs of combinations that are restricted. For example, in Figure 21a, we set z(3,3),(4,3) + z(4,4),(3,4) ≤ 1 and z(7,7),(7,8) + z(8,8),(8,7) ≤ 1.

Figure 22a shows an optimal solution with these constraints. Observe that when two driving fields are next to each other, the traffic moves in the same direction. In other words, it is possible to merge these fields into larger driveways that point in the same direction. E.g., see the fields anchored at (9, 5), (9, 6), (9, 7), (10, 5), (10, 6), and (10, 7). A model that adheres to these constraints can also approximate curved driveways using a step-like sequence of driving fields, as mentioned earlier in the two-way case. However, when the size of the driving field is smaller than the vehicle length, we might want the vehicles to fit fully within two adjacent junctions. In such cases, additional restrictions are required on combinations of z variables, which are illustrated in Figure 21b. In these diagrams, we examine eight possible turn movements at an active driving cell. Consider the example in the upper left cell (3, 3) of the figure's left panel. Vehicles driving east turn left to head north. If ℓ = 3, then to avoid sharp turns, we do not allow the z variables starting at (1, 3) and (2, 3) and going in the east-west direction to be active. No restrictions are placed on the z variables starting at (0, 3) since the longitudinal segment from (3, 3) to (0, 3) spans three cells, which is sufficient to hold a vehicle. Generalizing this, if z(i,j−1),(i,j) and z(i,j),(i−1,j) are ones, then z(i−k,j),(i−k,j−1) and z(i−k,j),(i−k,j+1) for k ∈ {1, . . . , ℓ − 1} must be zero.

(a) Lot and directions without infeasible overlaps (b) Lot and directions with minimum length constraints

Figure 22: Results from adding turn restriction constraints

In the earlier example, this can easily be set using four constraints, one of which is z(3,2),(3,3)+z(3,3),(2,3)+z(2,3),(2,4) ≤ 2. Note that some of these inequalities may be redundant if constraints that avoid overlapping of opposite moving traffic are included. For larger vehicles, turning might still present challenges; in such scenarios, we can modify these restrictions to either extend the distance between intersections or increase the sizes of the cells. Figure 22b shows a solution satisfying these inequalities. It can be seen that driveways are more organized and facilitate smoother turns, although this results in fewer available parking stalls. In both one-way and two-way cases, additional constraints may be needed at the entrance or exit depending on the configuration of the access roads.

Multiple entrances and exits: Parking lots often have multiple entrances and exits. We can design such lots in two ways. (1) All driveways can be connected, ensuring that entrances and exits are accessible from each other. (2) We can relax this requirement and potentially create multiple disjoint lots. In the first case, we make the driving field variables active for all entrance cells and solve the problem as a single entrance/exit model with any entrance cell in the grid as the entry point. An optimal solution for the two-way and one-way case with connected entrance cells is shown in Figure 23a. The number of parking stalls may be reduced compared to a single entrance/exit case due to the space allocated for entrance locations.

Figure 23: Layouts with multiple entrances and exits.

In the second approach, we can solve the problem assuming that all entrances/exits are not necessarily connected, but the driveways provide access to each parking space from at least one of the entrances/exits. This type of design may be suitable for large parking lots with multiple access roads on different sides. Solving this variant again is easy and can be done by simply connecting the entrances (and the exits) in the grid graph of valid driving fields with dummy arcs. The connectivity cut constraints would then require each active driving cell to be connected to at least one entrance/exit. Figure 23b shows an optimal solution using this technique. The driveways originating from different entrances, in this case, are disjoint. The number of parking stalls also increased compared to the connected layouts by two for both the two-way and one-way cases. Disconnected parking entrances can make the overall space behave as separate lots and increase capacity. However, the search for parking could be prolonged since if one section of the lot is full, vehicles must exit, navigate the public streets, and reenter a different area via an alternate entrance.

Appendix B Additional results

This section presents additional statistics on the problem sizes and results from experiments conducted on the oneway and two-way versions of the problem. Recall that for each driveway configuration, three formulations were analyzed. The first baseline model solves the flow-based formulation. The second uses flow variables but includes valid inequalities, and the third optimizes lots using the branch-and-cut algorithm.

Problem size: Figure 24a illustrates how the number of variables changes with the area for the 325 parking lots used in this research. The relationship is more or less linear for all formulations. In the two-way (and one-way) case, flow-based formulations have a lot more variables than the branch-and-cut method because of the f (and g) variables. The valid inequalities add about 135% more constraints on average for the two-way case and 74% for the one-way case (see Figure 24b). The branch-and-cut formulation generally has fewer constraints. Although valid inequalities are present in this formulation, the constraint count usually falls between those of flow-based models with and without valid inequalities due to the absence of flow constraints. However, in many cases, particularly the one-way configurations, the number of constraints in the branch-and-cut formulation might be lower than those in the flow-based formulation. These statistics only indicate the structural constraints and do not include the feasibility cuts added during the branching process. The constraints can increase sharply for larger lots, especially with fewer blocked fields. In these cases, the bidirectional hop inequalities can be significantly large in number.

Figure 24: Problem sizes for parking lots for different instances

Runtimes and gaps for experiments with a 15-minute limit: A scatter plot of the runtimes between the different formulations for the 325 instances is shown in Figure 25a. Adding hop and bidirectional hop inequalities to the flow formulation improved runtimes significantly, as seen in the left panel. The branch-and-cut method was also faster than flow formulation. However, as seen in the right panel, it did not offer significant advantages over the flow formulation with valid inequalities. The trends in the gaps for instances that did not find an optimal solution within the 15-minute time limit are also similar and can be seen in Figure 25b.

Figure 25: Computational results for the two-way experiments

Figures 26a and 26b compare the times and gaps for the one-way case, respectively. Unlike the two-way scenario,

adding valid inequalities to the flow formulation was counterproductive (see left panels). However, the branch-andcut method fared very well, as seen from the right panels. Five instances terminated with a very high gap when using the flow formulation and were excluded from these plots for better readability.

Figure 26: Computational results for the one-way experiments

Effect of bidirectional hop and dead end constraints on the branch-and-cut algorithm: To evaluate the impact of the valid inequalities added at the start (bidirectional hop and dead end constraints), we tested a version of the branch-and-cut algorithm without them. For the two-way case, with a time limit of 15 min, this version did not solve six instances optimally among the ones solved by the earlier branch-and-cut formulation. The median and average runtimes for instances where both methods produced optimal solutions were 42.51% and 71.64% slower than the previous branch-and-cut version, respectively. For the more difficult instances in which either one of the methods failed to find an optimal solution in 15 min, the median and average gaps without valid inequalities were 0.19 and 0.22, compared to 0.15 and 0.17 for the version with valid inequalities.

For the one-way case, the model performed very poorly without valid inequalities. Out of the 288 instances solved optimally in 15 min using the previous branch-and-cut algorithm, an optimal solution was found in only 132 instances when run without valid inequalities. For instances that could be solved optimally by both methods, the median and average runtimes without valid inequalities worsened to 198.58 s and 363.92 s (compared to 6.08 s and 8.77 s when using valid inequalities). Among the remaining problems, in 169 instances, no integer feasible solution was found after 15 min. Without valid inequalities, both models rely on dynamically generated feasibility cuts to achieve connectivity, which is greater in number, particularly in the one-way case. This drastically slows down the LP relaxations at intermediate nodes of the branch-and-bound tree.

Properties of instances used for experiments with a two-hour limit: The properties of the instances for the extended analysis, where the model was run with a two-hour time limit, are summarized in Table 5. The instance column displays abbreviated IDs, with the hyphen representing the sequence 00000. For example, the actual identifier for the instance 125-068 in the dataset is 12500000068. The area is in sq ft, and the proportion of blocked cells is a

Table 5: Summary of instance properties for experiments with a two-hour limit

Instance ID	Area	µ	ν	B %	0 P	90 P	2W D	1W D
125-068	6431	11	7	5.19	62	66	56	73
125-140	7596	15	15	51.56	93	93	78	109
125-299	9396	12	15	30.56	111	110	97	125
125-425	10941	18	18	53.09	134	134	117	152
125-116	13073	9	20	18.89	135	126	116	146
125-026	14359	23	12	39.13	145	156	134	168
125-269	16099	12	16	3.65	173	169	158	185
125-158	17726	11	33	34.16	221	206	189	239
125-355	19953	22	23	50.99	224	220	197	248
125-372	20847	30	14	37.14	234	249	220	264
215-145	22387	18	33	53.37	259	243	226	277
125-094	25118	23	15	15.65	268	276	254	291
125-407	26268	17	24	25.49	283	280	260	304
125-112	28108	20	21	22.14	306	306	286	327

percentage of the overall number of cells in the lot. (The area measurements exclude the blocked cells.) The columns 2W|D| and 1W|D| refer to the number of valid driving cells in the two-way and one-way cases, respectively. Notice that compared to the two-way case, valid one-way driving cells are, on average, about 24% higher and do not exhibit a multiplicative effect.

References

Abdelfatah, A. S. and M. A. Taha (2014). Parking capacity optimization using linear programming. Journal of Traffic and Logistics Engineering 2 (3).
Arora, N., J. Cook, R. Kumar, I. Kuznetsov, Y. Li, H.-J. Liang, A. Miller, A. Tomkins, I. Tsogsuren, and Y. Wang (2019). Hard to park? Estimating parking difficulty at scale. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2296–2304.
Azadeh, K., R. De Koster, and D. Roy (2019). Robotized and automated warehouse systems: Review and recent developments. Transportation Science 53 (4), 917–945.
Azevedo, J., P. M. D'orey, and M. Ferreira (2020). High-density parking for automated vehicles: A complete evaluation of coordination mechanisms. IEEE Access 8, 43944–43955.
Brooke, S., S. Ison, and M. Quddus (2014). On-street parking search: review and future research direction. Transportation Research Record 2469 (1), 65–75.
Bukchin, Y. and T. Raviv (2022). A comprehensive toolbox for load retrieval in puzzle-based storage systems with simultaneous movements. Transportation Research Part B: Methodological 166, 348–373.
Cai, B. Y., R. Alvarez, M. Sit, F. Duarte, and C. Ratti (2019). Deep learning-based video system for accurate and real-time parking measurement. IEEE Internet of Things Journal 6 (5), 7693–7701.
Chen, G., J. Hou, J. Dong, Z. Li, S. Gu, B. Zhang, J. Yu, and A. Knoll (2020). Multiobjective scheduling strategy with genetic algorithm and time-enhanced A* planning for autonomous parking robotics in high-density unmanned parking lots. IEEE/ASME Transactions on Mechatronics 26 (3), 1547–1557.
Diaz Og´as, M. G., R. Fabregat, and S. Aciar (2020). Survey of smart parking systems. Applied Sciences 10 (11), 3872.
Flake, G. W. and E. B. Baum (2002). Rush Hour is PSPACE-complete, or "Why you should generously tip parking lot attendants". Theoretical Computer Science 270 (1-2), 895–911.
Forbes, M. and M. Harris (2022). A new formulation of a parking lot design problem. In Proceedings of the 11th TRIennial Symposium on Transportation ANalysis (TRISTAN).
Gue, K. R. and B. S. Kim (2007). Puzzle-based storage systems. Naval Research Logistics 54 (5), 556–567.
Hampshire, R. C. and D. Shoup (2018). What share of traffic is cruising for parking? Journal of Transport Economics and Policy 52 (3), 184–201.
Hughes, C. J. (2019). Private parking goes deluxe. www.nytimes.com/2019/09/13/realestate/ new-york-city-private-parking-goes-deluxe.html. Accessed: December 16, 2022.
Iranpour, R. and D. Tung (1989). Methodology for optimal design of a parking lot. Journal of Transportation Engineering 115 (2), 139–160.
Lee, J., D. Agdas, and D. Baker (2017). Cruising for parking: New empirical evidence and influential factors on cruising time. Journal of Transport and Land Use 10 (1), 931–943.
Lin, T., H. Rivano, and F. Le Mou¨el (2017). A survey of smart parking solutions. IEEE Transactions on Intelligent Transportation Systems 18 (12), 3229–3253.
Raviv, T., Y. Bukchin, and R. de Koster (2023). Optimal retrieval in puzzle-based storage systems using automated mobile robots. Transportation Science 57 (2), 424–443.
Rosenfeld, A. (2022). Optimal retrieval in puzzle-based storage with heuristic search and tabulation. Networks 79 (3), 390–402.
Sch¨orner, P., M. Conzelmann, T. Fleck, M. Zofka, and J. M. Z¨ollner (2021). Park my car! Automated valet parking with different vehicle automation levels by V2X connected smart infrastructure. In IEEE International Intelligent Transportation Systems Conference (ITSC), pp. 836–843.
Shoup, D. C. (2006). Cruising for parking. Transport policy 13 (6), 479–486.
Siddique, P. J., K. R. Gue, and J. S. Usher (2021). Puzzle-based parking. Transportation Research Part C: Emerging Technologies 127, 103112.
Stephan, K., F. Weidinger, and N. Boysen (2021). Layout design of parking lots with mathematical programming. Transportation Science 55 (4), 930–945.
Tang, S., T. Rambha, R. Hatridge, S. D. Boyles, and A. Unnikrishnan (2014). Modeling parking search on a network by using stochastic shortest paths with history dependence. Transportation Research Record 2467 (1), 73–79.
Toy, V. S. (2007). For parking space, the price is right at \$225,000. www.nytimes.com/2007/07/12/us/12parking. html. Accessed: September 8, 2022.
Wang, Y., M. Li, X. Lin, and F. He (2021). Online operations strategies for automated multistory parking facilities. Transportation Research Part E: Logistics and Transportation Review 145, 102135.
Wu, G., X. Xu, R. De Koster, B. Zou, et al. (2019). Optimal design and planning for compact automated parking systems. European Journal of Operational Research 273 (3), 948–967.
Yan, X., J. Levine, and R. Marans (2019). The effectiveness of parking policies to reduce parking demand pressure and car use. Transport Policy 73, 41–50.

thomasbranchcutalgorithmoptimal2025.md 101 KB История Исходник