# Optimal Seat Allocation Under Social Distancing Constraints

Michael Barry1, Claudio Gambella, Fabio Lorenzi,
John Sheehan and Joern Ploennigs
IBM Research Europe
1<EMAIL_ADDRESS>…

###### Abstract

The Covid-19 pandemic introduces new challenges and constraints for return to
work business planning. We describe a space allocation problem that
incorporates social distancing constraints while optimising the number of
available safe workspaces in a return to work scenario. We propose and
demonstrate a graph based approach that solves the optimisation problem via
modelling as a bipartite graph of disconnected components over a graph of
constraints. We compare results obtained with a constrained random walk and a
linear programming approach.

##  I Introduction

The Covid 19 pandemic has raised new challenges in workplace health and safety
and is driving new requirements, approaches and innovations in workplace
management [6] [5] [8]. Respecting social distance between employees in an
office environment is a necessary step in providing a safe, comfortable
working environment.

Recently there has, understandably, been a lot of interest in solutions that
incorporate distance constraints into real-world seat allocation problems.
[11] and [1] describe seat allocation solutions for theatres and other
entertainment venues that explores the capacity of a venue under different
social distancing conditions. An interactive seat selection tool is described
in [2] that requires the user to manually select individual spaces. A solution
for social distancing for public facilities, inspired by previous work on the
optimal positions of turbines in offshore wind farms is presented in [7].

The office environment, presents its own unique challenges to seat allocation
and social distance constraints. While an office layout may be more structured
than that of a theatre, cinema or other venue, it also comes with a larger
variety of space sizes and shapes, as well as other business related
operational constraints, including prioritising teams and business units for
workspace allocation and the desire to co-locate existing teams so that
returning members are not spread across multiple floors or areas. Each
organisation brings its own unique use cases, quality metrics, and constraints
that must be taken into account in any workspace allocation exercise.

Notwithstanding the workspace allocation problem itself, applying a social
distance constraint to every floor in every building of a large organisation
is an immense undertaking. Existing building and office layouts must be
reviewed and assessed such that only those workspaces that are socially
distant from each other can be used. Reviewing, measuring and marking out
workspaces is a time consuming task for an space planner or office manager,
particularly for large organizations with office workspaces in the thousands.
Furthermore, these staff are not data scientists or optimization specialists
that are trained to analyse the data and develop an optimal plan.

We present an automated approach to optimising workspace allocation in office
environments based on pre-existing floorplan images. We describe different
approaches for identifying workspaces in a floorplan image. Next we propose a
graph based approach to optimising workspace allocation using the identified
workspaces. Finally we present a Linear Program based approach that
incorporates social distance constraints into a general model for workspace
allocation in an office environment

##  II Identifying Workspaces

Before we can formulate the optimization problem we need to identify
workspaces in the floor. Identifying workspaces, or indeed any shape in a
floorplan image is a challenging task due to the many formats a floorplan may
be represented by. Workspaces may be simple squares for a desk on a floorplan,
or a complex 3D model in a CAD file. We use a variety of computer vision
techniques and, where available, metadata to identify workspaces in
floorplans.

When a floorplan image is a vector file such as a SVG [10], we parse the image
to extract Polylines and Paths that describe likely workspaces. We prune this
set of likely workspaces based on the size of Before we can formulate the
optimization problem we need to identify workspaces in the floor of the
discovered workspaces. This technique works well for office spaces that
already make use of regularly shaped and oriented cubicles, where workspaces
can be represented as simple polygons. Moreover, it can be adapted to discover
more complex objects, such as individual workspaces or desks using a bounding-
box that encompasses the element.

Where the floorplan is a raster image, for example a JPEG or PNG file, we us
image convolution to detect workspaces in the floorplan [3]. By applying a
template of a workspace we identify and extract workspaces and their locations
in the target image. Figure 1 below shows the output of a template search on a
target floorplan. The workplace templates (a) and (b) are applied to the image
and spaces of each type are identified, regardless of orientation or size.

