© Wuhan University 2023

0 Introduction

Facility layout problem (FLP) is important both in theoretical and engineering application fields. FLP consists of finding the most efficient arrangement of facilities under certain constraints to meet one or more objectives^[1]. The most common objective is to minimize the material handling cost^[2]. Companies are able to reduce manufacturing cost and improve their productivity by arranging facilities effectively^[3]. As a kind of the FLP, the double row layout problem (DRLP) is a commonly encountered one in practice, such as the arrangement of rooms in buildings^[4], the layout of stacker cranes in the flexible manufacturing systems^[5] and the arrangement of facilities along two parallel straight lines on a floor plan^[6]. A general DRLP is to assign facilities on two rows in parallel so that the total cost of material handling among facilities is minimized.

Because of its importance, DRLP has attracted the attention of many researchers. A mixed integer programming (MIP) model for the DRLP was first developed by Chung and Tanchoco^[7], and then corrected by Zhang and Murray^[8]. Amaral^[9] studied the DRLP with implicit clearances and presented a new MIP model for it by using $\alpha$-incidence vectors. Reformulating some constraints, Secchin and Amaral^[10] obtained a tighter model for the DRLP. Considering some valid inequalities and a symmetry breaking constraint, Amaral^[11] established an improved MIP model for the DRLP. Chae and Regan^[12] proposed a new MIP model by introducing tighter constraints. Murray et al^[13] extended the DRLP by considering the non-zero aisle width and proposed a mixed integer linear programming formulation for it. Considering asymmetric material flows between machines, Murray et al^[14] proposed an extended formulation for the DRLP. Tang et al^[15] studied a robust DRLP where varying material flows were considered in different periods. Considering the dynamic environment, Wang et al^[16] proposed a dynamic DRLP. Anjos et al^[17] studied the DRLP with equidistant facilities and presented an integer linear programming for it. Gülşen et al^[18] presented a new variant of the DRLP that features types of capacitated machines. To meet several layout demands in the hospital, Zuo et al^[19] proposed a double row layout problem with center-islands. A large number of solution methods had been proposed to solve different DRLPs, such as semidefinite programming^[17], the combination of simulated annealing and mathematical programming^[16], the combination of simulation and optimization^[20], constructive heuristic^[7], decomposition based strategy^[21,22], and multi-objective Tabu search with a linear programming^[23].

Since solution methods must be based on the models of problems, a simple and effective model plays an important role in solving a problem. However, the model of the general DRLP (M-DRLP) is complex. The general DRLP has to determine not only the sequence of facilities in each row (relative placement), but also the actual location of each facility (absolute placement)^[24]. The relative and absolute placements are related to discrete and continuous decision variables, respectively. It is very time consuming to solve the general DRLP, because lots of discrete and continuous decision variables have to be dealt with together. The corridor allocation problem (CAP) is a special case of DRLP^[25], where continuous decision variables are not considered. The model of CAP (M-CAP) can be deemed as a simplified model for the DRLP. Although it is faster to solve the M-CAP than the M-DRLP, the solution quality is deteriorated. These observations motivate us to propose a new simplified model for the DRLP, which can be solved faster than the M-DRLP while its solution quality does not deteriorate significantly.

The main contribution of our work is to propose a new simplified model for the DRLP (SM-DRLP) and provide a MIP formulation for it. We divide the continuous decision variables of the general DRLP into two parts: start points of double rows and clearances between adjacent facilities. The former one is considered in the new simplified model, while the latter one is not taken into account. The experimental results show that our SM-DRLP outperforms M-CAP^[25] in terms of the solution quality. In comparison with M-DRLP^[11], our SM-DRLP can be solved faster with similar solution quality.

The remainder of this paper is organized as follows. Section 1 gives a detailed description of the simplified model for the double row layout problem (SM-DRLP). Section 2 presents a mixed-integer programming model for SM-DRLP. Section 3 shows the computational experiments. Section 4 outlines our conclusions and directions for future research.

1 Problem Description

