The capacitated facility location-allocation problem under uncertain environment

Abstract

Facility location-allocation (FLA) problem has been widely studied by operational researchers due to its many practical applications. In real life, it is usually very hard to present the customers’ demands in a precise way and thus they are regarded to be uncertain. Since the uncertain demands can be estimated from historical data, researchers tried to describe FLA problem under stochastic environment. Although stochastic models can cater for a variety of cases, they are not sufficient to describe many other situations, where the probability distribution of customers’ demands may be unknown or partially known. Instead we have to invite some domain experts to evaluate their belief degree that each event will occur. This paper will consider the capacitated FLA problem under small sample or no-sample cases and establish an uncertain expected value model based on uncertain measure. In order to solve this model, the simplex algorithm, Monte Carlo simulation and a genetic algorithm are integrated to produce a hybrid intelligent algorithm. Finally, a numerical example is presented to illustrate the uncertain model and the algorithm.

Keywords

Location-allocation problem uncertainty theory uncertain measure uncertain programming genetic algorithm

1 Introduction

Facility location-allocation (FLA) problem, as one of the most critical and strategic issues in supply-chain design and management, exhibits a significant impact on market share and profitability. Besides supply-chain management, it is also widely used in practical life, such as building an emergency service systems and constructing a telecommunication networks, etc.

FLA problem was initially studied by Cooper [5] in 1963, which wants to decide locations of warehouses and allocation of customers demand given the locations and demand of customers. Since then, this problem has received much attention from other researchers and it has been analyzed in a number of different ways. Hakimi [13, 14] applied it in network design as a powerful tool. In 1982, Murtagh and Niwattisyawong [32] proposed the capacitated FLA problem, which is considered as one of the most important researches in this field, specially focusing on facilities which have capacity constraints. Many extensions of FLA problem were studied, Such as continuous site location problemJiang and Yuan [16], joint FLA problem Jayaraman and Pirkul [15] and multi-objective FLA problem Revelle and Laporte [34]. For detailed review of literature on FLA problem, readers are referred to Klose and Drexl [17]. Megiddo and Supowit [30] have proved that the FLA problem is strongly NP-hard, and thus a large amount of solution approaches for different models have been proposed in the past decades Kuenne and Soland [18], Murray and Church [31]. A series of heuristic algorithms have also been developed to solve complicated FLA problems Ernst and Krishnamoorthy [9], Gong et al. [12].

A limitation of most existing studies on FLA problem is that customers’ demands are usually assumed deterministic and therefore a linear inventory holding cost is adopted. Without considering the uncertainty of customers’ demands, those models usually lead to sub-optimal in terms of total cost. In recent years, some studies consider stochastic customers’ demands and incorporate inventory policy into FLA problem Logendran and Terrell [19], Sabri and Beamon [35], Zhou and Liu [38, 41]. Although stochastic models can cater for a variety of cases, they are not sufficient to describe many other situations, where the probability distributions of customers¡¯ demands may be unknown or partially known. In order to have an approximate understanding of these cases, we usually consult the experts and obtain their empirical data. The empirical data from experts, like “about 100”, “more than 200”, etc., can be regarded as fuzzy variable initialized by Zadeh [39]. In the past decades many researchers have introduced fuzzy theory into FLA problem Bhattacharya et al. [1], Chen and Wei [3], Darzentas [7], Zhou and Liu [42, 43], Wen and Iwamura [37].

However, a lot of surveys showed that this assumption is also not suitable. For example, we say “the customer’s demand is about 100”. Generally, we employ fuzzy variable to describe the concept of “about 100”, then there exists a membership function, such as a triangular one (90, 100, 110). Based on this membership function, possibility theory will conclude: (a) the demand is “exactly 100” with belief degree 1, and (b) the demand is “not 100” with belief degree 1. Obviously, the belief degree of “exactly 100” is almost zero. Besides, (b) indicates “not 100” and “exactly 100” have the same belief degree. These conclusions are improper. In order to have a better mathematical tool to deal with empirical data, uncertainty theory was founded by Liu [20] in 2007 and refined in 2010 [24]. In this paper, we will assume the customers’s demands are uncertain variables, and propose an uncertain facility location-allocation model with capacitated supply.

The rest of this paper is organized as follows. Section 2 will introduce some basic concepts and properties about uncertain variables. An uncertain capacitated facility location-allocation model as well as its equivalent crisp model is presented in Section 3. In order to solve this uncertain model, we integrate the simplex algorithm, Monte Carlo simulation and genetic algorithm to design a powerful hybrid intelligent algorithm in Section 4. In Section 5, a numerical example will be provided to illustrate the performance and the effectiveness of the proposed model and algorithm. Finally, Section 6 will give the conclusion, in which the contributions of this paper and future research plans are shown.

