A Basic Variable Neighborhood Search Approach for the Bi-objective Multi-row Equal Facility Layout Problem

Abstract

The Bi-Objective Multi-Row Facility Layout Problem is a problem belonging to the family of Facility Layout Problems. This problem is challenging for exact and metaheuristics approaches. We use the Pareto front approach instead of the weight approach by means of a non-dominated solution set which we update in order to keep only the non-dominated solutions. To tackle this problem, we propose a Basic VNS algorithm based on a constructive method that generates random solutions, a mono-objective local search that relies on an interchange move, and a shake method that applies insert moves. In this regard, we also explain how to adapt the mono-objective schema of the BVNS for a multi-objective one. Then, we compare our results with the state of the art and propose future work.

This work has been partially supported by the Spanish Ministerio de Ciencia e Innovación (MCIN/AEI/10.13039/501100011033/FEDER, UE) under grant ref. PID2021-126605NB-I00.

1 Introduction

Facility Layout Problems (FLPs) are a well-known family of optimization problems with the goal of finding the optimal position of facilities in a given layout. See [1, 9] and [10] for recent surveys. FLP is seen as a challenge for both exact and heuristic procedures. The very first work addressing this family of problems originally dates from 1969 [16] and was motivated by the need for a linear arrangement of different rooms along a corridor. This problem is called Single-Row Facility Layout Problem (SRFLP).

Many FLP variants can also be found in the literature. For example, in the Single-Row Equal Facility Layout Problem (SREFLP) [11] all the facilities have the same width. Using two rows, we find the Double-Row Facility Layout Problem (DRFLP) [4], and its variants. Other variants consider several rows (more than two rows) such as the Multi-Row Facility Layout Problem (MRFLP) [12], and its variants. Another challenging variant is the Multi-Row Equal Facility Layout Problem (MREFLP) [2, 18]. From the multi-objective point of view, the bi-objective MREFLP is a variant of the MREFLP which considers two objective functions and where both, the number of rows and the number of facilities that can be allocated in each row, are given by the instance. In other words, the layout configuration is fixed by the target instance.

In general multi-objective problems can be addressed from two different approaches. The first one combines all objective functions into a single one by means of a weighted sum, and returns a single value [3, 6,7,8, 13, 15], and [17]. The second approach considers a set of different non-dominated solutions taking into account the objective functions separately [17]. In this work, we will follow this last approach.

The rest of the paper is structured as follows. In Sect. 2 we provide a description for the problem and an example of evaluation. Then, we describe our Basic VNS approach in Sect. 3. In Sect. 4 we explain our results and compare them with the state of the art. Finally, in Sect. 5, we present our conclusions and future work.

2 Problem Description

Given a set of facilities (F), a weight matrix corresponding to an objective function (W), a solution that we are going to evaluate ($\varphi$), the number of rows (m) and the number of columns (c), we can calculate the objective function value through Eq. 1 in this way: let $\rho (i,j)$ be the facility in row i and column j in $\varphi$, $w_{u,v}$ be the weight between facilities u and v in matrix W, and $d_{u,v}$ the distance between facilities u and v, the equation computes the sum of the products of all facilities pairwise weight and their pairwise distance.

$$\begin{aligned} \mathcal {F}({F}, W, \varphi ) = \sum _{i=1}^{m}\sum _{j = 1}^{c}\sum _{k=1}^{m}\sum _{l = j+1}^{c}w_{\rho (i,j),\rho (k,l)}\cdot d_{\rho (i,j),\rho (k,l)} \end{aligned}$$

(1)

As seen, the product has two parameters: a weight between the pairwise and the distance between these facilities. We extract the weight from the weight matrix, but we need to calculate the distance among them. In this problem, the Manhattan distance is used. This means that we will consider the vertical distance in addition to the horizontal distance between facilities. Manhattan distance is computed as shown in Equation (2).

$$\begin{aligned} d_{\rho (i,j),\rho (k,l)} = |l - j| + |k - i| \end{aligned}$$

