1 Introduction

The uncapacitated facility location problem (UFLP) is one of the well-studied facility location problems (FLPs) (Drezner and Hamacher 2001). UFLP is a well-known combinatorial optimization problem which seeks to find the optimal placement of undetermined number of facilities having unrestricted capacities among potential facility locations such that the sum of the service cost to serve all the customers and the opening cost of the opened facilities is minimized (Al-Sultan and Al-Fawzan 1999; Balinski 1964; Cornuéjols et al. 1983; Erlenkotter 1978; Krarup and Pruzan 1983; Sun 2006). The service cost to satisfy the demands of all customers is also known as the connection cost (Al-Sultan and Al-Fawzan 1999). In the literature of UFLP, it is also known as the Simple Plant Location Problem (SPLP) (Krarup and Pruzan 1983; Kratica et al. 2001) and the Warehouse Location Problem (WLP) (Khumawala 1972). This problem is a single-objective optimization problem which tries to minimize the total cost, i.e., the sum of the service cost and the opening cost. Many mathematical optimization-based solution strategies have been proposed for UFLP such as branch-and-bound method (Akinc and Khumawala 1977; Bilde and Krarup 1977), dual-based linear programming procedure (Erlenkotter 1978), Lagrangian relaxation and sub-gradient optimization-based heuristic (Beasley 1993), surrogate semi-Lagrangian dual approach (Monabbati 2014). This problem is known to be NP-hard problem (Garey and Johnson 1979; Lenstra and Kan 1979). So, many different heuristic algorithms have been proposed for UFLP such as tabu search algorithm (Al-Sultan and Al-Fawzan 1999; Sun 2006), message passing-based heuristic algorithm (Lazic et al. 2010), neighborhood search-based heuristic (Ghosh 2003) and discrete unconscious search (Ardjmand and Amin-Naseri 2012), deterministic and randomized heuristic algorithms (Atta et al. 2018a), solution method based on the monkey algorithm (Atta et al. 2018d). Over the last few decades, different soft computing approaches are also proposed by many researchers of different engineering fields to solve many real-life problems such as predicting forest fires (Al_Janabi et al. 2018), smart systems to promote higher education (Al_Janabi 2018), risk analysis in intrusion detection problem (Al-Janabi 2017), trusted web application development (Patel et al. 2015), fault prediction in electrical transformers (Al-Janabi et al. 2015), second-order boundary value problems (Arqub and Abo-Hammour 2014), solving fuzzy differential equations (Arqub et al. 2016), solving second-order, two-point fuzzy boundary value problems (Arqub et al. 2017), the maximal covering location problem (Atta and Mahapatra 2013; Atta et al. 2018b), the tool indexing problem (Atta et al. 2018c), to name a few.

Fig. 1
figure 1

Flowchart of NSGA-II

Full size image

Many variations of UFLP have emerged since its inception such as the two-level UFLP (Aardal et al. 1996; Gendron et al. 2016, 2017; Klose 1999, 2000; Leung et al. 1994; Tcha and Lee 1984; Zhang 2006), the multi-level UFLP (Aardal et al. 1999; Barros and Labbé 1993; Kochetov and Goncharov 2001; Kratica et al. 2014; Krishnaswamy and Sviridenko 2016), the hierarchical UFLP (Şahin and Süral 2007), a multi-objective UFLP for green logistics considered by Harris et al. (2009) where operating cost of distribution networks and environmental impact (for example, in terms of \({\hbox {CO}}_2\) emission) are considered as two objectives.

In this article, we propose a multi-objective UFLP with customers’ preferences (MOUFLPCP). In this model, we have considered that each customer has a specific predefined nonnegative preference for each facility. In MOUFLPCP, two objective functions are considered. One of the objective functions of MOUFLPCP is same as the classical single-objective UFLP, i.e., the sum of the service cost and opening cost. The second objective function of MOUFLPCP corresponds to the sum of the preferences of customers for facilities from which customers are getting services. In MOUFLPCP, we try to minimize the total cost and maximize the sum of the preferences. The detailed problem definition of MOUFLPCP and its mathematical formulation are given in Sect. 2.

