# Lagrangian Relaxation for an Inventory Location Problem with Periodic Inventory Control and Stochastic Capacity Constraints

Authors: Claudio Araya-Sassi; Pablo A. Miranda; Germán Paredes-Belmar
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

We studied a joint inventory location problem assuming a periodic review for inventory control. A single plant supplies a set of products to multiple warehouses and they serve a set of customers or retailers. The problem consists in determining which potential warehouses should be opened and which retailers should be served by the selected warehouses as well as their reorder points and order sizes while minimizing the total costs. The problem is a Mixed Integer Nonlinear Programming (MINLP) model, which is nonconvex in terms of stochastic capacity constraints and the objective function. We propose a solution approach based on a Lagrangian relaxation and the subgradient method. The decomposition approach considers the relaxation of different sets of constraints, including customer assignment, warehouse demand, and variance constraints. In addition, we develop a Lagrangian heuristic to determine a feasible solution at each iteration of the subgradient method. The proposed Lagrangian relaxation algorithm provides low duality gaps and near-optimal solutions with competitive computational times. It also shows significant impacts of the selected inventory control policy into total system costs and network configuration, when it is compared with different review period values.


---

## Body

## 1. Introduction

Aggressive competition and strong economic turbulence in today’s global markets drive companies to improve the performance of their supply chains in order to achieve a sustainable competitive advantage. The performance of a supply chain depends strongly on its design. Hence the managers’ focus is there. In this context, supply chain network design (SCND) is a widely studied problem, which currently plays an important role in supply chain management and logistics [1, 2]. SCND consists of locating plants, warehouses, and distribution centers, allocating customers to open facilities while minimizing system-wide costs and satisfying service level requirements. Historically, the SCND problem has been tackled through a sequential approach that omits related tactical and operational decisions (e.g., inventory control, fleet design, and warehouse design). In this way, the omitted decisions are addressed after SCND has been solved. This means that strategic decisions, like the facility location, are made without regard to tactical decisions such as inventory control policy. This implies obtaining suboptimal SCND configurations because tactical decisions are subordinates to this network design [3].This paper is focused on a three-level supply chain, where a single plant serves a set of warehouses, as Figure1 shows. This set of warehouses serves a set of end retailers in a single commodity scenario. Unlike major previous inventory location models that assume a continuous review policy for warehouse inventory control, we use a periodic review policy (R,s,S) for each warehouse, where R is the period review, s is the reorder point, and S is the inventory objective level.Figure 1
Representation of a distribution network of three stages.Thus, we study an inventory location model, in which stochastic inventory capacity constraints, expected inventory, and ordering costs are defined using a periodic review strategy. We formulate this inventory location model with periodic review control using an analysis of the expected safety stock, cyclic inventory and order quantities, and peak inventory levels for each potential warehouse. This MINLP model is NP-hard because it is an extension of the Capacitated Facility Location Problem (CFLP), which is already NP-hard.Considering the high complexity of the analyzed problem, we propose an approximate solution approach based on Lagrangian relaxation and the subgradient method. The decomposition approach considers the relaxation of a different combination of problem constraints, including customer assignment, warehouse demand, and variance constraints. Then, we decompose the relaxed problem in a subproblem for each warehouse, which in turn is disaggregated in an inventory and location subproblem. In addition, a Lagrangian heuristic is developed to achieve a feasible solution at each iteration of the subgradient method. This Lagrangian heuristic is made up of warehouse selection and retailers greedy assignment, followed by local search improvements. We solve instances up to 20 potential warehouses and 40 retailers. The Lagrangian relaxation algorithm proposed in this paper provides low duality gaps and near-optimal solutions with competitive computational times. These results imply that this solution approach may be used in larger problem instances and more complex inventory location problems (ILP) as multicommodity and multiperiod formulations. In addition, the inclusion of periodic review policy in this model is relevant for those companies in which a continuous review policy is not feasible or there is a need to reduce costs for the inventory control system, especially for items in high demand. Considering all these attributes, ILP models could represent more accurately the complexity faced by distribution companies today.This paper is organized as follows. In Section2, we review the literature related to inventory location models. In Section 3, we discuss inventory control and capacity constraint issues. In Section 4, we present the formulation of the inventory location model with periodic review and stochastic capacity constraints. Section 5 presents the proposed solution approach based on Lagrangian relaxation. Section 6 presents and analyzes the numerical results. Finally, Section 7 presents conclusions, managerial insights, and suggestions for future research.


## 2. Literature Review

Over the last twenty years, several authors have studied how the inventory control decisions impact the Facility Location Problem (FLP) through the different integrated inventory location models. Barahona and Jensen [4] present an integer programming (IP) model for the location of a plant with cycle inventory costs, that is, the inventory required to satisfy the demands between two consecutive orders. These inventory costs are incorporated into the objective function as parameters, constituting a third term that is added to the fixed facility costs and transportation costs of Uncapacitated Fixed Charge Location Problem (UFLP). The linear relaxation of the model is solved through Dantzig-Wolfe decomposition. Nozick and Turnquist [5] develop a linear approach to the safety stock of a set of products based on the number of distribution centers through a simple linear regression. This allows safety stock costs to be directly included in the fixed cost coefficient of the UFLP. The resolution of the model is carried out through a hybrid heuristic established by Daskin [6]. Using the same previous framework, Nozick and Turnquist [7] expand their analysis by now considering a two-tier system (plant or central warehouse and DCs), where decisions are made considering whether products should have safety stock on the DCs or at the plant. Nozick and Turnquist [8] modify the previous formulations [5, 7] and now present a maximum covering location model, which ensures finding a proportion of the demand that meets a specific “coverage” distance of a DC. Later, using the approach proposed by Nozick and Turnquist [5], Lin et al. [9] solve a strategic design model of a multilevel and multiproduct distribution system, incorporating economies of scale in transportation and safety stock levels of the various products that are kept on the DCs through a greedy heuristic. All the previous models presented incorporate the operation stock and safety stock costs indirectly in the objective function and therefore, a linear term is added to it, so these models are classified as mixed integer programming models (MIP).Erlebacher and Meller [10] are the first researchers to formulate a MINLP to address the ILP, in which the locations of the clients are continuously represented. Later Daskin et al. [11] present a location model of DCs that incorporate working and safety inventory costs, extending the UFLP model. In addition, the model includes transport costs from suppliers to DCs that explicitly combine economies of scale into a fixed cost term. The model is formulated as MINLP, where the average demand and total variance served by the DCs are calculated as the sum of the average demands and variances of the clients assigned to them, respectively. These average demands of the DCs are incorporated directly into the objective function through the economic order quantity (EOQ) expression, which in turn structures the working inventory costs. The variances of demand give the expression of the safety stock costs. It should be noted that they consider the ratio between the average demand and the variance of all customers constant, which simplifies the resolution of the problem. The authors propose a Lagrangian relaxation solution algorithm, in which they relax the restrictions of allocation customers to DCs. Shen et al. [12] restructure the model of Daskin et al. [11] as an IP model of Set-Covering; then they solve though branch-and-price approach, a variant of branch-and-bound in which nodes are processed by solving linear relaxations through column generation. Shu et al. [13] modify the model of Shen et al. [12], incorporating a generalization of the assumption that the demands and variances of the clients are proportional, making it more realistic. Similar to Shen et al. [12], they first restructure the model as a Set-Covering problem and solve it with the branch and price method, but making it more efficient. Snyder et al. [14] present a stochastic programming version of the Daskin et al. [11] model, where allocation decisions are made under random parameters such as the average daily demand and variance of the average demand of each retailer, which are described by discrete scenarios. The model minimizes the total expected cost (including location, transportation, and inventory costs) of the system in all scenarios. The location model explicitly handles the effects of economies of scale and risk pooling that result from the consolidation of inventory sites. They present an algorithm based on Lagrangian relaxation, which, as Daskin et al. [11] and Shen et al. [12], relaxes allocation constraints.Miranda and Garrido [15] solve SCND through a simultaneous approach and incorporate inventory control decisions (EOQ and safety stock) within a CFLP, considering a stochastic demand distributed in a normal form, also modeling the phenomenon of risk pooling. This MINLP model is called a distribution network design model with risk pooling (DNDRP). The DNDRP includes, as constraints, the calculation of the total demands and variances served by each DC. This contrasts with the formulation of Daskin et al. [11], Shen et al. [12], Snyder et al. [14], and Ozsen et al. [16, 17], which incorporate them directly into the objective function through operation inventory costs and safety stock costs, respectively. Another difference between the models mentioned above is that Miranda and Garrido [15] do not explicitly consider economies of scale in transport costs. The deterministic capacity constraint of the DCs is formulated as described by Daskin [6]. The authors do not consider any assumption that may restrict the relationship between customer demands and variances.The traditional deterministic capacitated location models do not consider inventory decision, and therefore capacity is typically calculated in an exogenous manner. As a result, to count enough inventory capacity, additional DCs must be installed. However, by ordering more frequently, we could have a lower average stock level and therefore lower costs. The papers that most resemble our work are the CFLP with stochastic inventory capacity and risk pooling proposed by Miranda and Garrido [18, 19] and Ozsen et al. [16, 17]; however, we consider a periodic review inventory control policy. Miranda and Garrido [18] use the same framework introduced in Miranda and Garrido [15] replacing the deterministic inventory capacity constraint in DCs by a stochastic constraint based on chance constrained programming. This constraint ensures that the inventory capacity for each DC is at least with respect to one1-β probability. Additionally, they incorporate an order quantity restriction for each DC. One of the relevant conclusions of the modeling approach that they propose is that a decrease in the inventory capacity does not certainly imply an increase in the number of opened warehouses. In fact, decreasing the order size allows the optimal allocation of customers (those with more significant variances) in different warehouses, reducing the total cost of the system. Miranda and Garrido [19] use the same formulation of Miranda and Garrido [18]; nevertheless, the authors explain in detail the exact method of resolution to find solutions to the subproblems of each warehouse. This procedure is based on the incorporation of a constraint that represents a set of inequalities valid for Di and Vi, where Ω is the domain of all the possible values of each combination of clients. The authors present a heuristic approach based on Lagrangian relaxation and the subgradient method. They relax the demand and variance constraints of DCs and allocation constraints. Lagos et al. [20] consider the Miranda and Garrido [18] model and solve it using a hybrid algorithm combining Ant Colony Optimization (ACO) and Lagrangian relaxation. They use ACO to assign clients to a subset of stores that is previously generated by Lagrangian relaxation. The results show that the hybrid approach is quite competitive, obtaining almost optimal solutions within a reasonable time.The study by Ozsen et al. [16] is based on the model of Daskin et al. [11] to formulate a capacitated location model with risk pooling (CLMRP). The model captures the interdependence between capacity and inventory management in DCs. They assume that there is no correlation between daily retailer demands and that it follows a Poisson process [11, 12, 14]. This implies that the variance of the daily demand is equal to the daily demand average for each retailer. The model simultaneously determines warehouse locations, order sizes from the plant to warehouses, working and safety stock levels at warehouses, and the allocation of retailers to the warehouses. Similar to Miranda and Garrido [18, 19], the inventory capacity constraint is stochastically modeled by chance constrained programming. The authors propose a Lagrangian relaxation solution algorithm, in which they relax the allocation constraints, offering low gaps with moderate computational requirements for large-scale instances. Ozsen et al. [17] slightly modify the formulation developed by Oszen et al. [16], allowing retailers to be supplied by more than one DC on a probabilistic basis.Jin et al. [21] propose a simultaneous localization and inventory model with multiple products. The model is formulated as the Capacitated P-Median Problem (CPMP). They assume that the stochastic demands of retailers are normally distributed. The model is formulated as a MINLP and solved through a combined simulation annealing algorithm (CSA). Chen et al. [22] discuss a reliable ILP, where facilities are subject to disruption risks. When a facility fails, customers can be reassigned to a different facility that exists to avoid high costs associated with loss of services. They propose a MINLP that minimizes the sum of installation costs, expected inventory costs, and costs expected under normal and breakdown states. They develop a Lagrangian relaxation solution framework, including an exact algorithm for relaxed nonlinear subproblems.Several recent studies, including Atamtürk et al. [23], Shahabi et al. [24], and Schuster and Tancrez [25], have reformulated ILP with uncertain demand as Conic Quadratic Mixed-Integer Program (CQMIP). Atamtürk et al. [23] propose a joint inventory location model with stochastic demand considering various cases with uncapacitated and capacitated facilities, correlated retailer demand, stochastic lead times, and multiple products. Later, Shahabi et al. [24] study a location problem with a three-level inventory, where the demand for retailers is assumed to be correlated. Besides, they propose a solution approach, based on an external approximation algorithm, which shows the advantage of using this methodology. Finally, the authors show that the omission of the effect of correlation can lead to substantially suboptimal solutions. Schuster and Tancrez [25] provide a nonlinear continuous formulation that integrates location, order, inventory, and assignment decisions and includes transport, cycle, and safety stock costs. Then, considering that the model becomes linear when specific variables are fixed, they propose a heuristic algorithm that solves the resulting linear program. Finally, they use the solution to improve the estimates of variables for the next iteration. In order to show the efficiency of the algorithm, they compare their results with those of Atamtürk et al., 2012 [23]. They conclude that safety stock and risk pooling in retailers affect the design of a supply chain.Petridis [26] addresses the optimal design of a multiproduct and multistep supply network under demand uncertainty. The system consists of multiproduct production sites, warehouses, and distribution centers and decisions are made regarding the selection of facilities and their capacity. Also, decision variables are based on the flow of products transferred and safety stock in each distribution center. The delivery time of an order to a customer is calculated, using the probabilities of excess and deficit of inventory. All these decisions are incorporated in a single period, configuring a MINLP. The author explores linearization techniques for the highly nonlinear terms selected from the models, reducing the computational effort for the solution of the model. Qu et al. [27] propose an ILP with stochastic demand through the application of two replacement policies, joint replenishment (JR) and independent replacement (IR). They solve the problem through three algorithms: Genetic Algorithm (GA), Evolutionary Differential Hybrid Algorithm (HDE), and Hybrid Self-adapting Evolutionary Differential Hybrid Algorithm (HSDE). Their computational results show the effectiveness of these algorithms. The results of the ILP suggest that the policy of JR can obtain better solutions regarding costs than the IR policy, due to the fixed ordering costs being shared in the same order.All the previous papers and their associated analyzed models tended to focus on the ILP with inventory continuous review policy (s, S), rather than inventory periodic review policy. Yao et al. [28] discuss the latter of the two. They study a problem of location and inventory that incorporates multiple sources of warehouses, similar to that of Ozsen et al. [17]. In this problem, the multiple products are produced in several plants. The problem is formulated as a MINLP model. Berman et al. [29] incorporate a (R, S) periodic review inventory policy in the formulation of a coordinated inventory location model, where the choice of revision intervals in the DCs achieves coordination of the system. They present two types of coordination: total coordination, where all DCs have the same interval of review, and partial coordination, where each DC can choose its own review interval. While total coordination increases location costs and inventory costs, it is likely to reduce overall system operating costs, i.e., if operational costs such as scheduling delivery are taken into account. The problem is determining the location of the DCs, the allocation of retailers to the DCs, and the parameters of the inventory policy of the DCs, so that the total cost of the whole system is minimized. The model is formulated as a nonlinear integer programming problem and they solve it through an efficient Lagrangian relaxation algorithm. The results of their computational experiments and case study suggest that the increased costs due to full coordination, compared to partial coordination, are not significant. Therefore, total coordination, while making the model more practical, is economically justifiable. Cabrera et al. [30] formulate a novel joint localization and inventory model including a stochastic capacity constraint based on an Inventory Location Model Periodic Review (ILM-PR) inventory control policy. One of the modifications that they make regarding the continuous review policy is the incorporation of the undershoot concept that has not been considered in the previous ILP models. Based on this, they design a distribution network for a two-tier supply chain, quantifying the impact of the inventory control period review on the configuration costs of network and system. They do this considering both warehouse location and customer allocation decisions. To solve the problem they apply two heuristics, Tabu Search and Particle Swarm Optimization (PSO). According to the authors, this methodology shows an effective convergence rate. This confirms that inventory control policy decisions have an effect on the design of the distribution network. Vahdani et al. [31] consider an ILP in a three-tier supply chain, where it is assumed that retailer demand is correlated and inventory shortage is allowed. The inventory periodic review control policy is utilized. In order to solve the joint ILP, they propose an optimization model based on MINLP, where the objective function is the minimization of total costs of the supply chain. To solve this MINLP model, they present a GA and a simulated annealing (SA) algorithm. Since the performance of the metaheuristic algorithms depends on the configuration of the parameters, the Taguchi method is used to establish the parameters of the indicated algorithms. Finally, the algorithms proposed by the authors are used in several numerical instances that indicate a better GA performance compared to the SA.


