An exact and a heuristic approach for the transportation-p-facility location problem

Abstract

The delineation of the transportation network is a strategic issue for all over the place. The problem of locating new facilities among several existing facilities and minimizing the total transportation cost are the main topics of the location network system. This paper addresses the transportation-p-facility location problem (T-p-FLP) which makes a connection between the facility location problem and the transportation problem, where p corresponds to the number of facilities. The T-p-FLP is a generalization of the classical transportation problem in which we have to seek where and how we impose the p-number of facilities such that the total transportation cost from existing facility sites to the potential facility sites will be minimized. The exact approach, based on the iterative procedure, and a heuristic approach as applied to the T-p-FLP are discussed and corresponding results are compared. An experimental example is incorporated to explore the efficiency and effectiveness of our proposed study in reality. Finally, a summary is given together with suggestions for future studies.

1 Introduction

The facility location problem (FLP) is actually a strategy, where and how to locate the new facilities among several existing facilities in such a way that at least one of the objective functions will be optimized (like cost, profit, travel distance, service, waiting time and market shares). Mainly, the traditional FLP contains three given sets: a set of existing facility sites, a set of potential facility sites and a set of weights related to existing facility sites. In fact, it seeks the best locations for a set of facilities with respect to a set of all existing facility sites. Industries locate assembly plants and warehouses. Stores are located by retail outlets. The efficiency of manufacturing and marketing of products is dependent on the location of facilities. Similarly, the government also takes the decisions about the location of schools, fire stations, hospitals, etc. In any case, good services depend on the location of facilities. The FLP was studied by several researchers. A few of them are depicted here. Interested readers may follow the books of Love et al. (1995) and Farahani and Hekmatfar (2009) to find more about the FLP. In fact, Farahani et al. (2010) made a comprehensive survey of the location problems under multi-criteria environment. Later, the FLP could be applied in a broad area of transportation industries, public facilities, business areas and public health-care such as Bieniek (2015), Chen et al. (2016), Dias et al. (2008), Gadegaard et al. (2016), Kim and Kim (2013), Klose and Kurt (2016) and Tokgöz et al. (2015).

In the real world, the network system provides a useful way for communications, logistics as well as electronic systems. The well-known network problem, the transportation problem (TP), is a special kind of linear programming problem which asks for the minimum cost to transport goods from a set of sources to a set of destinations. The classical TP consists of two sets: a set of all sources, a set of all demand points, and a single objective function as transportation cost. The amounts available at sources and demands at destination points are called supply and demand. Here, transportation cost is directly proportional to the amount of units to be transported. The TP was the first introduced by Hitchcock (1941); then Koopmans (1949) studied on optimum utilization of the transportation system. So many researchers have studied on the TP in several environments. Some research works could be annexed like Roy (2016); Roy et al. (2017a, b), Mahapatra et al. (2013), Roy (2015) and Maity et al. (2016).

In the present decade, the FLP and TP are a “hot topic” in supply chain management as well as the transportation planning system. Determining the best locations for the facilities (i.e., plants, depots, warehouses, offices, fire stations, railway stations, etc.) and minimizing the total transportation cost from existing sites to facilities can significantly affect the transportation planning system. Melo et al. (2009) depicted a review of the FLP and supply chain management. Cooper (1964) first introduced the location-allocation problem and he also discussed a heuristic approach to solve the problem. Afterwards, several researchers made connections between the FLP and distribution system in many different ways such as Das et al. (2019), Dohse (1996), Klibi et al. (2010), Loaiza et al. (2017), Mis̆ković et al. (2016), and Sherali and Tuncbilek (1992).

In this paper, the main aim is to introduce a way to connect the FLP and TP. We generalize the concept of TP by taking the sources as existing facility sites and demand points as potential facility sites which are to be determined. In fact, the T-p-FLP is a cost minimization problem obtained by integrating the FLP and TP. Thereafter, the T-p-FLP can be solved in a continuous planner surfaces with Euclidean distance. We determine the best location of a facility and the effective transportation cost from sources to this facility locations simultaneously by solving the T-p-FLP. Our formulation can be applied to plant location problems where minimizing transportation cost is the main priority. We believe that this model is more reasonable than the classical TP and FLP approach. The proposed formulation will be useful for the models of transportation systems, emergency services and online-shopping systems.

The rest of this paper is catalogued as follows: In Sect. 2, the T-p-FLP model formulation, the connection between the T-p-FLP and TP and its characteristics are discussed. The solution methodology of the exact approach with its algorithm and an algorithm of Loc-Alloc heuristic are described in Sect. 3. Thereafter, the scenario is illustrated by an example in closer detail, and two approaches are used to evaluate the results in Sect. 4. In Sect. 5, computational results are given and compared. Finally, conclusions and directions for future research work of the paper are placed at last.

