Facility Location Problem Formulation Critical Thinking
^{1}School of Management, South-Central University for Nationalities, Wuhan 430074, China
^{2}Department of Automation, Wuhan University, Wuhan 430072, China
Copyright © 2013 Dandan Hu et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
In many services, promise of specific response time is advertised as a commitment by the service providers for the customer satisfaction. Congestion on service facilities could delay the delivery of the services and hurts the overall satisfaction. In this paper, congestion service facilities location problem with promise of response time is studied, and a mixed integer nonlinear programming model is presented with budget constrained. The facilities are modeled as M/M/c queues. The decision variables of the model are the locations of the service facilities and the number of servers at each facility. The objective function is to maximize the demands served within specific response time promised by the service provider. To solve this problem, we propose an algorithm that combines greedy and genetic algorithms. In order to verify the proposed algorithm, a lot of computational experiments are tested. And the results demonstrate that response time has a significant impact on location decision.
1. Introduction
Facility location is a critical decision for a wide range of public and private firms. For example, in public sectors, location decisions for fire stations, ambulances, and other emergency service centers relate directly to the safety of citizens’ lives and properties. In private sectors, industries need to locate warehouses, distribution centers, retail outlets, and so forth. These locating decisions concern both costs and competitiveness. In short, the success or failure of both public and private facilities partly depends on the locations chosen for these facilities. Facility location theory has been studied in various forms for hundreds of years. The study formally started by Weber to position a single warehouse [1]. Then, many traditional location models are proposed, including -median problem [2], covering problem [3, 4], and -center problem [2]. Following these early investigations, the studies of location theory become popular in recent years. Yang and Zhang [5] studied chain stores location problem with bounded linear consumption expansion function on paths. Yu et al. [6] expanded capacitated facility location problem with consideration of serve radius and economic benefit. Ma et al. [7] studied facility location problem, combined with the feature of demand. Liu et al. [8] presented a location model that assigns online demands to the capacitated regional warehouses. For a survey on models and methods, please see the book edited by Daskin [9] and the review done by ReVelle et al. [10].
The studies that mentioned above mainly concentrate on travel time, physical distance, or some other related travel cost. They assume that facilities are sufficiently large to meet any demand immediately. However, facilities could be congested frequently. To address this issue, congestion facility location problem begins to be considered since Maximum Expected Covering Location Problem (MEXCLP) by Daskin [11] who introduced this model in connection with the location of ambulances and assumed that the probability of each server being busy is predetermined. Then Marianov and Serra [12] introduced queueing theory to address the congestion facility location problems. They applied a constraint to ensure that there is at least a server available on demand with probability . Huang et al. [13] studied the connections of network that are modeled as M/G/1 queues. Decision variables include selecting connections, assigning flows to the connections and sizing their capacities. To solve this model, they developed an algorithm based on Lagrangian relaxation. Hu et al. [14] examined bi-objective model based on flow interception problem. The model is formulated from the view of M/M/c queuing system. Service quantity and quality are simultaneously considered as objectives. T. Drezner and Z. Drezner [15] studied the server distribution problem with the objective to minimize the combined travel time and waiting time at the facility for all customers. In their method, the distribution of demand among the facilities is governed by the gravity rule. Other references on the subject include [16–18].
In the literature described above, the models are developed with the objective of optimizing congestion indicators, such as waiting time [14, 15, 18], response time [17], work load [16], and relative congestion costs [13]. However, in many service sectors, congestion indicators are often specified by the service providers. For example, Marianov and Serra [12] considered that the waiting time-limit and queueing length-limit are predetermined.
In real life, response time is often a key competitive priority and represents the firm’s commitment for the customer satisfaction. Therefore, specific response time guarantees are often advertised. For examples, Yonghe King, famous for soya bean milk and youtiao, reduces its promised response time from 30 to 20 minutes to enhance its competitiveness. Some take away restaurants often give a discount of food if it is not served within promised time. Jingdong on-line mall promises that customers are able to receive goods within 24 hours after the orders. Within a few years’ competition, Jingdong has already taken a leading position in China. The similar situation is common in reality but has not been investigated thoroughly. To keep the promise, proper planning of the facilities is one of the most important actions for service providers. Ideally, the more the service resources they have, the shorter the response time the customer can get. However, due to budget limitation in real life, reasonable facilities location and servers allocation are needed. Therefore, developing a model that addresses this issue could be a main contribution for the current study.
In view of the above described, we consider that the response time-limit is predetermined, which is an important characteristic of our model that distinguishes from others. In this case the objective of model we propose is to maximize requests served within a constant response time in consideration of budget limitation. We concentrate on two parts which affect response time. Travel time is determined by the distance between the service facility and demand node. Sojourn time in facilities is affected by many issues, such as shortage in supply, service interruption (power cut or water cut), strike, and other accidents, but one of the most common is service congestion.
Many existing works [11–14, 16, 17] appoint the value of servers’ number at each location in advance. Ideally, the more servers deployed at one facility location, the more effective it could be, but in reality the increasing number of servers also leads to more costs, which is often an important concern for decision makers. Another contribution of our work is that servers’ number of each potential facility location could be determined endogenously by the proposed model.
Most closely related to the work in this paper is the study of Berman and Drezner [19]. They introduced an servers allocation problem. In contrast to the research by Berman and Drezner, there are two differences between their model and ours. First, there are different objectives. In their model, the objective function is to minimize average response time, simple and explicitly convex in the number of servers. In view of the reality of response time-limit, however, our goal is to maximize requests served within a given response time. It is much more complicated and needs further analysis. Second, more generalized constraints. Berman and Drezner assumed that facility location incurs no cost and the total number of servers is known in advance. This is not the case in our problem. We propose constrained budget on the facility location and servers. When location cost is zero, our constraints are reduced to theirs, that is; our constraints are more generalized.
With the consideration of the limited budget, the difficulty of our problem is to solve two contradicting objectives. On the one hand, it is desirable to locate facilities as many as possible so that total travel time for customers could be reduced. On the other hand, with locating costs increasing and budget constraint, the available budget for servers is decreasing, which leads to lower service efficiency and longer waiting time. Therefore, when the demand is high and the travel distance is relatively short, the solution is expected to include fewer facility locations and more servers at each location. When travel time is relatively long, the solution is expected to include more locations and fewer servers at each location. Thus the key to maximize demands satisfied within promised response time lies in the balance of servers’ costs and facilities location costs.
This paper is organized as follows. We formulate the problem and provide some analysis in Section 2. In Section 3, we present solution algorithms. Computational results and sensitivity analysis are included in Section 4. In the last section, we provide conclusions and suggestions for future research.
2. Formulation of the Model
In this section, to solve facility location problem with response time-limit, a mixed integer model is formulated. A service facility is modeled as an M/M/c queuing system. Customers arrive at the facility according to a Poisson process. Service time is exponentially distributed. Each facility has multiple servers and the number of servers is a decision variable in our model. It is assumed that services at different facilities are homogenous, which means that the efficiency of every server is the same. In real life, customers generally have no idea of congestion at each facility before they arrive at the service facility so they choose the closest facility. Location and servers both incur costs, and servers’ costs are assumed to be linear with the number of servers.
Now, we denote index sets by the following: (i) set of demand nodes, denoted by , (ii): set of candidate locations, denoted by .
Next, we denote parameters by the following: (i): demand at node , yielding to random Poisson distribution with parameter , (ii): sojourn time at facility , including waiting time and service time, (iii): response time of facility to demand node , (iv): response time that service facilities have promised, (v): travel time between facility and demand node , (vi): budget limitation, (vii): cost of candidate facility location , (viii): cost of unit server, (ix): average service rate per unit server.
The decision variables of the problem are (i)(ii)(iii): the number of servers at facility .
Given the previous definitions, the location model can be formulated as follows: subject to
The model has the objective of maximizing expected demand rates that are served within promised time . Constraints (2) ensure that facility can serve demand node only if facility is open. Constraints (3) guarantee that demand node is served by one and only one facility. Constraints (4) assure that each demand node is served by the closest open facility. Constraint (5) is a budget limitation, spending on location and servers. Parameter , which is a very large number in constraints (6), can be chosen as ( denotes the largest positive integral that is no more than ). Constraints (6) ensure that servers can be deployed at facility only if facility is open. Constraints (7) prevent infinite waiting time. Constraints (8) and (9) are binary constraints, and the last constraints preserve the positive integer restrictions on decision variables of the number of servers at each open facility.
Since service response time includes travel time and sojourn time , the objective function can be transformed as follows: Let , .
is a probability distribution function, denoting the probability that demand node ’s sojourn time at facility is not larger than . So the response time restriction in the objective function is transformed to the sojourn time restriction.
For further analysis, we introduce some queuing theory relevant to our research.
In an M/M/c queuing system, the following parameters are always known: : average service rate, : average arrival rate, : the number of servers.
Let and . , the probability that no demand sojourns in system, is denoted by
A Simulated Annealing Methodology to Multiproduct Capacitated Facility Location with Stochastic Demand
Jin Qin,^{ 1 ,}^{ * }Hui Xiang,^{ 1 ,}^{ 2 }Yong Ye,^{ 1 } and Linglin Ni^{ 3 }
^{1}School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China
^{2}School of Traffic and Transportation Engineering, Changsha University of Science & Technology, Changsha 410076, China
^{3}Business Administration College, Zhejiang University of Finance & Economics, Hangzhou 310018, China
*Jin Qin: moc.liamtoh@nijniq_usc
Academic Editor: Chih-Chou Chiu
Author information ►Article notes ►Copyright and License information ►
Received 2014 Jun 29; Revised 2014 Nov 23; Accepted 2014 Nov 28.
Copyright © 2015 Jin Qin et al.
This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
ScientificWorldJournal. 2015; 2015: 826363.
Published online 2015 Mar 5. doi: 10.1155/2015/826363
Abstract
A stochastic multiproduct capacitated facility location problem involving a single supplier and multiple customers is investigated. Due to the stochastic demands, a reasonable amount of safety stock must be kept in the facilities to achieve suitable service levels, which results in increased inventory cost. Based on the assumption of normal distributed for all the stochastic demands, a nonlinear mixed-integer programming model is proposed, whose objective is to minimize the total cost, including transportation cost, inventory cost, operation cost, and setup cost. A combined simulated annealing (CSA) algorithm is presented to solve the model, in which the outer layer subalgorithm optimizes the facility location decision and the inner layer subalgorithm optimizes the demand allocation based on the determined facility location decision. The results obtained with this approach shown that the CSA is a robust and practical approach for solving a multiple product problem, which generates the suboptimal facility location decision and inventory policies. Meanwhile, we also found that the transportation cost and the demand deviation have the strongest influence on the optimal decision compared to the others.
1. Introduction
The facility location problem (FLP) is one of the most important models in the combinatorial optimization problem, which is to determine the number and locations of facilities and allocate customers' demands to these discrete located facilities in such a way that the total cost is minimized. Due to its wide application in numerous contexts such as regional planning, telecommunication and transportation infrastructure deployment, and energy management, a lot of problem variants and theirs models, which capture features of the real facility location problems, have been developed in the literature since the original formulation in Weber's work [1].
The FLP is NP-hard, which can be classified in two categories as capacitated problem and uncapacitated problem according to whether it includes the capacity of facilities. The capacitated facility location problem (CFLP) assumes that each facility can produce or ship limited quantities of the product and the demand of each customer is satisfied without violating the capacity restriction of any facility, which makes the CFLP more widely used, but also brings a lot of complexities to the problem.
Daskin [2] and Melo et al. [3] provided thorough reviews of the CFLP models. And we could found that many past models have several common characteristics, such as deterministic demands, a single product. Obviously, these models are insufficient to cope with many realistic capacitated facility location problems. So many extensions to the basic problems have been proposed and studied extensively.
Stochastic capacitated facility location problems have been proposed to approach situations in which some parameters are uncertain or stochastic. And in reality the demands are typically stochastic, which would bring risk to the inventory management. In order to deal with the stochastic demands and improve the service level, managers often hold some products as stock, which can result in increased inventory cost. In many contexts where product safekeeping is expensive, the inventory cost may account for a significant portion of the total system cost. So measuring the trade-off between the inventory cost and the service level is naturally very important in the facility location decision. However, inventory costs were not typically considered in many FLPs.
Inventory management and facility location are all major issues in the efficient design of a logistics network or supply chain (Gunasekaran et al., 2001 [4]; Pahl and Voß, 2014 [5]). However, literatures on supply chain optimization have traditionally considered these issues independently (e.g., [6–15]), which are not only because of different planning horizon but because of the computational complexity of the joint optimization problem.
Shen et al. [16] proposed a joint location model and restructured it into a set-covering model, and solutions only for two special cases were discussed; one is that variance of demand is proportional to the mean and the other is that demand has zero variance. Shu et al. (2005) [17] developed a more efficiency algorithm for the special cases. Shen [18] simplified the inventory cost of the products as the nonlinear function of the product quantity to the objective function and proposed the Lagrange algorithm to solve the problem; Shen and Qi (2007) [19] analyzed the transportation cost combined with the vehicle routing in the logistics network, but the order number was considered as a continuous variable in the formulation derivation. Kutanoglu and Lohiya [20] regarded the inventory cost as the linear function of product quantity. Ozsen et al. [21, 22] and Sourirajan et al. [23] proposed two different extensions to the model in Shen et al. [16]. Chen et al. [24] optimized facility locations, customer allocations, and inventory management decisions when facilities were subject to disruption risks. Hui et al. [25] studied the location-inventory results with joint replenishment (JR) and independent replenishment (IR), respectively, and found that the JR policy can obtain better solutions than IR policy.
In this paper, we study the stochastic multiproduct capacitated facility location problem (SMCFLP) that seeks the optimal solutions to minimize the total cost, including the facility setup cost, order cost, day-to-day shipment cost, and inventory cost, in which the demands for multiproducts are stochastic and satisfy the normal distribution. An open facility could serve one or more customers, while each customer could only be allocated to exactly one facility. The present work is motivated by a study of a local delivery service at a machinery manufacturing enterprise.
The remainder of the paper is organized as follows. Section 2 presents some rational assumptions and notations of the SMCFLP. In Section 3, based on system cost analysis, we propose the model formulation that incorporates inventory control decision into multiproduct facility location problem with stochastic demand. In Section 4, an improved simulated annealing algorithm is developed to solve the model, and the setting of parameters is also discussed. In Section 5, the numerical example and the analysis of the results are given.
2. Notations and Assumptions
In formulating the optimization model, the following notations are used.
- i denotes the candidate facility sites, i = 1,2,…, I.
- j denotes the customer, j = 1,2,…, J.
- l denotes the product, l = 1,2,…, L.
- λ_{l} is the storage capacity occupation per unit product l.
- f_{i} is the fixed setup cost of facility i.
- V_{i} is the storage capacity of facility i.
- d_{j}^{l}, u_{j}^{l} are the mean and the standard deviation of the demand for product l of customer j, respectively.
- D_{i}^{l}, U_{i}^{l} are the mean and the standard deviation of the demand for product l of facility i, respectively.
- T_{i}^{l} is the lead time (in days); that is to say, the supplier takes the time T_{i}^{l} to fulfill an incoming order from facility i for product l.
- Q_{i}^{l} is the fixed order quantity per order.
- h_{i}^{l} is the inventory cost per unit of product l of facility i (per day).
- o_{i}^{l} is the fixed cost of placing an order for product l in facility i.
- r_{i}^{l} is the transportation cost per unit to ship product l from the supplier to facility i.
- t_{i}^{l} is the elapsed time between two consecutive orders for product l in facility i.
- c_{ij}^{l} denotes the distribution cost per unit product l between the facility i and the customer j.
- δ_{1}, δ_{2} are the weight factors associated with transportation cost and inventory cost, respectively.
- α is the united service level in the system, 0 < α < 1; namely, the fill rate of all demands for all products must not be less than α in all facilities.
- η is the bank interest rate.
- μ is discount rate (calculated by r).
- H is the planning horizon (in year).
- M is the maximum number of the facilities that are allowed to locate.
And we set two decision variables as
(1)
Note that if X_{i} = 0, no products will pass facility i and vice versa.
According to the definition of the notations, we could know that
And the fixed setup costs of the facilities f_{i}, for all i, are all disposable, and the other costs are always invested per day, so in order to keep the consistency of all costs in time, the fixed setup costs should be shared in day in the planning horizon. And according to the above definitions, the discount rate μ could be calculated as follows:
(3)
Some rational assumptions are proposed as follows.
Similar to Shen et al. [16], we assume that all stochastic customer demands d_{j}^{l}, for all j, l, are assumed to follow standard normal distribution and are independent of each other.
Each customer demand point is directly served by one and only one facility; namely, the demand of a customer could not be partitioned.
According to Shen et al. [16], we assume that all facilities have the same service level; in the other words, the fill rates for the demands in all facilities are identical in the system.
According to Ozsen et al. [22] and Chen et al. [24], we assume facility i, for all i using an economic order quantity (EOQ) model (P_{i}^{l}, Q_{i}^{l}) for inventory policy; that is to say, a fixed quantity Q_{i}^{l} is ordered to the supplier, once the inventory quantity falls to or is below a reorder-point P_{i}^{l}.
According to assumption (1), for the rest of the paper, we could get the following evident relations:
(4)
(5)
From assumption (1), we also could know that the demands of all facilities are also stochastic and follow the standard normal distribution.
3. Model Formulation
According to assumption (4), the facility i performs (P_{i}^{l}, Q_{i}^{l}) inventory policy to meet the stochastic demand pattern. But even if the order is triggered, the ordered products could be received after T_{i}^{l} days. So once an order is submitted, the inventory products should cover the demand produced during lead time T_{i}^{l} with a given probability α. This probability α is known as the level of service for the system or the fill rate for the demand. So the service level constraints in the facility i can be expressed as follows:
(6)
where D(T_{i}^{l}) is the stochastic demand for product l in facility i produced with the lead time T_{i}^{l}.
According to Shen et al. [16, 18], we could know the average inventory cost rate of product l in facility i as
(7)
where Z_{α} is the value of standard normal variate, which accumulates a probability of α.
The operation cost for product l in facility i during the period is
(8)
We could get the operation cost rate of product l in facility i, based on expression 9 divided by t_{i}^{l} (t_{i}^{l} = Q_{i}^{l}/D_{i}^{l}):
(9)
So the total operation cost rate is
(10)
The transportation cost rate of the entire system is
(11)
The total fixed setup cost of the system is
As mentioned before, the fixed setup cost is one-time expenditure in the planning horizon, but the other costs are counted by day, so the setup cost should be converted into day-cost in order to be consistent with all costs in unit:
(13)
Therefore, the total cost rate of the system is
(14)
The objective of the problem is to minimize the cost 15. But there are too many uncertain variables in it, which could make the solution approach difficult to be designed.
Assume that the cost function 15 is continuously differentiable on order quantity, then performing differentiation on it in terms of Q_{i}^{l}, for all i, l, and letting the derivation be equal to zero (minimizing the total cost in a centralized approach), we could obtain
(15)
Then we could get the optimal order quantity of product l per order in facility i as follows:
(16)
Replacing 4, 5, and 16 in expression 14, the cost function 15 can be expressed as follows:
(17)
So, we could present the model to solve the SMCFLP considering the inventory cost as follows:
(18)
subject to
(19)
(20)
(21)
(22)
(23)
(24)
The model would determine where to open facilities no more than M in I candidate sites and how to serve J customers with stochastic demand under service level constraint. The objective function 18 is to minimize the total system cost, including location cost, inventory cost, order cost, and transportation cost. Constraint 19 states that each demand must be only allocated to one facility. Constraint 20 ensures that the total demands allocated to a certain facility should not exceed its capacity. Constraint 21 restricts a demand only to be allocated to an open facility. Constraint 22 is the maximum restriction of the opened facilities. Constraints 23 and 24 are the standard integrality constraints, and Y_{ij}^{l} ∈ {0,1} representing single-sourcing constraints, which means that all of the demands of a customer must be assigned to the same facility.
4. Solution Approach
The above SMCFLP model 19–24 is a large-scale nonlinear mixed-integer programming model, which is NP-hard problem [16]. We were able to easily compute optimal solutions for small problem instances. However, as the number of products, number of facilities, and number of customers approach some practical size, the attractiveness of this methodology to provide optimal solutions to such practical sized problems in a reasonable amount of time deteriorates considerably. Its NP-hard nature makes the exact algorithms only for small problems and heuristics the natural choice for larger instances. There was a long list of works on designing heuristics algorithms for this problem over the years.
The Lagrangian method (Miranda and Garrido, 2008 [26]; Nezhad et al, 2013 [27]) and branch and bound algorithm [28, 29] are always used to solve the similar problem. But the Lagrangian method and branch and bound method are intuitive, inflexible, and complicated. In order to increase the adaptability of the solution method, we therefore began testing heuristic approaches to this combinatorial problem. Several approaches were tried including genetic algorithm (GA) and simulated annealing (SA) algorithm.
Kirkpatrick et al. [30] introduced the SA; then, it has proved to be an effective tool for approximating globally optimal solutions to many NP-hard optimization problems. We adopted the SA procedure because of its ability to quickly combine the facility location decision and inventory control decision into a single large problem. In the last 30 years, SA has been applied to many optimization problems in a wide variety of areas such as facility layout [31–33], job scheduling [34–36], and network design ([37–43]).
The solution of SMCFLP includes two parts, X_{i} and Y_{ij}, where X_{i} denotes whether or not to open the facility in site i and Y_{ij} denotes the service allocation of customers' demand. The two variables are interdependent and interactional. As each demand must be allocated to an opening facility, we could think that Y_{ij} is determined by X_{i}. This relation also can be seen from constraint 22 in the model.
According to the above characteristics of the problem, we could use the combined simulated annealing (CSA; [43]) algorithm to solve the model. The CSA works in two layers as the outer layer algorithm (OLA) and the inner layer algorithm (ILA), in which the OLA optimizes the facility location decision. Then, the ILA optimizes the demand allocation decision based on the determined facility location decision determined in the OLA. In each layer the SA is used and the combination of them is CSA.
It is well known that the neighboring function is crucial to the good performance of the SA. In the algorithm we should design different neighboring functions in OLA and ILA, respectively.
The OLA would optimize the facility location decision. So the neighboring function of the OLA to modify the configuration of the current solution and generate a neighboring solution could have three different operations.
If the number of the opened facility is less than the allowed maximum M, then select a candidate site i which satisfies X_{i} = 0 in current solution S randomly and set X_{i} = 1; namely, a facility is located in the site X_{i}.
If the number of the opened facility is no less than 1, then select a site i which satisfies X_{i} = 1 in current solution S randomly and set X_{i} = 0; namely, the opened facility as site X_{i} is closed.
Exchange two facilities with different status; namely, select a site i which satisfies X_{i} = 0 and another site i′ which satisfies X_{i′} = 1 in current solution S, and then set X_{i} = 1 and X_{i′} = 0.
In the implementation of the OLA, we could only select one operation from the above three operations to perform the neighboring function each time. And after implementing this OLA operation, it should allocate the customers' demand to the opened facilities again.
ILA is to determine the demand allocation decision. According to the features of the allocation decision, there are two operations to generate the neighboring solutions in the ILA.
Select two allocation variables Y_{ij}^{l} and Y_{ij′}^{l} that satisfy Y_{ij}^{l} = 1 and Y_{ij′}^{l} = 0; then set y_{ij′} = 1, y_{ij} = 0; namely, it allocates the demand of customer i for product l from facility j to another facility j′.
Exchange the facilities which service two customers, respectively, with each other. To be specific, select four allocation variables as y_{i1j1} = 1, y_{i2j2} = 1, y_{i1j2} = 0, and y_{i2j1} = 0; then set y_{i1j2} = 1, y_{i2j1} = 1, y_{i1j1} = 0, and y_{i2j2} = 0.
Similarly, the neighboring function of the ILA could select only one operation to perform each time. In addition, it should ensure that demands of all customers must be satisfied and the facilities have no capacity violations that exist in the neighboring solution. Otherwise, it should return to the old solution and reselect an operation to perform.
In addition, it is well known that the SA algorithm must start with an initial solution or with a solution produced using a heuristic. In this work, we use the randomly generated initial solution, which is similar to that in Qin et al. [43].
Let Φ(S) denote the objective function value (total cost) of solution S; then, the steps of the CSA could be given as follows.
Step 0 (initialization). Set the initial temperature t, the cooling rate ξ, the stop temperature t_{f}, and the maximum iteration number N at each temperature value. Set counter number K_{1} = 1, K_{2} = 1.
Step 1 (generate initial solution). The initial solution S could be generated by randomly allocating customers' demands to the facilities. Let the global optimal solution .
Step 2 (check feasibility). The method now checks the demand allocations to ensure no capacity violations exist. The demands of the customers are also checked. If the solution S is not feasible, we should return to Step 1.
Step 3 (generate a feasible neighboring solution). Perform the outer layer neighboring function on S, and get the new feasible solution S′.
Step 4 (perform ILA)
Step 4.1. Regard solution S′ as the initial solution and the current optimal solution in the ILA; then, generate the ILA neighboring solution S′′ based on solution S′.
Step 4.2. If Φ(S′′) < Φ(S′), then set S′ = S′′; otherwise, generate a random number ρ′ from (0,1), if ρ′ < exp(−(Φ(S′′) − Φ(S′))/t); then, set S′ = S′′.
Step 4.3. Increase the counter number as K_{2} ← K_{2} + 1.
Step 4.4. If K_{2} ≤ N, then go to Step 4.1; otherwise, set K_{2} = 1, stop the ILA computation, and return to the OLA.
Step 5 (update the global optimal solution). If , then set .
Step 6 (evaluate current solution and examine metropolis condition). If Φ(S′) < Φ(S), then set S = S′, or else generate a random number ρ ∈ (0,1), if ρ < exp[−(Φ(S′) − Φ(S))/(t)], set S = S′.
Step 7 (increment counters). One has K_{1} ← K_{1} + 1. If K_{1} ≤ N, then return to Step 3; otherwise, proceed to Step 8.
Step 8 (adjust temperature). Adjust temperature by the cooling rate ξ. Mathematically this is t ← t · ξ. And set K_{1} = 1; then return to Step 3.
Step 9 (convergence check). If the temperature t is greater than or equal to the given stopping value t_{f}, then go to Step 3; otherwise, stop the computation and output the optimal solution .
Note that Step 5 is to save the global optimal solution that has been searched so far in the algorithm. This operation does not take the acceptance probability into consideration. So the algorithm could avoid the missing of the global optimal solution possibly.
5. Numerical Examples
To evaluate the performance of CSA algorithm on the problem, several problems with different sizes were developed. We varied the values of several parameters of problem and heuristic. The problem parameters are described by the number of candidate facilities I, the number of customers J, and the number of products L. The heuristic parameter is described by the coiling rate ξ.
Here we use 20 instances with different sizes as benchmark problems. The stopping temperature value t_{f} = 0.0001. The planning horizon time H = 10 years, the bank interest rate η = 0.04, and the service level α in all facilities is equal to 0.95. The weight factor of the inventory cost and transportation cost is δ_{1} = 2 and δ_{2} = 1, respectively. The other data are drawn from the certain range randomly; for example, the capacity values of the facilities are chosen randomly from the range [10000, 20000].
The model and CSA were implemented in Visual C# 2008. Computational experiments were performed on the personal computer with CORE I5-3317U (1.7 Ghz) CPU and 4 G RAM.
The setting of different parameters and computational results of these instances are reported in Table 1. Each instance was computed 10 times and the optimal solution is chosen as the results (the OFV is the objective function value Φ).
Table 1
Computational results of different sizes.
It can be seen from Table 1 that the CSA could find the near optimal solutions for all instances with different sizes. It is clear that the bigger value of cooling rate could provide more benefit to the larger size problem.
The quality of the optimal solution found by the local search algorithm may be dependent on its initial solution. In order to test the model and the algorithm, we solved ten optimal solutions with different initial solutions for the largest instance, in which the system includes 18 candidate facility sites, 60 customers, and 5 products. Table 2 shows the data.
Table 2
Objective function value of initial and optimal solutions.
Computational results based on the ten different initial solutions are reported in Table 2. We can find that even the initial solutions are different, the objective functions values Φ of the optimal solutions obtained by the CSA algorithm are very close, and the gap between the maximal value (7592152.387) and the minimum value (7390387.970) is only 2.73%. Compared with the initial solutions, the optimal objective values have 15.28%~34.94% cost saving. So it can prove the proposed optimal model and algorithm is rational and available.
Figure 1 shows the change rate of OFVs when the service level α varied from 0.5 to 0.99. It is obvious that the OFVs increase when the service level rises. Also the greater the service level is, the faster the OFV increases. This case accords with the fact perfectly.
Figure 1
OFV versus service level α.
Figure 2 illustrates that the relative change rate of OFV, compared with all the unit transportation costs, the unit inventory costs, and the demand deviations, changes with the same magnitude, respectively. We could find that the transportation cost has the most impact on the system, and when its magnitude of change varied from –50% to 50%, the change rate of the OFV exceeds 90%, which is beyond the impaction of inventory cost and service level on the OFV by far. Meanwhile, the change rate of the OFV is about 12% when the demand deviation varied.
It should be noted that the result is found under the condition of the weight factor of the inventory cost δ_{1} twice as large as the weight factor of the transportation cost δ_{2}. So we could consider the transportation cost is the most important factor in the logistics system cost.
From the above analysis, we could find that the service level, the demand deviation, the inventory cost, and the transportation cost all could have influence on the total system cost, which are directly proportional to the cost. But the demand deviation and the transportation cost have more influence on the system cost in contrast with other factors. So from the managers' point of view, if they want to save their logistics system cost, they should pay more attention to selecting the most economic transportation mode and predict the demand more accurately.
6. Conclusions
In this paper, we analyzed the stochastic multiproduct capacitated facility location problem with stochastic demand and service-level constraint. A nonlinear mixed-integer programming model is proposed, in which the objective is to minimize the total system cost, including fixed facility setup cost, inventory cost, order cost, and transportation cost, under the precondition of satisfying the certain service level.
The CSA solution method is developed to solve the large-scale problem, which is divided into two layers: the outer subalgorithm and the inner subalgorithm. The outer subalgorithm optimizes the facility location decision, and the inner subalgorithm optimizes the demand allocation based on the determined facility location decision. This method divides the problem into two layers to be solved; that is to say, the solution space in each iteration random search of the algorithm is also divided into smaller parts; thus the probability of obtaining the optimal solution of the problem in each iterative computation is raised.
We offer two important contributions to the SA application. First, we extend the breadth of applications by studying a new facility location problem, involving multiproduct and stochastic demand. Second, we developed a bilevel SA algorithm to solve the problem, in which computational performance was systematically evaluated under a variety of problem scenarios and control parameter settings.
Computational results show the CSA is a robust and practical approach for solving a multiple product problem, which could provide scientific guidance for the stochastic multiproduct facility location problem. Furthermore, the influences of the parameters (service level, demand deviation, unit inventory cost, and unit transportation cost) on the total system cost are investigated. We found that transportation cost and the demand deviation could have more influence than the other factors on the total cost (or the optimal decision).
Acknowledgments
The work was supported by the National Natural Science Foundation of China (Grant no. 71101155) and Natural Science Foundation of Hunan Province (2015JJ2184).
Conflict of Interests
The authors declare that there is no conflict of interests regarding the publication of this paper.
References
1. Weber A. Theory of the Location of Industries. Chicago, Ill, USA: University of Chicago Press; 1957.
2. Daskin M. S. What you should know about location modeling. Naval Research Logistics. 2008;55(4):283–294. doi: 10.1002/nav.20284.[Cross Ref]
3. Melo M. T., Nickel S., Saldanha-da-Gama F. Facility location and supply chain management—a review. European Journal of Operational Research. 2009;196(2):401–412. doi: 10.1016/j.ejor.2008.05.007.[Cross Ref]
4. Gunasekaran A., Patel C., McGaughey R. E. A framework for supply chain performance measurement. International Journal of Production Economics. 2004;87(3):333–347. doi: 10.1016/j.ijpe.2003.08.003.[Cross Ref]
5. Pahl J., Voß S. Integrating deterioration and lifetime constraints in production and supply chain planning: a survey. European Journal of Operational Research. 2014;238(3):654–674. doi: 10.1016/j.ejor.2014.01.060.[Cross Ref]
6. Klose A., Drexl A. Facility location models for distribution system design. European Journal of Operational Research. 2005;162(1):4–29. doi: 10.1016/j.ejor.2003.10.031.[Cross Ref]
7. Xu D. C., Du D. L. The k-level facility location game. Operations Research Letters. 2006;34(4):421–426. doi: 10.1016/j.orl.2005.06.002.[Cross Ref]
8. Lin C. K. Y. Stochastic single-source capacitated facility location model with service level requirements. International Journal of Production Economics. 2009;117(2):439–451. doi: 10.1016/j.ijpe.2008.11.009.[Cross Ref]
9. Marín A. The discrete facility location problem with balanced allocation of customers. European Journal of Operational Research. 2011;210(1):27–38. doi: 10.1016/j.ejor.2010.10.012.[Cross Ref]
10. Wen M., Kang R. Some optimal models for facility location-allocation problem with random fuzzy demands. Applied Soft Computing. 2011;11(1):1202–1207. doi: 10.1016/j.asoc.2010.02.018.[Cross Ref]
11. Küçükdeniza T., Baray A., Ecerkale K., Esnaf Ş. Integrated use of fuzzy c-means and convex programming for capacitated multi-facility location problem. Expert Systems with Applications. 2012;39(4):4306–4314. doi: 10.1016/j.eswa.2011.09.102.[Cross Ref]
12. Rahmani A., MirHassani S. A. A hybrid firefly-genetic algorithm for the capacitated facility location problem. Information Sciences. 2014;283:70–78. doi: 10.1016/j.ins.2014.06.002.[Cross Ref]
13. Guastaroba G., Speranza M. G. A heuristic for BILP problems: the single source capacitated facility location problem. European Journal of Operational Research. 2014;238(2):438–450. doi: 10.1016/j.ejor.2014.04.007.[Cross Ref]
14. de Rosa V., Hartmann E., Gebhard M., Wollenweber J. Robust capacitated facility location model for acquisitions under uncertainty. Computers & Industrial Engineering. 2014;72:206–216. doi: 10.1016/j.cie.2014.03.009.[Cross Ref]
15. Kratica J., Dugošija D., Savić A. A new mixed integer linear programming model for the multi level uncapacitated facility location problem. Applied Mathematical Modelling. 2014;38(7-8):2118–2129. doi: 10.1016/j.apm.2013.10.012.[Cross Ref]
16. Shen Z.-J. M., Coullard C., Daskin M. S. A joint location-inventory model. Transportation Science. 2003;37(1):40–55. doi: 10.1287/trsc.37.1.40.12823.[Cross Ref]
17. Shu J., Teo C. P., Max Shen Z. J. Stochastic transportation-inventory network design problem. Operations Research. 2005;53(1):48–60.
18. Shen Z.-J. M. A multi-commodity supply chain design problem. IIE Transactions. 2005;37(8):753–762. doi: 10.1080/07408170590961120.[Cross Ref]
19. Shen Z. J., Qi L. Incorporating inventory and routing costs in strategic location models. European Journal of Operational Research. 2007;179(2):372–389. doi: 10.1016/j.ejor.2006.03.032.[Cross Ref]
20. Kutanoglu E., Lohiya D. Integrated inventory and transportation mode selection: a service parts logistics system. Transportation Research E: Logistics and Transportation Review. 2008;44(5):665–683. doi: 10.1016/j.tre.2007.02.001.[Cross Ref]
21. Ozsen L., Coullard C. R., Daskin M. S. Capacitated warehouse location model with risk pooling. Naval Research Logistics. 2008;55(4):295–312. doi: 10.1002/nav.20282.[Cross Ref]
22. Ozsen L., Daskin M. S., Coullard C. R. Facility location modeling and inventory management with multisourcing. Transportation Science. 2009;43(4):455–472. doi: 10.1287/trsc.1090.0268.[Cross Ref]
23. Sourirajan K., Ozsen L., Uzsoy R. A genetic algorithm for a single product network design model with lead time and safety stock considerations. European Journal of Operational Research. 2009;197(2):599–608. doi: 10.1016/j.ejor.2008.07.038.[Cross Ref]
24. Chen Q., Li X., Ouyang Y. Joint inventory-location problem under the risk of probabilistic facility disruptions. Transportation Research B: Methodological. 2011;45(7):991–1003. doi: 10.1016/j.trb.2011.04.004.[Cross Ref]
25. Hui Q., Lin W., Rui L. A contrastive study of the stochastic location-inventory problem with joint replenishment and independent replenishment. Expert Systems with Applications. 2015;42(4):2061–2072. doi: 10.1016/j.eswa.2014.10.017.