Figure 1: Using templates to find workspaces in a Floorplan image

Metadata from a system of record can also be used to identify workspaces. As
well as providing floorplans, commercial space management systems may provide
a list of spaces per floor including workspace tags that allows us to clearly
identify target workspaces.

##  III Allocating Workspaces

Once we have identified a set of workspaces and their location we can develop
a seating plan that identifies that maximum set of spaces that can be
allocated while maintaining social distancing. The inputs to the space
allocation include the desired social distance, and the centroids; the centers
of the bounding boxes of the workspaces. The centroids image coordinates are
rescaled to human readable (metric or imperial) coordinates using a linear
rescaling along the x,y axis.

We developed different approaches to solve the seat assignment problem. The
first solution uses a random walk to divide the workspaces into sets of
allocated and unallocated workspaces. Next we describe a graphical approach to
map the problem to a set of disjoint bipartite graph mapping problems.
Finally, we present a Linear Program Formulation that includes a social
distancing constraint.

###  III-A Random Walk Heuristic

The random walk approach selects a workspace at random from the full floorplan
and evaluates the distance between the workspace centroid and the centroids of
all allocated workspaces. If the workspace is sufficiently distant from all
allocated workspaces it is added to the set of allocated workspaces; otherwise
it is unallocated. Once all workspaces have been added to the allocated or
unallocated sets, the set of allocated workspaces is returned.

This is a naive approach and does not result in an optimal allocation of
workspaces. The accuracy of the solution can be improved by running the
heuristic multiple times and selecting the individual solution with the
maximum allocation of workspaces.

###  III-B Graph Analysis

In graph analysis, a selection problem is a problem that involves splitting a
set of resources $R$ into two disjoint sets $S$ of selected resources and $N$
of non-selected resources such that $S\cap N=\emptyset$ and $R=S\cup N$
according to some selection criterion (or function) while maximizing the
cardinality of the selected nodes’ set $|S|$. In cases where the selection
function is dependent only on the elements of $R$ themselves $f\colon
R\to\\{0,1\\}$ the problem can be treated as a graph problem.

(a) $K_{50}$

(b) Graph of contstraints

(c) Seat selection

Figure 2: Visualisation of the three stages of the seat selection algorithm

####  III-B1 Graph of Constraint

We construct a weighted graph where each node is a workspace from the
floorplan and the edges between nodes are weighted using the distances between
workspace centroids. This results in a densely connected graph as shown in
2(a) where each node is connected to every other node in the graph. This
large, fully connected graph is unwieldy, and includes many edges whose weight
likely outside the social distance that we wish to apply. To reduce the size
and complexity of the graph we define a “graph of constraint“ as shown in 2(b)
that only includes those nodes connected by edges with weights that are within
social distance.

In the workspace allocation scenario under social-distancing constraints $R$
is the set of available workspaces. Let $d$ be the minimum required social
distance. Let $K_{\mid R\mid}=\\{R,E,w\\}$ be a complete undirected weighted
graph. $E=(R\times R)$ be the set of edges of the graph. $w\colon
E\to\mathbb{R}$ be a weight function that assigns each edge a weight based on
the distance between the spaces on the floorplan. Let
$C_{d}=\\{R^{\prime},E^{\prime},w\\}$ be a subgraph of $K_{\mid R\mid}$ where
$R^{\prime}\subset R$ and $E^{\prime}=\\{e_{i}\mid e_{i}\in E,w(e_{i})<k\\}$.
$C_{d}$ is a potentially disconnected graph named the “graph of constraint“.

####  III-B2 Allocating workspaces using a Bipartite Graph

