Facility Placement

How does a business decide where to build its next location? This decision involves several quantities to optimize: profit, consumer access, distance the consumer has to travel. This decision also depends on the possibly hierarchical structure of the business itself. Below I discuss considerations and approaches.

Hierarchical Systems

A hierarchical system is one “in which the entities while provide services or goods are classified according to the level of service offered by them”. The levels of service can be mutually exclusive, or the services offered by a facility at a lower level is a subset of the services offered at the next level.

There are several examples of this. In banking, at the lowest level are ATMs, then local bank branch offices, then large regional offices that offer a full range of services (a three-level hierarchy). In health care, there are local HMOs, then larger hospitals (a two-level hierarchy). In food/household product retail, there are small convenience stores (e.g. Walgreens), then larger grocery stores/supermarkets (e.g. Trader Joe’s, Shaw’s), then even larger “hypermarkets” (e.g. Super Wal-Mart).

So if a business is of a hierarchical nature, one thing to consider is which level of facility would be optimal.

Market Capture

All these business considerations can be encapsulated in the term market capture, which can be loosely defined as the percentage of total market sales volume that corresponds to a particular business.

The objective function is then some quantification of market capture, which can include hierarchical information, local demographic information, and measures of competitor presence.

It can also include the possibility of relocating an existing facility, e.g., maybe a potential site is optimal if an existing site is moved 5 miles away.

Formulating the Problem

We can model the existing structure of facilities as a network, and we want to optimize placement of a new node. As mentioned above, we could include the possibility of moving some fixed number of existing nodes.

One possible formulation of this “maximum-capture problem including relocation” (MAXRELOC) problem has been formulated by Serra et al. and I describe it below in the context of a duopoly example.

Say CVS is deciding where to put a new location (e.g., where to place a new node in the existing network), where they’re willing to move existing locations and they want to consider where there are already existing Walgreens locations. They want to maximize net population “captured” (defined below) from Walgreens, by maximizing the difference between population newly captured and population lost to Walgreens.

A node is fully captured by an existing CVS location if there is a CVS closer to this node than a Walgreens. A node is half captured if there are equidistant CVS and Walgreens locations.

The problem can then be cast as the following integer program.

maximize Z = \sum_{i \in I} a_i y_i + \sum_{i\in I} \frac{1}{2} a_i z_i

such that

  • y_i \leq \sum_{j \in N_i} x_j \quad \forall \, i \in I
  • z_i \leq \sum_{k \in O_i} x_k \quad \forall \, i \in I
  • z_i + y_i \leq 1 \quad \forall \, i \in I
  • \sum_{j \in J} x_j = r+p
  • \sum_{j \in J_A} x_j = p-s
  • y_i, z_i, x_j = 0,1 \quad \forall \, i \in I, j \in J


  • I is the set of all store locations (both Walgreens and CVS)
  • J is set of all possible new CVS locations, including existing locations
  • J_A is the set of existing CVS locations
  • S_i is the distance from node i to the closest Walgreens.
  • d_{ij} is the shortest distance (in time) between node i and site j
  • N_i = \{ j \in J \, | \, d_{ij} < S_i\} is the set of available facility sites that are strictly closer to node i than the closest Walgreens
  • O_i = \{ j \in J \, | \, d_{ij} = S_i\} is the set of available facility sites that are exactly distance S_i from node i
  • y_i \in \{0,1\} where it takes the value 1 if the solution node i is fully captured.
  • z_i \in \{0,1\} where it takes the value 1 if the solution node i is half captured.
  • x_i \in \{0,1\} where it takes the value 1 if a CVS location is at j
  • a_i is the population at node i
  • p is the number of existing CVS locations
  • r is the number of new CVS locations we’re looking to place
  • s is the number of CVS locations we’re willing to relocate

An additional layer of complexity is added if you then consider a hierarchical structure (e.g. do we place a small CVS, or a larger one with a pharmacy?).

A brief but interesting introduction can be found on Wikipedia.


Serra D, Marianov V, ReVelle C (1992). The maximum-capture hierarchical location problem. European Journal of Operational Research 62: 363–371.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s