2 Mathematical identification

In this section, we first incorporate the proposed problem. Thereafter, the mathematical formulation is stated on the basis of the following notations and assumptions. The model formulation, a connection between this formulation and the TP, and the structural properties are presented.

2.1 Problem description

Herein, a logistical problem is inspected from an economical point of view. Our proposed problem deals with a transportation network, which consists of multiple existing sites or sources, potential facility sites or demand points, and products are transported from existing sites to potential facility sites. The main aim is to minimize the total transportation cost of locating the potential facility sites simultaneously. For example, there are three existing facility sites and four potential facility sites. The corresponding supply and demand of the existing facility sites and the potential facility sites are given. Furthermore, the locations of existing sites are known. But, the locations of potential facility sites are not given on the planner surface (Euclidean plane). In this situation, the decision maker has to seek the optimal locations for the potential facility sites in such a way that the total transportation cost from existing facility sites to potential facility sites will be minimized.

2.2 Notations and assumptions

The notations are as follows:

m::

number of existing facility sites (origins).

p::

number of potential facility sites (demand points).

$\alpha _{i}$::

non-negative weights of existing facility sites $(i=1,2,\ldots ,m)$.

$a_i$::

availability at the i-th existing facility site $(i=1,2,\ldots ,m)$.

$b_j$::

demand at the j-th potential facility site $(j=1,2,\ldots ,p)$.

$(c_{i},d_{i})$::

coordinates of i-th existing facility sites $(i=1,2,\ldots ,m)$.

$(x_{j},y_{j})$::

coordinates of j-th potential facility sites $(j=1,2,\ldots ,p)$.

$u_{ij}$::

amounts of flow to be transported from the i-th existing facility site to the j-th potential facility site $(i=1,2,\ldots ,m;~j=1,2,\ldots ,p)$.

F::

$\{(u_{ij}):u_{ij}~\text{ subject } \text{ to } \text{ the } \text{ constraints }\}$: the feasible set with respect to the matrix variable u.

$U_B$::

$(u_{ij}^B:i=1,2,\ldots m;~j=1,2,\ldots , p)$: the initial basic feasible solution.

$\phi$::

transportation cost function per unit commodity from an existing facility site to a potential facility site.

There are the following assumptions:

• The solution space is continuous. The space in which potential facility sites are located is the planner. Potential facility sites are assumed as points. Parameters are deterministic.

• Facilities are capacitated. No relationship between potential facility sites. We ignore the opening cost of new potential facility sites.

• The objective function is to be minimized. The type of distance is the usual Euclidean distance in 2-dimensional space $(\phi (c_{i},d_{i};x_{j},y_{j})=[{(c_{i}-x_{j})^{2}+(d_{i}-y_{j})^{2}}]^{1/2})$.

2.3 Model formulation

Here, we introduce a formulation based on the classical FLP and TP. However, instead of minimizing the total transportation cost, this model finds optimal locations by determining the potential facility sites. We consider the mathematical model of the T-p-FLP as follows:

Model 1

$$\begin{aligned}&\text{ minimize }_{(x,y,u)}\qquad Z=\sum _{i=1}^{m}\sum _{j=1}^{p}\alpha _{i}u_{ij} \phi (c_{i},d_{i};x_{j},y_{j}) \end{aligned}$$

(2.1)

$$\begin{aligned}&\text{ subject } \text{ to }\qquad \sum _{j=1}^{p}u_{ij}\le a_i \quad (i=1,2,\ldots , m), \end{aligned}$$

(2.2)

$$\begin{aligned}&\sum _{i=1}^{m}u_{ij}\ge b_j \quad ( j=1,2,\ldots , p), \end{aligned}$$

(2.3)

$$\begin{aligned}&u_{ij} \ge 0 \quad \forall \,i \text{ and }\, j. \end{aligned}$$

(2.4)

The objective (2.1) aims to minimize the total transportation cost from existing facility sites to potential facility sites. Constraint (2.2) enforces that the total flow from each existing facility site cannot exceed its amount available. Constraint (2.3) imposes that the total flow to each potential facility site should satisfy its demand. Constraint (2.4) consists of non-negativity conditions.

2.4 Connection between the T-p-FLP and TP

The objective function (2.1) of the Model 1 depends on the locations of potential facility sites. If we fix the locations of potential facility sites, then the set of cost functions converts into the set of constant cost functions. Subsequently, in view of objective function (2.1) we use the short notation $\phi (c_{i},d_{i};x_{j},y_{j})=s_{ij}$ (constant cost functions), now $\alpha _{i}s_{ij}$ is chosen as $t_{ij}$ (unit transportation cost from sources to demand points). Hence, the objective function of Model 1 is reduced; the following Model 2 looks as:

Model 2

$$\begin{aligned}&\text{ minimize }_{(u)}\qquad Z =\sum _{i=1}^{m}\sum _{j=1}^{p}t_{ij}u_{ij}\nonumber \\&\text{ subject } \text{ to }\qquad \text{ the } \text{ constraints }\,(2.2) \ \hbox {to}\,(2.4); \end{aligned}$$

(2.5)

this is the classical form of a TP. Hence, for constant cost function the T-p-FLP becomes the TP.

2.5 Structural properties

In this subsection, we discuss some fundamental propositions and a theorem to recognize the nature of the T-p-FLP.

Proposition 1

A necessary and sufficient condition for a feasible solution of the problem T-p-FLP is that $\sum _{i=1}^{m}a_i\ge \sum _{j=1}^{p}b_j$.

Proof

This property is called the feasibility condition. It depends on the constraints. In fact, both the problems, i.e., Model 1 and 2 have the same constraints. Moreover, the proof is given in Hitchcock (1941) for the case of a TP. $\square$

Proposition 2

The feasible solution of the T-p-FLP is never unbounded.

Proof

The constraints of the T-p-FLP are as follows:

$$\begin{aligned}&\sum _{j=1}^{p}u_{ij}\le a_i \quad (i=1,2,\ldots , m), \\&\sum _{i=1}^{m}u_{ij}\ge b_j \quad ( j=1,2,\ldots , p),\\&u_{ij} \ge 0 \quad \forall \, i \,\,\text{ and } \, j. \end{aligned}$$

So, $b_{j} \le u_{ij}\le a_{i}\ \forall \,i$ and j, and also $u_{ij} \ge 0~\forall ~i$ and j. We conclude that $\min \{0,b_{j}\}\le u_{ij}\le a_{i}~\forall \,i \text{ and }~j$. As $b_{j}>0 ~\forall j$, now $\min \{0,b_{j}\}=0$ and $0\le u_{ij}\le a_i$. This completes the proof of the proposition. $\square$

Proposition 3

The number of basic variables in the T-p-FLP is at most $(m+p-1)$.

Proof

This property is also dependent on the constraints. Here, we see that the constraints of two the problems, i.e., Model 1 and 2 are the same. So, this proposition is also the same as the TP. $\square$

Proposition 4

For the problem $\text{ minimize }_{(x,y,u)}~Z =\sum _{i=1}^{m} \sum _{j=1}^{p}\alpha _{i}u_{ij}\phi (c_{i},d_{i};x_{j},y_{j}),~(u_{ij})\in F$, an optimal solution exists at an extreme point of the convex set F of feasible solutions to the T-p-FLP.

Proof

Let $(x,y)=(x_j,y_j)~(j=1,2,\ldots ,p), ~u=(u_{ij}:~i=1,2,\ldots , m;~j=1,2,\ldots , p)$ and $u_E\in \{(u_{ij}^E) ~(i=1,2,\ldots , m;~j=1,2,\ldots , p):\text{ extreme } \text{ points } \text{ of }~F\}$. If we choose the destination such that $(x,y)=(x_{j}^*,y_{j}^*)$ by seeking the optimal location, then the objective function to minimize is $Z=\sum _{i=1}^{m}\sum _{j=1}^{p}\alpha _{i}u_{ij}\phi (c_{i}, d_{i};x_{j}^*,y_{j}^*),~(u_{ij})\in F$, which is a classical TP. Then it always has a solution at an extreme point $u_{E} \in F$. Thus, we conclude that $(x^*,y^*,u_E)$ is an optimal solution at an extreme point of F to the T-p-FLP. $\square$

Proposition 5

The number of basic feasible solutions of a T-p-FLP is at most ${mp}\atopwithdelims (){m+p-1}$.

Proof

The T-p-FLP has mp variables and at most $m+p-1$ basic variables. Hence, the number of basic feasible solutions of the T-p-FLP is at most ${mp}\atopwithdelims (){m+p-1}$. The proof is left to the reader. $\square$

Theorem 1

The objective function $Z=\sum _{i=1}^{m}\sum _{j=1}^{p} \alpha _{i}u_{ij}^B\phi (c_{i},d_{i};x_{j},y_{j})$ is a convex function in the joint variable (x, y) on ${\mathbb {R}}^{2p}$.

Proof

We know that a function Z is convex over the region iff the Hessian matrix associated with Z is positive semidefinite over the region (Rockafellar 1970). Let $Z=\sum _{j=1}^{p}Z_j$, where $Z_j=\sum _{i=1}^{m}\alpha _{i}u_{ij}^B\phi (c_{i},d_{i};x_{j},y_{j})$ and the terms $u_{ij}^B$ are constants. Here, $Z_j$ only depends on the variables $x_j$ and $y_j$. Hence we can consider $Z_j$ to be a function in two variables $x_j$ and $y_j$. The Hessian matrix for $Z_j$ at $(x_j,y_j)$ is