## 3. Inventory Control Policy and Total System Cost

In this section, we discuss inventory control and capacity constraint issues involved in a periodic review policy within the facility location modeling structure with stochastic demand. We will use the methodology proposed by Miranda and Cabrera [32] and Cabrera et al. [30]. When a periodic review is taken into account in an (si, Si, Ri) inventory control policy, capacity constraints cannot be stated at any moment. In an (si, Si, Ri) inventory control policy, inventory levels are reviewed afterRi periods for each warehousei. Note that this parameter could be optimized; however, in the present research, it is fixed. In addition, if the inventory level is lower than the levelsi, then an order is placed to reach the objective levelSi. Consequently, order size for each warehousei must consider the well-known undershoot magnitude (USi), which is the number of items required to be ordered in addition toSi-si, in order to reachSi units of inventory, as shown in Figure 2. In other words, theUSi is the difference between the reorder pointsi and the inventory level directly prior to ordering.Figure 2
Inventory levels under an (s, S, R) control policy.For a given review periodRi, demand mean, and variance of a warehouse i (Di and Vi), the average undershoot magnitude is computed as follows [33]:(1)USiDi,Vi=Vi2·Di+DiRi2Peak inventory levels are not controlled at any moment, solely in specific moments for each review period. This peak inventory level is reached only when orders arrive at the warehouse, LTi time units after the previous order, and only if an order was submitted to the central warehouse or plant. Accordingly, each time an order arrives at a warehouse the inventory level is (2)si-USi+Si-si+USi-SDiLTi=Si-SDiLTiWhen an order is submitted to the plant, it is required that total inventory position reaches the level Si, and LTi later; inventory level is reduced by lead time demand SDi(LTi). Similar to Miranda and Garrido [18, 19], we propose that this inventory capacity constraint must be reviewed for each peak inventory instant (i.e., for each order period) with a fixed and known probability1-β, but now assuming a periodic review, as follows:(3)PrSi-SDiLTi≤ICap=1-βThis constraint is reformulated as a deterministic nonlinear constraint, which guarantees that the probabilistic constraint is fulfilled: (4)Si≤ICap+Di·LTi-Z1-βVi·LTiWe specify the minimum order size as Qi:(5)Si=si+Qi↔Qi=Si-siIn consequence, constraint (4) can be written as(6)Qi+si≤ICap+Di·LTi-Z1-βVi·LTiFinally, the reorder point si is set in order to ensure that an order is not submitted at each moment in time (i.e., inventory level is larger than si). The inventory level must be enough to fill demand until the next order has arrived Ri+LTi time units, with a probability or service level 1-α:(7)PrSDiRi+LTi≤si=1-αSimilar to (3), this constraint is reformulated as a deterministic nonlinear constraint:(8)si=Di·LTi+Ri+Z1-α·LTi+RiViFinally, replacing (8) in (6), the inventory capacity constraint for each warehouse i can be written as(9)Qi+DiRi+Z1-αLTi+Ri+Z1-βLTiVi≤ICapBased on a periodic (si,Si,Ri) inventory control policy, the safety stock to be included in the objective function is the average inventory level just before an order arrives at the warehouse:(10)si-USi-DiLTi=DiRi+Z1-α·LTi+RiVi-USiDi,ViIn addition, expected inventory and ordering costs related to order quantity or cycle inventory are evaluated in terms of the minimum order quantity Qi and the average undershoot USi, as in EOQ model:(11)OCi·DiQi+USiDi,Vi+HCi·Qi+USiDi,Vi2


## 4. Model Formulation

In this section, according to the previous inventory control assumptions, the Inventory Location Model with Stochastic Constraints of Inventory Capacity under Periodic Review (ILM-SCC-PR) is presented as a Stochastic Non-Linear Non-Convex Mixed Integer Programming (SNL-MIP) model. In this model, we tackle the problem of storage and delivery of a single product from a single plant or central warehouse to a collection of retailers through a set of candidate warehouses while minimizing the total system cost.The parameters of the model are as follows:N: number of available sites to install warehousesM: number of customers to be servedRCi: transportation unit cost between the plant and the warehouse i ($/unit)TCij: fixed transportation cost between the warehouse i and the customer jFi: operating fixed cost for each warehouse i ($/day)HCi: holding cost per time unit at site i ($/day)OCi: fixed ordering cost per time unit at site i ($/day)LTi: deterministic lead time when ordering from warehouse idj: mean of the daily demand for each customer jvj: variance of the daily demand for each customer jvj: variance of the daily demand for each customer jZ1-α: value of the standard normal distribution, which accumulates a probability of 1-αZ1-β: value of the standard normal distribution, which accumulates a probability of 1-βQCapi: order capacity of the warehouse iICapi: inventory capacity of the warehouse iThe variables considered in the mathematical formulation are as follows:X i: it takes the value 1, if a warehouse is located on site i, and 0 otherwiseY i j: it takes the value 1, if warehouse i serves customer j, and 0 otherwiseQ i: order size at the warehouse i (units)D i: served demand by each warehouse i (units)V i: variance of the served demand by each warehouse iConsequently, the SNL-MIP model to solve the problem is(12)min∑i=1NFiXi+∑i=1N∑j=1MRCidj+TCijYij+∑i=1NOCiDiQi+USiDi,Vi+HCiQi+USiDi,Vi2+∑i=1NHCiDiRi+Z1-αLTi+RiVi-USiDi,Vi(13)s.t.:∑i=1NYij=1∀j=1,…,M(14)Yij≤Xi∀i=1,…,N,∀j=1,…,M(15)Qi+DiRi+Z1-αLTi+Ri+Z1-βLTiVi≤ICapi·Xi∀i=1,…,N(16)Qi+USiDi,Vi≤QCapi∀i=1,…,N(17)Di=∑j=1MdjYij∀i=1,…,N(18)Vi=∑j=1MvjYij∀i=1,…,N(19)USiDi,Vi=Vi2·Di+DiRi2∀i=1,…,N(20)Xi,Yij∈0,1∀i=1,…,N,∀j=1,…,MThe objective function (12) minimizes the total system cost. The first term is the fixed and operating costs when opening warehouses. The second term is the transportation cost between each warehouse and its allocated customers, plus the transportation and ordering costs between the plant and warehouses. The third term contains fixed and inventory costs related to warehouse order size. The fourth term represents the storage cost associated with safety stock at each warehouse. Constraints (13) ensure that each customer is served exactly by one warehouse. Constraints (14) state that customers can only be assigned to open warehouses (Xi=1). Constraints (15) ensure that inventory capacity for each warehouse is fulfilled at least with a probability 1-β. Constraints (16) ensure that the order size is below the capacity order size allowed to warehouse i. Equations (17) and (18) determine the mean and variance of the served demand by each warehouse. Equations (19) calculate average undershoot magnitude for each warehouse. Finally, (20) indicates the domain of decision variables.The objective function and the two stochastic constraints are nonlinear, resulting in a model that is very hard to solve for large-scale instances. The complexity of the problem motivated us to propose a heuristic approach to solve it. An explanation of the algorithm is described in the next section.


## 5. Solution Approach

Most of the conventional location models have been solved successfully by Lagrangian relaxation-based heuristics. Fisher [34, 35] provides a detailed analysis of Lagrangian relaxation. Likewise, Daskin [6] applies the same solution approach to solve the UFLP and the CFLP obtaining reasonably good results. Because ILM-SCC-PR is an extension of the UFLP, we implement a Lagrangian relaxation algorithm and subgradient method to solve it. We develop two relaxations to solve the ILM-SCC-PR. First, we relax constraints (17) and (18), decoupling binary network design variables (X andY) from inventory control decisions (Q) and mean and variance for demand (D andV) in each warehouse. In addition, we relax customer assignment constraints (13), similar to several Lagrangian relaxation applications for standard FLP and ILP. Second, we relax only constraints (17) and (18).


### 5.1. First Lagrangian Relaxation Algorithm

Associating the dual variables vectorsλ and ω with the constraints (17) and (18), respectively, and ψ with constraint (13), we obtain the following relaxed problem:RLP1(21)min∑i=1NFiXi+∑i=1N∑j=1MRCi+λidj+TCij+ωivj-ψjYij+∑i=1NOCiDiQi+USiDi,Vi+HCiQi+USiDi,Vi2+∑i=1NHCiDiRi+Z1-αLTi+RiVi-USiDi,Vi-∑i=1NλiDi+ωiVi+∑j=1Mψjs.t.:Yij≤Xi∀i=1,…,N,∀j=1,…,MQi+DiRi+Z1-αLTi+Ri+Z1-βLTiVi≤ICapi·Xi∀i=1,…,NQi+USiDi,Vi≤QCapi∀i=1,…,NUSiDi,Vi=Vi2·Di+DiRi2∀i=1,…,NXi,Yij∈0,1∀i=1,…,N,∀j=1,…,MFor fixed values of the Lagrangian multipliers, λ, ω, and ψ, we minimize (21) over location variables, Xi, and the assignment variables Yij. For the given λ, ω, and ψ vectors, the problem decouples to the following subproblem for each warehouse i:SPi(22)minFiXi+∑j=1MRCi+λidj+TCij+ωivj-ψjYij+OCiDiQi+USiDi,Vi+HCiQi+USiDi,Vi2+HCiDiRi+Z1-αLTi+RiVi-USiDi,Vi-λiDi+ωiVis.t.:Yij≤Xi∀j=1,…,MQi+DiRi+Z1-αLTi+Ri+Z1-βLTiVi≤ICapi·XiQi+USiDi,Vi≤QCapiUSiDi,Vi=Vi2·Di+DiRi2Di,Vi∈ΩXi,Yij∈0,1∀j=1,…,MWe include a set of valid inequalities (Di,Vi)∈Ω to solve previous subproblems and to reduce duality gaps by increasing upper bounds. Valid inequalities are defined as a set of constraints, which bound all feasible solutions of dependent variables Di and Vi [19].Each subproblem (22) may be decoupled for the fixed values of the Lagrangian multipliers for each iteration k, λik,ωik,ψik, as follows:SPi1k(23)Πik=minOCiDiQi+USiDi,Vi+HCiQi+USiDi,Vi2+HCiDiRi+Z1-αLTi+RiVi-USiDi,Vi-λikDi+ωikVis.t.:Qi+DiRi+Z1-αLTi+Ri+Z1-βLTiVi≤ICapiQi+USiDi,Vi≤QCapiUSiDi,Vi=Vi2·Di+DiRi2Di,Vi∈ΩSPi2k(24)θik=minFi+ΠiXi+∑j=1MRCi+λikdj+TCij+ωikvj-ψjkYijs.t.:Yij≤Xi∀j=1,…,MXi,Yij∈0,1∀j=1,…,Mθi denotes the benefit of facility i and represents the contribution of opening facility i to the objective function (12). This decomposition consists of solving SPi1 to compute Πi and then solving SPi2 to calculate θi, based on the computed Πi, as explained in Section 5.3.


### 5.2. Second Lagrangian Relaxation Algorithm