In this section, we introduce the general DRAP and a special case of the DRLP first. Then we propose a simplified model for the double row layout problem. Given a set $\mathbb{N}=\{\mathrm{1,2},\cdots ,n\}$ of $n\ge \mathrm{2}$ facilities, each facility $i$ in the set has a length$l_i$. There is a nonnegative amount of material flow $c_{ij}$ for each pair $(i,j)$ of facilities in $\mathbb{N}$.

The general DRLP is a problem that considers how to arrange these $n$ facilities on two rows along a straight line so as to minimize the total cost of material handling among facilities^[7]. The total cost depends on the material flows and the distances between facilities. The material flows are given. The distances are determined by the sequence of facilities in each row (relative placement) and the actual location of each facility (absolute placement). The relative and absolute placements are related to discrete and continuous decision variables, respectively. The continuous decision variables of the general DRLP can be divided into two parts: adjustable clearances between adjacent facilities and start points of double rows. The adjustable clearances are called as extra clearances in Ref. [13] or additional gaps in Ref. [26]. They are used for the purpose of minimizing the overall material handling cost^[27], by reducing the distances between some facilities in the opposite row. A double row layout is illustrated in Fig. 1(a), where an automated guided vehicle (AGV) is used to transport material between facilities. The arrangements in both rows can start from different points and the adjacent facilities can be placed with adjustable clearances. The distance $d_{ij}$ between a pair $(i,j)$ of facilities is related to the distance $\delta$ between the starting points of the rows which contain facilities $i$ and $j$, the adjustable clearances $a_{k,k+\mathrm{1}}$ between adjacent facilities which are before facilities $i$ and $j$, and the lengths of facilities before facilities $i$ and $j$.

Fig.1 Different models for the DRLP

The corridor allocation problem (CAP) is a problem that also considers how to arrange $n$ facilities along two parallel rows to minimize the total cost of material handling among facilities^[25]. Different from the DRLP, a CAP layout should satisfy two main conditions: the arrangements in both rows start from a common point and no clearance is allowed between adjacent facilities. The CAP just needs to determine the sequence of facilities in double rows. It belongs to combinatorial problems. A CAP layout is illustrated in Fig. 1(b). The distance $d_{ij}$ between a pair $(i,j)$ of facilities is just related to the lengths of facilities before facilities $i$ and $j$.

In the general M-DRLP, the sequence of facilities in each row, the distance between the starting points of double rows and the adjustable clearances between adjacent facilities are decision variables. These three aspects make the DRLP model complex. The CAP is a special case of DRLP, and its model (M-CAP) can be deemed as a simplified model of the DRLP for the purpose of reducing its complexity. However, it is over simplified to ignore both the adjustable clearances and the start points, which may make the solution quality deteriorate.

The adjustable clearances reduce the distances between some facilities in the opposite row, while increasing the distances between some facilities in the same row. The adjustable clearances are able to reduce the total cost in very few cases, only where the flows between the facilities in the opposite row are much more than those in the same row. While, the start points of double rows are able to reduce the distances between some facilities in the opposite row without increasing the distances between facilities in the same row. The start points of double rows are more useful than the adjustable clearances to minimize the overall material handling cost. Furthermore, the number of variables for adjustable clearances is much larger than that of variables for the start points. It is time consuming to obtain the adjustable clearances between adjacent facilities. Therefore, we attempt to propose a new and simplified model for the DRLP (SM-DRLP) without taking the adjustable clearances between adjacent facilities into account. The goal of ignoring the adjustable clearances is to reduce the computational time. The start points have a significant influence on the solution quality of an arrangement, so our simplified model takes the start points into account with the goal of maintaining the solution quality, which is different from the model of CAP. A layout of simplified model is illustrated in Fig. 1(c). The distance $d_{ij}$ between a pair $(i,j)$ of facilities is related to the distance $\delta$ between the starting points of the rows which contain facilities $i$ and $j$ and the lengths of facilities before facilities $i$ and $j$.

2 Mixed-Integer Programming Formulation for the SM-DRLP

In this section, we extend the model of CAP^[25] to obtain a mixed-integer programming formulation for the SM-DRLP. Consistent with Ref. [11], we make the following assumptions:

• The facilities are in rectangular shape;