A bipartite graph is one whose nodes can be divided into two disjoint,
independent sets such that a node in one set can only connect to nodes in the
other set, and not to nodes in its own set[9]. If the “graph of constraints“
is a bipartite graph, or can be made bipartite, then the two sets of nodes
represent independent sets of allocatable workspaces. As the nodes in each set
are not connected to each other, they are outside social distance of each
other. We then choose the larger set as the allocated workspaces for the
floor, and all other workspaces are unallocated.

Let $B_{d}\subset C_{d}$ be a bipartite subgraph of $C_{d}$. We denote the set
of nodes of a graph $G$ with $N(G)$ and the set of edges with $E(G)$. Given a
set of workspaces $R$ and a minimum social distance parameter $d$ we can
obtain an acceptable selection of workspaces by partitioning the graph and
selecting the partition with the most nodes as described in Algorithm 1. A
visualization of the algorithm is shown in Figure 2.

Algorithm 1 Workspace selection algorithm

1:procedure SpaceSelection($C_{d}$) $\triangleright$ The graph of constraints
$C_{d}$

2: $S\leftarrow\emptyset$

3: for all $C^{\prime}\in C_{d}$ do $\triangleright$ We check each connected
component of $C_{d}$

4: $B_{d}\leftarrow partition(C^{\prime})$

5: $U,V\leftarrow bicolor(B_{d})$

6: $S^{\prime}\leftarrow\operatorname*{argmax}_{X\in\\{U,V\\}}(\mid X\mid)$
$\triangleright$ We select the partition with maximum cardinality

7: $S\leftarrow S\cup S^{\prime}$

8: end for

9: return $S$$\triangleright$ A selection of workspaces satisfying the spatial
constraints on $d$

10:end procedure

If the graph is not a bipartite graph, we delete nodes from the graph until
the remaining graph is bipartite. After a node is deleted from the graph it is
no longer available to become allocated in any remaining bipartite graph, and
so that workspace must become unavailable on the floorplan. When deleting
nodes from the graph, we must ensure that a maximum number of nodes remains in
the bipartite graph, so that a maximum number of workspaces are available for
allocation.

Figure 3 depicts how nodes are selected for deletion. Examining 3(f), the
depicted graph is not bipartite as it contains odd cycles: 68-30-62-68 and
55-62-30-55. Nodes 62 and 30 are present in both odd-cycles and so are
candidates for elimination. Each candidate has three outgoing connections, so
one is chosen at random for deletion. Consider that for node 30 to be in the
set of allocated workspaces, nodes 68, 62 and 55 cannot be allocated; they are
connected to node 30 and so are within social distance of node 30 and must
remain unallocated. This would reduce the number of nodes in the graph to
three: nodes 30, 38 and 47. Deleting node 30 results in a larger graph with
five nodes. Node 30 is deleted and the resulting graph is shown in 3(g). This
graph is bipartite and can be partitioned as shown in 3(h).

The heuristic to transform an odd cycle graph to a bipartite graph through
through node elimination is described in Algorithm 2 and Algorithm 3. As a
graph with odd-cycles cannot be bipartite, the heuristic first examines the
cycle basis of the graph to identify nodes that participate in the most number
of odd-cycles in the graph. Then the node with the most outgoing connections
is selected for elimination. Nodes are eliminated until the graph contains no
odd-cycles and is bipartite.

(a) $C^{\prime}$

(b) $c=4$

(c) $c=93$

(d) $c=72$

(e) $c=19$

(f) $c=69$

(g) $c=30$

(h) bipartition

Figure 3: A visualisation of the heuristic candidate selection algorithm. The
sequence of images from (3(a)) to (3(h)) represents the stages of the
selection and elimination of the nodes Algorithm 2 Partitioning algorithm

1:procedure Partition($C^{\prime}$) $\triangleright$ A component of the graph
of constraints $C_{d}$

2: $X\leftarrow cycle\\_basis(C^{\prime})$

3: $X^{\prime}\leftarrow\\{x\mid x\in X,\mid N(x)\mid\bmod 2\neq 0\\}$

4: while $X^{\prime}\neq\emptyset$ do