Multi-objective optimization (MOO) deals with several conflicting objective functions (Coello 2006; Deb 2001, 2014; Mukhopadhyay et al. 2015). The final solution set of MOO problem contains a number of Pareto-optimal solutions (Deb 2001, 2014). Non-dominated sorting algorithm II (NSGA-II) (Deb et al. 2000, 2002) is one of the popular elitist multi-objective GAs. NSGA-II has found its applications in many diverse domains such as the conflicting bi-objective facility location problem (Bhattacharya and Bandyopadhyay 2010), multi-objective k-center sum clustering problem (Atta and Mahapatra 2015), multi-objective flexible job shop scheduling problem (Rahmati et al. 2013), multi-objective facility layout problem (Ripon et al. 2009), multi-objective traffic grooming in SONET/WDM ring networks (Biswas et al. 2009), multi-objective fuzzy clustering for pixel classification (Bandyopadhyay et al. 2007; Mukhopadhyay and Maulik 2009), multi-objective location routing problem (Rabbani et al. 2017), to name a few. The framework of NSGA-II is shown in Fig. 1.

In this article, elitist NSGA-II is used to solve MOUFLPCP. The proposed NSGA-II-based method uses a stability measure based on the maximal crowding distance proposed by Roudenko and Schoenauer (2004) as the terminating condition and a deterministic heuristic strategy is used to select a single final solution from the final set of non-dominated near-Pareto-optimal solutions of NSGA-II.

One of the mostly used techniques besides Pareto optimality is the weighted sum method which aggregates different objective values to a single value (Jakob and Blume 2014). In this article, a weighted sum genetic algorithm (WSGA) is also proposed to solve MOUFLPCP where the two objectives after normalization have given weights to compute the single-objective value of WSGA. The detailed description of the proposed WSGA is described in Sect. 4.

Since there exists no instances of the problem proposed in this article, we have generated instances of MOUFLPCP from the existing benchmark instances of UFLP. Experiments are conducted on these newly generated instances of MOUFLPCP. The experimental results obtained using both the proposed methods based on NSGA-II and WSGA are presented and compared in Sect. 5.

The organization of the article is as follows: in Sect. 2, the proposed model for MOUFLPCP is described in detail with its mathematical formulation. The proposed NSGA-II and weighted sum GA-based methods are described in Sects. 3 and 4, respectively. Section 5 provides the experimental results. Finally, Sect. 6 concludes the article.

2 Problem formulation of MOUFLPCP

The multi-objective uncapacitated facility location problem with customer’s preferences (MOUFLPCP) optimizes two objective functions while satisfying several constraints. In the following subsections, we formally define the two objective functions of MOUFLPCP and describe all the constraints.

2.1 Terminologies and variables

Let \(I = \{i_1, i_2, \ldots , i_n\}\) be the set of n potential facility locations and \(J = \{j_1, j_2, \ldots , j_m\}\) be the set of m customers. We also consider that \(C = (c_{ij})_{n\times m}\) is the service cost matrix where \(c_{ij}\) denotes the service cost between facility i and customer j. The preference matrix is denoted by \(P = (p_{ij})_{n\times m}\) where \(p_{ij}\) denotes the preference of customer j for facility i. \(F = \{f_1, f_2, \ldots , f_n\}\) is the set of nonnegative opening costs where \(f_i\) denotes the opening cost for facility i. Note that a customer can avail service from exactly one opened facility for which it has the maximum preference among all the other opened facilities. Now consider two binary decision variables \(s_{ij}\) and \(y_{i}\) which are defined as follows:

$$\begin{aligned} s_{ij}= & {} \left\{ \begin{array}{ll} 1, &{} \quad \hbox {if facility } i \hbox { provides service to customer } j \\ 0, &{} \quad \hbox {otherwise.} \end{array} \right. \\ y_i= & {} \left\{ \begin{array}{ll} 1, &{} \quad \hbox { if facility } i \hbox { is opened}\\ 0, &{} \quad \hbox { otherwise.} \end{array} \right. \end{aligned}$$

2.2 Objective functions

The first objective function of MOUFLPCP is to minimize the total cost that can be expressed as:

$$\begin{aligned} \hbox {(minimize)}~F_1 = \sum \limits _{i = 1}^{n} \sum \limits _{j = 1}^{m} c_{ij} s_{ij} + \sum \limits _{i = 1}^{n} f_i y_i. \end{aligned}$$
(1)

The first term of \(F_1\) in Eq. 1 denotes the sum of the service costs, and the second term of \(F_1\) in Eq. 1 refers to the sum of the opening costs of opened facilities. \(F_1\) also corresponds to the objective function of the classical single-objective UFLP (Al-Sultan and Al-Fawzan 1999).

The second objective function \(F_2\) of MOUFLPCP is to maximize the sum of preferences for all the customers that can be expressed as:

$$\begin{aligned} \hbox {(maximize)}~F_2 = \sum \limits _{i = 1}^{n} \sum \limits _{j = 1}^{m} p_{ij} s_{ij}. \end{aligned}$$
(2)

2.3 Constraints

According to the definitions of the two decision variables \(s_{ij}\) and \(f_{j}\) in 2.1, we have the following two constraints:

$$\begin{aligned}&s_{ij} \in \{0, 1\}, \quad \forall ~i, j, \end{aligned}$$
(3)
$$\begin{aligned}&y_j \in \{0, 1\},\quad \forall ~j. \end{aligned}$$
(4)

The constraints mentioned in Eqs. 3 and 4 confirm the \(0-1\) nature of the problem. Apart from these two binary constraints on the decision variables \(s_{ij}\) and \(y_{j}\), there are other constraints which can also be found in the single-objective UFLP (Al-Sultan and Al-Fawzan 1999).

In MOUFLPCP, a customer can get service from exactly one facility. This can be described as follows:

$$\begin{aligned} \sum _{i = 1}^{n} s_{ij} = 1, \quad j = 1, \ldots , m. \end{aligned}$$
(5)

Moreover, a customer must get service from the facility which is already opened. This constraint can be written as follows:

$$\begin{aligned} s_{ij} \le y_j, \quad i = 1, \ldots n, \quad j = 1, \ldots m. \end{aligned}$$
(6)

3 Proposed multi-objective GA technique

In this section, the NSGA-II-based multi-objective genetic algorithm (MOGA) is proposed to solve MOUFLPCP. The proposed method is described in the subsequent subsections in detail.

3.1 Chromosome encoding and initial population generation

Each gene of the chromosome has an allele value either 0 or 1. The length of each chromosome is equal to the number of potential facilities, i.e., n. Here, the kth chromosome is denoted by a vector \(X^k = \{x^k_1, x^k_2, \ldots , x^k_n\}\) of length n where \(x^k_i \in \{0, 1\}\). The facility i is considered to be opened if \(x^k_i = 1\). Thus, a chromosome encodes whether a facility is opened or not. The initial population is created randomly by generating \(n\textit{Pop}\) such chromosomes. Here, \(n\textit{Pop}\) is the population size which remains fixed throughout the evolution process.

3.2 Fitness computation

Each customer is assigned to its nearest opened facility. Note that ties are broken by arbitrarily selecting any one of the opened facilities. In this way, the decision variables \(s_{ij}\) (mentioned in Sect. 2.1) are computed and the chromosome under consideration encodes \(y_i\). Then the objective values are computed using Eqs. 1 and 2.

3.3 Selection

The mating pool of chromosomes is generated using crowded binary tournament selection (Deb et al. 2000, 2002). In the proposed method, we have sorted the population based on crowding distance and rank of each individual chromosome.

Two genetic operators, viz., crossover and mutation are applied iteratively in every generation with their corresponding probabilities. These operators are used to explore the solution space.

3.4 Crossover

In the proposed technique, three types of crossover methods are used depending on the cumulative sum of their respective probabilities of usage. The details of these crossover methods, viz., single-point crossover, double-point crossover and uniform crossover can be found in Goldberg (2006), Srinivas and Patnaik (1994), Syswerda (1989). The crossover operation is described in Pseudocode 1.

figure a

3.5 Mutation

Simple inversion-based mutation technique is used in the proposed method. Since the elements of chromosome are either 0 or 1, they are complemented with a probability \(\mu _\mathrm{{m}}\), known as the mutation probability. This may open new facilities and close the already existing facilities. In this article, \(\mu _\mathrm{{m}}\) is considered as 0.40.

3.6 Elitism

The best solutions of previous generation are propagated to the new generation by means of elitism operation of NSGA-II. The intermediate population is generated by combining the parent population and the newly generated offspring solutions. This will create an intermediate population having size twice of \(n\textit{Pop}\). The top \(n\textit{Pop}\) solutions from the combined population are selected based on non-dominated sorting (Deb et al. 2002) and crowding distance operator (Deb et al. 2002), and these solutions are propagated to the next generation.

Fig. 2
figure 2

Selecting a solution from rank 1 solutions

Full size image

3.7 Terminating condition

The most popular terminating criterion used in NSGA-II and any other evolutionary multi-objective algorithms is to run the algorithm for a fixed number of generations. Unfortunately, this terminating criterion does not guarantee to give the best results in terms of objective values and it may run the algorithm without improving any objective consuming more running time. In this article, we have used the stabilization of the maximal crowding distance proposed by Roudenko and Schoenauer (2004) as the terminating condition. The stability measure\(\sigma _L\) (Roudenko and Schoenauer 2004) is measured over the last L generations using Eq. 7 as shown:

$$\begin{aligned} \sigma _L = \sqrt{\frac{1}{L}\sum \limits _{l=1}^L (d_l - {\bar{d}}_{L})^2}, \end{aligned}$$
(7)

where \(d_l\) is the maximal crowding distance computed at generation l and \(\bar{d_L}\) is the average of \(d_l\) over L generations (Roudenko and Schoenauer 2004).

If the value of \(\sigma _L\) falls below predefined small threshold \(\delta _{lim}\), then the algorithm is terminated (Roudenko and Schoenauer 2004). In the proposed work, the values of L and \(\delta _{lim}\) are chosen as 20 and 0.02, respectively.

3.8 Selecting a solution from the non-dominated set

In the final generation, NSGA-II produces near-Pareto-optimal non-dominated set of solutions. So, we proposed a method to figure out a particular solution from the obtained set of solutions. We have chosen the rank 1 solution which has the minimum sum of Euclidean distances from all other solutions having rank 1. Now, if there exist multiple solutions having the same second objective value with this chosen solution then we update the final solution by the solution for which the first objective value is minimum. This is illustrated in Fig. 2.

4 Proposed weighted sum genetic algorithm

In this section, the weighted sum genetic algorithm (WSGA) is proposed to solve MOUFLPCP. The proposed method is described in the subsequent subsections in detail.

4.1 Chromosome encoding and initial population generation

The same chromosome representation and initial population generation methods are used as mentioned in Sect. 3.1.

4.2 Fitness computation

At first, each customer is assigned to its nearest opened facility. Here, ties are also broken arbitrarily. Then the objective values \(F_1\) and \(F_2\) of MOUFLPCP are computed using Eqs. 1 and 2 for the corresponding chromosome (refer to Sect. 3.2). Since these objective values have different scales, they are normalized using the following Eqs. 8 and 9, respectively:

$$\begin{aligned} F_1^\mathrm{norm}= & {} \frac{F_1}{F_1^{\max } - F_1^{\min }}, \end{aligned}$$
(8)
$$\begin{aligned} F_2^\mathrm{norm}= & {} 1 - \frac{F_2}{F_2^{\max } - F_2^{\min }}, \end{aligned}$$
(9)

where \(F_1^{\max }\) and \(F_1^{\min }\) denote the objective values when each customer is served by its farthest and nearest facilities, respectively, and \(F_2^{\max }\) and \(F_2^{\min }\) represent the objective values when each customer is getting its service from the least preferable and the most preferable facilities, respectively. The weighted sum (WS) of these two objectives is computed using the following Eq. 10:

$$\begin{aligned} \mathrm{{WS}} = w_1F_1^\mathrm{norm} + w_2F_2^\mathrm{norm}, \end{aligned}$$
(10)

where \(w_1\) and \(w_2\) are set to 0.10 and 0.90, respectively. Here, we have given \(10\%\) weight to the first objective function and \(90\%\) weight to the second objective function of MOUFLPCP. These values are obtained experimentally. The intuition behind giving more weight to the second objective function is that customers are always assigned to its nearest opened facility. This eventually prefers the first objective function. Hence, the second objective value is given more weight than the first objective value. The objective of the proposed WSGA is to minimize WS over the generations.

4.3 Selection

Mating pool is created using the binary tournament selection method (Goldberg 1989). The chromosomes in the mating pool are eligible to take part in crossover. Two chromosomes \(p_1\) and \(p_2\) are selected randomly from the population and one of them is chosen as described in Pseudocode 2 and put into the mating pool. The mating pool is created in such a way that the size of the population is preserved.

figure b

4.4 Crossover

The crossover method described in Sect. 3.4 is also used here. The crossover operation is performed on the chromosomes from the mating pool and a separate population is generated.

4.5 Mutation

The same mutation method described in Sect. 3.5 is used here for generating a separate population.

4.6 Elitism

The parent population and the new population generated from crossover and mutation are merged together. Subsequently, based on the weighted sum objective values computed using Eq. 10, chromosomes are sorted and the top most \(n\textit{Pop}\) chromosomes are chosen to form the parent population of next generation.

4.7 Terminating condition

The proposed GA is terminated if no improvement in terms of the weighted sum objective value of the best chromosome in a generation is observed for a maximum number of predefined value maxCount. In this work, we have considered the value of maxCount as 10.

5 Experimental results

In this section, experimental results are discussed. At first, the procedure for generating benchmark instances for MOUFLPCP is discussed. Then these test instances are used to compare the performance of the proposed two algorithms for MOUFLPCP and the results obtained from the experiments are reported and discussed in detail.

5.1 Test instances

Since there exist no benchmark data sets for the proposed problem, we create benchmark instances for MOUFLPCP from the existing benchmark instances of UFLP. Each instance of MOUFLPCP consists of two matrices, viz., service cost matrix and preference matrix, and a vector defining the opening cost of each facility. The service costs and the opening costs are available in the UFLP benchmark instances. The UFLP benchmark instances used in this article can be found from the Beasley’s OR-Library (Beasley 1990). Given the service cost matrix C, we generate the preference matrix P as described in Pseudocode 3.

figure c

Note that preference \(p_{ij}\) of customer j for facility i is dependent on the corresponding service cost and a random value (see line 4 of Pseudocode 3). All the created benchmark data sets for MOUFLPCP are available in the supplementary web-page (http://kucse.in/mouflpcp) of this article.

Table 1 Performance comparison for instances of sizes \(16 \times 50\)
Full size table
Table 2 Performance comparison for instances of sizes \(25 \times 50\)
Full size table
Table 3 Performance comparison for instances of sizes \(50 \times 50\)
Full size table
Fig. 3
figure 3

Differences of normalized average objective values for Table 1

Full size image
Fig. 4
figure 4

Differences of normalized average objective values for Table 2

Full size image

5.2 Results and discussion

The proposed NSGA-II and weighted sum GA-based algorithms are coded with MATLAB R2017a, and all the experiments are performed in a machine with Intel Core i5 processor (3.10 GHz) running Windows 10 operating system with 8 GB of RAM. For both the proposed algorithms, the population size (\(n\textit{Pop}\)) is considered as 50.

Fig. 5
figure 5

Differences of normalized average objective values for Table 3

Full size image

The instances are grouped according to their sizes. The size of an instance is defined by \(n \times m\) where n denotes the number of potential facility locations and m is the number of the customers. Experiments are conducted for each of these groups. The experimental results for both of the proposed algorithms are shown in Table 1, 2 and 3 in which the first column represents the instance names and the second column gives the size of the instances. The maximum, minimum, average and standard deviation of each of the objective values \(F_1\), \(F_2\) and the average, standard deviation of computation time (T) in seconds are mentioned in Table 1, 2 and 3 for both type of experiments. Note that each experiment is carried out 50 times for each instance.

It is evident from Tables 1, 2 and 3 that both the proposed methods are comparable. For better understanding of their respective performances, the two objective values \(F_1\) and \(F_2\) obtained from both the methods are normalized according to Eqs. 8 and 9, and then their respective differences are graphically shown in Figs. 3, 4 and 5, respectively. The two objective functions in MOUFLPCP are conflicting to each other. The first objective function is trying to decrease, whereas the second one is trying to increase. Moreover, the scale of these two objective values \(F_1\) and \(F_2\) are not same. Hence, we have normalized them in the same range [0, 1] to understand how much improvement is done in one objective value by sacrificing the other. A solution method for MOUFLPCP is said to be better than the other method if \(F_1\) and \(F_2\) obtained using the first method are, respectively, less than and greater than the same obtained using the second method. For example, it is clear from Figs. 3, 4 and 5 that the proposed NSGA-II-based technique is superior than WSGA-based method for the test instances mouflpcp{61, 81, 82, 83, 91, 92, 101, 102, 111, 112, 121, 122, 131, 132}. Similarly, WSGA-based method gives better results than NSGA-II-based approach for the test instances mouflpcp{41, 44, 51, 62, 63, 71, 72, 73, 84, 94, 104, 113, 114, 123, 124, 133, 134}.

6 Conclusion

In this article, a new model for multi-objective uncapacitated facility location problem having two objective functions is presented. The first objective function tries to minimize the total cost consisting of service cost and facility opening cost, whereas the second objective function tries to maximize the sum of the preferences of customers for facilities. At first, NSGA-II-based method is presented to solve MOUFLPCP. In the proposed method, a stability measure based on the maximal crowding distance is used as the terminating condition and a deterministic heuristic is used to select a single solution from the set of non-dominated near-Pareto-optimal solutions obtained in the last generation. Then a weighted sum GA-based method is also proposed to solve MOUFLPCP where two conflicting objectives are aggregated to a single measure. Experiments are conducted on newly generated benchmark instances and numerical results are demonstrated and compared graphically for both of the proposed methods.