(2)

For this problem, we have two objective functions: material handling cost, MHC and closeness ratio, CR, and both are calculated with Equation (1). The difference between them is the weight matrix they use, which is different. Notice that these objectives are opposed due to these weight matrices values. Table 1 shows the weight matrix for MHC on the left and the weight matrix for CR on the right. Here we see that the weight between $\texttt{A}$ and $\texttt{E}$ facilities for MHC is 6, and it is -1 for CR. On the contrary, the weights between $\texttt{C}$ and $\texttt{F}$ are 1 and -1. So, depending on the values of these weight matrix, the objectives could be opposed.

Table 1. Weight matrices for the solution in Fig. 1. On the left, the weight matrix for the MHC. On the right, the weight matrix for the CR.

Fig. 1.

Example layout with size 6.

For the sake of understanding we provide an example through Table 1 and Fig. 1. Let us begin with the contribution of the facility located in the first row and in the first column, $\rho (\texttt{1,1}) = \texttt{A}$, to the objective functions. First, we need to calculate the distance between facilities A and D, where $\rho (\texttt{1,2}) = \texttt{D}$. Notice that both facilities are in the same column, so, there is no vertical distance between them ($d_{\texttt{AD}} = |(1 - 1)| + |(2 - 1)| = 1$). Then we proceed with the weight matrix. The contribution to the objective CR is $w_\texttt {AD} \cdot d_\texttt {AD}$, where $d_\texttt {AD} = 1$ and $w_\texttt {AD} = 2$. As a result, we have $w_\texttt {AD} \cdot d_\texttt {AD} = 2$. For the other objective function, we use the weight between $\texttt{A}$ and $\texttt{D}$. Since $w_\texttt {AD} = 2$, we have the same result for the objective function MHC. We repeat this process for each pairwise between $\texttt{A}$ and the other facilities. In the final step, we calculate the last pairwise facilities value, $\texttt{A}$ and $\texttt{F}$. For these facilities, where $\rho (\texttt{1,1}) = \texttt{A}$ and $\rho (\texttt{2,3}) = \texttt{F}$, the distance is $d_{\texttt{AF}} = |(3 - 1)| + |(2 - 1)| = 3$. The weight between facilities $\texttt{A}$ and $\texttt{F}$ is 4, for CR and for MHC. Then, the contribution of this pairwise for the objective function CR is $w_\texttt {AF} \cdot d_\texttt {AF} = 12$ and $w_\texttt {AF} \cdot d_\texttt {AF} = 12$ for the MHC one. In summary, to obtain the total contribution of facility $\texttt{A}$, we need the following operation:

$$ w_\texttt {AD} \cdot d_\texttt {AD}+w_\texttt {AE} \cdot d_\texttt {AE}+ w_\texttt {AB} \cdot d_\texttt {AB} + w_\texttt {AC} \cdot d_\texttt {AC} +w_\texttt {AF} \cdot d_\texttt {AF} $$

Once we finish calculating facility $\texttt{A}$, we have to repeat this process with the rest of facilities.

3 Basic Variable Neighborhood Search

One of the most famous metaheuristics is Variable Neighborhood Search (VNS), which was proposed in 1997 by Mladenovic and Hansen [14]. This algorithm has several variants and, among them, one of the most used is the Basic Variable Neighborhood Search (BVNS). This variant lets us escape from the local optima through a shake movement. For mono-objective problems, we can apply the schema for BVNS as it was originally proposed. For multi-objective problems, we have to change this schema because this schema works for one solution, but not a set of solutions.

3.1 Bi-Objective BVNS

In this section, we will explain our algorithm proposal and the details of each proposed component for this algorithm.

