Keywords

1 Introduction

The uncapacitated facility location problem (UFLP) is the problem of finding the optimal placement of facilities of unrestricted capacities among n potential facility locations such that the cost of satisfying demands of all the customers is minimized [1,2,3,4,5]. Here, the cost is of two types: the service or connection cost to provide service to a customer by a facility and the opening cost to open a facility. UFLP is also known as the Simple Plant Location Problem (SPLP) [1, 6] and the Warehouse Location Problem (WLP) [7]. UFLP is known to be an NP-hard problem [8, 9]. So, different heuristic approaches are used to solve this problem to obtain near-optimal solution. Some of the approaches are branch-and-bound algorithm [10, 11], tabu search [4, 5], constant factor approximation algorithm [12], greedy heuristic [13], neighborhood search [14], hybrid multi-start heuristic [15], semi-Lagrangian relaxation [16], message-passing [17], surrogate semi-Lagrangian dual [18], discrete unconscious search [19], etc.

In this paper, two heuristic algorithms are proposed. We call these two algorithms as the deterministic BFR and the randomized BFR. Here, BFR is the acronym for backward–forward–replacement phase. As the name suggests the first algorithm is deterministic in nature, i.e., it always produces same output for a particular input data set instance. The output of the second algorithm depends on random behavior of some steps. Both the algorithms consist of three phases. These phases are forward phase, backward phase, and replacement phase. The detailed description of these phases is given in Sect. 3. The effectiveness of these two algorithms is tested on UFLP instances of different sizes taken from the literature.

The organization of the rest of the paper is as follows: Sect. 2 formally defines the problem. The proposed algorithms are described in Sect. 3. Computational results are reported and compared in Sect. 4. Finally, Sect. 5 concludes the paper.

2 Problem Definition

The uncapacitated facility location problem (UFLP) [1, 3,4,5] can be stated as follows: A set \(J = \{j_1, j_2, \ldots , j_M\}\) of M customers or cities and a set \(I = \{i_1, i_2, \ldots , i_N\}\) of N potential facility locations (sites) are given. A nonnegative opening cost \(f_i\) associated with each facility location and a nonnegative service or connection cost \(c_{ij}\) between facility i and each customer or city j are also given. The objective of UFLP is to connect each customer or city to the nearest opened facility such that the total cost, i.e., the sum of service or connection cost and opening cost of opened facilities is minimized. It is worthy to note that the demand of any customer is fulfilled by only one facility and hence the capacity of each facility is assumed to be infinite.

Using the above descriptions of variables, the mathematical formulation of UFLP [4] is as follows:

$$ minimize \sum _{i = 1}^{N} \sum _{j = 1}^{M} c_{ij} x_{ij} + \sum _{i = 1}^{N} f_i y_i $$

subject to

$$ \sum _{i = 1}^{N} x_{ij} = 1, ~~~ j = 1, \ldots M, $$
$$ x_{ij} \le y_j, ~~~ i = 1, \ldots N, ~ j = 1, \ldots M, $$
$$ x_{ij}, ~ y_i = \{0, 1\}, ~~~ i = 1, \ldots n, ~ j = 1, \ldots M, $$

where

