import re
class WlpDataCenter:
def __init__(self):
self._num_warehouses = None
self._num_stores = None
self._capacities = None
self._fixed_costs = None
self._demands = None
self._transport_costs = None
def read_data(self, data_file):
with open(data_file) as f:
lines = f.readlines()
self._num_warehouses = int(re.findall(r'\d+',
lines[0])[0])
self._num_stores = int(re.findall(r'\d+',
lines[1])[0])
self._capacities = [
int(num)
for num in re.findall(r'\d+', lines[3])
]
self._fixed_costs = [
int(num)
for num in re.findall(r'\d+', lines[4])
]
self._demands = [
int(num)
for num in re.findall(r'\d+', lines[5])
]
self._transport_costs = []
for line in lines[6:]:
numbers = [
int(num)
for num in re.findall(r'\d+', line)
]
self._transport_costs.append(numbers)
@property
def num_warehouses(self): return self._num_warehouses
@property
def num_stores(self): return self._num_stores
@property
def capacities(self): return self._capacities
@property
def demands(self): return self._demands
@property
def fixed_costs(self): return self._fixed_costs
@property
def transport_costs(self): return self._transport_costs11 Warehouse Location Problem
The warehouse location problem (WLP) is a classic optimization problem in operations research that aims to find the optimal locations for warehouses in order to minimize transportation costs while meeting the demand for goods from a set of customers. The problem is particularly relevant for businesses that need to distribute their products across a large geographic region.
The problem can be formulated as follows: Given a set of stores \(\mathcal{S} = \{1, \cdots, s\}\) and a set of potential warehouse locations \(\mathcal{W} = \{1, \cdots, w\}\), the objective is to select a subset of warehouse locations and allocate stores to these locations such that the total transportation cost is minimized. The transportation cost typically depends on the distance between each store and the warehouse they are assigned to, as well as the quantity of goods that need to be transported.
In order to simplify our mathematical model, we utilize the following symbols to indicate the input parameters:
- \(f_w\): the fixed cost required for initiating warehouse \(w\)
- \(c_{ws}\): the cost of transporting goods from warehouse \(w\) to store \(s\)
- \(d_s\): the quantity of goods demanded by store \(s\)
- \(N_w\): the storage capacity of warehouse \(w\)
We can then define two variables:
- \(y_s\): a binary variable that takes on a value of 1 if warehouse \(s\) is chosen, and 0 otherwise
- \(x_{ws}\): a continuous variable that represents the fraction of store \(s\)’s demand that will be met by warehouse \(w\)
The complete model of this problem is given below.
\[\begin{align} \text{min.} &\quad \sum_{w \in \mathcal{W}} \sum_{s \in \mathcal{S}} c_{ws} d_s x_{ws} + \sum_{w \in \mathcal{W}} f_w y_w \label{wlp-obj} \\ \text{s.t.} &\quad \sum_{w \in \mathcal{W}} x_{ws} = 1, \ \forall s \in \mathcal{S} \label{wlp-cons1} \\ &\quad \sum_{s \in \mathcal{S}} d_s x_{ws} \leq N_w y_w, \ \forall w \in \mathcal{W} \label{wlp-cons2} \\ &\quad 0 \leq x_{ws} \leq 1, \ \forall w \in \mathcal{W}, s \in \mathcal{S} \label{wlp-cons3} \\ &\quad y_w \in \{0, 1\}, \ \forall w \in \mathcal{W} \label{wlp-cons4} \end{align}\]
The objective function \(\eqref{wlp-obj}\) is to minimize the total cost of transportation and the fixed cost of opening warehouses. The first term of the objective function sums up the transportation cost of moving goods from each warehouse \(w\) to each store \(s\), multiplied by the proportion of store \(s\)’s demand met by warehouse \(w\), represented by \(x_{ws}\). The second term of the objective function sums up the fixed cost of opening each warehouse \(w\), represented by \(f_w\), multiplied by a binary variable \(y_w\) that takes on a value of 1 if warehouse \(w\) is selected, and 0 otherwise.
The model is subject to four constraints:
- Constraint \(\eqref{wlp-cons1}\) ensures that the entire demand of each store \(s\) is met. The sum of \(x_{ws}\) over all warehouses must be equal to 1 for each store \(s\).
- Constraint \(\eqref{wlp-cons2}\) ensures that the total demand of all stores served by warehouse \(w\) does not exceed its capacity \(N_w\). The sum of \(d_s x_{ws}\) over all stores \(s\) must be less than or equal to \(N_w y_w\) for each warehouse \(w\).
- Constraint \(\eqref{wlp-cons3}\) ensures that the fraction of store \(s\)’s demand met by warehouse \(w\), represented by \(x_{ws}\), is between 0 and 1.
- Constraint \(\eqref{wlp-cons4}\) ensures that the binary variable \(y_w\) takes on a value of either 0 or 1, indicating whether or not warehouse \(w\) is selected.
To demonstrate the solution process for the Warehouse Location Problem (WLP) using OR-Tools, we will use some sample instances available online from the website https://opthub.uniud.it/problem/facility-location/wlp. Specifically, we will be using an instance file called wlp2, the contents of which are shown below.
Warehouses = 2;
Stores = 5;
Capacity = [65, 47];
FixedCost = [80, 184];
Goods = [4, 15, 17, 6, 6];
SupplyCost = [|57, 71
|30, 59
|43, 71
|37, 72
|30, 68|];In this instance file, there are 2 warehouses and 5 stores. The Capacity array specifies the maximum capacity of each warehouse, where the first warehouse has a capacity of 65 and the second has a capacity of 47. The FixedCost array specifies the fixed cost of opening each warehouse, where the first warehouse has a fixed cost of 80 and the second has a fixed cost of 184. The Goods array specifies the demand for each store, where the first store has a demand of 4, the second store has a demand of 15, the third store has a demand of 17, the fourth store has a demand of 6, and the fifth store has a demand of 6. The SupplyCost matrix specifies the transportation cost of moving goods from each warehouse to each store. The entry in row \(i\) and column \(j\) of the matrix represents the transportation cost of moving goods from warehouse \(j\) to store \(i\). For example, the transportation cost of moving goods from the first warehouse to the first store is 57, the transportation cost of moving goods from the second warehouse to the fourth store is 71, etc.
We will create a WlpDataCenter class that will be responsible for reading and storing the necessary information required for solving the problem later on.
Now we are ready to solve the WLP using OR-Tools!
from ortools.linear_solver import pywraplp
from itertools import product
import numpy as np
class WlpSolver:
def __init__(self, data_center):
self._data_center: WlpDataCenter = data_center
self._solver = None
self._var_x = None
self._var_y = None
self._opt_obj = None
self._opt_x = None
self._opt_y = None
def build_model(self):
self._solver = pywraplp.Solver.CreateSolver('SCIP')
self._create_variables()
self._create_objective()
self._create_constraints()
def optimize(self):
self._solver.SetTimeLimit(20000)
status = self._solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
num_warehouses = self._data_center.num_warehouses
num_stores = self._data_center.num_stores
self._opt_obj = self._solver.Objective().Value()
self._opt_x = np.zeros((num_warehouses,
num_stores))
for w, s in product(range(num_warehouses),
range(num_stores)):
self._opt_x[w][s] = \
self._var_x[w][s].solution_value()
self._opt_y = [
self._var_y[w] for w in range(num_warehouses)
]
def _create_variables(self):
num_warehouses = self._data_center.num_warehouses
num_stores = self._data_center.num_stores
self._var_x = np.empty((num_warehouses, num_stores),
dtype=object)
for w, s in product(range(num_warehouses),
range(num_stores)):
self._var_x[w][s] = \
self._solver.NumVar(0, 1,
name=f'x_{w,s}')
self._var_y = [
self._solver.BoolVar(name=f'y_{w}')
for w in range(num_warehouses)
]
def _create_objective(self):
num_warehouses = self._data_center.num_warehouses
num_stores = self._data_center.num_stores
demands = self._data_center.demands
transport_costs = self._data_center.transport_costs
fixed_costs = self._data_center.fixed_costs
expr1 = [
transport_costs[s][w] *
demands[s] *
self._var_x[w][s]
for w in range(num_warehouses)
for s in range(num_stores)
]
expr2 = [
fixed_costs[w] *
self._var_y[w]
for w in range(num_warehouses)
]
self._solver.Minimize(
self._solver.Sum(expr1) +
self._solver.Sum(expr2)
)
def _create_constraints(self):
num_warehouses = self._data_center.num_warehouses
num_stores = self._data_center.num_stores
for s in range(num_stores):
expr = [
self._var_x[w][s]
for w in range(num_warehouses)
]
self._solver.Add(
self._solver.Sum(expr) == 1
)
demands = self._data_center.demands
capacities = self._data_center.capacities
for w in range(num_warehouses):
expr = [
self._var_x[w][s] *
demands[s]
for s in range(num_stores)
]
self._solver.Add(
self._solver.Sum(expr) <=
capacities[w] *
self._var_y[w]
)
@property
def opt_obj(self): return self._opt_obj
@property
def opt_x(self): return self._opt_x
@property
def opt_y(self): return self._opt_yThe program defines a class named WlpSolver which has methods to build the model, optimize it and retrieve the optimized solution.
The WlpSolver class takes an instance of WlpDataCenter as input, which contains the data necessary to solve the problem. The build_model() method creates variables, objectives, and constraints for the problem using the OR-Tools library. The optimize() method solves the problem and saves the optimized objective function value, opt_obj, the matrix opt_x that indicates the optimal assignment of stores to warehouses, and a list opt_y of binary variables that indicate whether or not each warehouse is open.
The _create_variables() method creates two types of variables: a matrix of continuous variables that indicates the proportion of a store’s demands that’s served by a warehouse and a list of binary variables that indicate whether or not each warehouse is open. The _create_objective() method creates the objective function of the problem, which is to minimize the total cost of opening warehouses and serving stores. The _create_constraints() method creates constraints that ensure that every store’s demands are fully fulfilled and a warehouse’s capacity is not violated.
Finally, the opt_obj, opt_x, and opt_y properties allow access to the results of the optimization.
Table 11.1 reports the best solutions found within the time limits of 10 seconds for some testing instances.
| Instance | No. Warehouses | No. Stores | Best Solution |
|---|---|---|---|
| wlp1 | 1 | 3 | 1931 |
| wlp2 | 2 | 5 | 1891 |
| wlp3 | 3 | 7 | 4358 |
| wlp4 | 4 | 10 | 4246 |
| wlp5 | 5 | 12 | 3502 |
| wlp6 | 6 | 15 | 4108 |
| wlp7 | 7 | 17 | 4276 |
| wlp8 | 8 | 20 | 4888 |
| wlp9 | 9 | 22 | 7959 |
| wlp10 | 10 | 25 | 8893 |
| wlp12 | 12 | 30 | 4890 |
| wlp15 | 15 | 37 | 14881 |
| wlp20 | 20 | 50 | 9727 |
| wlp30 | 30 | 75 | 11964 |
| wlp50 | 50 | 120 | 15164 |
| wlp100 | 100 | 220 | 20848 |