If we work with mono-objective problems, it is simple to define if one solution is better than another. If we minimize, the solution with lowest value will be the best. If we are maximizing, then the other way around. For multi-objective problems, we have to compare the values for different objective functions. In this particular case, we have two functions that we have to minimize. One solution can dominate another, be dominated by another, or these solutions can be non-dominated among them. More precisely a solution $\varphi _{1}$ dominates $\varphi _{2}$ ($\varphi _{1} \prec \varphi _{2}$) if the value of objective function ${\mathcal {G}}_{i} (\varphi _{1})$ is better of equal for all objectives i, and exists one objective value where $\varphi _{1}$ is better. Equation (3) formally shows this concept.

$$\begin{aligned} \begin{aligned} \varphi _{1} \prec \varphi _{2} \; if \; \\ \forall i \in \{1..k\} : {\mathcal {G}}_{i} (\varphi _{1}) \le {\mathcal {G}}_{i} (\varphi _{2}) \\ \wedge \; \exists i \in \{1..k\}: {\mathcal {G}}_{i} (\varphi _{1}) < {\mathcal {G}}_{i} (\varphi _{2}) \end{aligned} \end{aligned}$$

(3)

Due to the fact that we are going to work with more than one solution, we have to store them in a data structure. We will use a set of non-dominate solutions which we call ND. This set will contain only non-dominated solutions. Whenever we want to add a solution $\varphi$ to this set, we will use the function Update, which will check if $\varphi$ is dominated by any solution in the set. If so, we will not add this solution. If not, we will check all the solutions in the set, removing all the solutions dominated by $\varphi$.

One of the most important points of this algorithm is to define when we have improved our solution. To this aim, we will use the approach proposed [5]. This approach uses ND as the solution to be improved. If any changes have been made to ND, we consider that our algorithm has improved our current solution. Algorithm 1 shows our implementation of this approach.

In step 1) we create an empty ND. Then we generate a set of solutions by mean of a constructive method in step 2 which will be explained in Sect. 3.2. The number of solutions that we generate is given by the maxCons parameter. Then, in step 3, we populate ND with the solutions previously generated (S). It is worth noting that we Update each time we add a solution to our ND. Then, in step 4, we try to improve all our solutions as explained in Sect. 3.3. As a result, we obtain a new set S of improved solutions. Then, we update again our ND with S, obtaining the initial set of non-dominated solutions. In step 6, we set $k = 1$. Then, in step 7, we will iterate until we reach kMax. In this case, kMax depends on the size of the instance. Inside the loop, in step 8, we select a random solution ($\varphi$) from ND. Then, in step 9, we shake our solution $\varphi$ as described in Sect. 3.4. The parameter k indicates how many times we shake our solution. In step 10, we apply our local search procedure to $\varphi '$, saving the resulting solutions in S. In step 11 we update our ND with S obtaining a new set ND’. In step 12 we check if ND’ is equal to ND. If they are different then there was an improvement. Therefore, we update ND to ND’ in step 11 and then, in step 13, we set $k = 1$ to reset the loop. If there was no improvement, k is incremented in step. Finally, in step 17, we return ND.

3.2 Constructive Method

In this first approach, we have used only one constructive method. With the aim of increasing diversity, our algorithm generates feasible solutions at random following a multi-start approach. This way, the non-dominated solution set will be populated with a number of different solutions. We have run this constructive 100 times, and we have stored these solutions in S. Once we have these solutions, we proceed to update our ND. Due to the fact that this set will contain only non-dominated solutions, ND could contain less than 100 solutions.

3.3 Local Search

Once we have a constructive method, we proceed to try to improve the solutions that we have obtained. We have implemented two different neighborhoods through two different moves: interchange and insert. In this section, we will explain the interchange movement. In the next section we will explain the insert one. Moreover, we will explain the local search that we have used. It is worth remembering that the layout is already defined by the instance, that means we know, as a constraint of the problem, the number of rows and the number of facilities per row.

Let us explain the interchange movement through Fig. 2. As stated in Sect. 1, the layout is already defined. Whenever we use a movement, we have to keep the same layout. On the left, we have the original layout, and on the right, we have the resulting one after the movement. The interchange movement changes the position of two facilities, leaving the others in their previous position. As we can see in Fig. 2, we have interchanged facilities $\texttt{D}$ and $\texttt{C}$.