$$\begin{aligned} H_j= \left( \begin{array}{ccc} \frac{\partial ^2Z_j}{\partial x_j^2} &{} \frac{\partial ^2Z_j}{\partial x_j\partial y_j} \\ \frac{\partial ^2Z_j}{\partial y_j\partial x_j} &{} \frac{\partial ^2Z_j}{\partial y_j^2} \end{array} \right) . \end{aligned}$$

The principal minors of $H_j$ are $\frac{\partial ^2Z_j}{\partial x_j^2}$ and $\det H_j$ (determinant of $H_j$).

$$\begin{aligned} \frac{\partial ^2Z_j}{\partial x_j^2} =\sum _{i=1}^{m} \frac{\alpha _iu_{ij}^B(d_i-y_j)^2}{[(c_i-x_j)^2 +(d_i-y_j)^2]^{3/2}}, \end{aligned}$$

and

$$\begin{aligned}&\det H_j=\frac{\partial ^2Z_j}{\partial x_j^2}\frac{\partial ^2Z_j}{\partial y_j^2} -\Big (\frac{\partial ^2Z_j}{\partial x_j\partial y_j}\Big )^2 \quad \Big (\text{ since } \frac{\partial ^2Z_j}{\partial x_j\partial y_j} =\frac{\partial ^2Z_j}{\partial y_j\partial x_j}\Big )\\&\quad =\left( \sum _{i=1}^{m}\frac{\alpha _iu_{ij}^B(d_i-y_j)^2}{[(c_i-x_j)^2 +(d_i-y_j)^2]^{3/2}}\right) \left( \sum _{i=1}^{m}\frac{\alpha _iu_{ij}^B (c_i-x_j)^2}{[(c_i-x_j)^2+(d_i-y_j)^2]^{3/2}}\right) \\&\qquad -\left( \sum _{i=1}^{m} \frac{\alpha _iu_{ij}^B(c_i-x_j)(d_i-y_j)}{[(c_i-x_j)^2+(d_i-y_j)^2]^{3/2}}\right) ^2\\&\quad =\left( \sum _{i=1}^{m}\big (\frac{\sqrt{\alpha _iu_{ij}^B}(d_i-y_j)}{[(c_i-x_j)^2 +(d_i-y_j)^2]^{3/4}}\big )^2\right) \left( \sum _{i=1}^{m}\big (\frac{\sqrt{\alpha _iu_{ij}^B} (c_i-x_j)}{[(c_i-x_j)^2+(d_i-y_j)^2]^{3/4}}\big )^2\right) \\&\qquad -\left( \sum _{i=1}^{m}\frac{\sqrt{\alpha _iu_{ij}^B}(d_i-y_j)}{[(c_i-x_j)^2 +(d_i-y_j)^2]^{3/4}}\frac{\sqrt{\alpha _iu_{ij}^B}(c_i-x_j)}{[(c_i-x_j)^2 +(d_i-y_j)^2]^{3/4}}\right) ^2. \end{aligned}$$

Now, $\big (\sum _{i=1}^{m}(\frac{\sqrt{\alpha _iu_{ij}^B} (d_i-y_j)}{[(c_i-x_j)^2+(d_i-y_j)^2]^{3/4}})^2\big ) \big (\sum _{i=1}^{m}(\frac{\sqrt{\alpha _iu_{ij}^B} (c_i-x_j)}{[(c_i-x_j)^2+(d_i-y_j)^2]^{3/4}})^2\big ) \ge \big (\sum _{i=1}^{m}\frac{\sqrt{\alpha _iu_{ij}^B} (d_i-y_j)}{[(c_i-x_j)^2+(d_i-y_j)^2]^{3/4}} \frac{\sqrt{\alpha _iu_{ij}^B}(c_i-x_j)}{[(c_i-x_j)^2 +(d_i-y_j)^2]^{3/4}}\big )^2~(\text{ by } \text{ Cauchy--Schwarz } \text{ inequality })$. As $\alpha _i>0, u_{ij}^B\ge 0, (c_i-x_j)^2\ge 0 ~\text{ and }~(d_i-y_j)^2\ge 0$, we conclude that $\frac{\partial ^2Z_j}{\partial x_j^2}\ge 0$ and $\det H_j\ge 0$ for all values of $x_j,y_j$. Hence, $Z_j$ is convex with respect to $x_j$ and $y_j$. Let $\big ((x_1,y_1),(x_2,y_2),\ldots ,(x_p,y_p) \big )$ and $\big ((x_1^\prime ,y_1^\prime ),(x_2^\prime ,y_2^\prime ), \ldots ,(x_p^\prime ,y_p^\prime )\big )$ be two arbitrary points of ${\mathbb {R}}^{2p}$, and $t^{\prime }\in [0,1]$.