$$ x_{ij} = \left\{ \begin{array}{lr} 1,~ {\mathrm{\, if \, customer} \,j \in J \, \mathrm{\,is\,\, served\,\, from\,\, site}\, i \in I}\\ 0,~ \text {otherwise;}\\ \end{array} \right. $$
$$y_i = \left\{ \begin{array}{lr} 1,~ {\mathrm{if\, a\, facility \,is \,\,established \,\,at \,\,location}\, i \in I}\\ 0,~ \text {otherwise.}\\ \end{array} \right. $$

3 Proposed Heuristic Algorithms

Each of the proposed algorithms, viz., deterministic BFR and randomized BFR consists of forward phase, backward phase, and replacement phase. So, these phases are described in details in the following Sects. 3.1, 3.2, and 3.3, respectively, before the two proposed heuristic algorithms. Each of these phases takes two data structures, viz., cost matrix and a set of opened facilities as its inputs. Throughout the paper, the cost matrix, the set of opened facilities, and the set of non-opened facilities are denoted by \(\mathcal{C}\), \(\mathcal{F}\) and \({\overline{\mathcal{F}}}\), respectively. The cost matrix \(\mathcal{C}\) is a matrix of order \(N \times (M+1)\) where (i) \(\mathcal{C}(i,j)\) denotes the service cost between the ith facility location to the jth customer, \(1\le i\le N\), \(1\le j\le M\) and (ii) \(\mathcal{C}(i, M+1)\), \(1\le i\le N\) denotes the opening cost of the ith facility.

In the proposed algorithms, a function, named as TotalCost, is used to compute the total cost. This function takes \(\mathcal{C}\) and \(\mathcal{F}\) as its inputs and gives the corresponding total cost. The time complexity of this function is \(\mathcal {O}(N |\mathcal{F}|)\).

3.1 Forward Phase

In this phase, new facilities are opened if and only if the total cost is reduced. The if block from line 4 to 7 of Algorithm 1 is executed only when the existing set of opened facilities, \(\mathcal{F}_e\) is empty. The sum of each row of \(\mathcal{C}\) is computed and then these sums are sorted in line 5 to find the index of each facility. The first facility according to this sorted index is assigned to \(\mathcal{F}_e\) in line 6. So, after the execution of the if block from lines 4 to 7, the cardinality of \(\mathcal{F}_e\) must be at least one. The while loop in line 8 is executed at least once to add a new facility, if possible, in \(\mathcal{F}_e\) and the execution of this loop stops when there is no improvement in terms of total cost by adding a new facility in \(\mathcal{F}_e\). So, this while loop in line 8 may be executed at most \((N - |\mathcal{F}_e|)\)-times. For each \(i \in \overline{\mathcal{F}_e}\), the total cost corresponding to the set \(\mathcal{F}_e~\cup ~\{i\}\) is computed and the ith facility for which the total cost is minimum is opened if the total cost is reduced. The for loop in line 11 is executed \((N - |\mathcal{F}_e|)\)-times. At the end of the while loop in line 27, \(\mathcal{F}_e\) is assigned to the new set of opened facilities, \(\mathcal{F}_n\) in line 28. The pseudocode of forward phase is given in Algorithm 1 and the time required for the execution of each statement is mentioned there.

figure a
figure b

3.2 Backward Phase

In this phase, the facilities are closed from the already opened facilities if and only if the total cost is reduced. The if condition in line 4 of Algorithm 2 checks the cardinality of \(\mathcal{F}_e\). If the set \(\mathcal{F}_e\) is empty or its cardinality is 1 then \(\mathcal{F}_n\) is assigned as \(\mathcal{F}_e\) in line 5 and the algorithm is terminated. If the set \(\mathcal{F}_e\) contains more than one facility then the algorithm performs the following steps to close one facility at a time. The while loop in line 7 may iterate at most \((|\mathcal{F}_e| - 1)\)-times and the execution of this loop stops when there is no improvement in terms of total cost by deleting a facility from \(\mathcal{F}_e\). For each \(i \in \mathcal{F}_e\), the total cost corresponding to the set \(\mathcal{F}_e \backslash \{i\}\) is computed in line 13 and the ith facility for which the total cost is minimum is closed provided that it reduces the total cost. These steps are repeated for closing one facility at a time as long as the total cost is reduced. The for loop in line 10 is iterated \(|\mathcal{F}_e|\)-times. The pseudocode of backward phase is given in Algorithm 2 and the time required for the execution of each statement is mentioned there.

3.3 Replacement Phase

The objective of replacement phase is to check whether it is possible to replace already opened facilities in \(\mathcal{F}_e\) with non-opened facilities in \({\overline{\mathcal{F}}_e}\) to reduce the total cost without changing the number of opened facilities. The algorithm performs the following steps to replace the opened facility j in \(\mathcal{F}_e\) with a non-opened facility i in \({\overline{\mathcal{F}}_e}\). For each \(i \in \overline{\mathcal{F}_e}\), the total cost for each of the sets \((\mathcal{F}_e \backslash \{j\}) \cup \{i\}\) is computed and the ith facility for which the total cost is minimum is opened and the facility j is closed if it improves the total cost. These steps are repeated as long as improvement occurs in terms of the total cost. The pseudocode of replacement phase is given in Algorithm 3 and the time required for the execution of each statement is mentioned there.

figure c

3.4 Deterministic BFR

The deterministic BFR (i.e., Algorithm 4) takes the cost matrix \(\mathcal{C}\) as its input and gives the set of opened facilities \(\mathcal{F}\) and the corresponding total cost as its outputs. Algorithm 4 starts with opening all the facilities as shown in line 2. Then, the following steps are repeated to reduce the total cost. In line 6, the backward phase is used to close some opened facilities (if possible) and this is followed by the replacement phase in line 7 that may replace some opened facilities. Then, the forward phase is used in line 8 to open new facilities (if possible) which is again followed by the replacement phase in line 9. The steps at lines 6 to 9 are repeated as long as the total cost improves.

figure d
figure e

3.5 Randomized BFR

It is likely that the deterministic BFR may stuck into a local optima. The randomized BFR tries to overcome this problem by the help of randomness. The randomized BFR given in Algorithm 5 also takes the cost matrix \(\mathcal{C}\) as its input and gives the set \(\mathcal{F}\) and the corresponding total cost as its outputs. The deterministic BFR is called in line 2 to produce a solution \(\mathcal{F}_1\). In line 3, the solutions \(\mathcal{F}_2\), \(\mathcal{F}_3\), and \(\mathcal{F}_4\) are generated randomly from the solution \(\mathcal{F}_1\) by arbitrarily changing the elements in \(\mathcal{F}_1\) by the elements in \({\overline{\mathcal{F}}}_1\) keeping the cardinality same as \(\mathcal{F}_1\). We now modify each of the solutions \(\mathcal{F}_i\), \(1\le i \le 4\), in the following way. Each opened facility in \(\mathcal{F}_i\) is swapped with a randomly chosen non-opened facility in \({\overline{\mathcal{F}}}_i\) with probability 0.5. If any swapping occurs at all then both the sets \(\mathcal{F}_i\) and \({\overline{\mathcal{F}}}_i\) are modified. At the end of the for loop in line 13, the total cost for each \(\mathcal{F}_i\) is computed in line 14 and the solution with the maximum total cost is replaced by the solution with the minimum total cost of the previous iteration. Here, the variables iterate and count are used to terminate Algorithm 5. The value of count is incremented by one if the minimum total cost for two consecutive iterations remains same, otherwise it is set to zero. Algorithm 5 terminates if the value of either iterate or count exceeds \(max\_iterate\) or \(max\_count\) respectively.

Table 1 Results obtained for OR-library benchmark data (uncapacitated)
Full size table
Table 2 Comparison for OR-library benchmark
Full size table

4 Experimental Results and Discussion

The efficiency of the proposed two algorithms is tested on 15 benchmark instances of Beaslay’s OR-Library [20]. Here, all the benchmark instances and the corresponding optimal costs are taken from UflLib [21]. The proposed algorithms are coded with MATLAB R2013a and all the computations are performed in a machine with Intel Core i3 2.30 GHz processor having Ubuntu 14.40 LTS with 4 GB of RAM. To evaluate the performance of the proposed algorithms, we define two performance metrics \(Gap\%\) and \(Quality\%\) which are defined as follows:

$$\begin{aligned} \textit{Gap\%} = \left( \frac{\mathrm{{Total~Cost}} - \mathrm{{Optimal~Value}}}{\mathrm{{Optimal~Value}}}\right) \times 100, \end{aligned}$$
$$\begin{aligned} Quality\% = 100 - Gap\%. \end{aligned}$$

At first, we run the deterministic BFR on the instances of UFLP. If optimal results given in UflLib [21] are obtained for these instances then we do not run the randomized BFR. The randomized BFR is applied on UFLP instances only when the deterministic BFR fails to give optimal results. In our experiments, the values of \(max\_iterate\) and \(max\_count\) are set to 10 and 4 respectively. The results for the benchmark instances are given in Table 1. Out of the total 15 instances, the deterministic algorithm achieves optimal results for 13 instances and for the remaining two instances, the randomized algorithm achieves the optimal results. In Table 2, the results of large size OR-Library instances [20] are compared with the Lagrangian-type relaxation algorithm proposed by Monabbati [18]. It is observed from Table 2 that the proposed algorithms perform better.

5 Conclusion

In this paper, two heuristic algorithms are proposed to solve the Uncapacitated Facility Location Problem (UFLP). For most of the instances, the deterministic BFR gives optimal or near-optimal results. The randomized BFR has been found to provide optimal results for all the instances where the deterministic BFR fails to give optimal results. It is to be noted that the result found by the randomized BFR is always better or at least same as the result obtained by the deterministic BFR. For future work, the effects of the three phases used in the proposed algorithms on the final result can be analyzed and more experiments on other UFLP instances available in the literature can be performed.