Fig. 2.

Interchange facilities C and D.

For the local search, we will use the interchange movement. Our local search is based on the one proposed in [18] which considers only one objective. Due to the fact that we have two objectives, we need to adapt the implementation. The idea is to run two searches on each solution, one per objective. Let us explain in detail the local search through its implementation in Algorithm 2.

First, in step 1 we create an empty initial set of solutions S. Then in step 2, we will go through all the solutions in ND. We launch the local search that we mentioned above, focusing on the objective MHC and store this result in $s_{1}$. We do the same for the CR in step  4. Then, we add $s_{1}$ and $s_{2}$ to S in step 5 and iterate to the next solution in ND. Finally, we return S in step 6.

We represent this idea of the alternate local searches in Fig. 3. In this figure, we have two solutions, indicated as (b) and (a). In addition, we have also represented the two objectives MHC and CR. On the abscissa axis, MHC is represented; meanwhile, on the ordinate axis, CR is represented. There are four colored arrows. On the one hand, the orange ones represent how the solutions follow a trajectory toward the MHC objective. On the other hand, the blue ones follow a path toward the CR objective.

Fig. 3.

Mono-objective local search.

3.4 Shake

In the previous section we have explained how the interchange movement works, and how we had used it in our local search procedure. In this section, we explain the insert movement. We have reserved this movement for the shake procedure. The reason is that this movement diversifies more than the interchange movement. Let us explain this movement through Fig. 4.

In Fig. 4 we have the original solution on the left, while on the right we have the one obtained after a certain insert. In particular, we have inserted facility $\texttt{A}$ in the second row, third column. As we can see in this solution, all the other facilities but $\texttt{F}$ have changed positions. The reason is that the layout has been previously defined and we have to keep this layout.

Fig. 4.

Insert facility $\texttt{A}$ in the second row and third column.

4 Results

In this section, we show our experimental results and then compare them with the state of the art. We represent our results graphically, in order to make the comparison easier for the reader.

The previous state of the art presented three algorithms: BBO, NSBBO and NSGA - II [17]. They used BBO as a weighted approach and NSBBO and NSGA - II as a Pareto front approach. In particular, NSBBO is the adaptation of the BBO to the Pareto front approach. The previous authors proposed four instances where we have run our proposal. As it will be shown, the authors reported only a few solutions per instance, but they did not report execution times. The solutions proposed by the previous paper are colored green for NSBBO and blue for NSGA - II. Our proposal is colored red en the figures.

Figure 5 shows the results for the instance of size 6. In this instance, the values reported for NSBBO and NSGA - II are the same. Our BVNS approach obtains four solutions that clearly dominate the previous ones. In fact, solution (71, 105) dominates all previous solutions.

Fig. 5.

Previous instance with size 6.

Figure 6 shows the results for the instance of size 8. Again, our BVNS approach obtains four solutions that clearly dominate the previous ones.

Fig. 6.

Previous instance with size 8.

Figure 7 shows the results for the instance of size 12. In this instance, our BVNS proposal obtains eleven solutions that clearly dominate the previous ones.

Fig. 7.

Previous instance with size 12.

Finally, Fig. 8 shows the results for the instance of size 15. In this instance, the values reported for the NSBBO and NSGA - II are more dispersed than in the previous instances. Our BVNS proposal obtains eight solutions where two of them are similar to the previous results. However, the resulting solutions clearly dominates the previous ones.

Fig. 8.

Previous instance with size 15.

5 Conclusions and Future Work

The BO-MREFLP was recently studied in several works, using different approaches. In this paper, we propose a metaheuristic algorithm based on the BVNS methodology. We have reached and improved the results in the state of the art.

As a future work, we will work on a new constructive method based on a GRASP methodology. In addition, it could be possible to implement another kind of local search instead of the mono-objective one. Finally, instead of selecting random solutions from ND, we can use the crowding distance to select the solution.