Associating the dual variables vectorsλ and ω with constraints (17) and (18), respectively, we obtain the following relaxed problem:RLP2(25)min∑i=1NFiXi+∑i=1N∑j=1MRCi+λidj+TCij+ωivjYij+∑i=1NOCiDiQi+USiDi,Vi+HCiQi+USiDi,Vi2+∑i=1NHCiDiRi+Z1-αLTi+RiVi-USiDi,Vi-∑i=1NλiDi+ωiVis.t.:∑i=1NYij=1∀j=1,…,MYij≤Xi∀i=1,…,N,∀j=1,…,MQi+DiRi+Z1-αLTi+Ri+Z1-βLTiVi≤ICap·Xi∀i=1,…,NQi+USiDi,Vi≤QCap∀i=1,…,NUSiDi,Vi=Vi2·Di+DiRi2∀i=1,…,NXi,Yij∈0,1∀i=1,…,N,∀j=1,…,MFor fixed values of the Lagrangian multipliers, λ and ω, we want to minimize (25) over location variables, Xi, and the assignment variables Yij. For the given λ and ω vectors, the problem decouples to the following subproblems:SP1(26)min∑i=1NOCiDiQi+USiDi,Vi+HCiQi+USiDi,Vi2+∑i=1NHCiDiRi+Z1-αLTi+RiVi-USiDi,Vi-∑i=1NλiDi+ωiVis.t.:Qi+DiRi+Z1-αLTi+Ri+Z1-βLTiVi≤ICap·Xi∀i=1,…,NQi+USiDi,Vi≤QCap∀i=1,…,NUSiDi,Vi=Vi2·Di+DiRi2∀i=1,…,NSP2(27)min∑i=1NFiXi+∑i=1N∑j=1MRCi+λidj+TCij+ωivjYijs.t.:∑i=1NYij=1∀j=1,…,MYij≤Xi∀i=1,…,N,∀j=1,…,MXi,Yij∈0,1∀i=1,…,N,∀j=1,…,MEach subproblem (26) may be decoupled for the fixed values of the Lagrangian multipliers for each iteration k, λik,ωik, in the following subproblems for each warehouse i:SP1ik(28)Πik=minOCiDiQi+USiDi,Vi+HCiQi+USiDi,Vi2+HCiDiRi+Z1-αLTi+RiVi-USiDi,Vi-λikDi+ωikVis.t.:Qi+DiRi+Z1-αLTi+Ri+Z1-βLTiVi≤ICapQi+USiDi,Vi≤QCapUSiDi,Vi=Vi2·Di+DiRi2Di,Vi∈ΩSP2k(29)θk=min∑i=1NFi+ΠikXi+∑i=1N∑j=1MRCi+λikdj+TCij+ωikvjYijs.t:∑i=1NYij=1∀j=1,…,MYij≤Xi∀i=1,…,N,∀j=1,…,MXi,Yij∈0,1∀i=1,…,N,∀j=1,…,MThis decomposition consists of solving SP1i to compute Πi and then solving SP2 to calculate θ, based on the computed Πi, as explained in Section 5.3.


### 5.3. Subproblem Solving

#### 5.3.1. First Lagrangian Relaxation

For fixed values of the Lagrangian multipliersλik,ωik,ψik, which are associated with relaxing constraints (17), (18), and (13), respectively, we obtain an infeasible solution of the primal problem in each iteration k of the algorithm. This solution generates a lower bound on the optimal value of the primal problem.First, we solveSPi1 to calculate the value of Πi of subproblems (23), for which an exact procedure is found in Miranda [36]. Once Πi is obtained, SPi2 is solved based on the value of Πi according to Algorithm 1 (see Appendix A).Algorithm 1:Subproblem solving for first Lagrangian relaxation.
for  i=1toN Compute Δi=Fi+Πi+∑j=1Mmin0,(RCi+λi)dj+TCij+ωivj-ψj If  Δi<0  then X i = 1, and Y i j = 1 if   ( R C i + λ i ) d j + T C i j + ω i v j - ψ j < 0 0 if    ( R C i + λ i ) d j + T C i j + ω i v j - ψ j ≥ 0  ∀ j = 1 , . . . , M D i, Vi and Qi retain the values computed from the resolution of subproblem (23) If  Δi≥0  then X i = D i = V i = Q i = 0, Y i j = 0 ,  ∀ j = 1 , . . . , M


#### 5.3.2. Second Lagrangian Relaxation

For fixed values of the Lagrangian multipliersλik and ωik, which are associated with relaxing constraints (17) and (18), respectively, we obtain an infeasible solution of the primal problem in each iteration k of the algorithm. As in the first Lagrangian relaxation, this solution corresponds to a lower bound on the optimal value of the primal problem. First, we solve SP1i to calculate the value of Πi of subproblems (26), which is identical to subproblem (23). Once Πi is obtained, SP2 is solved based on the value of Πi through the solver CPLEX.


### 5.4. Lagrangian Heuristic and Subgradient Optimization

At each iterationk of the Lagrangian algorithm, we use the current lower bound solution to obtain a feasible solution, which is an upper bound to the optimal value of the primal problem. The Lagrangian heuristic considers three main procedures: warehouse selection, greedy assignment of customers, and K-OPT improvements. These three procedures are run for different numbers of warehouses, from 1 toN, based on the results and dual information of the subproblems SPi. Namely, the complete heuristic is executedN times, and the best solution is selected. Notice the high complexity of the heuristic, especially, K-OPT improvement procedure, in contrast to the standard, simple Lagrangian heuristic observed in the literature. In order to avoid a potential high time consumption, only the K-OPT procedure is executed every 30 iterations of the algorithm. The three main procedures are described as follows.


#### 5.4.1. Warehouse Selection

This procedure assumes that the optimal solutionx-k=(X-k,Y-k,D-k,V-k,Q-k) of the subproblems SPi and the Lagrange multipliers (λik,ωik,ψik) are known. For the warehouse selection, the optimal costs of subproblems SPi are taken as initial values. Then, the best P(≤N) warehouses are chosen (see Algorithm 2 in Appendix A).Algorithm 2:Warehouse selection algorithm.
for  i=1 to N Π ¯ i k =  O C i D ¯ i k ( Q ¯ i k + U S i ( D ¯ i k , V ¯ i k ) ) + H C i ( Q ¯ i k + U S i ( D ¯ i k , V ¯ i k ) ) 2  + H C i ( D ¯ i k R i + Z 1 - α L T i + R i V ¯ i k - U S i ( D ¯ i k , V ¯ i k ) ) - λ i k D ¯ i k - ω i k V ¯ i k Δ ¯ i = F i + Π ¯ i k + ∑ j = 1 M min ⁡ 0 , ( R C i + λ i k ) d j + T C i j + ω i k v j - ψ j k  return  (P sites in ascending order of Δ¯i)


#### 5.4.2. Greedy Assignment of Customers

Once the warehouses are chosen, the customers are greedy assigned to the chosen warehouses; i.e., each client is assigned to the nearest warehouse, based on the transportation costRCi·dj+TCij, respecting the constraint of ordering capacity and maximum inventory. In order to satisfy these constraints, we calculate three types of order quantities at each warehousei. First is QiEOQ, which is economic order quantity in absence of capacity constraints. Second is Qi′, which is the available inventory capacity once inventory associated with variances are discounted, based on the inventory capacity constraint. Third is Qi′′, which is the available order quantity once undershoot is subtracted, based on the order capacity constraint. Then, the optimal order quantity Qi∗ is the minimum of the three previous different values for Qi, as long as Qi∗ has a nonnegative value. Otherwise, deletei from the potential site’s pool. The heuristic is described according to Algorithm 3 (see Appendix A).Algorithm 3:Greedy assignment of customers and local search algorithm.
for  i=1 to N for   j=1 to M d k i j = R C I i ⋅ d j + T C I i , j   for  q=1 to N for  i=1 to q X ~ I i = 1  for  j=1  to M for  i=1 to N Y ~ J i j , j = 1 for  l=1 to N D ~ l = ∑ s = 1 m d s ⋅ Y ~ l s V ~ l = ∑ s = 1 m v s ⋅ Y ~ l s  U S J i j = V ~ J i j 2 ⋅ D ~ J i j + D ~ J i j R J i j 2 Q J i j E O Q = ( 2 ⋅ O C J i j ⋅ D ~ J i j ) H C J i j - U S J i j Q J i j ′ = I C a p - D ~ J i j R J i j - Z 1 - α L T J i j + R J i j + Z 1 - β L T J i j V ~ J i j Q J i j ′ ′ = Q C a p - U S J i j Q J i j ∗ = m i n ( Q J i j E O Q , Q J i j ′ , Q J i j ′ ′ ) if   QJij∗>0   then break  i else Y~Jij,j=0,USJij=0,QJij∗=0 next   i   x ~ k = ( X ~ k , Y ~ k , D ~ k , V ~ k , Q ~ k ) U B k = f ( x ~ k ) 1 - O P T 2 - O P T


#### 5.4.3. K-OPT Improvements

Once a feasible solution is obtained through the last two steps (i.e.,x~k=(X~k,Y~k,D~k,V~k,Q~k)), two K-OPT improvements are run, 1-OPT and 2-OPT. The former evaluates the reassignment of each customer to the other installed warehouses, if capacity constraints allow it; then, the best feasible interchange is chosen. If the total cost decreases then the reassignment is permanent. The latter takes pairs of clients in different warehouses and swaps them if capacity constraints allow it. If the total cost decreases the swap becomes permanent. In this algorithm, the optimal value of the dual problem is obtained based on dual maximization, which represents a lower bound to the optimal value of the problem P. Thus, the difference between this lower bound and the cost of the best solution obtained through the heuristic previously described is an upper bound to errors of the heuristic solutions.The update of dual variables in each iterationk is based on the subgradient method [37, 38]. This method employs the slackness/violation vector associated with relaxed constraints. Furthermore, this method utilizes an upper bound UB on the optimal value of the primal problem, which is obtained by solving the Lagrangian heuristic procedure described previously in this section. The procedure is repeated until a standard convergence criterion is met.


## 5.1. First Lagrangian Relaxation Algorithm

Associating the dual variables vectorsλ and ω with the constraints (17) and (18), respectively, and ψ with constraint (13), we obtain the following relaxed problem:RLP1(21)min∑i=1NFiXi+∑i=1N∑j=1MRCi+λidj+TCij+ωivj-ψjYij+∑i=1NOCiDiQi+USiDi,Vi+HCiQi+USiDi,Vi2+∑i=1NHCiDiRi+Z1-αLTi+RiVi-USiDi,Vi-∑i=1NλiDi+ωiVi+∑j=1Mψjs.t.:Yij≤Xi∀i=1,…,N,∀j=1,…,MQi+DiRi+Z1-αLTi+Ri+Z1-βLTiVi≤ICapi·Xi∀i=1,…,NQi+USiDi,Vi≤QCapi∀i=1,…,NUSiDi,Vi=Vi2·Di+DiRi2∀i=1,…,NXi,Yij∈0,1∀i=1,…,N,∀j=1,…,MFor fixed values of the Lagrangian multipliers, λ, ω, and ψ, we minimize (21) over location variables, Xi, and the assignment variables Yij. For the given λ, ω, and ψ vectors, the problem decouples to the following subproblem for each warehouse i:SPi(22)minFiXi+∑j=1MRCi+λidj+TCij+ωivj-ψjYij+OCiDiQi+USiDi,Vi+HCiQi+USiDi,Vi2+HCiDiRi+Z1-αLTi+RiVi-USiDi,Vi-λiDi+ωiVis.t.:Yij≤Xi∀j=1,…,MQi+DiRi+Z1-αLTi+Ri+Z1-βLTiVi≤ICapi·XiQi+USiDi,Vi≤QCapiUSiDi,Vi=Vi2·Di+DiRi2Di,Vi∈ΩXi,Yij∈0,1∀j=1,…,MWe include a set of valid inequalities (Di,Vi)∈Ω to solve previous subproblems and to reduce duality gaps by increasing upper bounds. Valid inequalities are defined as a set of constraints, which bound all feasible solutions of dependent variables Di and Vi [19].Each subproblem (22) may be decoupled for the fixed values of the Lagrangian multipliers for each iteration k, λik,ωik,ψik, as follows:SPi1k(23)Πik=minOCiDiQi+USiDi,Vi+HCiQi+USiDi,Vi2+HCiDiRi+Z1-αLTi+RiVi-USiDi,Vi-λikDi+ωikVis.t.:Qi+DiRi+Z1-αLTi+Ri+Z1-βLTiVi≤ICapiQi+USiDi,Vi≤QCapiUSiDi,Vi=Vi2·Di+DiRi2Di,Vi∈ΩSPi2k(24)θik=minFi+ΠiXi+∑j=1MRCi+λikdj+TCij+ωikvj-ψjkYijs.t.:Yij≤Xi∀j=1,…,MXi,Yij∈0,1∀j=1,…,Mθi denotes the benefit of facility i and represents the contribution of opening facility i to the objective function (12). This decomposition consists of solving SPi1 to compute Πi and then solving SPi2 to calculate θi, based on the computed Πi, as explained in Section 5.3.


## 5.2. Second Lagrangian Relaxation Algorithm