Herewith,

$$\begin{aligned}&Z\Big (t^{\prime }\big ((x_1,y_1),(x_2,y_2),\ldots ,(x_p,y_p)\big )+(1-t^{\prime }) \big ((x_1^\prime ,y_1^\prime ),(x_2^\prime ,y_2^\prime ), \ldots ,(x_p^\prime ,y_p^\prime )\big )\Big )\\&\quad =\sum _{j=1}^{p}Z_j\Big (t^{\prime }\big ((x_1,y_1),(x_2,y_2), \ldots ,(x_p,y_p)\big )+(1-t^{\prime })\big ((x_1^\prime ,y_1^\prime ), (x_2^\prime ,y_2^\prime ),\ldots ,(x_p^\prime ,y_p^\prime )\big )\Big )\\&\quad \le t^{\prime }\sum _{j=1}^{p}Z_j\big ((x_1,y_1),(x_2,y_2), \ldots ,(x_p,y_p)\big )+(1-t^{\prime })\sum _{j=1}^{p}Z_j\big ((x_1^\prime ,y_1^\prime ), (x_2^\prime ,y_2^\prime ),\ldots ,(x_p^\prime ,y_p^\prime )\big )\\&\quad = t^{\prime }Z\big ((x_1,y_1),(x_2,y_2),\ldots ,(x_p,y_p)\big )+(1-t^{\prime })Z \big ((x_1^\prime ,y_1^\prime ),(x_2^\prime ,y_2^\prime ),\ldots , (x_p^\prime ,y_p^\prime )\big ). \end{aligned}$$

Therefore, Z is convex in the variable (x, y) on ${\mathbb {R}}^{2p}$. $\square$

3 Solution methodology

In this section, we first briefly describe an exact method with its algorithm, and then present a heuristic algorithm for solving our model.

3.1 Exact approach

The iterative procedure is an exact and simple solution procedure in which we find the best nearest optimal locations. We see that the objective function has a minimum value at an extreme point of the convex set F and the number of basic feasible solutions in F are finite (by Theorem 1 and Propositions 4 and 5). First, we find all basic feasible solutions in F by solving the constraints of the T-p-FLP. Then we observe that these constraints are the same as the constraints of the classical TP. Therefore, we apply the Northwest-Corner method (Hadley 1962) to generate the initial basic feasible solutions which are $U_B=(u_{ij}^B:i=1,2,\ldots , m;~j=1,2,\ldots , p)$; then for each such solution, we solve the problem.

$$\begin{aligned}&\text{ minimize }_{(x,y)}\qquad Z^B=\sum _{i=1}^{m}\sum _{j=1}^{p} \alpha _iu_{ij}^B\sqrt{(c_i-x_j)^2+(d_i-y_j)^2}\\&\text{ subject } \text{ to }\qquad \text{ the } \text{ constraints }\, (2.2) \ \hbox {to}\, (2.4). \end{aligned}$$

Now we can write the problem as

$$\begin{aligned}&\text{ minimize }_{(x,y)}\qquad Z^B=\sum _{j=1}^{p}Z_j^B\\&\text{ subject } \text{ to }\qquad \text{ the } \text{ constraints }\, (2.2) \ \hbox {to}\, (2.4), \end{aligned}$$

where $Z_j^B=\sum _{i=1}^{m}\alpha _iu_{ij}^B\sqrt{(c_i-x_j)^2 +(d_i-y_j)^2}~~( j=1,2,\ldots , p)$. Then, we minimize $Z_j^B(j=1,2,\ldots , p)$ for minimizing $Z^B$. We use the iterative formulas (A.8) to (A.11) (see Appendix A) to minimize the function $Z_j^B$. Let $S=\{Z_n^*:\text{ the } \text{ optimum } \text{ value } \text{ for }~ Z^B~ \text{ for }~ n\text{-th } \text{ basic } \text{ feasible } \text{ solutions }\}$. Clearly, S is a finite set from Proposition 5. Hence, it has a minimum, then the optimal value of the objective function $Z^*$ for the T-p-FLP will be $Z^*=\min S$. If the optimum has been attained at $n=l$, then the best nearest optimal solutions are $(x_{j}^l,y_{j}^l),~(j=1,2,\ldots , p),~\text{ and } ~u_{ijl}^B ~(i=1,2,\ldots , m; j=1,2,\ldots , p)$, where $(x_{j}^l,y_{j}^l)$ indicates $(x_j,y_j)$ for the l-th basic feasible solution and $u_{ij_l}^B$ are the values of $u_{ij}^B$ for this solution.

