Facility location problems can be commonly found in many industries, including logistics and telecommunications. In this example, we’ll show you how to tackle a facility location problem that involves determining the number and location of warehouses that are needed to supply a group of supermarkets. We’ll demonstrate how to construct a mixed-integer programming (MIP) model of this problem, implement this model in the Gurobi Python API, and then use the Gurobi Optimizer to find an optimal solution.
This modeling example is at the beginner level, where we assume that you know Python and that you have some knowledge about building mathematical optimization models.
Download the Repository
You can download the repository containing this and other examples by clicking here.
The study of facility location problems - also known as "location analysis" [1] - is a branch of operations research and computational geometry concerned with the optimal placement of facilities to minimize transportation costs while considering factors like safety (e.g. by avoiding placing hazardous materials near housing) and the location of competitors' facilities.
The Fermat-Weber problem, formulated in the 17'th century, was one of the first facility location problems ever devised. The Fermat-Weber problem can be described as follows: Given three points in a plane, find a fourth point such that the sum of its distances to the three given points is minimal. This problem can be viewed as a variation of the facility location problem, where the assumption is made that the transportation costs per distance are the same for all destinations.
Facility location problems have applications in a wide variety of industries. For supply chain management and logistics, this problem can be used to find the optimal location for stores, factories, warehouses, etc. Other applications range from public policy (e.g. positioning police officers in a city), telecommunications (e.g. cell towers in a network), and even particle physics (e.g. separation distance between repulsive charges). Another application of the facility location problem is to determine the locations for natural gas transmission equipment. Finally, facility location problems can be applied to cluster analysis.
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 identified, but the locations of the warehouses have yet to be determined.
Several good candidate locations for the warehouses have been identified, but decisions must be made regarding 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 the warehouse to the supermarket, and hence reduce the delivery cost. However, opening a warehouse has a fixed cost associated with it.
In this example, our goal is to find the optimal tradeoff between delivery costs and the costs of building new facilities.
Mathematical programming is a declarative approach where the modeler formulates a mathematical optimization model that captures the key aspects of a complex business problem. The Gurobi Optimizer solves such models using state-of-the-art mathematics and computer science.
A mathematical optimization model has five components, namely:
We now present a MIP formulation for the facility location problem.
$i \in I$: Index and set of supermarket (or customer) locations.
$j \in J$: Index and set of candidate warehouse (or facility) locations.
$f_{j} \in \mathbb{R}^+$: Fixed cost associated with constructing facility $j \in J$.
$d_{i,j} \in \mathbb{R}^+$: Distance between facility $j \in J$ and customer $i \in I$.
$c_{i,j} \in \mathbb{R}^+$: Cost of shipping between candidate facility site $j \in J$ and customer location $i \in I$. We assume that this cost is proportional to the distance between the facility and the customer. That is, $c_{i,j} = \alpha \cdot d_{i,j}$, where $\alpha$ is the cost per mile of driving, adjusted to incorporate the average number of trips a delivery truck would be expected to make over a five year period.
$select_{j} \in \{0, 1 \}$: This variable is equal to 1 if we build a facility at candidate location $j \in J$; and 0 otherwise.
$0 \leq assign_{i,j} \leq 1$: This non-negative continuous variable determines the fraction of supply received by customer $i \in I$ from facility $j \in J$.
This example considers two supermarkets and nine warehouse candidates. The coordinates of each supermarket are provided in the following table.
| Coordinates | |
|---|---|
| Supermarket 1 | (0,1.5) |
| Supermarket 2 | (2.5,1.2) |
The following table shows the coordinates of the candidate warehouse sites and the fixed cost of building the warehouse in millions of GBP.
| coordinates | fixed cost | |
|---|---|---|
| Warehouse 1 | (0,0) | 3 |
| Warehouse 2 | (0,1) | 2 |
| Warehouse 3 | (0,2) | 3 |
| Warehouse 4 | (1,0) | 1 |
| Warehouse 5 | (1,1) | 3 |
| Warehouse 6 | (1,2) | 3 |
| Warehouse 7 | (2,0) | 4 |
| Warehouse 8 | (2,1) | 3 |
| Warehouse 9 | (2,2) | 2 |
The cost per mile is one million GBP.
We now import the Gurobi Python Module and other Python libraries. Then, we initialize the data structures with the given data.
# %pip install gurobipy
from itertools import product
from math import sqrt
import gurobipy as gp
from gurobipy import GRB
# tested with Gurobi v9.1.0 and Python 3.7.0
# Parameters
customers = [(0,1.5), (2.5,1.2)]
facilities = [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)]
setup_cost = [3,2,3,1,3,3,4,3,2]
cost_per_mile = 1
We define a function that determines the Euclidean distance between each facility and customer sites. In addition, we compute key parameters required by the MIP model formulation of the facility location problem.
# This function determines the Euclidean distance between a facility and customer sites.
def compute_distance(loc1, loc2):
dx = loc1[0] - loc2[0]
dy = loc1[1] - loc2[1]
return sqrt(dx*dx + dy*dy)
# Compute key parameters of MIP model formulation
num_facilities = len(facilities)
num_customers = len(customers)
cartesian_prod = list(product(range(num_customers), range(num_facilities)))
# Compute shipping costs
shipping_cost = {(c,f): cost_per_mile*compute_distance(customers[c], facilities[f]) for c, f in cartesian_prod}
We now determine the MIP model for the facility location problem, by defining the decision variables, constraints, and objective function. Next, we start the optimization process and Gurobi finds the plan to build facilities that minimizes total costs.
# MIP model formulation
m = gp.Model('facility_location')
select = m.addVars(num_facilities, vtype=GRB.BINARY, name='Select')
assign = m.addVars(cartesian_prod, ub=1, vtype=GRB.CONTINUOUS, name='Assign')
m.addConstrs((assign[(c,f)] <= select[f] for c,f in cartesian_prod), name='Setup2ship')
m.addConstrs((gp.quicksum(assign[(c,f)] for f in range(num_facilities)) == 1 for c in range(num_customers)), name='Demand')
m.setObjective(select.prod(setup_cost)+assign.prod(shipping_cost), GRB.MINIMIZE)
m.optimize()
Restricted license - for non-production use only - expires 2023-10-25
Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (mac64[rosetta2])
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 20 rows, 27 columns and 54 nonzeros
Model fingerprint: 0x0939f503
Variable types: 18 continuous, 9 integer (9 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [5e-01, 4e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Presolve time: 0.00s
Presolved: 20 rows, 27 columns, 54 nonzeros
Variable types: 18 continuous, 9 integer (9 binary)
Found heuristic solution: objective 6.0385165
Root relaxation: objective 4.723713e+00, 15 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
* 0 0 0 4.7237129 4.72371 0.00% - 0s
Explored 1 nodes (15 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)
Solution count 2: 4.72371 6.03852
Optimal solution found (tolerance 1.00e-04)
Best objective 4.723712908962e+00, best bound 4.723712908962e+00, gap 0.0000%
# display optimal values of decision variables
for facility in select.keys():
if (abs(select[facility].x) > 1e-6):
print(f"\n Build a warehouse at location {facility + 1}.")
Build a warehouse at location 4.
This plan determines the percentage of shipments to be sent from each facility built to each customer.
# Shipments from facilities to customers.
for customer, facility in assign.keys():
if (abs(assign[customer, facility].x) > 1e-6):
print(f"\n Supermarket {customer + 1} receives {round(100*assign[customer, facility].x, 2)} % of its demand from Warehouse {facility + 1} .")
Supermarket 1 receives 100.0 % of its demand from Warehouse 4 . Supermarket 2 receives 100.0 % of its demand from Warehouse 4 .
In this example, we addressed a facility location problem where we want to build warehouses to supply a large number of supermarkets while minimizing the fixed total costs of building warehouses and the total variable shipping costs from warehouses to supermarkets. We learned how to formulate the problem as a MIP model. Also, we learned how to implement the MIP model formulation and solve it using the Gurobi Python API.
[1] Laporte, Gilbert, Stefan Nickel, and Saldanha da Gama, Francisco. Location Science. Springer, 2015.
Copyright © 2020 Gurobi Optimization, LLC