Associating the dual variables vectorsλ and ω with constraints (17) and (18), respectively, we obtain the following relaxed problem:RLP2(25)min∑i=1NFiXi+∑i=1N∑j=1MRCi+λidj+TCij+ωivjYij+∑i=1NOCiDiQi+USiDi,Vi+HCiQi+USiDi,Vi2+∑i=1NHCiDiRi+Z1-αLTi+RiVi-USiDi,Vi-∑i=1NλiDi+ωiVis.t.:∑i=1NYij=1∀j=1,…,MYij≤Xi∀i=1,…,N,∀j=1,…,MQi+DiRi+Z1-αLTi+Ri+Z1-βLTiVi≤ICap·Xi∀i=1,…,NQi+USiDi,Vi≤QCap∀i=1,…,NUSiDi,Vi=Vi2·Di+DiRi2∀i=1,…,NXi,Yij∈0,1∀i=1,…,N,∀j=1,…,MFor fixed values of the Lagrangian multipliers, λ and ω, we want to minimize (25) over location variables, Xi, and the assignment variables Yij. For the given λ and ω vectors, the problem decouples to the following subproblems:SP1(26)min∑i=1NOCiDiQi+USiDi,Vi+HCiQi+USiDi,Vi2+∑i=1NHCiDiRi+Z1-αLTi+RiVi-USiDi,Vi-∑i=1NλiDi+ωiVis.t.:Qi+DiRi+Z1-αLTi+Ri+Z1-βLTiVi≤ICap·Xi∀i=1,…,NQi+USiDi,Vi≤QCap∀i=1,…,NUSiDi,Vi=Vi2·Di+DiRi2∀i=1,…,NSP2(27)min∑i=1NFiXi+∑i=1N∑j=1MRCi+λidj+TCij+ωivjYijs.t.:∑i=1NYij=1∀j=1,…,MYij≤Xi∀i=1,…,N,∀j=1,…,MXi,Yij∈0,1∀i=1,…,N,∀j=1,…,MEach subproblem (26) may be decoupled for the fixed values of the Lagrangian multipliers for each iteration k, λik,ωik, in the following subproblems for each warehouse i:SP1ik(28)Πik=minOCiDiQi+USiDi,Vi+HCiQi+USiDi,Vi2+HCiDiRi+Z1-αLTi+RiVi-USiDi,Vi-λikDi+ωikVis.t.:Qi+DiRi+Z1-αLTi+Ri+Z1-βLTiVi≤ICapQi+USiDi,Vi≤QCapUSiDi,Vi=Vi2·Di+DiRi2Di,Vi∈ΩSP2k(29)θk=min∑i=1NFi+ΠikXi+∑i=1N∑j=1MRCi+λikdj+TCij+ωikvjYijs.t:∑i=1NYij=1∀j=1,…,MYij≤Xi∀i=1,…,N,∀j=1,…,MXi,Yij∈0,1∀i=1,…,N,∀j=1,…,MThis decomposition consists of solving SP1i to compute Πi and then solving SP2 to calculate θ, based on the computed Πi, as explained in Section 5.3.


## 5.3. Subproblem Solving

### 5.3.1. First Lagrangian Relaxation

For fixed values of the Lagrangian multipliersλik,ωik,ψik, which are associated with relaxing constraints (17), (18), and (13), respectively, we obtain an infeasible solution of the primal problem in each iteration k of the algorithm. This solution generates a lower bound on the optimal value of the primal problem.First, we solveSPi1 to calculate the value of Πi of subproblems (23), for which an exact procedure is found in Miranda [36]. Once Πi is obtained, SPi2 is solved based on the value of Πi according to Algorithm 1 (see Appendix A).Algorithm 1:Subproblem solving for first Lagrangian relaxation.
for  i=1toN Compute Δi=Fi+Πi+∑j=1Mmin0,(RCi+λi)dj+TCij+ωivj-ψj If  Δi<0  then X i = 1, and Y i j = 1 if   ( R C i + λ i ) d j + T C i j + ω i v j - ψ j < 0 0 if    ( R C i + λ i ) d j + T C i j + ω i v j - ψ j ≥ 0  ∀ j = 1 , . . . , M D i, Vi and Qi retain the values computed from the resolution of subproblem (23) If  Δi≥0  then X i = D i = V i = Q i = 0, Y i j = 0 ,  ∀ j = 1 , . . . , M


### 5.3.2. Second Lagrangian Relaxation

For fixed values of the Lagrangian multipliersλik and ωik, which are associated with relaxing constraints (17) and (18), respectively, we obtain an infeasible solution of the primal problem in each iteration k of the algorithm. As in the first Lagrangian relaxation, this solution corresponds to a lower bound on the optimal value of the primal problem. First, we solve SP1i to calculate the value of Πi of subproblems (26), which is identical to subproblem (23). Once Πi is obtained, SP2 is solved based on the value of Πi through the solver CPLEX.


## 5.3.1. First Lagrangian Relaxation

For fixed values of the Lagrangian multipliersλik,ωik,ψik, which are associated with relaxing constraints (17), (18), and (13), respectively, we obtain an infeasible solution of the primal problem in each iteration k of the algorithm. This solution generates a lower bound on the optimal value of the primal problem.First, we solveSPi1 to calculate the value of Πi of subproblems (23), for which an exact procedure is found in Miranda [36]. Once Πi is obtained, SPi2 is solved based on the value of Πi according to Algorithm 1 (see Appendix A).Algorithm 1:Subproblem solving for first Lagrangian relaxation.
for  i=1toN Compute Δi=Fi+Πi+∑j=1Mmin0,(RCi+λi)dj+TCij+ωivj-ψj If  Δi<0  then X i = 1, and Y i j = 1 if   ( R C i + λ i ) d j + T C i j + ω i v j - ψ j < 0 0 if    ( R C i + λ i ) d j + T C i j + ω i v j - ψ j ≥ 0  ∀ j = 1 , . . . , M D i, Vi and Qi retain the values computed from the resolution of subproblem (23) If  Δi≥0  then X i = D i = V i = Q i = 0, Y i j = 0 ,  ∀ j = 1 , . . . , M


## 5.3.2. Second Lagrangian Relaxation

For fixed values of the Lagrangian multipliersλik and ωik, which are associated with relaxing constraints (17) and (18), respectively, we obtain an infeasible solution of the primal problem in each iteration k of the algorithm. As in the first Lagrangian relaxation, this solution corresponds to a lower bound on the optimal value of the primal problem. First, we solve SP1i to calculate the value of Πi of subproblems (26), which is identical to subproblem (23). Once Πi is obtained, SP2 is solved based on the value of Πi through the solver CPLEX.


## 5.4. Lagrangian Heuristic and Subgradient Optimization

At each iterationk of the Lagrangian algorithm, we use the current lower bound solution to obtain a feasible solution, which is an upper bound to the optimal value of the primal problem. The Lagrangian heuristic considers three main procedures: warehouse selection, greedy assignment of customers, and K-OPT improvements. These three procedures are run for different numbers of warehouses, from 1 toN, based on the results and dual information of the subproblems SPi. Namely, the complete heuristic is executedN times, and the best solution is selected. Notice the high complexity of the heuristic, especially, K-OPT improvement procedure, in contrast to the standard, simple Lagrangian heuristic observed in the literature. In order to avoid a potential high time consumption, only the K-OPT procedure is executed every 30 iterations of the algorithm. The three main procedures are described as follows.


### 5.4.1. Warehouse Selection

This procedure assumes that the optimal solutionx-k=(X-k,Y-k,D-k,V-k,Q-k) of the subproblems SPi and the Lagrange multipliers (λik,ωik,ψik) are known. For the warehouse selection, the optimal costs of subproblems SPi are taken as initial values. Then, the best P(≤N) warehouses are chosen (see Algorithm 2 in Appendix A).Algorithm 2:Warehouse selection algorithm.
for  i=1 to N Π ¯ i k =  O C i D ¯ i k ( Q ¯ i k + U S i ( D ¯ i k , V ¯ i k ) ) + H C i ( Q ¯ i k + U S i ( D ¯ i k , V ¯ i k ) ) 2  + H C i ( D ¯ i k R i + Z 1 - α L T i + R i V ¯ i k - U S i ( D ¯ i k , V ¯ i k ) ) - λ i k D ¯ i k - ω i k V ¯ i k Δ ¯ i = F i + Π ¯ i k + ∑ j = 1 M min ⁡ 0 , ( R C i + λ i k ) d j + T C i j + ω i k v j - ψ j k  return  (P sites in ascending order of Δ¯i)


### 5.4.2. Greedy Assignment of Customers

Once the warehouses are chosen, the customers are greedy assigned to the chosen warehouses; i.e., each client is assigned to the nearest warehouse, based on the transportation costRCi·dj+TCij, respecting the constraint of ordering capacity and maximum inventory. In order to satisfy these constraints, we calculate three types of order quantities at each warehousei. First is QiEOQ, which is economic order quantity in absence of capacity constraints. Second is Qi′, which is the available inventory capacity once inventory associated with variances are discounted, based on the inventory capacity constraint. Third is Qi′′, which is the available order quantity once undershoot is subtracted, based on the order capacity constraint. Then, the optimal order quantity Qi∗ is the minimum of the three previous different values for Qi, as long as Qi∗ has a nonnegative value. Otherwise, deletei from the potential site’s pool. The heuristic is described according to Algorithm 3 (see Appendix A).Algorithm 3:Greedy assignment of customers and local search algorithm.
for  i=1 to N for   j=1 to M d k i j = R C I i ⋅ d j + T C I i , j   for  q=1 to N for  i=1 to q X ~ I i = 1  for  j=1  to M for  i=1 to N Y ~ J i j , j = 1 for  l=1 to N D ~ l = ∑ s = 1 m d s ⋅ Y ~ l s V ~ l = ∑ s = 1 m v s ⋅ Y ~ l s  U S J i j = V ~ J i j 2 ⋅ D ~ J i j + D ~ J i j R J i j 2 Q J i j E O Q = ( 2 ⋅ O C J i j ⋅ D ~ J i j ) H C J i j - U S J i j Q J i j ′ = I C a p - D ~ J i j R J i j - Z 1 - α L T J i j + R J i j + Z 1 - β L T J i j V ~ J i j Q J i j ′ ′ = Q C a p - U S J i j Q J i j ∗ = m i n ( Q J i j E O Q , Q J i j ′ , Q J i j ′ ′ ) if   QJij∗>0   then break  i else Y~Jij,j=0,USJij=0,QJij∗=0 next   i   x ~ k = ( X ~ k , Y ~ k , D ~ k , V ~ k , Q ~ k ) U B k = f ( x ~ k ) 1 - O P T 2 - O P T


### 5.4.3. K-OPT Improvements

Once a feasible solution is obtained through the last two steps (i.e.,x~k=(X~k,Y~k,D~k,V~k,Q~k)), two K-OPT improvements are run, 1-OPT and 2-OPT. The former evaluates the reassignment of each customer to the other installed warehouses, if capacity constraints allow it; then, the best feasible interchange is chosen. If the total cost decreases then the reassignment is permanent. The latter takes pairs of clients in different warehouses and swaps them if capacity constraints allow it. If the total cost decreases the swap becomes permanent. In this algorithm, the optimal value of the dual problem is obtained based on dual maximization, which represents a lower bound to the optimal value of the problem P. Thus, the difference between this lower bound and the cost of the best solution obtained through the heuristic previously described is an upper bound to errors of the heuristic solutions.The update of dual variables in each iterationk is based on the subgradient method [37, 38]. This method employs the slackness/violation vector associated with relaxed constraints. Furthermore, this method utilizes an upper bound UB on the optimal value of the primal problem, which is obtained by solving the Lagrangian heuristic procedure described previously in this section. The procedure is repeated until a standard convergence criterion is met.


## 5.4.1. Warehouse Selection

This procedure assumes that the optimal solutionx-k=(X-k,Y-k,D-k,V-k,Q-k) of the subproblems SPi and the Lagrange multipliers (λik,ωik,ψik) are known. For the warehouse selection, the optimal costs of subproblems SPi are taken as initial values. Then, the best P(≤N) warehouses are chosen (see Algorithm 2 in Appendix A).Algorithm 2:Warehouse selection algorithm.
for  i=1 to N Π ¯ i k =  O C i D ¯ i k ( Q ¯ i k + U S i ( D ¯ i k , V ¯ i k ) ) + H C i ( Q ¯ i k + U S i ( D ¯ i k , V ¯ i k ) ) 2  + H C i ( D ¯ i k R i + Z 1 - α L T i + R i V ¯ i k - U S i ( D ¯ i k , V ¯ i k ) ) - λ i k D ¯ i k - ω i k V ¯ i k Δ ¯ i = F i + Π ¯ i k + ∑ j = 1 M min ⁡ 0 , ( R C i + λ i k ) d j + T C i j + ω i k v j - ψ j k  return  (P sites in ascending order of Δ¯i)


## 5.4.2. Greedy Assignment of Customers

Once the warehouses are chosen, the customers are greedy assigned to the chosen warehouses; i.e., each client is assigned to the nearest warehouse, based on the transportation costRCi·dj+TCij, respecting the constraint of ordering capacity and maximum inventory. In order to satisfy these constraints, we calculate three types of order quantities at each warehousei. First is QiEOQ, which is economic order quantity in absence of capacity constraints. Second is Qi′, which is the available inventory capacity once inventory associated with variances are discounted, based on the inventory capacity constraint. Third is Qi′′, which is the available order quantity once undershoot is subtracted, based on the order capacity constraint. Then, the optimal order quantity Qi∗ is the minimum of the three previous different values for Qi, as long as Qi∗ has a nonnegative value. Otherwise, deletei from the potential site’s pool. The heuristic is described according to Algorithm 3 (see Appendix A).Algorithm 3:Greedy assignment of customers and local search algorithm.
for  i=1 to N for   j=1 to M d k i j = R C I i ⋅ d j + T C I i , j   for  q=1 to N for  i=1 to q X ~ I i = 1  for  j=1  to M for  i=1 to N Y ~ J i j , j = 1 for  l=1 to N D ~ l = ∑ s = 1 m d s ⋅ Y ~ l s V ~ l = ∑ s = 1 m v s ⋅ Y ~ l s  U S J i j = V ~ J i j 2 ⋅ D ~ J i j + D ~ J i j R J i j 2 Q J i j E O Q = ( 2 ⋅ O C J i j ⋅ D ~ J i j ) H C J i j - U S J i j Q J i j ′ = I C a p - D ~ J i j R J i j - Z 1 - α L T J i j + R J i j + Z 1 - β L T J i j V ~ J i j Q J i j ′ ′ = Q C a p - U S J i j Q J i j ∗ = m i n ( Q J i j E O Q , Q J i j ′ , Q J i j ′ ′ ) if   QJij∗>0   then break  i else Y~Jij,j=0,USJij=0,QJij∗=0 next   i   x ~ k = ( X ~ k , Y ~ k , D ~ k , V ~ k , Q ~ k ) U B k = f ( x ~ k ) 1 - O P T 2 - O P T