3.2 An exact algorithm

Here, we describe an algorithm for solving the T-p-FLP. The following steps are appraised for selection of optimal potential facility sites in the T-p-FLP as:

Step 1 First, we solve the constraints using the Northwest-Corner method to evaluate the initial basic feasible solutions.

Step 2 We address each such l-th basic feasible solution as $u_{ij_l}^B$. Based on each such solution, we consider a set of problems as indicated below:

$$\begin{aligned}&\text{ minimize }_{(x,y)}\qquad Z_l^B=\sum _{j=1}^{p}Z_{j_l}^B\\&\text{ subject } \text{ to }\qquad \text{ the } \text{ constraints }\, (2.2) \, \hbox {to}\, (2.4), \end{aligned}$$

where $Z_{j_l}^B=\sum _{i=1}^{m}\alpha _iu_{ij_l}^B \sqrt{(c_i-x_j)^2+(d_i-y_j)^2}~~~~( j=1,2,\ldots , p)$.

Step 3 We solve the set of problems in Step 2 by using the iterations Eqs. (A.8) to (A.11).

Step 4 After a finite number of iterations, we observe that when the coordinates of some existing facility sites are equal to the potential facility sites, then the denominator of the iteration in Step 3 becomes 0. In that case, we cannot move to the next iteration. As our aim is to seek the best nearest location of the existing facility sites, we take this result as an optimal location and terminate the loop.

Step 5 Repeat Steps 3 and 4 until no further changes are possible in correct up to 4 decimal places.

Step 6 We choose optimal solutions are $(x_{j}^l,y_{j}^l)~ \text{ and }~Z^*=\min S$.

Step 7 Stop.

3.3 A Loc-Alloc heuristic algorithm

The locate-allocate (Loc-Alloc) heuristic algorithm was first introduced to solve the large-scale traditional location problems by Cooper (1964), which provides always a good solution (sub-optimal) within a relatively short computational time. We moderate it to solve the T-p-FLP. The steps of the Loc-Alloc heuristic algorithm are as follows:

Step 1 First, we choose the initial locations for the p-facilities from m-existing locations.

Step 2 Therefore, two cases arise: If $p\le m$, then we can easily find the distances between the existing and the potential facility sites. But, if $p>m$, then we cannot find all the distances. So, in that case, we assign a positive number for each distance to less calculation burden.

Step 3 Without loss of generality, we assume that the distances are proportional to the cost functions. So, we take these distances as the cost coefficients $t_{ij}$ [in Eq. (2.5)]. Then, it is converted to the classical TP.

Step 4 Using the LINGO optimization tool we easily find the set of initial basic feasible solutions $U_B$.

Step 5 Employing $U_B$ from Step 4 and the iteration from Eqs. (A.8) to (A.11), we solve the T-p-FLP to generate a new set of potential locations.

Step 6 If any of the locations have changed correct up to 4 decimal places, then repeat Step 5; otherwise, stop.

4 Experimental analysis

In this section, we incorporate a real-life based experiment to illustrate our model and to work out that our procedures are effective to locate the potential facility sites in the Euclidean plane with the objective to minimize the total transportation cost. A reckoned company wishes to establish some new wings in such a way that the total transportation cost from the existing plants is minimized. The company has four plants $S_1$, $S_2$, $S_3$ and $S_4$, and the company want to set-up three new wings (plants) $D_1$, $D_2$ and $D_3$. The capacities of supply at $S_1$, $S_2$, $S_3$ and $S_4$, the requirement to the wings $D_1$, $D_2$ and $D_3$, the position and the weights of the plants $S_1$, $S_2$, $S_3$ and $S_4$ are also known. The supplied data of the problem are given in Tables 1 and 2.

Table 1 The capacities of supply and demand of the plants

Table 2 The positions and weights of the existing plants

We code the approaches in C++ and execute it using a code-block compiler on a Lenovo z580 computer with 2.50 GHz Intel (R) Core (TM) i5-3210M CPU and 4 GB RAM. We set up the same configuration as above, and compared its performance with our Loc-Alloc heuristic. In contrast, we compare the results obtained from Linux terminal on a computer with Intel(R) Core (TM) i3-4130 CPU @3.40 GHz and 4 GB RAM.

4.1 Performance of the exact approach

Here, we mainly concentrate on the following topics:

• First, we find the possible initial Basic Feasible Solutions (BFSs) by the Northwest-Corner method.

• To fix the optimum position of $D_1$, $D_2$ and $D_3$ for minimizing transportation cost and maximizing the profit.