2 Preliminaries

Uncertainty theory was founded by Liu [20] in 2007 and refined by Liu [24] in 2010. As extensions of uncertainty theory, uncertain process and uncertain differential equations Liu [21], uncertain calculus Liu [22] were proposed. Uncertain programming was first proposed by Liu [23] in 2009, which wants to deal with the optimal problems involving uncertain variable. This work was followed by an uncertain multiobjective programming and an uncertain goal programming Liu and Chen [26], and an uncertain multilevel programming Liu and Yao [27]. Since that, uncertainty theory was used to solve variety of real optimal problems, including finance Chen and Liu [4], Peng [33], Liu [28], reliability analysis Liu [25], Zeng et al. [40], graph Gao [10], Gao and Gao [11], et al. Nowadays uncertainty theory has become a branch of axiomatic mathematics for modeling human uncertainty. In this section, we will state some basic concepts and results on uncertain variable and uncertain programming. These results are crucial for the remainder of this paper.

Let Γ be a nonempty set, and $L$ a σ-algebra over Γ. Each element $Λ \in L$ is assigned a number $M {Λ} \in [0, 1]$ . In order to ensure that the number $M {Λ}$ has certain mathematical properties, Liu [20, 22] presented the four axioms:

Axiom 1. $M {Γ} = 1$ for the universal set Γ.

Axiom 2. $M {Λ} + M {Λ^{c}} = 1$ for any event Λ.

Axiom 3. For every countable sequence of events Λ ₁, Λ ₂, ⋯, we have $M {⋃_{i = 1}^{\infty} Λ_{i}} \leq \sum_{i = 1}^{\infty} M {Λ_{i}} .$

Axiom 4. Let $(Γ_{k}, L_{k}, M_{k})$ be uncertainty spaces for k = 1, 2, ⋯ , ∞. Then the product uncertain measure $M$ is an uncertain measure satisfying $M {\prod_{k = 1}^{\infty} Λ_{k}} = ⋀_{k = 1}^{\infty} M_{k} {Λ_{k}} .$

If the set function $M$ satisfies the first three axioms, it is called an uncertain measure.

Definition 1. Liu [20] Let Γ be a nonempty set, $M$ a σ-algebra over Γ, and $M$ an uncertain measure. Then the triplet $(Γ, L, M)$ is called an uncertainty space.

2.1 Uncertain variable

Definition 2. Liu [20] An uncertain variable is a measurable function ξ from an uncertainty space $(Γ, L, M)$ to the set of real numbers, i.e., for any Borel set B of real numbers, the set ${ξ \in B} = {γ \in Γ} | ξ (γ) \in B}$ (1) is an event.

Definition 3. Liu [20] The uncertainty distribution Φ of an uncertain variable ξ is defined by $Φ (x) = M {ξ \leq x}$ (2) for any real number x.

