A New Formulation of a Parking Lot Design Problem∗

A. Michael Forbes, B. Mitchell Harris

School of Mathematics and Physics, The University of Queensland, Brisbane, Australia
m.forbes@uq.edu.au, m.g.harris@uq.edu.au

Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island
April 4, 2022

Keywords: parking, composite variables, logic based Benders decomposition

1INTRODUCTION

A recent paper in Transportation Science, Stephan et al. (2021), considered the optimizationof parking lots with the help of mathematical programming where, for a xed lot, the goal isto maximize the number of reachable perpendicular parking spaces. They propose several novelow based models. We describe a new formulation based on composite variables and logic based
Benders decomposition.

2FORMULATIONLet S denote the set of 1 × 1 squares identied by their (i, j) coordinates. Parking spaces havesize 1 × 2 or 2 × 1 and driving squares must be at least 2 × 2 squares wide to allow bidirectionaltrac ow (we could use another resolution ). We can generate the sets P of all legal parking
tiles and D of all legal driving tiles a priori. Initialize P = D = ∅ and for all (i, j) ∈ S , Add p = {(i, j), (i + 1, j)} to P if p ⊂ S , Add p = {(i, j), (i, j + 1)} to P if p ⊂ S , and Add d = {(i, j), (i, j + 1), (i + 1, j), (i + 1, j + 1)} to D if d ⊂ S .
We have a set F ⊂ D which is the set of driving tiles which must be active; in particular e ∈ Dis the entrance tile.

Driving lanes will be wide enough automatically since we only generate

valid driving tiles. We need to nd a valid packing of tiles into S which maximizes the numberof parking tiles reachable from the entrance, where driving tiles may overlap. To that end weintroduce the following binary variables: xp = 1 if tile p ∈ P is active, xp = 0 otherwise; yd = 1 if tile d ∈ D is active, yd = 0 otherwise; and zs = 1 if square s ∈ S is a driving square, zs = 0 otherwise.
The number of variables is bounded above by 4|S|.

It will be useful to dene the following

neighbourhoods:

 ND (d ) ⊂ D is the set of driving tiles adjacent to d ∈ D including up to four properly
adjacent tiles, and up to four overlapping tiles:

TRISTAN XI Symposium

Original abstract submittal

A. Michael Forbes, B. Mitchell Harris

2∪= ND (d).

 NP ( p) ⊂ D is the set of up to 4 driving tiles adjacent to p ∈ P :∨= NP (p).

The following integer program gives a valid packing of tiles:

Xmaxxp(1)p∈Psubject toX

xp ⩽∀p ∈ P,(2)xp ⩽ 1 ∀s ∈ S,(3)ydd∈ND (p)Xzs +p∈P :s∈p

yd ⩽ zs∀d ∈ D, s ∈ d,(4)yd = 1∀d ∈ F.

(5)

The objective function, (1), is the number of active parking tiles; (2) ensures that every parking
tile is adjacent to a driving tile; (3) ensures that parking tiles do not overlap driving squares;(4) forces driving squares; and (5) xes the set tiles. It is not hard to see that (1 - 5) does notguarantee each parking tile will be reachable from the entrance. We remedy this by adding logic
based Benders cuts at incumbent nodes of the branch-and-bound tree. While there are several
promising cutting schemes, here we summarize one.

′′′Let (x , y , z ) be a feasible incumbent solution to (1 - 5). With special purpose code, we cannd the set of all contiguous regions of active driving tiles; that is, a partition of the active
driving tiles such that every tile in the region is reachable from every other tile in the region.

′′′If (x , y , z ) is optimal and there is only one region, then we are done, since that region must
contain the entrance.
If, on the other hand, there is more than one contiguous region, let R ⊂ D \ {e} be a region
not containing the entrance. LetND (R) = d ∈ D : yd′ = 0, d ∈ Nd (d′ ) for some d′ ∈ R, d ̸⊆ ∪d′ ∈R d′denote the set of strict inactive neighbours of R. Then ND (R) is a cut set in D separating Rfrom e. We can add the following Benders feasibility cuts as a lazy constraints:

yd ⩽Xyd′for alld ∈ R.

(6)d′ ∈ND (R)The principle diculties with this formulation are the large number of legal packings, and theweak LP relaxation of (1 - 5); the main culprit being (3), since all ve tiles may be partially
active on each square. Advantages, however, include the exibility of the composite variables,
and the fact that no big M constraints are required.

TRISTAN XI Symposium

Original abstract submittal

A. Michael Forbes, B. Mitchell Harris

33IMPROVEMENTS

We propose a heuristic which constraints ow between adjacent driving tiles.

′network (D, A) with A = {(d, d ) : d ∈ D, d′ ∈ NConsider theD (d)}. For each d ∈ D \ e we calculate theshortest distance from d to e in the graph with respect to two sets of arc lengths:

 First with respect to unit lengths, and Second, where the length of an arc (d, d′ ) is penalized by the number of parking tiles′adjacent to d. A promising penalty function is given by 1/|ND (d )|.
′′Then we delete each arc (d, d ) from A unless d is at least as close to e as d is with respect to atleast one of the two metrics. For each d ∈ D \ {e} we add the following constraint to (1-5):

yd ⩽Xyd′ .

(7)d′ ∈ ND (d):(d, d′ ) ∈ A
The idea is to force the driving tiles to ow generally closer to the entrance. Unit lengths alone do
not behave well with obstacles or corners, but the penalized metric allows us to deviate to makeroom for parking tiles. There is scope to explore more sophisticated heuristics of this nature.
This heuristic achieves the optimal objective value for the instance depicted in Figure 1 ofStephan et al. (2021) in under a minute.

See the gure below.

More detailed computational

experiments are in progress, and will be described in the conference presentation.

References
Stephan, Konrad, Weidinger, Felix, & Boysen, Nils. 2021. Layout Design of Parking Lots with Mathematical Programming. Transportation Science, 55(06).

TRISTAN XI Symposium

Original abstract submittal