## 5.4.3. K-OPT Improvements

Once a feasible solution is obtained through the last two steps (i.e.,x~k=(X~k,Y~k,D~k,V~k,Q~k)), two K-OPT improvements are run, 1-OPT and 2-OPT. The former evaluates the reassignment of each customer to the other installed warehouses, if capacity constraints allow it; then, the best feasible interchange is chosen. If the total cost decreases then the reassignment is permanent. The latter takes pairs of clients in different warehouses and swaps them if capacity constraints allow it. If the total cost decreases the swap becomes permanent. In this algorithm, the optimal value of the dual problem is obtained based on dual maximization, which represents a lower bound to the optimal value of the problem P. Thus, the difference between this lower bound and the cost of the best solution obtained through the heuristic previously described is an upper bound to errors of the heuristic solutions.The update of dual variables in each iterationk is based on the subgradient method [37, 38]. This method employs the slackness/violation vector associated with relaxed constraints. Furthermore, this method utilizes an upper bound UB on the optimal value of the primal problem, which is obtained by solving the Lagrangian heuristic procedure described previously in this section. The procedure is repeated until a standard convergence criterion is met.


## 6. Numerical Results and Discussion

In this section, we study the quality of the solutions by the proposed heuristic procedure. Furthermore, we validate the model ILM-SCC-PR and its heuristic solutions. We used the instances of Miranda and Garrido [18, 19] as a benchmark for an ILP under continuous review with the assumptions required for a periodic review problem.We used an Intel Core i3 processor at 2.4 GHz with 6 GB of RAM and Windows 7 to run the heuristic procedure. The program was developed in Microsoft Visual Studio 2010 C++ and the subproblems of Lagrangian relaxation were solved in IBM CPLEX 12.5. The numerical experiments have 20 warehouses and 40 clients (840 binary variables). The main aim of presenting these experiments is to show the quality of the heuristic solutions in terms of their differences with the dual optimal values. This provides lower bounds for the optimal solution for the original problem. In addition, we test the performance with two different Lagrangian relaxations, as we explain previously in Sections5.1 and 5.2, respectively. The average execution time for the test examples of the first and second Lagrangian relaxation was 42 and 102 seconds, respectively.The model and the heuristic approach were validated through a sensitivity analysis of the following key parameters: ordering capacity, demand variability, and fixed costs. We considered two levels of order capacity:QCap = 600 and 900. Demand variances and warehouse fixed location costs ranged over seven values from the base case: ±0%,±10%,±20%,and±30% each. Two values of the review period were considered:R=1, 3. A total of 2×7×7×2 = 196 instances were solved for each one of two Lagrangian relaxations, which sum to 196×2 = 392 instances finally.The cost parameters are expressed in a generic cost unit,CU. Fixed costsF, ordering costs,OC, and lead times,LT, for each warehouse are reported in Table 2. For holding costs,HC, and transportation costs,RC, a value of 100CU was assumed. Also,ICap is equal to 1200. Z1-α and Z1-β were set to be 1.64 (95% of service level).The parameters for Lagrangian relaxation used for all experiments are given in Table1. We determined the Lagrangian procedure based on the maximum number of iterations allowed, or the optimality gap, or the minimum value of α (the scale used in calculating the different step sizes for updating each Lagrange multiplier), whichever happened first. The optimality gap is defined as ((UB-LB)/LB) ×100.Table 1
Parameters for the Lagrangian relaxation procedure.
Parameter Value Maximum number of iterations 5000 Number of iterations before halvingα 30 Initial value ofα 2 Minimum value ofα 0.0000001 Minimum LB-UB gap 0.001% Initial value for Lagrangian multipliers 0.0Table 2
Parameters of warehouses or distribution centers, W.
W 1 2 3 4 5 6 7 8 9 10  F 103,062 81,691 104,051 103,724 89,875 124,375 101,713 87,989 106,199 98,629 OC 61,800 47,150 41,940 88,650 62,100 55,220 41,470 62,650 68,440 69,080 LT 3 2 2 4 2 2 2 2 3 3  W 11 12 13 14 15 16 17 18 19 20  F 103,648 93,505 76,507 93,668 83,391 100,396 104,592 114,521 123,498 91,817 OC 64,070 45,320 69,690 45,680 77,260 41,000 74,780 53,030 32,930 76,990 LT 3 2 3 2 3 2 3 2 1 3The customer’s mean and variance are shown in Table3. Both the clients and potential warehouse sites were randomly distributed over a square with 2000 km sides. Transportation costsTC were assumed as 56 CU/km. For more details ofTC complete data, see Tables 14 and 15 in Appendix C.Table 3
Demand parameters of customers.
Customer 1 2 3 4 5 6 7 8 9 10  Mean 73.81 68.86 70.24 64.07 69.52 69.96 76.01 61.74 63.92 74.26 Variance 1,249.06 979.75 1,112.21 955.50 1,132.31 1,152.86 1,380.28 837.35 946.12 1,192.01  Customer 11 12 13 14 15 16 17 18 19 20  Mean 73.50 67.58 69.02 70.62 63.26 75.95 66.70 66.53 68.30 72.43 Variance 1,304.16 1,129.90 1,188.83 1,166.77 900.02 1,378.81 958.43 1,026.32 1,029.22 1,153.60  Customer 21 22 23 24 25 26 27 28 29 30  Mean 57.65 82.92 57.99 65.32 61.99 77.96 63.03 75.06 60.79 64.73 Variance 737.09 1,565.53 776.18 1,035.71 908.62 1,427.99 922.58 1,402.98 931.67 999.49  Customer 31 32 33 34 35 36 37 38 39 40  Mean 69.28 72.99 71.01 72.01 81.32 72.55 73.1 65.24 52.74 69.88 Variance 1,053.06 1,104.93 1,146.79 1,170.89 1,439.62 1,334.44 1,314.54 1,022.56 783.50 1,215.62The upper bounds of errors were between 0.5% and 2.5%, and 0.5% and 3.0% for first and second relaxation, respectively, consideringR=1, showing the quality of the found solutions. The histogram for the upper bounds of errors is shown in Figure 3. The average error obtained was 1.1% and 1.3% for first and second relaxation, correspondingly.Figure 3
Observed upper bounds for the solution errors in the 98 analyzed instances for first and second relaxation,R=1.The upper bounds of errors were between 4.0% and 9.0%, and 5.0% and 9.0% for first and second relaxation, respectively, consideringR=3, showing a worst quality of the found solutions comparatively withR=1 solutions. The histogram for the upper bounds of errors is shown in Figure 4. The average error obtained was 6.4% and 6.5% for first and second relaxation, correspondingly.Figure 4
Observed upper bounds for the solution errors in the 49 analyzed instances for first and second relaxation,R=3.Table4 shows the solutions obtained considering both values of ordering capacity (600 and 900), for variances at baseline andR=1 for first and second relaxations. It presents the installed warehouses (W), the served demands, and variance of the served demand by each warehouse (D and V, respectively). It also displays the optimal order quantity in absence of capacity constraints (QEOQ) and the available inventory capacity once the inventory associated with variances is discounted based on the inventory capacity constraint (Q′). It also shows the available order quantity once undershoot is subtracted based on the order capacity constraint (Q∗) and the order quantity given by the heuristic, Q∗. It can be noted that the order quantity given by the heuristic never violates the constraints and in all cases is the same as Q′,which means that the inventory capacity constraints are active. Correspondingly, Table 5 presents the same outcomes but now considering a period ofR=3. In this case, the order quantity additionally takes the same value of Q′; it can also be equal to QEOQ, which means that neither inventory nor order capacity constraints are active.Table 4
Sensitivity analysis for the capacity constraints with variances at baseline andR=1.
First relaxation:QCap= 600, 900 Second relaxation:QCap= 600, 900 W D V Q E O Q Q ′ Q ′ ′ Q∗ W D V Q E O Q Q ′ Q ′ ′ Q ∗  2 661.9 10,433.7 451.2 11.1 261.2 11.1 2 661.9 10,433.7 451.2 11.1 561.2 11.1 3 618.2 9,990.7 402.9 66.0 282.8 66.0 3 614.0 9,862.1 402.6 73.6 585.0 73.6 5 565.7 9,332.3 547.1 135.9 308.9 135.9 5 496.7 8,143.5 528.9 237.7 643.5 237.7 8 486.9 7,865.7 529.6 255.5 348.5 255.5 8 562.8 9,244.5 550.2 141.1 610.4 141.1 14 421.2 6,845.0 401.6 351.9 381.3 351.9 10 418.5 6,783.6 543.1 277.4 682.6 277.4Table 5
Sensitivity analysis for the capacity constraints with variances at baseline andR=3.
First relaxation:QCap= 600, 900 Second relaxation:QCap= 600, 900 W D V Q E O Q Q ′ Q ′ ′ Q ∗ W D V Q E O Q Q ′ Q ′ ′ Q ∗  2 257.0 4,004.5 99.0 50.2 206.7 50.2 2 254.7 3,910.3 100.4 61.5 210.2 61.5 3 263.6 3,995.6 67.2 30.7 197.0 30.7 3 263.6 3,995.6 67.2 30.7 197.0 30.7 5 215.5 3,510.3 186.0 198.7 268.6 186.0 5 216.2 3,610.1 185.5 191.7 267.3 185.5 8 268.3 4,116.9 169.7 11.1 190.0 11.1 8 268.3 4,116.9 169.7 11.1 190.0 11.1 10 217.5 3,683.5 213.5 131.2 265.2 131.2 10 215.8 3,495.2 214.2 147.2 268.2 147.2 11 204.6 3,163.0 197.4 200.6 285.4 197.4 11 204.6 3,163.0 197.4 200.6 285.4 197.4 13 210.6 3,615.8 217.3 156.0 275.6 156.0 12 223.5 3,936.9 106.0 153.9 255.9 106.0 14 263.9 4,026.6 87.5 28.4 196.5 28.4 13 204.8 3,265.8 219.1 193.8 284.9 193.8 15 200.5 3,211.1 247.9 209.8 291.2 209.8 14 198.0 3,169.2 120.3 269.1 295.0 120.3 16 240.2 4,384.0 74.4 83.1 230.6 74.4 16 231.9 4,049.3 79.5 123.5 243.5 79.5 19 203.2 3,179.8 53.2 313.0 287.4 53.2 19 263.6 4,178.6 13.4 91.2 196.7 13.4 20 209.0 3,576.4 245.2 163.0 278.0 163.0 20 209.0 3,576.4 245.2 163.0 278.0 163.0The details of the solutions of first and second relaxation are presented in Tables6 and 7, respectively, in which the columns are as follows:Prob no.:problem number,FC: factor of fixed cost sensitivity (i.e., 0.7 corresponds to a variation -30%), FV: factor of variance sensitivity,DCs opened:the additional DCs that are located compared to the baseline instance,DCs closed:the additional DCs that are closed compared to the baseline instance.No. of open DCs:total number of DCs that are open,Upper Bound:objective value of the best feasible solution,Lower Bound: the best lower bound found for optimal objective function,% Gap:percentage gap between upper bound and lower bound solution,Lag iter:total number of Lagrangian relaxation iterations, andCPU time (s): the number of CPU seconds elapsed when the algorithm terminates.Table 6
Results for first relaxation.
Prob no. R QCap FC FV DCs opened (∗) DCs closed (∗) No. of open DCs Upper Bound Lower Bound % Gap Lag iter CPU time (s) 1 1 600 0.7 0.7 10, 11 8, 14 5 2,023,248 2,003,836 0.97 1785 39 4 1 600 0.7 1.0 10, 20 14 6 2,070,318 2,056,800 0.66 1555 34 22 1 600 1.0 0.7 10 14 5 2,161,246 2,131,154 1.41 1011 22 25 1 600 1.0 1.0 2, 3, 5, 8, 14 N/A 5 2,221,538 2,202,020 0.89 1705 37 28 1 600 1.0 1.3 10, 20 14 6 2,282,509 2,263,675 0.83 1343 30 46 1 600 1.3 1.0 None None 5 2,358,720 2,330,384 1.22 1453 31 49 1 600 1.3 1.3 None None 5 2,422,577 2,406,503 0.67 1037 23 50 1 900 0.7 0.7 10 14 5 2,022,576 2,002,329 1.01 1906 40 53 1 900 0.7 1.0 10, 20 14 6 2,070,318 2,057,794 0.61 1439 31 71 1 900 1.0 0.7 10 14 5 2,161,246 2,130,454 1.45 1164 24 74 1 900 1.0 1.0 2, 3, 5, 8, 14 N/A 5 2,221,538 2,200,616 0.95 1832 39 77 1 900 1.0 1.3 10, 20 14 6 2,282,509 2,263,675 0.83 1343 30 95 1 900 1.3 1.0 None None 5 2,358,720 2,330,567 1.21 997 21 98 1 900 1.3 1.3 None None 5 2,422,577 2,406,503 0.67 1037 23 99 3 600/900 0.7 0.7 12 15,16 11 2,746,539 2,626,621 4.57 1791 51 102 3 600/900 0.7 1.0 None None 12 2,884,336 2,736,967 5.38 2002 59 120 3 600/900 1.0 0.7 7,12 15,16,19 11 3,063,005 2,910,209 5.25 2707 76 123 3 600/900 1.0 1.0 2,3,5,8,10,11,13, 14,15,16,19,20 N/A 12 3,224,884 3,040,498 6.06 1879 54 126 3 600/900 1.0 1.3 1,12 15 13 3,380,411 3,144,904 7.49 2829 95 144 3 600/900 1.3 1.0 None None 12 3,565,432 3,340,563 6.73 2372 69 147 3 600/900 1.3 1.3 12 None 13 3,765,373 3,481,191 8.16 1894 57 (∗): with respect to base case, Prob no 25, 74, and 123, respectively; N/A, not applicable.Table 7
Results for second relaxation.
Prob no. R QCap FC FV DCs opened (∗) DCs closed (∗) No. of open DCs Upper Bound Lower Bound % Gap Lag iter CPU time (s) 148 1 600 0.7 0.7 11 8 5 2,023,248 2,004,405 0.94 1330 103 151 1 600 0.7 1.0 20 None 6 2,070,318 2,058,653 0.57 1372 206 169 1 600 1.0 0.7 None None 5 2,161,246 2,126,896 1.62 1071 83 172 1 600 1.0 1.0 2, 3, 5, 8, 10 N/A 5 2,222,254 2,197,156 1.14 818 65 175 1 600 1.0 1.3 14 10 5 2,285,395 2,264,942 0.90 867 97 193 1 600 1.3 1.0 None None 5 2,360,924 2,310,342 2.19 773 49 196 1 600 1.3 1.3 14 10 5 2,422,577 2,400,707 0.91 855 54 197 1 900 0.7 0.7 11 8 5 2,023,248 2,002,202 1.05 1378 110 200 1 900 0.7 1.0 14,20 10 6 2,072,384 2,058,187 0.69 1329 188 218 1 900 1.0 0.7 None None 5 2,161,246 2,126,900 1.61 1318 102 221 1 900 1.0 1.0 2, 3, 5, 8, 10 N/A 5 2,222,254 2,197,156 1.14 818 68 224 1 900 1.0 1.3 14 10 5 2,285,395 2,264,942 0.90 867 102 242 1 900 1.3 1.0 None None 5 2,360,924 2,310,342 2.19 773 50 245 1 900 1.3 1.3 14 10 5 2,422,577 2,400,707 0.91 855 55 246 3 600/900 0.7 0.7 None 12 11 2,762,632 2,624,245 5.27 813 51 249 3 600/900 0.7 1.0 1 12 12 2,902,314 2,738,089 6.00 1653 102 267 3 600/900 1.0 0.7 7 12,16 11 3,071,115 2,908,436 5.59 1463 94 270 3 600/900 1.0 1.0 2,3,5,8,10,11,12 13,14,16,19,20 N/A 12 3,241,325 3,040,813 6.59 1574 98 273 3 600/900 1.0 1.3 15 None 13 3,396,774 3,160,391 7.48 1428 83 291 3 600/900 1.3 1.0 15 16 12 3,592,914 3,343,519 7.46 1539 91 294 3 600/900 1.3 1.3 1,15 19 13 3,761,791 3,481,305 8.06 1666 101 (∗): with respect to base case, Prob no 172, 221, and 270, respectively; N/A, not applicable.Note that upper bound values tend to increase with respect to the increment of the fixed cost (FC). A similar behavior is observed for variation in demand variance (FV). Both tendencies denote a reasonable response of the Lagrangian heuristic since it is expected that system costs increase with respect to both sets of parameters. On the other hand, if we compare results in Table 6 for the first relaxation and results in Table 7 for the second relaxation increasing order capacity constraints a system cost reduction is produced. Finally, when we compare results in Table 6 for first relaxation and results in Table 7 for second relaxation, an increment in the duration of the review period (R= 1 andR= 3) produces worst solutions in terms of system cost and % Gap. These results show the reasonability of the Lagrangian heuristic, based on the tendencies of the objective function when different input parameters are modified (see Tables 8–13 in Appendix B for more details).Table 8
Results for the first relaxation,R=1 and QCap=600.
Prob no. FC FV DCs opened (∗) DCs closed (∗) No. of open DCs Upper Bound Lower Bound % Gap Lag iter CPU time (s) 1 0.7 0.7 10, 11 8, 14 5 2,023,248 2,003,836 0.97 1785 39 2 0.7 0.8 10, 20 14 6 2,041,897 2,022,987 0.93 1363 29 3 0.7 0.9 10, 20 14 6 2,056,136 2,041,066 0.74 1611 35 4 0.7 1.0 10, 20 14 6 2,070,318 2,056,800 0.66 1555 34 5 0.7 1.1 10, 20 14 6 2,085,017 2,071,114 0.67 1499 33 6 0.7 1.2 20 None 6 2,099,931 2,089,759 0.49 1397 31 7 0.7 1.3 10, 20 14 6 2,116,294 2,104,572 0.56 1633 36 8 0.8 0.7 10 14 5 2,068,799 2,051,432 0.85 1554 34 9 0.8 0.8 None None 5 2,092,841 2,071,195 1.05 1827 38 10 0.8 0.9 10 14 5 2,109,062 2,091,839 0.82 2139 46 11 0.8 1.0 10, 20 14 6 2,125,723 2,109,966 0.75 1775 39 12 0.8 1.1 10, 20 14 6 2,140,422 2,115,810 1.16 1415 32 13 0.8 1.2 20 None 6 2,154,840 2,144,656 0.47 2015 44 14 0.8 1.3 10, 20 14 6 2,171,699 2,161,893 0.45 1830 41 15 0.9 0.7 10 14 5 2,115,023 2,091,648 1.12 1554 33 16 0.9 0.8 10 14 5 2,144,384 2,114,680 1.40 1036 22 17 0.9 0.9 10 14 5 2,155,285 2,136,610 0.87 1788 38 18 0.9 1.0 None None 5 2,175,811 2,153,626 1.03 2038 44 19 0.9 1.1 10, 20 14 6 2,195,827 2,177,076 0.86 1686 37 20 0.9 1.2 20 None 6 2,209,749 2,183,209 1.22 1470 32 21 0.9 1.3 10, 20 14 6 2,227,104 2,212,965 0.64 1688 37 22 1.0 0.7 10 14 5 2,161,246 2,131,154 1.41 1011 22 23 1.0 0.8 None None 5 2,184,295 2,155,778 1.32 1910 40 24 1.0 0.9 None None 5 2,202,343 2,177,796 1.13 2718 58 25 1.0 1.0 2, 3, 5, 8, 14 N/A 5 2,221,538 2,202,020 0.89 1705 37 26 1.0 1.1 20 None 6 2,250,748 2,218,640 1.45 1474 32 27 1.0 1.2 20 None 6 2,264,658 2,242,602 0.98 1274 28 28 1.0 1.3 10, 20 14 6 2,282,509 2,263,675 0.83 1343 30 29 1.1 0.7 10 14 5 2,207,470 2,170,288 1.71 929 20 30 1.1 0.8 None None 5 2,230,023 2,194,687 1.61 1131 24 31 1.1 0.9 10 14 5 2,247,732 2,219,852 1.26 2022 43 32 1.1 1.0 None None 5 2,267,266 2,244,557 1.01 1834 40 33 1.1 1.1 12 3 5 2,299,007 2,265,427 1.48 1389 31 34 1.1 1.2 12 3 5 2,319,104 2,289,564 1.29 1452 32 35 1.1 1.3 None None 5 2,331,122 2,307,567 1.02 1804 40 36 1.2 0.7 10 14 5 2,253,693 2,208,455 2.05 1296 28 37 1.2 0.8 None None 5 2,275,750 2,235,681 1.79 937 20 38 1.2 0.9 None None 5 2,293,798 2,264,077 1.31 1043 22 39 1.2 1.0 None None 5 2,312,993 2,288,491 1.07 956 21 40 1.2 1.1 10 14 5 2,346,628 2,311,584 1.52 1531 34 41 1.2 1.2 None None 5 2,364,918 2,336,833 1.20 1548 34 42 1.2 1.3 None None 5 2,376,850 2,357,551 0.82 1288 28 43 1.3 0.7 None None 5 2,299,884 2,247,278 2.34 1011 22 44 1.3 0.8 None None 5 2,321,478 2,276,995 1.95 1032 22 45 1.3 0.9 None None 5 2,339,525 2,300,269 1.71 1064 22 46 1.3 1.0 None None 5 2,358,720 2,330,384 1.22 1453 31 47 1.3 1.1 10 14 5 2,392,852 2,357,628 1.49 1823 40 48 1.3 1.2 12 3 5 2,408,450 2,382,329 1.10 1337 29 49 1.3 1.3 None None 5 2,422,577 2,406,503 0.67 1037 23 (∗): with respect to base case, Prob no 25; N/A, not applicable.Table 9
Results for the first relaxation,R=1 and QCap=900.
Prob no. FC FV DCs opened (∗) DCs closed (∗) No. of open DCs Upper Bound Lower Bound % Gap Lag iter CPU time (s) 50 0.7 0.7 10 14 5 2,022,576 2,002,329 1.01 1906 40 51 0.7 0.8 10, 20 14 6 2,041,655 2,014,576 1.34 3631 76 52 0.7 0.9 10, 20 14 6 2,056,095 2,034,976 1.04 955 20 53 0.7 1.0 10, 20 14 6 2,070,318 2,057,794 0.61 1439 31 54 0.7 1.1 10, 20 14 6 2,085,017 2,070,541 0.70 1426 31 55 0.7 1.2 20 None 6 2,099,808 2,085,217 0.70 1454 32 56 0.7 1.3 10, 20 14 6 2,116,294 2,104,572 0.56 1633 36 57 0.8 0.7 10 14 5 2,068,799 2,050,586 0.89 2355 50 58 0.8 0.8 None None 5 2,092,809 2,071,120 1.05 1913 40 59 0.8 0.9 10 14 5 2,109,062 2,090,298 0.90 2993 63 60 0.8 1.0 10, 20 14 6 2,125,723 2,109,420 0.77 1818 39 61 0.8 1.1 10, 20 14 6 2,140,422 2,127,241 0.62 1157 25 62 0.8 1.2 20 None 6 2,154,717 2,144,883 0.46 1847 40 63 0.8 1.3 10, 20 14 6 2,171,699 2,161,893 0.45 1830 40 64 0.9 0.7 None None 5 2,116,940 2,091,450 1.22 1980 41 65 0.9 0.8 None None 5 2,138,537 2,115,098 1.11 1170 25 66 0.9 0.9 10 14 5 2,155,285 2,136,615 0.87 1094 23 67 0.9 1.0 None None 5 2,175,811 2,155,136 0.96 1277 27 68 0.9 1.1 20 None 6 2,195,646 2,176,603 0.87 1428 31 69 0.9 1.2 20 None 6 2,209,626 2,196,774 0.59 1478 32 70 0.9 1.3 10, 20 14 6 2,227,104 2,212,965 0.64 1688 37 71 1.0 0.7 10 14 5 2,161,246 2,130,454 1.45 1164 24 72 1.0 0.8 None None 5 2,184,264 2,153,972 1.41 2043 43 73 1.0 0.9 10 14 5 2,201,509 2,179,809 1.00 1256 26 74 1.0 1.0 2, 3, 5, 8, 14 N/A 5 2,221,538 2,200,616 0.95 1832 39 75 1.0 1.1 10, 20 14 6 2,253,266 2,224,064 1.31 1227 27 76 1.0 1.2 20 None 6 2,264,535 2,244,660 0.89 1154 25 77 1.0 1.3 10, 20 14 6 2,282,509 2,263,675 0.83 1343 30 78 1.1 0.7 10 14 5 2,207,470 2,169,785 1.74 965 21 79 1.1 0.8 None None 5 2,229,992 2,195,949 1.55 948 20 80 1.1 0.9 10 14 5 2,247,732 2,218,807 1.30 992 21 81 1.1 1.0 None None 5 2,267,266 2,245,445 0.97 1924 42 82 1.1 1.1 10 3 5 2,297,032 2,264,559 1.43 931 21 83 1.1 1.2 12 3 5 2,319,104 2,287,954 1.36 1303 28 84 1.1 1.3 None None 5 2,331,122 2,307,567 1.02 1804 39 85 1.2 0.7 10 14 5 2,253,693 2,207,597 2.09 979 21 86 1.2 0.8 None None 5 2,275,719 2,236,741 1.74 989 21 87 1.2 0.9 None None 5 2,293,798 2,260,875 1.46 1452 31 88 1.2 1.0 None None 5 2,312,993 2,288,393 1.07 976 21 89 1.2 1.1 10 14 5 2,346,628 2,311,784 1.51 1518 33 90 1.2 1.2 12 3 5 2,363,777 2,336,760 1.16 1514 33 91 1.2 1.3 None None 5 2,376,850 2,357,551 0.82 1288 28 92 1.3 0.7 None None 5 2,299,850 2,246,840 2.36 946 20 93 1.3 0.8 None None 5 2,321,446 2,275,764 2.01 870 18 94 1.3 0.9 None None 5 2,339,525 2,303,075 1.58 1047 22 95 1.3 1.0 None None 5 2,358,720 2,330,567 1.21 997 21 96 1.3 1.1 10 14 5 2,392,852 2,351,971 1.74 2396 52 97 1.3 1.2 10 3 5 2,410,607 2,382,015 1.20 1195 26 98 1.3 1.3 None None 5 2,422,577 2,406,503 0.67 1037 23 (∗): with respect to base case, Prob no 74; N/A, not applicable.Table 10
Results for the first relaxation,R=3 and QCap=600; QCap=900.
Prob no. FC FV DCs opened (∗) DCs closed (∗) No. of open DCs Upper Bound Lower Bound % Gap Lag iter CPU time (s) 99 0.7 0.7 12 15,16 11 2,746,539 2,626,621 4.57 1791 51 100 0.7 0.8 1,12 15,16 12 2,821,579 2,668,238 5.75 1516 43 101 0.7 0.9 12 16 12 2,851,136 2,698,879 5.64 2071 59 102 0.7 1.0 None None 12 2,884,336 2,736,967 5.38 2002 59 103 0.7 1.1 1,12 11,15 12 2,924,387 2,767,487 5.67 1652 49 104 0.7 1.2 12 None 13 2,988,536 2,804,060 6.58 1764 53 105 0.7 1.3 1,12 15 13 3,005,910 2,839,190 5.87 1904 59 106 0.8 0.7 1,12 15,16,19 11 2,855,967 2,722,479 4.90 1860 53 107 0.8 0.8 None 15 11 2,927,783 2,764,501 5.91 2232 64 108 0.8 0.9 1,12 15,19 12 2,965,225 2,796,807 6.02 1931 55 109 0.8 1.0 None None 12 2,997,852 2,838,973 5.60 1625 48 110 0.8 1.1 1,12 11,15 12 3,033,260 2,867,744 5.77 2254 67 111 0.8 1.2 12 None 13 3,111,402 2,910,038 6.92 1814 54 112 0.8 1.3 1,12 15 13 3,130,744 2,946,207 6.26 1783 54 113 0.9 0.7 7 15,16 11 2,965,807 2,817,936 5.25 1645 46 114 0.9 0.8 1 11,15 11 3,027,515 2,862,289 5.77 1798 51 115 0.9 0.9 1,12 15,19 12 3,077,708 2,893,453 6.37 1905 54 116 0.9 1.0 None None 12 3,111,368 2,939,921 5.83 1789 52 117 0.9 1.1 1,12 11,15 12 3,147,729 2,972,010 5.91 1991 59 118 0.9 1.2 12 None 13 3,234,269 3,017,179 7.20 1793 53 119 0.9 1.3 1,12 15 13 3,255,577 3,048,281 6.80 2170 65 120 1.0 0.7 7,12 15,16,19 11 3,063,005 2,910,209 5.25 2707 76 121 1.0 0.8 None 15 11 3,138,137 2,958,396 6.08 1838 52 122 1.0 0.9 1,12 15,19 12 3,190,192 2,992,886 6.59 1964 55 123 1.0 1.0 2,3,5,8,10,11,13, N/A 12 3,224,884 3,040,498 6.06 1879 54 14,15,16,19,20 124 1.0 1.1 1,12 11,15 12 3,267,793 3,074,058 6.30 1797 53 125 1.0 1.2 12 None 13 3,357,135 3,122,780 7.50 1882 56 126 1.0 1.3 1,12 15 13 3,380,411 3,144,904 7.49 2829 95 127 1.1 0.7 7 15,16 11 3,176,424 3,007,463 5.62 2633 74 128 1.1 0.8 12 15,19 11 3,226,169 3,055,590 5.58 2583 74 129 1.1 0.9 1,12 15,19 12 3,302,676 3,092,201 6.81 1647 47 130 1.1 1.0 None None 12 3,338,400 3,141,701 6.26 2035 61 131 1.1 1.1 7,12 11,16 12 3,380,893 3,173,092 6.55 2466 81 132 1.1 1.2 1,12 19 13 3,479,214 3,228,727 7.76 1706 59 133 1.1 1.3 12 None 13 3,519,640 3,263,281 7.86 2507 80 134 1.2 0.7 1,12 15,16,19 11 3,265,744 3,098,273 5.41 2484 71 135 1.2 0.8 1,7,12 11,15,16,19 11 3,347,472 3,151,445 6.22 2130 61 136 1.2 0.9 1,12 15,19 12 3,415,160 3,190,416 7.04 2025 58 137 1.2 1.0 None None 12 3,451,916 3,242,612 6.45 1981 58 138 1.2 1.1 7,12 11,16 12 3,493,527 3,275,587 6.65 2420 71 139 1.2 1.2 1,12 19 13 3,600,037 3,331,035 8.08 2534 76 140 1.2 1.3 1,12 15 13 3,630,078 3,374,142 7.59 2022 61 141 1.3 0.7 1 11,15 11 3,386,827 3,191,709 6.11 3215 91 142 1.3 0.8 1,7,12 11,15,16,19 11 3,449,723 3,243,352 6.36 2728 77 143 1.3 0.9 1,12 15,19 12 3,527,644 3,288,221 7.28 1698 49 144 1.3 1.0 None None 12 3,565,432 3,340,563 6.73 2372 69 145 1.3 1.1 7,12 11,16 12 3,606,160 3,376,022 6.82 2576 76 146 1.3 1.2 1,12 19 13 3,720,860 3,423,069 8.70 2089 73 147 1.3 1.3 12 None 13 3,765,373 3,481,191 8.16 1894 57 (∗): with respect to base case, Prob no 123; N/A, not applicable.Table 11
Results for the second relaxation,R=1 and QCap=600.
Prob no. FC FV DCs opened (∗) DCs closed (∗) No. of open DCs Upper Bound Lower Bound % Gap Lag iter CPU time (s) 148 0.7 0.7 11 8 5 2,023,248 2,004,405 0.94 1330 103 149 0.7 0.8 20 None 6 2,041,897 2,024,218 0.87 1344 138 150 0.7 0.9 20 None 6 2,056,136 2,041,853 0.70 999 106 151 0.7 1.0 20 None 6 2,070,318 2,058,653 0.57 1372 206 152 0.7 1.1 14,20 10 6 2,093,276 2,070,168 1.12 3156 375 153 0.7 1.2 12,14,20 3 7 2,113,500 2,086,609 1.29 1680 198 154 0.7 1.3 20 None 6 2,120,860 2,104,350 0.78 1025 124 155 0.8 0.7 None None 5 2,068,799 2,051,220 0.86 1017 79 156 0.8 0.8 13,14,20 3,5 6 2,096,264 2,072,203 1.16 1186 110 157 0.8 0.9 None None 5 2,109,062 2,091,920 0.82 859 92 158 0.8 1.0 20 None 6 2,126,971 2,108,184 0.89 1283 145 159 0.8 1.1 14,20 10 6 2,140,929 2,125,481 0.73 895 105 160 0.8 1.2 14,20 10 6 2,154,840 2,144,731 0.47 907 112 161 0.8 1.3 20 None 6 2,171,699 2,162,440 0.43 1071 123 162 0.9 0.7 None None 5 2,115,023 2,087,493 1.32 1693 133 163 0.9 0.8 14 10 5 2,138,568 2,110,547 1.33 1105 86 164 0.9 0.9 None None 5 2,155,285 2,136,130 0.90 881 69 165 0.9 1.0 14 10 5 2,175,811 2,155,991 0.92 890 97 166 0.9 1.1 14,20 10 6 2,195,839 2,178,961 0.77 1759 194 167 0.9 1.2 14,20 10 6 2,209,749 2,194,826 0.68 865 93 168 0.9 1.3 20 None 6 2,231,671 2,214,517 0.77 948 100 169 1.0 0.7 None None 5 2,161,246 2,126,896 1.62 1071 83 170 1.0 0.8 14 10 5 2,184,295 2,151,423 1.53 1092 83 171 1.0 0.9 None None 5 2,201,509 2,175,341 1.20 984 76 172 1.0 1.0 2, 3, 5, 8, 10 N/A 5 2,222,254 2,197,156 1.14 818 65 173 1.0 1.1 14 10 5 2,257,526 2,219,496 1.71 818 86 174 1.0 1.2 14,20 10 6 2,264,658 2,241,920 1.01 823 91 175 1.0 1.3 14 10 5 2,285,395 2,264,942 0.90 867 97 176 1.1 0.7 None None 5 2,207,470 2,165,608 1.93 1225 98 177 1.1 0.8 14 10 5 2,230,023 2,191,819 1.74 831 66 178 1.1 0.9 None None 5 2,247,732 2,214,688 1.49 808 54 179 1.1 1.0 14 10 5 2,267,266 2,244,320 1.02 1060 85 180 1.1 1.1 14 10 5 2,303,254 2,264,255 1.72 806 83 181 1.1 1.2 14 10 5 2,319,191 2,292,148 1.18 877 106 182 1.1 1.3 14 10 5 2,331,122 2,308,181 0.99 925 108 183 1.2 0.7 None None 5 2,253,693 2,203,834 2.26 1314 88 184 1.2 0.8 None None 5 2,283,055 2,231,213 2.32 1341 102 185 1.2 0.9 None None 5 2,293,956 2,252,404 1.84 827 54 186 1.2 1.0 None None 5 2,314,701 2,283,059 1.39 815 64 187 1.2 1.1 None None 5 2,346,628 2,307,932 1.68 809 70 188 1.2 1.2 12, 14 3,10 5 2,363,777 2,336,492 1.17 845 90 189 1.2 1.3 14 10 5 2,376,850 2,354,471 0.95 833 113 190 1.3 0.7 14 10 5 2,299,884 2,242,034 2.58 1277 84 191 1.3 0.8 None None 5 2,329,278 2,270,847 2.57 781 50 192 1.3 0.9 None None 5 2,340,179 2,298,306 1.82 1211 76 193 1.3 1.0 None None 5 2,360,924 2,310,342 2.19 773 49 194 1.3 1.1 None None 5 2,392,852 2,346,581 1.97 797 50 195 1.3 1.2 14 10 5 2,410,646 2,371,311 1.66 839 53 196 1.3 1.3 14 10 5 2,422,577 2,400,707 0.91 855 54 (∗): with respect to base case, Prob no 172; N/A, not applicable.Table 12
Results for the second relaxation,R=1 and QCap=900.
Prob no. FC FV DCs opened (∗) DCs closed (∗) No. of open DCs Upper Bound Lower Bound % Gap Lag iter CPU time (s) 197 0.7 0.7 11 8 5 2,023,248 2,002,202 1.05 1378 110 198 0.7 0.8 20 None 6 2,041,655 2,024,155 0.86 1588 175 199 0.7 0.9 20 None 6 2,056,095 2,041,989 0.69 1078 122 200 0.7 1.0 14,20 10 6 2,072,384 2,058,187 0.69 1329 188 201 0.7 1.1 20 None 6 2,087,050 2,069,874 0.83 3781 474 202 0.7 1.2 14,20 10 6 2,099,808 2,088,349 0.55 897 106 203 0.7 1.3 20 None 6 2,120,860 2,104,350 0.78 1025 115 204 0.8 0.7 None None 5 2,068,799 2,050,990 0.87 1017 79 205 0.8 0.8 13,14,20 3,5 6 2,095,860 2,072,179 1.14 1712 173 206 0.8 0.9 14 10 5 2,110,888 2,092,099 0.90 1377 150 207 0.8 1.0 20 None 6 2,126,763 2,110,466 0.77 1465 170 208 0.8 1.1 14,20 10 6 2,140,737 2,126,893 0.65 920 109 209 0.8 1.2 14,20 10 6 2,154,717 2,143,841 0.51 913 123 210 0.8 1.3 20 None 6 2,171,699 2,162,509 0.42 1021 121 211 0.9 0.7 None None 5 2,115,023 2,087,493 1.32 1693 135 212 0.9 0.8 14 10 5 2,138,537 2,110,820 1.31 886 71 213 0.9 0.9 None None 5 2,155,285 2,136,130 0.90 881 71 214 0.9 1.0 14 10 5 2,175,811 2,154,123 1.01 806 90 215 0.9 1.1 14,20 10 6 2,195,646 2,179,059 0.76 972 117 216 0.9 1.2 14,20 10 6 2,209,626 2,196,715 0.59 943 110 217 0.9 1.3 20 None 6 2,231,671 2,214,517 0.77 948 106 218 1.0 0.7 None None 5 2,161,246 2,126,900 1.61 1318 102 219 1.0 0.8 None None 5 2,190,608 2,153,284 1.73 879 67 220 1.0 0.9 None None 5 2,201,509 2,175,200 1.21 1139 89 221 1.0 1.0 2, 3, 5, 8, 10 N/A 5 2,222,254 2,197,156 1.14 818 68 222 1.0 1.1 14,20 10 6 2,250,555 2,222,358 1.27 830 93 223 1.0 1.2 14,20 10 6 2,264,535 2,243,913 0.92 882 96 224 1.0 1.3 14 10 5 2,285,395 2,264,942 0.90 867 102 225 1.1 0.7 None None 5 2,207,470 2,165,608 1.93 1225 96 226 1.1 0.8 14 3 5 2,236,425 2,191,676 2.04 1293 98 227 1.1 0.9 None None 5 2,247,732 2,214,688 1.49 808 54 228 1.1 1.0 14 10 5 2,267,266 2,241,419 1.15 904 70 229 1.1 1.1 None None 5 2,300,405 2,259,632 1.80 830 63 230 1.1 1.2 14 10 5 2,319,191 2,283,489 1.56 884 78 231 1.1 1.3 14 10 5 2,331,122 2,308,181 0.99 925 108 232 1.2 0.7 None None 5 2,253,693 2,203,840 2.26 1004 67 233 1.2 0.8 None None 5 2,283,055 2,231,213 2.32 1341 104 234 1.2 0.9 None None 5 2,293,956 2,252,404 1.84 827 53 235 1.2 1.0 None None 5 2,314,701 2,283,059 1.39 815 63 236 1.2 1.1 None None 5 2,346,628 2,306,865 1.72 811 65 237 1.2 1.2 14 10 5 2,364,918 2,333,821 1.33 935 100 238 1.2 1.3 14 10 5 2,376,850 2,354,471 0.95 833 115 239 1.3 0.7 14 10 5 2,299,850 2,242,041 2.58 1249 85 240 1.3 0.8 None None 5 2,329,278 2,270,854 2.57 781 51 241 1.3 0.9 None None 5 2,340,179 2,298,306 1.82 1211 78 242 1.3 1.0 None None 5 2,360,924 2,310,342 2.19 773 50 243 1.3 1.1 None None 5 2,392,852 2,346,581 1.97 797 50 244 1.3 1.2 12 10 5 2,422,495 2,365,429 2.41 786 50 245 1.3 1.3 14 10 5 2,422,577 2,400,707 0.91 855 55 (∗): with respect to base case, Prob no 221; N/A, not applicable.Table 13
Results for the second relaxation,R=3 and QCap=600; QCap=900.
Prob no. FC FV DCs opened (∗) DCs closed (∗) No. of open DCs Upper Bound Lower Bound % Gap Lag iter CPU time (s) 246 0.7 0.7 None 12 11 2,762,632 2,624,245 5.27 813 51 247 0.7 0.8 1 16 12 2,821,579 2,667,098 5.79 1700 102 248 0.7 0.9 1 19 12 2,852,741 2,699,063 5.69 1800 109 249 0.7 1.0 1 12 12 2,902,314 2,738,089 6.00 1653 102 250 0.7 1.1 1 11 12 2,924,387 2,767,645 5.66 1674 101 251 0.7 1.2 15 None 13 2,988,536 2,808,140 6.42 1526 94 252 0.7 1.3 15 None 13 3,028,174 2,839,398 6.65 1534 94 253 0.8 0.7 7 12,16 11 2,860,498 2,719,105 5.20 851 54 254 0.8 0.8 None 19 11 2,919,636 2,764,674 5.61 2577 153 255 0.8 0.9 1 19 12 2,965,225 2,797,354 6.00 1691 101 256 0.8 1.0 1 12 12 3,017,797 2,839,010 6.30 1703 102 257 0.8 1.1 1 11 12 3,038,856 2,869,832 5.89 1917 123 258 0.8 1.2 15 None 13 3,111,402 2,913,305 6.80 1436 86 259 0.8 1.3 7,15 16 13 3,136,899 2,946,396 6.47 1599 95 260 0.9 0.7 None 12 11 2,972,986 2,814,084 5.65 1240 79 261 0.9 0.8 None 19 11 3,021,814 2,862,296 5.57 1713 107 262 0.9 0.9 1 19 12 3,077,708 2,895,100 6.31 2142 134 263 0.9 1.0 1 12 12 3,133,280 2,939,919 6.58 1595 105 264 0.9 1.1 1 11 12 3,153,325 2,972,015 6.10 1771 119 265 0.9 1.2 15 None 13 3,234,269 3,018,470 7.15 1491 97 266 0.9 1.3 15 None 13 3,273,907 3,053,394 7.22 1687 108 267 1.0 0.7 7 12,16 11 3,071,115 2,908,436 5.59 1463 94 268 1.0 0.8 15 10,16 11 3,122,842 2,956,507 5.63 2108 129 269 1.0 0.9 1 19 12 3,190,192 2,993,937 6.56 1776 113 270 1.0 1.0 2,3,5,8,10,11,12 13,14,16,19,20 N/A 12 3,241,325 3,040,813 6.59 1574 98 271 1.0 1.1 1 11 12 3,267,793 3,074,195 6.30 1497 90 272 1.0 1.2 15 None 13 3,357,135 3,123,635 7.48 1793 106 273 1.0 1.3 15 None 13 3,396,774 3,160,391 7.48 1428 83 274 1.1 0.7 7 12,16 11 3,176,424 3,006,561 5.65 1631 102 275 1.1 0.8 None 12 11 3,243,314 3,054,626 6.18 2187 134 276 1.1 0.9 1 19 12 3,302,676 3,092,207 6.81 1806 110 277 1.1 1.0 1 12 12 3,364,246 3,141,710 7.08 1610 97 278 1.1 1.1 15 3 12 3,377,059 3,176,389 6.32 1350 83 279 1.1 1.2 1,15 19 13 3,479,214 3,228,800 7.76 1691 100 280 1.1 1.3 15 None 13 3,519,640 3,267,390 7.72 1667 100 281 1.2 0.7 None 16 11 3,268,978 3,101,566 5.40 1734 107 282 1.2 0.8 None 19 11 3,328,346 3,152,607 5.57 1645 99 283 1.2 0.9 1 19 12 3,415,160 3,190,419 7.04 1772 110 284 1.2 1.0 1 12 12 3,479,729 3,242,618 7.31 1715 107 285 1.2 1.1 15 3 12 3,489,521 3,278,575 6.43 1542 97 286 1.2 1.2 1,15 19 13 3,600,037 3,333,966 7.98 1428 83 287 1.2 1.3 15 None 13 3,642,507 3,374,388 7.95 1491 86 288 1.3 0.7 1 3,19 11 3,389,315 3,194,564 6.10 1805 108 289 1.3 0.8 None 19 11 3,430,524 3,248,659 5.60 1706 101 290 1.3 0.9 1 19 12 3,527,644 3,288,238 7.28 1589 94 291 1.3 1.0 15 16 12 3,592,914 3,343,519 7.46 1539 91 292 1.3 1.1 15 11 12 3,618,080 3,380,594 7.02 1630 97 293 1.3 1.2 1,15 19 13 3,720,860 3,439,130 8.19 1549 88 294 1.3 1.3 1,15 19 13 3,761,791 3,481,305 8.06 1666 101 (∗): with respect to base case, Prob no 270; N/A, not applicable.Table 14
TC ij, fixed transportation cost between the warehouse i and the customer j.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 68015 26816 58294 85997 91121 23524 78853 27326 94451 93276 71013 8557 32141 18954 54919 42018 68610 27355 46763 49274 2 54038 17036 45491 72276 78255 30363 66441 16354 78457 78339 70782 12676 20651 4233 43819 26047 54243 41907 47661 41910 3 57369 56031 7346 70964 29915 59932 19578 35692 47128 32015 63671 55129 31019 48718 64344 32777 54938 90004 54232 29825 4 82616 99538 53516 87042 26639 107004 37444 83516 43137 18196 96759 102914 78869 94900 97864 74447 79407 137435 96435 72772 5 87898 57221 44189 105728 70870 18453 58614 29490 96491 82442 31581 32253 29929 44092 82409 54293 87054 60700 7508 22878 6 25140 16929 53845 42810 81590 60808 72476 39255 61106 72848 96432 42929 40589 26281 14209 20466 26270 61391 75337 62142 7 34478 15893 40983 52744 70906 49068 60749 25176 60212 65563 82049 32716 26160 16594 28605 9228 34371 58596 61419 47673 8 20228 23619 60514 36564 86669 68864 78273 47567 60883 76029 104668 50753 48786 34271 5997 27425 22206 66376 83672 70092 9 38479 15979 68192 53608 97859 61322 87970 46848 78428 90386 103439 42643 49723 29094 19554 35769 40581 49842 80463 72160 10 80170 83491 29855 90526 3778 80441 9131 60634 54537 25055 66543 79814 55819 75627 90235 60023 77310 115246 67091 44528 11 11595 31295 60191 28373 83808 74935 76416 51706 53628 71239 107874 57344 52189 40622 9348 28742 13708 74858 87939 72342 12 71842 57524 13554 87537 39199 44878 26654 28595 67891 50207 43357 46204 24220 46508 73906 40661 69965 81471 34138 9675 13 97465 76822 39310 113620 53169 46412 43091 45847 92847 70832 17915 57044 43225 64128 97425 64942 95768 88456 23429 21367 14 34706 47575 29307 47199 46518 69820 40347 42049 30947 35054 85268 58677 38954 46038 45728 23021 31973 89510 71647 49201 15 94150 54770 66854 112399 96851 13350 84307 40691 113649 105275 54025 27473 44176 44214 82895 63865 94266 37596 32293 48848 16 29475 22028 39006 47545 67089 54632 57675 29050 53348 60048 84464 39064 28969 23358 27613 5697 28909 65484 65006 48979 17 99639 66306 56804 117649 81916 21246 69979 41154 109403 94751 29856 39191 42234 53504 92775 66308 98969 61074 11134 34885 18 57060 17006 51224 75148 84036 29779 72151 21396 83666 84193 73290 11081 25946 7844 45023 31161 57551 36114 49591 46375 19 56743 32264 27250 74521 60120 31303 47981 3957 69365 63077 57615 23341 1855 20618 53015 23087 55849 58424 37566 24292 20 80126 38060 73004 97611 105687 29464 93292 42082 109198 108456 78131 22652 46859 33345 64848 56693 81098 13325 54296 61885Table 15
TC ij, fixed transportation cost between the warehouse i and the customer j.
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 1 72703 46345 20056 7194 71962 40887 55999 68423 15895 77913 51138 66081 61667 88720 78259 7130 54735 16090 66690 18564 2 59896 32132 4388 22583 65202 41304 42203 61033 19380 66009 50540 50795 47891 77046 62396 23055 44916 23003 50919 34467 3 12655 47280 46809 67126 39077 50892 52574 34509 67591 20727 51493 13120 1080 31167 28561 68615 68854 57878 20505 80578 4 40747 84238 93075 114940 67474 94809 84558 65384 113495 40476 92116 45715 48924 35934 41371 116378 103072 105559 48616 128358 5 54963 67485 43129 37684 38332 1532 77383 36511 54368 56118 11800 61753 50373 64751 77672 40026 84310 23831 66644 48355 6 65579 6844 26423 50436 83459 69100 13254 78692 33844 73573 76975 46932 52373 84079 50683 49982 17137 53494 42477 58912 7 53805 13002 15787 42474 69250 55275 23113 64524 31564 61417 62771 38071 40552 72249 46050 42643 31577 42339 35664 53304 8 71466 11707 34548 57559 91017 77437 10366 86216 39456 79630 85277 51524 58447 89858 52884 56915 9951 61452 46160 65098 9 81025 24610 30347 45995 94838 74107 28431 90274 25146 88676 83259 63908 67756 99492 68444 44760 17046 53525 59964 50673 10 15444 73761 73701 91424 37258 66133 77686 35136 94441 11018 62448 34035 28269 7461 41415 93181 95016 80307 40807 104908 11 69811 13687 40589 64991 92078 81842 4985 87229 47713 78125 89038 48593 57252 87874 47529 64506 14555 67768 42385 73164 12 22497 56518 44668 57148 23049 31712 64333 18238 64121 24664 30897 33291 20010 34716 49202 59096 77560 45148 39923 70447 13 42714 80483 62612 64748 13022 26551 89118 14372 78518 39686 17560 59050 45461 44690 74564 67053 100508 50814 66004 76197 14 34342 31044 44511 70270 62625 66935 32661 57937 63196 42636 70294 11842 23986 51396 14324 71063 50787 65286 4942 82664 15 79666 72250 44455 22254 66323 29406 82329 64441 43747 82236 38126 80939 72192 91657 95662 23949 83066 17824 83921 25769 16 50761 10221 22392 49197 69358 59052 19135 64542 38312 58713 65807 33067 37527 69272 39652 49442 31501 48240 29774 60203 17 66871 78711 52857 40988 45971 13180 88766 45280 60537 67235 16532 74642 63075 75057 90579 43240 94227 28783 79556 48808 18 65653 35278 9184 18268 69654 43302 45070 65635 14186 71638 53009 56610 53741 82651 67937 18313 45447 22026 56548 29203 19 41689 36925 18806 35350 47186 31688 46534 42772 38408 47291 38457 37032 30730 58265 51347 36829 55721 27296 39593 48791 20 87326 59120 34706 11175 83610 49294 68171 80515 21967 92147 59495 81289 76643 102786 93319 9241 63619 24619 81807 3923The upper bound to errors was 6.4% and 6.5% for first and second Lagrangian relaxation for instances withR= 3, which are higher than instances withR = 1. This might be explained by an increment in duality gaps instead of a heuristic error. For more details of complete results, see Tables 8–13 in Appendix B.