5: $c\leftarrow candidateH(X^{\prime})$$\triangleright$ Apply the heuristic-
based candidate selection and select a candidate node for elimination

6: $N(C^{\prime})\leftarrow N(C^{\prime})\setminus\\{c\\}$

7: $E(C^{\prime})\leftarrow E(C^{\prime})\setminus\\{e\mid e\in
E(C^{\prime}),c\notin e\\}$

8: $X^{\prime}\leftarrow\\{x\mid c\notin N(x),x\in X^{\prime}\\}$

9: end while

10: return $C^{\prime}$ $\triangleright$ Return $C^{\prime}$ without odd
cycles

11:end procedure

Algorithm 3 Heuristic candidate selection algorithm

1:procedure CandidateH($X^{\prime}$) $\triangleright$ A cycle basis for
$C^{\prime}$

2: $C\leftarrow\operatorname*{argmax}_{x\in\bigcup_{y\in
X^{\prime}}N(y)}\sum_{X_{i}\in X^{\prime}}[x\in X_{i}]$ $\triangleright$
Select the candidate with the highest participation in the cycle basis

3: $C\leftarrow\operatorname*{argmax}_{x\in C}(deg(x))$ $\triangleright$
Select the candidate with the highest out degree

4: return $random(C)$ $\triangleright$ Return one element from the set C

5:end procedure

###  III-C Seat Allocation using Integer Linear Programming

The heuristic graph partitioning approach presented before is very efficient
in solving simple assignment problems, but is limited in encoding more complex
constraints.Each return to the office scenario is unique and must take into
account business requirements as well as social distancing. This may, for
example, necessitate prioritising some business units or teams over others, or
ensuring that teams that do return to the office are seated together and not
scattered across multiple floors or buildings. In this section we integrate
social distancing into a simplified allocation model for an office environment
formulated as an Integer Linear Programming model. The aim of the model is to
maximize the number of workspaces allocated across a set of business units,
while respecting constraints of a feasible allocation plan. For the sake of
simplicity, we focus on the workspaces allocation of a single floor.

First, we describe a mathematical formulation that provides a set of basic
requirements for workspace allocation. We denote with $e_{j}$ the number of
employees of business unit $j$, $c_{ij}$. We introduce binary variables
$x_{ij}$, to indicate whether the workspace $i$ is allocated to business unit
$j$. Determining the optimal seat allocation means solving the following
Integer Linear Programming formulation:

$\displaystyle\max_{x}\sum_{ij}x_{ij}$ (1a) $\displaystyle\sum_{j}x_{ij}\leq
1$ $\displaystyle\forall\ i$ (1b) $\displaystyle\sum_{i}x_{ij}\leq e_{j}$
$\displaystyle\forall\ j$ (1c)

The objective (1a) is to maximimse the number of allocated workspaces. Note
that a workspace is not allocated to more than 1 business unit, because of
constraints (1b). Constraints (1c) allocates no more workspaces to a business
unit than the number of its employees. Being a generalized assignment problem,
Model (1a)-(1c) can be efficiently solved with commercial optimization
solvers. We have adopted CPLEX [4] for this purpose.

We accommodate social distance in the model by introducing a constraint based
on the distance between workspaces, which we can learn by analysing a
floorplan as described above. Assuming the distance $d_{ik}$ between each pair
$(i,k)$ of workspaces is known, we denote with $I=\\{(i,k):d_{ik}<D,i<k\\}$ a
set of workspace pairs which cannot both be occupied simultaneously. Since the
distance requirement between workspaces does not pertain to which business
unit they belong to, we introduce auxiliary binary variables $y_{i},\forall$
workspace $i$ to indicate whether a workspace is assigned to any business
unit. Therefore, social distancing is introduced by adding

$\displaystyle y_{i}=\sum_{j}x_{ij}$ $\displaystyle\forall\ i$ (2)
$\displaystyle y_{i}+y_{k}\leq 1$ $\displaystyle\forall\ (i,k)\in I$ (3)