• The facilities are placed on two rows in parallel. The width between two rows is very small and negligible. The distance between two facilities is calculated with respect to their centroid along the $x$-axis;

• The facilities have implicit minimum clearances. It means that the minimum clearances are deemed to be all equal and included in the lengths of the facilities.

The notations for the mixed-integer programming formulation of the SM-DRLP are defined in Table 1.

2.1 Binary Variables

In order to determine the relative positions between facilities $i$ and $j$, we use the following 0-1 variable:

$a_{ij}=\{\begin{array}{c}\mathrm{1},\mathrm{i}\mathrm{f}\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{i}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{e}\mathrm{s}i\mathrm{a}\mathrm{n}\mathrm{d}j\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{w}\\ \mathrm{a}\mathrm{n}\mathrm{d}\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{i}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{y}i\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{f}\mathrm{t}\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{i}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{y}j\\ \mathrm{0},\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\end{array}$

To represent whether a facility $i$ is placed on the same row with the reference facility $r^{*}$, we also define another 0-1 variable:

${\beta }_{i{r}^{*}}=\{\begin{array}{c}\mathrm{1},\mathrm{i}\mathrm{f}\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{i}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{e}\mathrm{s}i\mathrm{a}\mathrm{n}\mathrm{d}{r}^{*}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{w}\\ \mathrm{0},\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\end{array}$

It is clear that ${\beta }_{i{r}^{*}}$ is related to ${\alpha }_{i{r}^{*}}$ and ${\alpha }_{r^{*}i}$. It can be obtained by

${\beta }_{i{r}^{*}}={\alpha }_{i{r}^{*}}+{\alpha }_{r^{*}i},\mathrm{0}\le i\le n,i\ne r^{*}$(1a)

${\beta }_{i{r}^{*}}=\mathrm{1},i=r^{*}$(1b)

2.2 Continuous Variables

When facilities are placed on double rows, the start point of the row with the reference facility $r^{*}$ is deemed to be at zero abscissa. We need the following continuous variables:

$\delta$: abscissa of the start point of the opposite row to the reference facility $r^{*}$.

$x_i$: abscissa of the centroid of facility $i$;

$d_{ij}$: distance between the centroid of facilities $i$ and $j$.

If facilities $i$ and $r^{*}$ are at the same row, the abscissa of the centroid of facility $i$ is $x_i=l_i/\mathrm{2}+{\displaystyle \sum _{k=\mathrm{1},k\ne i}^n}lk{\alpha }_{ki}$. Otherwise, it is $x_i=\delta +l_i/\mathrm{2}+{\displaystyle \sum _{k=\mathrm{1},k\ne i}^n}lk\alpha ki$. Thus, we have

$x_i=\delta (\mathrm{1}-{\beta }_{i{r}^{*}})+\frac{l_i}{\mathrm{2}}+{\displaystyle \sum _{k=\mathrm{1},k\ne i}^n}{l}_k{\alpha }_{ki},\mathrm{1}\le i\le n$(2)

From the definitions of $x_i$ and $d_{ij}$, we have

$d_{ij}=\left|x_i-x_j\right|,\mathrm{1}\le i<j\le n$

2.3 Constraints

If facilities $i$ and $j$ are in the same row, facility $i$ cannot be both to the left and to the right of facility $j$ at the same time. Thus, the following inequality must be satisfied:

${\alpha }_{ij}+{\alpha }_{ji}\le \mathrm{1,1}\le i<j\le n$(3)

Based on the work of Ref. [9], the following inequalities are also valid:

$-{\alpha }_{ij}+{\alpha }_{ik}+{\alpha }_{jk}-{\alpha }_{ji}+{\alpha }_{ki}+{\alpha }_{kj}\le \mathrm{1},i,j,k\in \mathbb{N};i<j;k\ne i,k\ne j$(4)

$-{\alpha }_{ij}+{\alpha }_{ik}-{\alpha }_{jk}+{\alpha }_{ji}-{\alpha }_{ki}+{\alpha }_{kj}\le \mathrm{1},i,j,k\in \mathbb{N};i<j;k<j,i\ne k$(5)

${\alpha }_{ij}+{\alpha }_{ik}+{\alpha }_{jk}+{\alpha }_{ji}+{\alpha }_{ki}+{\alpha }_{kj}\ge \mathrm{1,1}\le i<j<k\le n$(6)

All distances between facilities in the opposite rows will increase, as the distance between the start points of two rows increases from $L$. To reduce the distances between facilities in the opposite rows, $\delta$ should satisfy the following constraint:

$-L\le \delta \le L$(7)

Since the product term $\delta (\mathrm{1}-{\beta }_{i{r}^{*}})$ of Eq. (2) is nonlinear and nonconvex, the expression of Eq. (2) cannot be directly handled by CPLEX^[28]. We replaced the product term by a new variable ${\delta }_{i{r}^{*}}=\delta (\mathrm{1}-{\beta }_{i{r}^{*}})$. Then, Eq.(2)can be rewritten as:

$x_i={\delta }_{i{r}^{*}}+\frac{l_i}{\mathrm{2}}+{\displaystyle \sum _{k=\mathrm{1},k\ne i}^n}{l}_k{\alpha }_{ki},(\mathrm{1}\le i\le n)$(8)

The variable ${\delta }_{i{r}^{*}}=\delta (\mathrm{1}-{\beta }_{i{r}^{*}})$ can be expressed by two inequalities: ${\delta }_{i{r}^{*}}\le \delta \left(\mathrm{1}-{\beta }_{i{r}^{*}}\right)$ and ${\delta }_{i{r}^{*}}\ge \delta \left(\mathrm{1}-{\beta }_{i{r}^{*}}\right)$.Variable ${\beta }_{i{r}^{*}}$ is Boolean, then $\left(\mathrm{1}-{\beta }_{i{r}^{*}}\right)$ is also Boolean. A big-M linearization technology^[29] was used to deal with the product term. Given a variable $e$ and a boolean $b$, then $\neg b\to e\le \mathrm{0}$ can be expressed using the linear constraint $e\le Mb$ ($M$ is an arbitrarily large possible value).

For ${\delta }_{i{r}^{*}}\le \delta \left(\mathrm{1}-{\beta }_{i{r}^{*}}\right)$, it has $\neg {\beta }_{i{r}^{*}}\to {\delta }_{i{r}^{*}}-\delta \le \mathrm{0}$ and $\neg (\mathrm{1}-{\beta }_{i{r}^{*}})\to {\delta }_{i{r}^{*}}\le \mathrm{0}.$ Then ${\delta }_{i{r}^{*}}-\delta \le M{\beta }_{i{r}^{*}}$ and ${\delta }_{i{r}^{*}}\le M(\mathrm{1}-{\beta }_{i{r}^{*}})$. It yields:

${\delta }_{i{r}^{*}}\le \delta +M{\beta }_{i{r}^{*}},{\delta }_{i{r}^{*}}\le M(\mathrm{1}-{\beta }_{i{r}^{*}})$

For ${\delta }_{i{r}^{\mathrm{*}}}\ge \delta \left(\mathrm{1}-{\beta }_{i{r}^{\mathrm{*}}}\right)\Rightarrow -{\delta }_{i{r}^{*}}\le -\delta \left(\mathrm{1}-{\beta }_{i{r}^{*}}\right)$, it has: $\neg {\beta }_{i{r}^{*}}\to -{\delta }_{i{r}^{*}}+\delta \le \mathrm{0}$ and $\neg \left(\mathrm{1}-{\beta }_{i{r}^{*}}\right)\to -{\delta }_{i{r}^{*}}\le \mathrm{0}.$ Then $-{\delta }_{i{r}^{*}}+\delta \le M{\beta }_{i{r}^{*}}$ and $-{\delta }_{i{r}^{*}}\le M(\mathrm{1}-{\beta }_{i{r}^{*}})$. It yields:

${\delta }_{i{r}^{*}}\ge \delta -M{\beta }_{i{r}^{*}},{\delta }_{i{r}^{*}}\ge -M(\mathrm{1}-{\beta }_{i{r}^{*}})$

This means that the following linear constraints are valid for the variable ${\delta }_{i{r}^{*}}$:

$-M\cdot (\mathrm{1}-{\beta }_{i{r}^{*}})\le {\delta }_{i{r}^{*}}\le M\cdot (\mathrm{1}-{\beta }_{i{r}^{*}}),\mathrm{1}\le i\le n$(9)

$\delta -M\cdot {\beta }_{i{r}^{*}}\le {\delta }_{i{r}^{*}}\le \delta +M\cdot {\beta }_{i{r}^{*}},\mathrm{1}\le i\le n$(10)

As a minimization problem, the distance between each pair of facilities $d_{ij}=|x_i-x_j|$ can be written as: $d_{ij}\ge x_i-x_j$ and $d_{ij}\ge x_j-x_i$. When $x_i$ and $x_j$ are substituted by Eq. (8), we have:

$\begin{array}{l}{d}_{ij}\ge \left({\delta }_{i{r}^{*}}+\frac{l_i}{\mathrm{2}}+{\displaystyle \sum _{k=\mathrm{1},k\ne i}^n}{l}_k{\alpha }_{ki}\right)-\left({\delta }_{j{r}^{*}}+\frac{l_j}{\mathrm{2}}+{\displaystyle \sum _{k=\mathrm{1},k\ne j}^n}{l}_k{\alpha }_{kj}\right),\\ \mathrm{1}\le i<j\le n\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\end{array}$(11)

$\begin{array}{l}{d}_{ij}\ge \left({\delta }_{j{r}^{*}}+\frac{l_j}{\mathrm{2}}+{\displaystyle \sum _{k=\mathrm{1},k\ne j}^n}{l}_k{\alpha }_{kj}\right)-\left({\delta }_{i{r}^{*}}+\frac{l_i}{\mathrm{2}}+{\displaystyle \sum _{k=\mathrm{1},k\ne i}^n}{l}_k{\alpha }_{ki}\right),\\ \mathrm{1}\le i<j\le n\hspace{1em}\hspace{1em}\hspace{1em}\end{array}$(12)

If facilities $i$ and $j$ are at the same row, the distance $d_{ij}$ must be more than $(l_i+l_j)/\mathrm{2}$. This means the following constraint is also valid:

$d_{ij}-\left(\frac{l_i+l_j}{\mathrm{2}}\right){\alpha }_{ij}-\left(\frac{l_i+l_j}{\mathrm{2}}\right){\alpha }_{ji}\ge \mathrm{0,1}\le i\le j\le n$(13)

2.4 Proposed Formulation

The objective of SM-DRLP is to consider the total cost of transporting materials among facilities. It depends on the material flow $c_{ij}$ and the distance $d_{ij}$ between facilities:

${\displaystyle \sum _{i=\mathrm{1}}^{n-\mathrm{1}}}{\displaystyle \sum _{j=i+\mathrm{1}}^n}{c}_{ij}{d}_{ij}$(14)

Our proposed mixed-integer programming formulation for the SM-DRLP is given as: Minimize {(14): (1a), (1b), (3)-(7),(9)-(13)}.

The numbers of binary variables ${\alpha }_{ij}$ and ${\beta }_{i{r}^{*}}$ are $A_n^{\mathrm{2}}=n(n-\mathrm{1})$ and $n$, respectively. Then, the number of binary variables is $n(n-\mathrm{1})+n$. The number of continuous variable $\delta$ is 1. The number of continuous variables $x_i$ is $n$. The number of continuous variables $d_{ij}$ is $C_n^{\mathrm{2}}=n(n-\mathrm{1})/\mathrm{2}$. Then, the number of continuous variablesis $n(n-\mathrm{1})/\mathrm{2}+n+\mathrm{1}$. The number of constraints (1a) and (1b) is$n$.The number of constraints (3) is $C_n^{\mathrm{2}}=n(n-\mathrm{1})/\mathrm{2}$. The number of constraints (4) is $\mathrm{3}{C}_n^{\mathrm{3}}=\mathrm{3}n(n-\mathrm{1})(n-\mathrm{2})/\mathrm{6}$. The number of constraints (5) is 2$C_n^{\mathrm{3}}=\mathrm{2}n(n-\mathrm{1})(n-\mathrm{2})/\mathrm{6}$. The number of constraints (6) is $C_n^{\mathrm{3}}=n(n-\mathrm{1})(n-\mathrm{2})/\mathrm{6}$. The number of constraints (7) is 1.The numbers of constraints (9) and (10) are both $n$. The numbers of constraints (11), (12) and (13) are all $C_n^{\mathrm{2}}=n(n-\mathrm{1})/\mathrm{2}$. Then, the number of constraints (excluding nonnegativity constraints and bounds on variables) is $n\left(n-\mathrm{1}\right)\left(n-\mathrm{2}\right)+\frac{\mathrm{7}n\left(n-\mathrm{1}\right)}{\mathrm{2}}+\mathrm{5}n+\mathrm{2}$.

3 Computational Results and Comparisons

To evaluate the performance of the SM-DRLP, we compared its computational results with those of the following models: the representative model of general DRLP (M-DRLP) proposed by Amaral^[11] and the model of another simplified DRLP (M-CAP) proposed by Amaral^[25]. They were all solved by CPLEX on the same personal computer with Intel core i5-4460 3.20 GHz processor and 8 GB RAM. The computational experiments were conducted on the benchmark instances used in Ref. [11]: four small instances (S9, S9H, S10, S11) introduced by Simmons^[30]; twenty random instances with 9 and 10 facilities and eighteen random instances with $n\in \{\mathrm{11,12,13}\}$ proposed by Amaral.

The computational results are given in Table 2.

In Table 2, the columns "Inst", "$n$" and "Best" stand for the instance name, the number of facilities and the best solution of all models. The gap between the best solution and the solution (Sol) of the corresponding model is reported in column "$G_B$" ($G_B$ = Sol $-$ Best). If the value of $G_B$ is equal to zero, it indicates that CPLEX obtains the best solution for the corresponding model. The larger value of $G_B$, the worse solution of the corresponding model. Column "$t$" shows the computational time in seconds. To show the comparison of computational time more visually, we plot a figure with respect to "$t$", as shown in Fig. 2, where $x$ axis denotes the serial number of instances and $y$ axis indicates the natural logarithm of t.

Fig.2 Comparison of computational time of three models

From Table 2, it can be observed that the M-DRLP is able to obtain the best solutions for all 42 instances, which indicates that the M-DRLP has the best performance in all compared models in terms of the solution quality. However it is the most time consuming one, which is displayed in Fig. 2. Furthermore, its execution time increases more obviously as the number of facilities increases. Although the M-CAP spends the least computational time, it is just able to obtain 8 best solutions of 42 instances (Table 2). Its performance is the worst one in terms of the solution quality. Obtaining 41 best solutions of 42 instances (Table 2), our proposed SM-DRLP exhibits the similar performance to the best one M-DRLP in terms of the solution quality, while SM-DRLP spends much less time than M-DRLP.

4 Conclusion

We have considered a new simplified model for the double row layout problem (SM-DRLP). Different from the general model for the double row layout problem (M-DRLP)^[11], the SM-DRLP does not take adjustable clearances between adjacent facilities into account, which is helpful to reduce the computation time. Different from the model of the corridor allocation problem (M-CAP)^[25], the SM-DRLP takes the start points of double rows into account, which is helpful to maintain the solution quality. A MIP model has also been proposed for our SM-DRLP.

The experiments on 42 instances have been conducted to compare the SM-DRLP with M-DRLP and M-CAP. The SM-DRLP was able to achieve similar solution quality to the M-DRLP in much less computational time. Compared with M-CAP, the SM-DRLP was able to achieve much better solution quality with similar computational time. The results demonstrate the high competitiveness of SM-DRLP. At the same time, it provides an evidence to confirm that the start points seem to be more important than adjustable clearances for solution quality.

Although the SM-DRLP can be solved faster than the M-DRLP by the standard solver CPLEX, it is still time consuming. As further research, we intend to investigate heuristics for solving the SM-DRLP. Furthermore, we will study the MIP for the SM-DRLP considering the explicit minimum clearances.

References

All Tables

All Figures

	Fig.1 Different models for the DRLP
In the text

	Fig.2 Comparison of computational time of three models
In the text