Example 1. An uncertain variable ξ is said to have an empirical uncertainty distribution if $Φ (x) = {\begin{matrix} 0, & if x < x_{1} \\ α_{i} + \frac{(α_{i + 1} - α_{i}) (x - x_{i})}{x_{i + 1} - x_{i}}, & if x_{i} \leq x \leq x_{i + 1} \\ 1, & if x > x_{n} \end{matrix}$ denoted by $E (x_{1}, α_{1}, x_{2}, α_{2}, \dots, x_{n}, α_{n})$ , where x ₁ < x ₂ < ⋯ < x _n and 0 ≤ α ₁ ≤ α ₂ ≤ ⋯ ≤ α _n ≤ 1.

Example 2. The inverse uncertainty distribution of zigzag uncertain variable $Z (a, b, c)$ is $Φ^{- 1} (α) = {\begin{matrix} (1 - 2 α) a + 2 α b, & if α < 0.5 \\ (2 - 2 α) b + (2 α - 1) c, & if α \geq 0.5 . \end{matrix}$

Definition 4. Liu [24] Let ξ be an uncertain variable. Then the expected value of ξ is defined by $E [ξ] = \int_{0}^{+ \infty} M {ξ \geq r} d r - \int_{- \infty}^{0} M {ξ \leq r} d r$ (3) provided that at least one of the two integrals is finite.

Example 3. The zigzag uncertain variable $ξ \sim Z (a, b, c)$ has an expected value $E [ξ] = \frac{a + 2 b + c}{4} .$

Example 4. Let ξ have an empirical uncertainty distribution, i.e., $ξ \sim E (x_{1}, α_{1}, x_{2}, α_{2}, \dots, x_{n}, α_{n})$ . Then $\begin{matrix} E [ξ] = \frac{α_{1} + α_{2}}{2} x_{1} + \sum_{i = 2}^{n - 1} \frac{α_{i + 1} - α_{i - 1}}{2} x_{i} \\ + (1 - \frac{α_{n - 1} + α_{n}}{2}) x_{n} \end{matrix}$ where x ₁ < x ₂ < ⋯ < x _m and 0 ≤ α ₁ ≤ α ₂ ≤ ⋯ ≤ α _n ≤ 1.

Definition 5. Liu [24] An uncertainty distribution Φ is said to be regular if its inverse function Φ ^-1 (α) exists and is unique for each α ∈ (0, 1).

Definition 6. Liu [22] The uncertain variables ξ ₁, ξ ₂, ⋯ , ξ _n are said to be independent if $M {⋂_{i = 1}^{n} (ξ_{i} \in B_{i})} = ⋀_{i = 1}^{n} M {ξ_{i} \in B_{i}}$ (4) for any Borel sets B ₁, B ₂, ⋯ , B _n.

Theorem 1. Liu and Ha [29] Assume ξ ₁, ξ ₂, ⋯ , ξ _n are independent uncertain variables with regular uncertainty distributions Φ ₁, Φ ₂, ⋯ , Φ _n, respectively. If f (x ₁, x ₂, ⋯ , x _n) is strictly increasing with respect to x ₁, x ₂, ⋯ , x _m and strictly decreasing with respect to x _m+1, x _m+2, ⋯ , x _n, then the uncertain variable ξ = f (ξ ₁, ξ ₂, ⋯ , ξ _n) has an expected value $\begin{matrix} E [ξ] = \int_{0}^{1} f (Φ_{1}^{- 1} (α), \dots, Φ_{m}^{- 1} (α), Φ_{m + 1}^{- 1} (1 - α), \\ \dots, Φ_{n}^{- 1} (1 - α)) d α \end{matrix}$ (5) provided that E [ξ] exists.

Example 5. Let ξ and η be independent and nonnegative uncertain variables with regular uncertainty distributions Φ and Ψ, respectively. Then $E [ξ η] = \int_{0}^{1} Φ^{- 1} (α) Ψ^{- 1} (α) | d α .$

Example 6. Let ξ be an uncertain variable with regular uncertainty distribution Φ. Then $E [exp (ξ)] = \int_{0}^{1} exp (Φ^{- 1} (α)) d α .$

Theorem 2. Liu [24] Let ξ ₁, ξ ₂, ⋯ , ξ _n be independent uncertain variables with regular uncertainty distributions Φ ₁, Φ ₂, ⋯ , Φ _n, respectively. If f is a strictly increasing function, then $ξ = f (ξ_{1}, ξ_{2}, \dots, ξ_{n})$ (6) is an uncertain variable with inverse uncertainty distribution $Ψ^{- 1} (α) = f (Φ_{1}^{- 1} (α), Φ_{2}^{- 1} (α), \dots, Φ_{n}^{- 1} (α)) .$ (7)

Example 7. Let ξ be an uncertain variable with regular uncertainty distribution Φ. since f (x) = ax + b is a strictly increasing function for any constants a > 0 and b, the inverse uncertainty distribution ofaξ + b is $Ψ^{- 1} (α) = a Φ_{1}^{- 1} (α) + b .$ (8)

Example 8. Let ξ ₁, ξ ₂, ⋯ , ξ _n be independent uncertain variables with regular uncertainty distributions Φ ₁, Φ ₂, ⋯ , Φ _n, respectively. Since $f (x_{1}, x_{2}, \dots, x_{n}) = x_{1} + x_{2} + \dots + x_{n}$ (9) is a strictly increasing function, the sum $ξ = ξ_{1} + ξ_{2} + \dots + ξ_{n}$ (10) is an uncertain variable with inverse uncertaintydistribution $Ψ^{- 1} (α) = Φ_{1}^{- 1} (α) + Φ_{2}^{- 1} (α) + \dots + Φ_{n}^{- 1} (α) .$ (11)

2.2 Uncertain programming

Uncertain programming, which was first proposed by Liu [23] in 2009, is a type of mathematical programming involving uncertain variables. After that, an uncertain multiobjective programming and an uncertain goal programming Liu and Chen [26], and an uncertain multilevel programming Liu and Yao [27] were provided.

Assume that x is a decision vector, and ξ is an uncertain vector. Since the uncertain programming model contains the uncertain objective function f (x, ξ ) and uncertain constraints g _j (x, ξ) ≤0, j = 1, 2, ⋯ , p, Liu [23] proposed the following uncertain programming model, ${\begin{matrix} min_{x} E [f (x, ξ)] \\ subject to : \\ M {g_{j} (x, ξ) \leq 0} \geq α_{j}, j = 1, 2, \dots, p . \end{matrix}$ (12)

Definition 7. Liu[24] A vector x is called a feasible solution to Model (12) if $M {g_{j} (x, ξ) \leq 0} \geq α_{j}$ (13) for j = 1, 2, ⋯ , p.

Definition 8. Liu [24] A feasible solution x ^* is called an optimal solution to Model (12) if $E [f (x^{*}, ξ)] \leq E [f (x, ξ)]$ (14) for any feasible solution x.

Theorem 3. Liu[24] Assume f (x, ξ₁, ξ₂, ⋯ , ξ_n) is strictly increasing with respect to ξ₁, ξ₂, ⋯ , ξ_m and strictly decreasing with respect to ξ_m+1, ξ_m+2, ⋯ , ξ_n, and g_j (x, ξ₁, ξ₂, ⋯ , ξ_n) are strictly increasing with respect to ξ₁, ξ₂, ⋯ , ξ_k and strictly decreasing with respect to ξ_k+1, ξ_k+2, ⋯ , ξ_n for j = 1, 2, ⋯ , p. If ξ₁, ξ₂, ⋯ , ξ_n are independent uncertain variables with uncertainty distributions Φ₁, Φ₂, ⋯ , Φ_n, respectively, then the uncertain programming ${\begin{matrix} min_{x} E [f (x, ξ_{1}, ξ_{2}, \dots, ξ_{n})] \\ subject to : \\ M {g_{j} (x, ξ_{1}, ξ_{2}, \dots, ξ_{n}) \leq 0} \geq α_{j}, \\ j = 1, 2, \dots, p \end{matrix}$ (15) is equivalent to the crisp mathematical programming ${\begin{matrix} min_{x} \int_{0}^{1} f (x, Φ_{1}^{- 1} (α), \dots, Φ_{m}^{- 1} (α), \\ Φ_{m + 1}^{- 1} (1 - α), \dots, Φ_{n}^{- 1} (1 - α)) d α \\ subject to : \\ g_{j} (x, Φ_{1}^{- 1} (α_{j}), \dots, Φ_{k}^{- 1} (α_{j}), \\ Φ_{k + 1}^{- 1} (1 - α_{j}), \dots, Φ_{n}^{- 1} (1 - α_{j})) \leq 0, \\ j = 1, 2, \dots, p . \end{matrix}$

3 Uncertain capacitated FLA problem

The capacitated continuous FLA problem is to find the locations of n facilities in continuous space in order to serve customers at m fixed points as well as the allocation of each customer to the facilities so that total transportation costs are minimized. In order to model the capacitated FLA problem, firstly we make some assumptions:

Each facility has a limited capacity. Thus we need to select locations and decide the amount from each facility i to each customer j.

The path between any customers and facilities is connected and transportation cost is proportionate to the quantity supplied and the travel distance.

Facility i is assumed to be located within a certain region R _i = {(x _i, y _i) |g _i (x _i, y _i) ≤0} , i = 1, 2, …, n, respectively.

As we know, when we use probability or statistics to build models, a large amount of historical data is needed. However, in most case the sample size is too small (even no-sample) to estimate a probability distribution. Then we have to invite some domain experts to evaluate their belief degree that each event will occur. This provides a motivation for Liu [20] to found an uncertainty theory. Then we will give the symbols and notations as follows:

i = 1, 2, …, n is the index of facilities;

j = 1, 2, …, m is the index of customers;

(a _j, b _j) denotes the location of customer j, 1 ≤ j ≤ m;

ξ _j is the uncertain demand of customer j, 1 ≤ j ≤ m;

Φ _j is the uncertainty distribution of ξ _j, 1 ≤ j ≤ m;

s _i is the capacity of facility i, 1 ≤ i ≤ n;

(x _i, y _i) is the decision variable which represents the location of facility i, 1 ≤ i ≤ n;

z _ij denotes the quantity supplied by facility i to customerj, 1 ≤ i ≤ n, 1 ≤ j ≤ m.

For convenience, we also write

$Z (ξ) = {\begin{matrix} z_{ij} \geq 0, i = 1, 2, \dots, n, j = 1, 2, \dots, m \\ z | & \sum_{i = 1}^{n} z_{ij} = ξ_{j}, j = 1, 2, \dots, m \\ \sum_{j = 1}^{m} z_{ij} \leq s_{i}, i = 1, 2, \dots, n \end{matrix}} .$ (16)

Then we can give the uncertain transportation cost with the best allocation z ,

$C (x, y, ξ) = min_{z \in Z (ξ)} \sum_{i = 1}^{n} \sum_{j = 1}^{m} z_{ij} \sqrt{(x_{i} - a_{j})^{2} + (y_{i} - b_{j})^{2}} .$ (17)

If Z ( ξ ) is an empty set for some ξ , we can define

$C (x, y, ξ) = \sum_{j = 1}^{m} max_{1 \leq i \leq n} ξ_{j} \sqrt{(x_{i} - a_{j})^{2} + (y_{i} - b_{j})^{2}} .$ (18)

3.1 Uncertainty distributions of customers’ demands

Liu [24] proposed a questionnaire survey for collecting expert’s experimental data. It is based on expert’s experimental data rather than historical data. The starting point is to invite one expert who is asked to complete a questionnaire about the meaning of an uncertain demand ξ like “How many is the customer’s demand”.

We first ask the domain expert to choose a possible value x that the uncertain demand ξ may take, and then quiz him

“How likely is ξ less than or equal to x?”

Denote the expert’s belief degree by α. An expert’s experimental data (x, α) thus acquired from the domain expert.

Repeating the above process, we can obtain the following expert’s experimental data $(x_{1}, α_{1}), (x_{2}, α_{2}), \dots, (x_{n}, α_{n})$ (19) that meet the following consistence condition (perhaps after a rearrangement) $x_{1} < x_{2} < \dots < x_{n}, 0 \leq α_{1} \leq α_{2} \leq \dots α_{n} \leq 1 .$ (20)

Based on those expert’s experimental data, Liu [24] suggested an empirical uncertainty distribution, $Φ (x) = {\begin{matrix} 0, & x \leq x_{1} \\ α_{i} + \frac{(α_{i + 1} - α_{i}) (x - x_{i})}{x_{i + 1} - x_{i}}, & x_{i} \leq x \leq x_{i + 1}, \\ 1, & x > x_{n} . \end{matrix}$ (21) denoted by $E (x_{1}, α_{1}, x_{2}, α_{2}, \dots, x_{n}, α_{n})$ . Essentially, it is a type of linear interpolation method. The distribution function has been shown in Fig. 1.

Assume there are m domain experts and each produces an uncertainty distribution. Then we may get m uncertainty distributions Φ ₁ (x) , Φ ₂ (x) , ⋯ , Φ _m (x). The Delphi method was originally developed in the 1950s by the RAND Corporation based on the assumption that group experience is more valid than individual experience. Wang et al.[36] recast the Delphi method as a process to determine the uncertainty distribution. The main steps are listed as follows:

Step 1: The m domain experts provide their expert’s experimental data, $(x_{ij}, α_{ij}), j = 1, 2, \dots, n_{i}, i = 1, 2, \dots, m .$ (22)

Step 2: Use the i-th expert’s experimental data (x _i1, α _i1) , (x _i2, α _i2) , ⋯ , (x _{in
_i}, α _{in
_i}) to generate the i-th expert’s uncertainty distribution Φ _i.

Step 3: Compute Φ (x) = w ₁ Φ ₁ (x) + w ₂ Φ ₂ (x) + ⋯ + w _m Φ _m (x) where w ₁, w ₂, ⋯ , w _m are convex combination coefficients.

Step 4: If |α _ij - Φ (x _ij) | are less than a given level ɛ > 0, then go to Step 5. Otherwise, the i-th expert receives the summary (Φ and reasons), and then provides a set of revised expert’s experimental data. Go to Step 2.

Step 5: The last Φ is the uncertainty distribution of the customer’s demand.

3.2 Uncertain expected value model

The essential idea of the expected cost minimization model is to optimize the expected value of C ( x , y , ξ ) subject to some expected constraints. Zhou and Liu [41] have formulated the expected cost minimization model under stochastic demands. Here we shall give the model with uncertain environment as follows: ${\begin{matrix} min_{x, y} E [C (x, y, ξ)] \\ subject to : \\ g_{i} (x, y) \leq 0, i = 1, 2, \dots, p \end{matrix}$ (23) where g _i ( x , y ) ≤0, i = 1, 2, …, p, are the potential regions of locations of new facilities.

Since the uncertain transportation cost C ( x , y , ξ ) is strictly increasing with respect to ξ ₁, ξ ₂, ⋯ , ξ _m, the uncertain capacitated FLA model is equivalent to ${\begin{matrix} min_{x, y} \int_{0}^{1} C (x, y, Φ_{1}^{- 1} (α), Φ_{2}^{- 1} (α), \dots, Φ_{m}^{- 1} (α)) d α \\ subject to : \\ g_{i} (x, y) \leq 0, i = 1, 2, \dots, p . \end{matrix}$ (24)

The model is different from traditional programming models because there is a sub-optimal problem in it, i.e., $C (x, y, Φ_{1}^{- 1} (α), Φ_{2}^{- 1} (α), \dots, Φ_{m}^{- 1} (α))$ $= {\begin{matrix} min_{z} \sum_{i = 1}^{n} \sum_{j = 1}^{m} z_{ij} \sqrt{(x_{i} - a_{j})^{2} + (y_{i} - b_{j})^{2}} \\ subject to : \\ z_{ij} \geq 0, i = 1, 2, \dots, n, j = 1, 2, \dots, m \\ \sum_{i = 1}^{n} z_{ij} = Φ_{j}^{- 1} (α), j = 1, 2, \dots, m \\ \sum_{j = 1}^{m} z_{ij} \leq s_{i}, i = 1, 2, \dots, n . \end{matrix}$ (25)

This sub-optimal problem can be easily solved by simplex algorithm because it is a linear programming.

4 Hybrid intelligent algorithm

Generally speaking, uncertain programming models are difficult to solve by traditional methods due to its complexity. Moreover the FlA problem has been proved to be NP-hard Megiddo and Supowit[30]. Heuristic methods have been shown to be the best way to tackle larger NP-hard problems. Modern heuristics such as simulated annealing, tabu search, genetic algorithms (GA), variable neighborhood search, and ant systems increase the chance of avoiding local optimality. In this paper, we use GA which was shown useful and effective in solving engineering design and optimization problems by numerous experiments to compute the FLA problem. And we use simplex algorithm to solve the sub-optimal problem (25) in uncertain expected value model. In this paper, we integrate the simplex algorithm, Monte Carlo simulation and genetic algorithm to produce a hybrid intelligent algorithm for solving the uncertain FLA model. We describe the algorithm as the following procedure:

From the potential region {( x , y ) |g _i ( x , y ) ≤0, i = 1, 2, …, n}, initialize pop _ size chro-mosomes $V_{k} = (x^{k}, y^{k}) = (x_{1}^{k}, x_{2}^{k}, \dots, x_{n}^{k}, y_{1}^{k}, y_{2}^{k},$ $\dots, y_{n}^{k})$ , k = 1, 2, …, pop _ size, which denote the locations of all the facilities.

Calculate the objective values U ^k for all chromosomes V _k, k = 1, 2, …, pop _ size by Monte Carlo simulation, where the simplex algorithm is used to solve (25) to get the optimal cost $C (x, y, Φ_{1}^{- 1} (α),$ $Φ_{2}^{- 1} (α), \dots, Φ_{m}^{- 1} (α))$ .

Compute the fitness of all chromosomes V _k, k = 1, 2, …, pop _ size. The rank-based evaluation function is defined as

$\begin{matrix} Eval (V_{k}) = β (1 - β)^{k - 1}, \\ k = 1, 2, \dots, pop_size \end{matrix}$ (26) where the chromosomes V ₁, V ₂, …, V _{pop_size} are assumed to have been rearranged from good to bad according to their objective values U ^k and β ∈ (0, 1) is a parameter in the genetic system.

Select the chromosomes for a new population. The selection process is based on spinning the roulette wheel characterized by the fitness of all chromosomes for pop _ size times, and each time we select a single chromosome. Thus we obtain pop _ size chromosomes, denoted also by V _k, k = 1, 2, …, pop _ size.

Renew the chromosomes V _k, k = 1, 2, …, pop _ size by crossover operation. We define a parameter P _c of a genetic system as the probability of crossover. This probability gives us the expected number P _c · pop _ size chromosomes undergoing the crossover operation.

Update the chromosomes V _k, k = 1, 2, …, pop _ size by mutation operation. The parameter P _m is the probability of mutation, which gives us the expected number of P _m · pop _ size chromosomes undergoing the mutation operations.

Repeat the second to the sixth steps for a given number of cycles.

Report the best chromosome V ^* = ( x ^*, y ^*) as the optimal locations.

5 A numerical example

Consider a company that wishes to locate four new facilities within the square region [0, 100] × [0, 100]. Assume that there are 20 customers whose demands ξ _i are zigzag uncertainty variables. The location (a _i, b _i) of the customer i is given in Table 1, i = 1, 2, …, 20. The capacities s _i of the four facilities are 100, 110, 120 and 130, respectively.

We choose 3 experts to give questionnaire surveys. The process is as follows:

Q1: May I ask you how many demand of customer 1 is? What do you think is the minimum demand?

A1: 13. (an expert’s experimental data (13,0) is acquired).

Q2: What do you think the maximum demand is?

A2: 17. (an expert’s experimental data (17,1) is acquired).

Q3: What do you think a likely demand is?

A3: 15.

Q4: What is the belief degree that the real demand is less than 15?

A4: 0.6. (an expert’s experimental data (15,0.6) is acquired).

Every expert will give the questionnaire surveys to every customer. After all the surveys, all the customers’ demands are shown in Table 2.

In the Delphi method, we set w = 1/3. Then we get the distributions of all the customers in Table 3.

In this example, Model (24) can be written as ${\begin{matrix} min_{x, y} \int_{0}^{1} C (x, y, Φ_{1}^{- 1} (α), Φ_{2}^{- 1} (α), \dots, Φ_{m}^{- 1} (α)) d α \\ subject to : \\ 0 \leq x_{i} \leq 100, i = 1, 2, 3, 4 \\ 0 \leq y_{i} \leq 100, i = 1, 2, 3, 4 \end{matrix}$ (27) where $C (x, y, Φ_{1}^{- 1} (α), Φ_{2}^{- 1} (α), \dots, Φ_{m}^{- 1} (α)) =$ ${\begin{matrix} min_{z} \sum_{i = 1}^{4} \sum_{j = 1}^{20} z_{ij} \sqrt{(x_{i} - a_{j})^{2} + (y_{i} - b_{j})^{2}} \\ subject to : \\ z_{ij} \geq 0, i = 1, 2, 3, 4, j = 1, 2, \dots, 20 \end{matrix}$ ${\begin{matrix} \sum_{i = 1}^{4} z_{ij} = Φ_{j}^{- 1} (α), j = 1, 2, \dots, 20 \\ \sum_{j = 1}^{20} z_{1 j} \leq 100 \\ \sum_{j = 1}^{20} z_{2 j} \leq 110 \\ \sum_{j = 1}^{20} z_{3 j} \leq 120 \\ \sum_{j = 1}^{20} z_{4 j} \leq 130 . \end{matrix}$ (28)

In Model (27), the goal wants to minimize the total costs and the constraints denote the square region [0, 100] × [0, 100]. In order to get the goal function $C (x, y, Φ_{1}^{- 1} (α), Φ_{2}^{- 1} (α), \dots, Φ_{m}^{- 1} (α))$ , model (28) is given. In model (28), the constraint $\sum_{i = 1}^{4} z_{ij} = Φ_{j}^{- 1} (α)$ implies that the total supply amounts can not exceed customer demand, j = 1, 2, …, 20. Otherwise, the waste of resources appears, which is not allowed in supply chain. The last four constraints express the capacities of the four facilities.

In order to solve Model (27), the hybrid intelligent algorithm is employed. Monte Carlo simulation has been run with 5000 cycles in every generation in GA. After 1000 generations in GA, we get the optimal results in Table 4. In Table 4, we compare solutions with different number of chromosomes pop _ size, different probability of crossover P _c and different probability of mutation P _m taken with the same stopping rule. It appears that all the minimal costs differ little from each other. The percent error of the last column can be expressed by (actual value - optimal value)/optimal value ×100%, where optimal value is the least one of all the ten minimal costs. It follows from Table 5 that the percent error does not exceed 1.6% when different parameters are selected, which implies that the hybrid intelligent algorithm is robust to the parameter settings and effective to solve Model (23).

6 Conclusion

In this paper, we have contributed to the research area of the FLA problem in the following three aspects.

(i) The expected value FLA model was proposed under uncertain environment, which can be converted to a crisp mathematical programming;

(ii) To solve the models efficiently, we integrated the simplex algorithm, Monte Carlo simulation and genetic algorithm to produce a hybrid intelligent algorithm.

(iii) A numerical example was provided to illustrate the expected value model and the performance of the hybrid intelligent algorithm.

Several further studies should be considered. For one thing, we will try to present other uncertain FLA models besides expected value model. In addition, we will try to apply the expected value FLA model to the actual case, and then modify this uncertain model. Moreover, we will give some researches to the hybrid FLA problem in which the randomness and fuzziness of the customers’ demands are mixed up with each other.

Acknowledgments

This work was supported by National Natural Science Foundation of China (Nos. 71201005, 71371019, 61104132), and in part by the Program for New Century Excellent Talents in University (No. NCET-12-0026).

References

Bhattacharya

Rao

Tiwari

1993

Bi-criteria multi facility location problem in fuzzy environment

Fuzzy Sets and Systems 56 145 153

Charnes

Cooper

1961 Management models and industrial applications of linear programming New York, Wiley

Chen

Wei

1998

An efficient fuzzy MADM method for selecting facility locations

Journal of Engineering Valuation and Cost Analysis 2 19 32

Chen

Liu

2010

Existence and uniqueness theorem for uncertain differential equations

Fuzzy Optimization and Decision Making 9 1 69 81

Cooper

1963

Location-allocation problems

Operational Research 11 331 344

Chernoff

1954

Rational selection of decision functions

Econometrica 22 422 443

Darzentas

1987

A discrete location model with fuzzy accessibility measures

Fuzzy Sets and Systems 23 149 154

Dantzig

1951

Maximiztion of linear function of variables subject to linear inequalities

Activity Analysis of Production and Allocation Koopman

339 347

Ernst

Krichnamoorthy

1999

Solution algorithms for the capacitated single allocation hub location problem

Annals of Operations Research 86 141 159

10.

Gao

2013

Cycle index of uncertain graph

Information: An International Interdisciplinary Journal 16 2(A) 131 138

11.

Gao

2013

Connectedness index of uncertainty graphs

International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 21 1 127 137

12.

Gong

Gen

Yamazaku

1995

Hybrid evolutionary method for obstacle location-allocation problem

International Journal of Computers and Industrial Engineering 29 525 530

13.

Hakimi

1964

Optimum locations of switching centers and absolute centers and medians of a graph

Oprations Research 12 450 459

14.

Hakimi

1965

Optimum distribution of switching centers in a communication network and some related graph theoretic problems

Operations Research 13 462 475

15.

Jayaraman

Pirkul

2001

Planning and coordination of production and distribution facilities for multiple commodities

European Journal of Operational Research 133 394 408

16.

Jiang

Yuan

2008

A heuristic algorithm for constrained multi-source Weber problem-The variational inequality approach

European Journal of Operational Research 187 357 370

17.

Klose

Drexl

2005

Facility location models for distribution system design

European Journal of Operational Research 162 4 29

18.

Kuenne

Soland

1972

Exact and approximate solutions to the multisource Weber problem

Mathematical Programming 3 193 209

19.

Logendran

Terrell

1998

Uncapacitated plant locationallocation problems with price sensitive stochastic demands

Computers and Operations Research 15 189 198

20.

Liu

2007 Uncertainty Theory 2nd

Berlin

Springer-Verlag

21.

Liu

2008

Fuzzy process, hybrid process and uncertain process

Journal of Uncertain Systems 2 1 3 16

22.

Liu

2009

Some research problems in uncertainty theory

Journal of Uncertain Systems 3 1 3 10

23.

Liu

2009 Theory and practice of Uncertain Programming 2nd

Berlin

Springer-Verlag

24.

Liu

2010 Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty Berlin

Springer-Verlag

25.

Liu

2010

Uncertain risk analysis and uncertain reliability analysis

Journal of Uncertain Systems 4 3 163 170

26.

Liu

Chen

2013

Technical Report

Uncertain multiobjective programming and uncertain goal programming

27.

B. Liu and K. Yao, Uncertain multilevel programming: Algorithm and application, http://orsc.edu.cn/online/120114.pdf

28.

Liu

2013

Extreme value theorems of uncertain process with application to insurance risk model

Soft Computing 17 4 549 556

29.

Liu

2010

Expected value of function of uncertain variables

Journal of uncertain Systems 13 181 186

30.

Megiddo

Supowit

1984

On the complexity of some common geometric location problems

SIAM Journal of Computing 13 182 196

31.

Murray

Church

1996

Applying simulated annealing to location-planning models

Journal of Heuristics 2 31 53

32.

Murtagh

Niwattisyawong

1982

Efficient method for the muti-depot location em dash allocation problem

Journal of the Operational Research Society 33 629 634

33.

Peng

Yao

2010

A new option pricing model for stocks in uncertainty markets

International Journal of Operations Research 7 4 213 224

34.

Revelle

Laporte

1996

The plant location problem: New models and research prospects

Operations Research 44 6 864 874

35.

Sabri

Beamon

2000

A multi-objective approach to simultaneous strategic and operational planning in supply chain design

OMEGA 28 5 581 598

36.

Wang

Gao

Guo

2012

Delphi method for estimating uncertainty distributions

Information: An International Journal 15 2 449 460

37.

Wen

Iwamura

2008

Fuzzy facility location-allocation problem under the hurwicz criterion

European Journal of Operational Research 184 627 635

38.

Zhou

2000

Uncapacitated facility layout problem with stochastic demands

Proceedings of the Sixth National Conference of Operations Research Society of China 904 911

39.

Zadeh

1965

Fuzzy sets

Information and Control 8 338 353

40.

Zeng

Wen

Kang

2013

Belief reliability: A new metrics for products’ reliability

Fuzzy Optimization and Decision Making 12 1 15 27

41.

Zhou

Liu

2003

New stochastic models for capacitated location-allocation problem

Computers & Industrial Engineering 4 111 125

42.

Zhou

Liu

2007

Modeling capacitated location-allocation problem with fuzzy demands

Computers & Industrial Engineering 53 3 454 468

43.

Zhou

2002

Fuzzy programming models for minimax location problem

Asian Journal of Information-Science-Life 1 3 231 240