to Model (1a)-(1c). While constraints (2) define whether each workspace is
allocated, constraints (3) enforce the social distance between allocated
workspace. Note that variables $y_{i}$ are bounded by $1$, because of
constraints (1b).

####  III-C1 ”Preserving an existing allocation plan”

It is likely that in an office environment we are working with an existing
allocation plan. In general, we wish to minimize variations from that plan so
that where possible business units maintain existing allocations, albeit with
less overall workspaces. We discourage changes in the allocation plan
$\tilde{x}$ in the objective function (1a) via penalization terms. Considering
variables $x_{ij}$ are binary, it is possible to penalize the variations from
allocation plan $\tilde{x}$ simply adding the following linear terms to the
objective (1a):

$\displaystyle C\cdot x_{ij}\quad\forall
i\in\tilde{I},j\in\tilde{J}\quad\text{if}\;\tilde{x}_{ij}=1$ (4)
$\displaystyle-C\cdot x_{ij}\quad\forall
i\in\tilde{I},j\in\tilde{J}\quad\text{if}\;\tilde{x}_{ij}=0,$ (5)

where $C>0$ is an appropriately large constant that acts a penalization factor
for the variations from $\tilde{x}$. The larger $C$ is, the more likely CPLEX
is to discourage variations from the given allocation plan $\tilde{x}$.

The result of a seat allocation using an existing floorplan are shown in
Figure 4. Different colors in the floorplan represent workspaces allocated to
different business units in an initial allocation plan. After a social
distance is applied,with few exceptions, existing workspace allocations are
reused by the same business units.

(a) $ExistingFloorplan$

(b) $SocialDistanceFloorplan$

Figure 4: Space Allocation with Social Distance

##  IV Results

The result of a workspace allocation by creating a bipartite graph from a
floorplan is illustrated in Figure 5.The input floorplan is an SVG file with
300 workspaces; discovered from parsing the file as described in section II.
Allocated workspaces are blue, unallocated workspaces are pink. The social
distance factor is 72 inches. Workspace dimensions are 60 inches x 60 inches.
At a social distance of 72 inches horizontally adjacent and vertically
adjacent workspaces are not both allocated as the distance between those
workspace centroids is less than the social distance of 72 inches.

For the same floorplan, he Linear Program and bipartitie graph approaches both
identify a maximum of 162 workspaces out of a total of 300 that can be
allocated at this social distance. The Random walk approach identifies a
maximum allocation of 159 workspaces

Table I compares the maximum number of allocated desks for the floorplan for a
range of social distances and allocation methods. The random walk approach
yields the fewest number of allocatable desks. The graph partition and Linear
Program produce similar results for distances of 72 inches and 84 inches. At
higher distances the Linear Program outperforms the graph partition approach
in identifying a maximum number of workspaces that can be allocated

Figure 5: Allocating workspaces via graph partition. Allocated workspaces are blue, unallocated are pink | Allocation Approach
---|---
Social Distance (inches) | Random Walk | Partition | ILP
72 | 149 | 162 | 162
84 | 146 | 162 | 162
96 | 114 | 123 | 123
108 | 99 | 100 | 107
TABLE I:  Allocated Workspaces at a range of social distances for a single
workspace

Table II compares the maximum number of allocated workspaces for a range of
floorplans. Each workspace has a different number of workspaces ranging from
173, to 653. The size of the workspaces varies from floor to floor, as does
the arrangement of workspaces on each floor. The 1st column contains the
number of workspaces on each floor. Subsequent columns contain the maximum
number of seats that can be allocated using different approaches at a given
social distance.

As expected, the random walk approach produces the worst results and
identifies the least number of seats that can be allocated. The graph
partition and Linear Program produce similar results for distances of 72
inches and 84 inches.

