import numpy as np
class SRFLPDataCenter:
def __init__(self):
self._num_rooms = None
self._room_lengths = None
self._distance_matrix = None
def read_data(self, data_file):
with open(data_file) as f:
first_line = f.readline()
self._num_rooms = int(first_line)
second_line = f.readline().split()
self._room_lengths = [
float(v) for v in second_line
]
self._distance_matrix = \
np.zeros((self._num_rooms, self._num_rooms))
for row in range(self._num_rooms):
line = f.readline().split()
for col in range(self._num_rooms):
self._distance_matrix[row][col] = \
float(line[col])
@property
def num_rooms(self): return self._num_rooms
def get_room_length(self, room_idx):
return self._room_lengths[room_idx]
def get_distance(self, i, j):
return self._distance_matrix[i][j]
10 Single Row Facility Layout Problem
Single Row Facility Layout Problem (SRFLP) is a type of optimization problem in which the objective is to arrange a set of facilities in a single row in such a way as to minimize the total cost of movement between facilities. In other words, the goal is to find the best possible arrangement of facilities in a linear fashion that minimizes the total distance traveled by workers or materials between facilities. The SRFLP has a wide range of applications in various industries:
Manufacturing Industry: In manufacturing plants, the SRFLP is used to determine the optimal placement of machines, workstations, and other facilities in a single line to minimize material handling and transportation costs. By arranging the facilities in an optimal sequence, the movement of raw materials, work-in-progress, and finished products can be minimized, reducing production time and costs.
Warehousing and Distribution: In the warehousing and distribution industry, the SRFLP is used to optimize the layout of storage areas, packing and shipping stations, and other facilities. By minimizing the distance traveled between facilities, the time and cost of moving products within the warehouse or distribution center can be reduced.
Retail Industry: The SRFLP can be used to optimize the layout of retail stores, such as supermarkets and department stores. By arranging product displays and checkout stations in an optimal sequence, customer flow can be improved, and waiting times can be reduced, resulting in better customer satisfaction and increased sales.
Healthcare Industry: In hospitals and clinics, the SRFLP can be used to optimize the layout of patient rooms, laboratories, and other medical facilities. By arranging these facilities in an optimal sequence, healthcare professionals can move more efficiently, reducing patient wait times and improving the quality of care.
Office Layout: The SRFLP can also be used to optimize the layout of office spaces, including the arrangement of desks, meeting rooms, and common areas. By minimizing the distance between facilities, the productivity and efficiency of workers can be improved.
In summary, the SRFLP has many applications in different industries, where the optimization of facility layout can result in significant cost savings, improved productivity, and increased customer satisfaction.
The SRFLP can be defined as follows: Assume there are \(n\) rooms of different lengths \(h_i\) that need to be arranged in a single row. The flow of materials between each pair of rooms, denoted by \(w_{ij}\), is already known. Let \(\mathcal{N}\) represent the set of rooms to be arranged, which consists of integers from 0 to \(n-1\). Let \(H\) be the sum of the lengths of all the rooms, and let \(V\) be a large number.
To formulate the problem mathematically, we introduce the following variables:
- \(x_{ij}\): a binary variable that takes the value of 1 if room \(i\) is placed to the left of room \(j\), and 0 otherwise.
- \(y_i\): a continuous variable that represents the location of the starting point of room \(i\) on the line.
- \(l_{ij}\): a continuous variable that represents the distance between the centroid of room \(i\) and the centroid of room \(j\) if room \(i\) is placed to the left of room \(j\), and 0 otherwise.
- \(r_{ij}\): a continuous variable that represents the distance between the centroid of room \(i\) and the centroid of room \(j\) if room \(i\) is placed to the right of room \(j\), and 0 otherwise.
The SRFLP can then be formulated as follows:
\[\begin{align} \text{min.} &\quad \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} w_{ij} \cdot (l_{ij} + r_{ij}) \label{srfl-obj}\\ \text{s.t.} &\quad 0 \leq y_i \leq H, \ \forall i = 0, \cdots, n-1 \label{srfl-cons1} \\ &\quad y_i \geq y_j + h_j - V \cdot x_{ij}, \ \forall i, j \in \mathcal{N}, \ i < j \label{srfl-cons2} \\ &\quad y_j \geq y_i + h_i - V \cdot (1 - x_{ij}), \ \forall i, j \in \mathcal{N}, \ i < j \label{srfl-cons3} \\ &\quad r_{ij} - l_{ij} = y_i - y_j + \frac{1}{2} (h_i - h_j), \ \forall i, j \in \mathcal{N}, i \neq j \label{srfl-cons4} \\ &\quad x_{ij} \in \{0, 1\}, \ \forall i, j \in \mathcal{N}, i \neq j \label{srfl-cons5} \\ &\quad y_i \geq 0, \ \forall i \in \mathcal{N} \label{srfl-cons6} \\ &\quad l_{ij} \geq 0, \ \forall i, j \in \mathcal{N}, i \neq j \label{srfl-cons7} \\ &\quad r_{ij} \geq 0, \ \forall i, j \in \mathcal{N}, i \neq j \label{srfl-cons8} \\ \end{align}\]
The goal of the objective function \(\eqref{srfl-obj}\) is to minimize the total cost of moving all the rooms. The constraints \(\eqref{srfl-cons1}\) ensure that the starting point of each room is within the range of \([0, H]\). Constraints \(\eqref{srfl-cons2}\) and \(\eqref{srfl-cons3}\) are complementary disjunctive constraints that ensure that no two rooms overlap with each other. Constraints \(\eqref{srfl-cons4}\) calculate the distance between the centroids of any two rooms placed in a specific order on the line. The remaining constraints specify the type of variables used.
To evaluate the effectiveness of the formulated model, we utilize benchmarking instances obtained from an online source (https://grafo.etsii.urjc.es/optsicom/srflp.html). In the following code, we define a class called SRFLPDataCenter. This class is responsible for parsing the instance file and storing the relevant information in its attributes.
The following code provides a comprehensive program that uses OR-Tools to solve the SRFLP.
from ortools.linear_solver import pywraplp
from itertools import product
import numpy as np
class SRFLPSolver:
def __init__(self, data_center):
self._data_center = data_center
self._solver = None
self._var_x = None
self._var_y = None
self._var_l = None
self._var_r = None
self._opt_obj = 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 _create_variables(self):
num_rooms = self._data_center.num_rooms
self._var_x = np.empty(
(num_rooms, num_rooms),
dtype=object
)
for i, j in product(range(num_rooms),
range(num_rooms)):
if i == j: continue
self._var_x[i][j] = \
self._solver.BoolVar(name=f'x_{i, j}')
H = sum([self._data_center.get_room_length(r)
for r in range(num_rooms)])
self._var_y = [
self._solver.NumVar(0, H, name=f"y_{i}")
for i in range(num_rooms)
]
infinity = self._solver.Infinity()
self._var_l = np.empty((num_rooms, num_rooms),
dtype=object)
self._var_r = np.empty((num_rooms, num_rooms),
dtype=object)
for i, j in product(range(num_rooms),
range(num_rooms)):
if i == j: continue
self._var_l[i][j] = \
self._solver.NumVar(0,
infinity,
name=f"l_{i,j}")
self._var_r[i][j] = \
self._solver.NumVar(0,
infinity,
name=f"r_{i,j}")
def _create_objective(self):
num_rooms = self._data_center.num_rooms
expr = [
self._data_center.get_distance(i, j) *
(self._var_l[i][j] + self._var_r[i][j])
for i in range(0, num_rooms - 1)
for j in range(i + 1, num_rooms)
]
self._solver.Minimize(self._solver.Sum(expr))
def _create_constraints(self):
num_rooms = self._data_center.num_rooms
H = sum([self._data_center.get_room_length(r)
for r in range(num_rooms)])
for i in range(0, num_rooms):
hi = self._data_center.get_room_length(i)
for j in range(i + 1, num_rooms):
hj = self._data_center.get_room_length(j)
self._solver.Add(
self._var_y[i] >=
self._var_y[j] +
hj -
H * self._var_x[i][j]
)
self._solver.Add(
self._var_y[j] >=
self._var_y[i] +
hi -
H * (1 - self._var_x[i][j])
)
for i, j in product(range(num_rooms),
range(num_rooms)):
if i == j: continue
hi = self._data_center.get_room_length(i)
hj = self._data_center.get_room_length(j)
self._solver.Add(
self._var_r[i][j] - self._var_l[i][j] ==
self._var_y[i] - self._var_y[j] +
0.5 * (hi - hj)
)
def optimize(self):
status = self._solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
self._opt_obj = self._solver.Objective().Value()
print(f"obj = {self._opt_obj:.2f}")
num_rooms = self._data_center.num_rooms
self._opt_y = [
self._var_y[r].solution_value()
for r in range(num_rooms)
]
for r in range(num_rooms):
print(f"room {r} starting position: \
{self._opt_y[r]:.2f},\t\
length: \
{self._data_center.get_room_length(r)}")To test the program since the original instance is too large, we use the first 8 rooms from the instance AnKeVa_2005_60dept_set1 and solve it using OR-Tools. The program will output the optimal objective value and the positions of all the rooms.
import os
data_dir = "./data/srflp/Anjos"
data_file = "AnKeVa_2005_60dept_set1-mini.txt"
data_center = SRFLPDataCenter()
data_center.read_data(os.path.join(data_dir, data_file))
solver = SRFLPSolver(data_center)
solver.build_model()
solver.optimize()obj = 3715.00
room 0 starting position: 217.00, length: 53.0
room 1 starting position: 138.00, length: 7.0
room 2 starting position: 53.00, length: 47.0
room 3 starting position: 147.00, length: 15.0
room 4 starting position: 100.00, length: 38.0
room 5 starting position: 189.00, length: 28.0
room 6 starting position: 162.00, length: 27.0
room 7 starting position: 145.00, length: 2.0