Now, we use the Northwest-Corner method by utilizing Table 1 and get the possible initial BFS sets. They are placed in Tables 3, 4 and 5.

Table 3 The possible BFS set 1

Table 4 The possible BFS set 2

Table 5 The possible BFS set 3

The computational results for Tables 3, 4 and 5 using the C++ programming language are shown in Table 6.

Table 6 Computational results for Tables 3, 4 and 5

4.2 Performance of the Loc-Alloc heuristic

For solving the T-p-FLP by the Loc-Alloc heuristic, we focus on the following:

• First, we choose three initial locations for each of the 3 wings from Table 2. Then, 4 possible cases have arisen and they are displayed in Tables 7, 8, 9 and 10.

Table 7 1st case

Table 8 2nd case

Table 9 3rd case

Table 10 4th case

• Now, we calculate the distances between existing plants and initial locations of wings by using Tables 7, 8, 9 and 10. We put the distances as cost coefficients in Tables 11, 12, 13 and 14, respectively.

Table 11 Cost coefficients for Table 7

Table 12 Cost coefficients for Table 8

Table 13 Cost coefficients for Table 9

Table 14 Cost coefficients for Table 10

• We use the LINGO optimization tool for initial BFSs by utilizing Tables 11, 12, 13 and 14, and the obtained results are shown in Tables 15, 16, 17 and 18, respectively.

Table 15 Initial BFS for Table 7

Table 16 Initial BFS for Table 8

Table 17 Initial BFS for Table 9

Table 18 Initial BFS for Table 10

• Finally, the computational results for Tables 15, 16, 17 and 18 using C++ programming language are placed in Table 19.

Table 19 Computational results for Tables 15, 16, 17 and 18

5 Computational results and discussion

Here, first, we present the optimal solutions of the experimental study, obtained by two approaches. Second, we compare the performances of the proposed solution procedures for the T-p-FLP, based on our experiment analysis.

Exact approach We obtain the following nearest optimal solution by our iterative procedure, utilizing Table 6, as shown in Table 20. The convergence performance of the iterative procedure is delineated in Fig. 1.

Table 20 The optimal solution of the proposed T-p-FLP

Fig. 1

Performance of the exact approach

Loc-Alloc heuristic We derive the sub-optimal solution by the Loc-Alloc heuristic, employing Table 19, which is displayed in Table 21. Figure 2 shows the convergence performance of the heuristic.

Table 21 The sub-optimal solution of the proposed T-p-FLP

Fig. 2

Performance of the Loc-Alloc heuristic

5.1 Comparison of the obtained results

Here, we confront the computational results obtained by our two approaches. From Tables 20 and 21, the following conclusions are made and offered to further consideration and research.

• No difference exists between solutions (correct up to 4 decimal places).

• When we consider correct up to 6 decimal places, then the solution of the Loc-Alloc heuristic is slightly sub-optimal, compared to the exact solution which is depicted in Fig. 3.

Fig. 3

Comparison between the obtained results

6 Conclusions and future works

This study has introduced a practical problem for the transportation network that aims to minimize the total transportation cost along the entire supply chain and to select potential facility sites for different plants. In fact, we have provided a way of analyzing the connection between the FLP and TP. Thereafter, some fundamental propositions and a theorem on the T-p-FLP have been introduced to investigate the nature of the T-p-FLP. In addition to the aforementioned achievements, the development of novel versions of two approaches is analyzed to solve the proposed problem in an efficient manner. The studied model and developed procedures have been tested by a real-life based example. Finally, the obtained computational results from our two approaches have been compared with suggestions for selecting the potential facility sites. In comparison, the iterative approach is more appropriate to solve the T-p-FLP with small sizes, for which it is possible to generate better solutions with a reasonable timeframe. The Loc-Alloc heuristic is more suitable for the T-p-FLP of larger size since it can generate comparable solutions in less computational time. In fact, the formulation presented here can be employed in large-scale industrial applications such as the manufacturing of plants, transportation systems, emergency services, and online-shopping systems.

Several research directions remain open, so that scientists can initiate the problem treatment by alternative methodologies such as Lagrangian relaxation heuristic, genetic algorithm, branching method, greedy algorithm, etc. Moreover, they can use different distance functions (or, cost functions) like rectangular distance, block distance, signed distance, Hausdorff distance, etc. One may consider uncertain environments such as intuitionistic fuzzy, rough set and grey numbers within the frame of our proposed model. Finally, in our future study, we will focus on flourishing the T-p-FLP in the light of multi-objective optimization problems and techniques.

Appendix A

Here, we describe the iteration formulas used in the solution methodology section. Now, we refer to

$$\begin{aligned} Z(x,y) = \sum _{i=1}^{m}\sum _{j=1}^{p} \alpha _{i}u_{ij}^B\phi (c_{i},d_{i};x_{j},y_{j}), \end{aligned}$$