At higher distances the results from graph partition approach does not perform
as well as the Linear Program. A higher social distance implies that the
workspace allocation is more constrained and that there will be more connected
nodes in the floorplan “graph of constraints“. This requires that more nodes
be deleted before the graph becomes bipartite. If the heuristic is too
aggressive in deleting nodes then an optimal allocation of nodes will not be
acheived.

|  | Random Walk |  | Bi-Partition |  | CPLEX
---|---|---|---|---|---|---
Workspaces |  | 72 | 84 | 96 |  | 72 | 84 | 96 |  | 72 | 84 | 96
173 |  | 81 | 80 | 51 |  | 85 | 85 | 51 |  | 85 | 85 | 51
267 |  | 120 | 124 | 82 |  | 130 | 129 | 82 |  | 130 | 129 | 86
300 |  | 149 | 146 | 99 |  | 162 | 162 | 104 |  | 162 | 162 | 109
309 |  | 158 | 157 | 114 |  | 167 | 167 | 123 |  | 167 | 167 | 123
510 |  | 238 | 238 | 134 |  | 255 | 255 | 134 |  | 255 | 255 | 134
564 |  | 237 | 163 | 159 |  | 288 | 166 | 164 |  | 288 | 166 | 165
653 |  | 304 | 185 | 146 |  | 334 | 199 | 161 |  | 334 | 205 | 185
TABLE II:  Allocatable Workspaces at a range of social distances for different
workspaces

##  V Conclusion

Enforcing social distances in office environments is a necessary step in
facilitating return to work planning. Automation of floorplan analysis and
workspace allocation can greatly improve the speed and efficiency of selecting
workspaces that meet social distance constraints. This paper describes an
approach that combines image processing techniques with optimization
approachess to solve this problem. This paper demonstrates the use of standard
image processing techniques to extract workspace data from floorplan images.
From the workspace data, we build a connected graph of workspaces, and reduce
that graph to a bipartitionable graph of workspaces by applying social
distance constraints. We further illustrate how social distance constraints
can be incorporated more complex decision support systems through a linear
programming formulation for workspace allocation that incorporates enterprise
constraints as well as social distance constraints.

## References

  * [1] “Add Social Distancing to your venue”, 2020  URL: https://softjourn.com/expertise/social-distancing-checkerboard-seating-algorithm
  * [2] Danielle Aihini  “How to plan your office seating chart using physical distancing”, 2020  URL: https://robinpowered.com/blog/robin-physical-distancing-tool
  * [3] G. Bradski  “The OpenCV Library”  In _Dr. Dobb’s Journal of Software Tools_ , 2000, pp. 14–77 –14–78
  * [4] IBM ILOG Cplex  “V12. 9: User’s Manual for CPLEX”  In _International Business Machines Corporation_ , 2017
  * [5] European Agency for Health and Safety at work  “COVID-19: Resources for the Workplace”  URL: https://osha.europa.eu/en/themes/covid-19-resources-workplace
  * [6] European Center for Disease Prevention and Control  “Considerations relating to social distancing measures in response to COVID-19 – second update”, 2020  URL: https://www.ecdc.europa.eu/en/publications-data
  * [7] Martina Fischetti, Matteo Fischetti and Jakob Stoustrup  “Mathematical optimization for social distancing”, 2020  URL: https://www.researchgate.net/publication/341708793_Mathematical_optimization_for_social_distancing
  * [8] “IBM Return to Workplace Advisor”  URL: https://www.ibm.com/products/return-to-workplace-advisor
  * [9] Salvatore, J  “Bipartite graphs and problem solving”, 2007  URL: https://www.math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/FINALAPP/Salvatore.pdf
  * [10] “Scalable Vector Graphics (SVG) 2”, 2018  URL: https://www.w3.org/TR/SVG2
  * [11] Activity Stream  “Social Distancing and Seating letting an algorithm take control”, 2020  URL: https://www.activitystream.com/social-distancing-and-seating-letting-an-algorithm-take-control