## 7. Conclusions and Managerial Insights

This research paper is focused on studying a simultaneous model addressing inventory and location decisions, with stochastic demands assuming a periodic review policy and probabilistic constraints of inventory capacity. We determine the location of warehouses from a strategic perspective while taking into consideration several inventory concerns such as costs and constraints. Note that the safety stock and order quantity costs and decisions are also integrated.The model is built on mathematical expressions for safety stocks, probabilistic inventory capacity constraints, and average cyclic inventory costs. These expressions are considered when on-hand inventory level is lower than reorder inventory level afterR periods. This produces an additional ordering quantity called undershoot, which is a relevant issue widely reviewed and researched in the inventory control field.Furthermore, the fact that the Lagrangian relaxation approach can be applied to solve the ILP with periodic review and stochastic inventory capacity constraints is a significant contribution to the field of study. It is important to mention that a set of inequalities and a local search Lagrangian heuristic are taken into account to provide effective solutions, similar to some related previous studies.It is shown that upper bounds of the Lagrangian relaxation approach increase when review periods are larger while observing more stable behavior. This is based on a numerical application of small real size instances. This result may be explained because of an increment in duality gaps rather than the heuristic error.In terms of managerial insights, an integrated inventory location model with a periodic review is suggested to be implemented when the supply chain network topology is analyzed, and the review period of inventory control decisions is significant (2 or more days). Review periods involve a prominent usage of storage space at warehouses or distribution centers, which affects the strategic network topology. Nevertheless, it is not enough to solely analyze benefits related to inventory costs for periodic review versus continuous review policies, or evaluating the variation in the review period of the inventory control policy. As a consequence, strategic network topology costs, such as facility location and transportation costs, must be included in the analysis. Finally, the solution approach and line of research are enhanced, as this allows modeling of several significant issues in inventory control, simultaneously with facility location issues, within the scope of supply chain network design problems.Further research is suggested in the analysis of different Lagrangian relaxations that may lead to better dual lower bounds and duality gaps. Issues such as different periodic inventory control policies, a multicommodity scenario, demand backorders and backlogging features, and service level optimization may be considered for future investigation. Additionally, we encourage the examination of other Lagrangian heuristics, such as simple versions of Ant Colony Optimization and GRASP, among other well-known heuristics and metaheuristics. In terms of supply chain network design issues, having in mind the present inventory location modeling structure, different distribution strategies may be studied simultaneously with inventory planning aspects (e.g., direct shipments and cross-docking).



---

*Source: 8237925-2018-10-08.xml*