Facility Location

with integer programming and Gurobi

In this example we'll solve a simple facility location problem: where to build warehouses to supply a large number of supermarkets.

We'll construct a mathematical model of the business problem, implement this model in Gurobi's Python interface, and compute and visualize an optimal solution.

Although your own business may not involve supermarkets, the same basic techniques used in this example can be used for many other applications in supply chain, logistics and transportation.

Click the screenshot to skip directly to the Live Demo!

Live Demo

Problem Description

A large supermarket chain in the UK needs to build warehouses for a set of supermarkets it is opening in Northern England. The locations of the supermarkets have been decided, but the locations of the warehouses are yet to be chosen.

Several good candidate locations for the warehouses have been determined, but it remains to decide how many warehouses to open and at which candidate locations to build them.

Opening many warehouses would be advantageous as this would reduce the average distance a truck has to drive from warehouse to supermarket, and hence reduce the delivery cost. However, opening a warehouse is costly.

We will use Gurobi to find the optimal tradeoff between delivery cost and the cost of building new facilities.

Mathematical Model

Our example is an instance of the Uncapacitated Facility Location Problem. There are many different types of facility location problems. For more details, see the book Facility Location: Applications and Theory.

Let us now formulate a mathematical model for our problem. Let $I$ be the set of supermarket (or customer) locations. Let $J$ be the set of candidate warehouse (or facility) locations. The goal is to choose which locations in $J$ should be used to construct a facility. Therefore, for each location we define a binary variable \[ x_j = \left\{\begin{array}{ll} 1 & \text{if we locate facility at candidate site $j \in J$, }\\ 0 & \mathrm{otherwise.} \end{array}\right. \]

There is a cost associated with constructing each warehouse. We denote this fixed charge by $f_j$.

We also define continuous variables $y_{ij}$ to be the fraction of supply received by customer $i$ from facility $j$. These quantities are positive, so we have the constraints: \[ y_{ij} \ge 0, \quad \forall i \in I, j \in J. \]

We denote by $c_{ij}$ the cost of shipping between candidate warehouse site $j$ and supermarket location $i$. This cost is usually proportional to the distance $d_{ij}$ between the facility and the customer: \[ c_{ij} = \alpha d_{ij} \] The constant $\alpha$ is the cost per mile of driving, adjusted to incorporate the average number of a trips a delivery truck would be expected to make over a 5 year period.

We wish to minimize the total cost to open and operate the facilites. This is the sum of the cost of opening facilities and the cost related to shipping between facilities and customers: \[ \text{total cost} = \sum_{j \in J} f_j x_j + \sum_{j \in J} \sum_{i \in I} c_{ij} y_{ij}. \] This total cost measures the tradeoff between the cost of building a new warehouse and the total delivery cost over a 5 year period.

Finally, we need to add two constraints. First, the demand for each customer must be fulfilled. That is, the sum of the fraction received from each facility for each customer must be equal to 1: \[ \sum_{j \in J} y_{ij} = 1, \quad \forall i \in I. \] Second, we can only ship from facility $j$ if that facility has actually been built. So we have the following constraints: \[ y_{ij} \leq x_{ij}, \quad \forall i \in I \quad \forall j \in J. \]

Thus, the uncapacitated facility location problem is defined by the following model in the variables $x_j$ and $y_{ij}$: \[ \begin{array}{ll} \text{minimize} & {\displaystyle \sum_{j \in J} f_j x_j + \sum_{j \in J} \sum_{i \in I} c_{ij} y_{ij}} \\ \text{subject to} & {\displaystyle \sum_{j \in J} y_{ij}} = 1, \quad \forall i \in I, \\ & y_{ij} \leq x_{ij}, \quad \forall i \in I, \forall j \in J, \\ & y_{ij} \geq 0, \quad \forall i \in I, \forall j \in J, \\ & x_j \in \{ 0, 1 \}, \quad \forall j \in J. \end{array} \]

Implementation

Below is the full implementation of the model (and the associated data) in Gurobi's Python interface:

from gurobipy import * import math def distance(a,b): dx = a[0] - b[0] dy = a[1] - b[1] return math.sqrt(dx*dx + dy*dy) # Problem data clients = [[0, 1.5],[2.5, 1.2]] facilities = [[0,0],[0,1],[0,1], [1,0],[1,1],[1,2], [2,0],[2,1],[2,2]] charge = [3,2,3,1,3,3,4,3,2] numFacilities = len(facilities) numClients = len(clients) m = Model() # Add variables x = {} y = {} d = {} # Distance matrix (not a variable) alpha = 1 for j in range(numFacilities): x[j] = m.addVar(vtype=GRB.BINARY, name="x%d" % j) for i in range(numClients): for j in range(numFacilities): y[(i,j)] = m.addVar(lb=0, vtype=GRB.CONTINUOUS, name="t%d,%d" % (i,j)) d[(i,j)] = distance(clients[i], facilities[j]) m.update() # Add constraints for i in range(numClients): for j in range(numFacilities): m.addConstr(y[(i,j)] <= x[j]) for i in range(numClients): m.addConstr(quicksum(y[(i,j)] for j in range(numFacilities)) == 1) m.setObjective( quicksum(charge[j]*x[j] + quicksum(alpha*d[(i,j)]*y[(i,j)] for i in range(numClients)) for j in range(numFacilities)) ) m.optimize()

Live Demo

Below is a visualization of our example. We are using the location data from GeoLytix for a large supermarket chain in the UK, and visualizing its outlets in Northern England.

The supermarkets are represented by:

By clicking the map you can add potential warehouse locations. These are represented by:

Click "Compute Warehouse Locations" to find the locations where warehouses will be built using Gurobi. These will be represented by:

A few potential warehouse locations have already been set up, but you can add more by clicking the screen.

The cost of transportation is 3 pounds/mile. You can use the slider to vary the cost of building a warehouse. When the cost is low, many facilities will be built. When the cost is high, it will dominate the transportation cost and there will be fewer facilities with greater driving distances.

Cost to build warehouse:

1.5 million pounds

Location data: Supermarket locations © GeoLytix copyright and database right 2014.

Try Gurobi for Free

We hope this example has taught you a bit about the facility location problem and using Gurobi. We encourage you to try the example out for yourself with Gurobi. To enable this, we provide easy access to a full-featured evaluation version of Gurobi.

We are always happy to discuss your needs and answer your questions. Just contact us at your convenience.