where $\phi (c_{i},d_{i};x_{j},y_{j}) =[{(c_{i}-x_{j})^{2}+(d_{i}-y_{j})^{2}}]^{1/2}$ and the terms $u_{ij}^B$ are constants. Differentiating Z with respect to $(x_j,y_j)$ and equating with 0, we get

$$\begin{aligned}&\sum _{i=1}^{m}\frac{\alpha _iu_{ij}^B(c_i-x_j)}{\phi (c_{i}, d_{i};x_{j},y_{j})}=0 \quad ( j=1,2,\ldots , p), \end{aligned}$$

(A.6)

$$\begin{aligned}&\sum _{i=1}^{m}\frac{\alpha _iu_{ij}^B(d_i-y_j)}{\phi (c_{i}, d_{i};x_{j},y_{j})}=0 \quad ( j=1,2,\ldots , p). \end{aligned}$$

(A.7)

Now, from Eqs. (A.6)–(A.7) we obtain

$$\begin{aligned}&\sum _{i=1}^{m}\frac{\alpha _iu_{ij}^Bc_i}{\phi (c_{i},d_{i};x_{j},y_{j})} -x_j\sum _{i=1}^{m}\frac{\alpha _iu_{ij}^B}{\phi (c_{i},d_{i};x_{j},y_{j})} =0 \quad ( j=1,2,\ldots , p), \\&\sum _{i=1}^{m}\frac{\alpha _iu_{ij}^Bd_i}{\phi (c_{i},d_{i};x_{j},y_{j})} -y_j\sum _{i=1}^{m}\frac{\alpha _iu_{ij}^B}{\phi (c_{i},d_{i};x_{j},y_{j})} =0 \quad ( j=1,2,\ldots , p). \end{aligned}$$

Then,

$$\begin{aligned}&x_j=\frac{\sum _{i=1}^{m}\frac{\alpha _iu_{ij}^Bc_i}{\phi (c_{i}, d_{i};x_{j},y_{j})}}{\sum _{i=1}^{m}\frac{\alpha _iu_{ij}^B}{\phi (c_{i},d_{i};x_{j},y_{j})}} \quad ( j=1,2,\ldots , p), \\&y_j=\frac{\sum _{i=1}^{m}\frac{\alpha _iu_{ij}^Bd_i}{\phi (c_{i}, d_{i};x_{j},y_{j})}}{\sum _{i=1}^{m}\frac{\alpha _iu_{ij}^B}{\phi (c_{i},d_{i};x_{j},y_{j})}} \quad ( j=1,2,\ldots , p). \end{aligned}$$

These equations are solved iteratively. The iteration equations for $(x_j,y_j)$ are as follows:

$$\begin{aligned}&x_j^{k+1}=\frac{\sum _{i=1}^{m}\frac{\alpha _iu_{ij}^Bc_i}{\phi (c_{i}, d_{i};x_{j}^k,y_{j}^k)}}{\sum _{i=1}^{m}\frac{\alpha _iu_{ij}^B}{\phi (c_{i},d_{i};x_{j}^k,y_{j}^k)}} \quad ( j=1,2, \ldots ,p;~k\in {\mathbb {N}}), \end{aligned}$$

(A.8)

$$\begin{aligned}&y_j^{k+1}=\frac{\sum _{i=1}^{m}\frac{\alpha _iu_{ij}^Bd_i}{\phi (c_{i},d_{i};x_{j}^k,y_{j}^k)}}{\sum _{i=1}^{m} \frac{\alpha _iu_{ij}^B}{\phi (c_{i},d_{i};x_{j}^k,y_{j}^k)}} \quad ( j=1,2,\ldots ,p;~k\in {\mathbb {N}}), \end{aligned}$$

(A.9)

where $\phi (c_{i},d_{i};x_{j}^k,y_{j}^k) =[{(c_{i}-x_{j}^k)^{2}+(d_{i}-y_{j}^k)^{2}}]^{1/2}$. The initial estimates of $(x_j,y_j)$ are simply chosen by the weighted mean coordinates:

$$\begin{aligned}&x_j^{0}=\frac{\sum _{i=1}^{m}\alpha _iu_{ij}^Bc_i}{\sum _{i=1}^{m} \alpha _iu_{ij}^B} \quad ( j=1,2,\ldots , p), \end{aligned}$$

(A.10)

$$\begin{aligned}&y_j^{0}=\frac{\sum _{i=1}^{m}\alpha _iu_{ij}^Bd_i}{\sum _{i=1}^{m} \alpha _iu_{ij}^B} \quad (j=1,2,\ldots , p). \end{aligned}$$

(A.11)