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.

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 Figure 1 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 for each warehouse, where is the period review, is the reorder point, and 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 Section 2, 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 one 1- 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 and , 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 (s_i, S_i, R_i) inventory control policy, capacity constraints cannot be stated at any moment. In an (s_i, S_i, R_i) inventory control policy, inventory levels are reviewed after R_i periods for each warehouse i. 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 level s_i, then an order is placed to reach the objective level S_i. Consequently, order size for each warehouse i must consider the well-known undershoot magnitude (US_i), which is the number of items required to be ordered in addition to S_i-s_i, in order to reach S_i units of inventory, as shown in Figure 2. In other words, the US_i is the difference between the reorder point s_i and the inventory level directly prior to ordering.

Figure 2 

Inventory levels under an (s, S, R) control policy.

For a given review period , demand mean, and variance of a warehouse ( and ), the average undershoot magnitude is computed as follows [33]:Peak 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, 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 When an order is submitted to the plant, it is required that total inventory position reaches the level , and later; inventory level is reduced by lead time demand . 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 probability, but now assuming a periodic review, as follows:This constraint is reformulated as a deterministic nonlinear constraint, which guarantees that the probabilistic constraint is fulfilled: We specify the minimum order size as :In consequence, constraint (4) can be written asFinally, the reorder point is set in order to ensure that an order is not submitted at each moment in time (i.e., inventory level is larger than ). The inventory level must be enough to fill demand until the next order has arrived time units, with a probability or service level :Similar to (3), this constraint is reformulated as a deterministic nonlinear constraint:Finally, replacing (8) in (6), the inventory capacity constraint for each warehouse can be written asBased on a periodic 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:In addition, expected inventory and ordering costs related to order quantity or cycle inventory are evaluated in terms of the minimum order quantity and the average undershoot , as in EOQ model:

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: : number of available sites to install warehouses : number of customers to be served : transportation unit cost between the plant and the warehouse ($/unit) : fixed transportation cost between the warehouse and the customer  : operating fixed cost for each warehouse ($/day) : holding cost per time unit at site ($/day) : fixed ordering cost per time unit at site ($/day) : deterministic lead time when ordering from warehouse  : mean of the daily demand for each customer  : variance of the daily demand for each customer  : variance of the daily demand for each customer  : value of the standard normal distribution, which accumulates a probability of  : value of the standard normal distribution, which accumulates a probability of  : order capacity of the warehouse  : inventory capacity of the warehouse

The variables considered in the mathematical formulation are as follows:

: it takes the value 1, if a warehouse is located on site , and 0 otherwise

: it takes the value 1, if warehouse serves customer , and 0 otherwise

: order size at the warehouse (units)

: served demand by each warehouse (units)

: variance of the served demand by each warehouse

Consequently, the SNL-MIP model to solve the problem isThe 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 (). Constraints (15) ensure that inventory capacity for each warehouse is fulfilled at least with a probability . Constraints (16) ensure that the order size is below the capacity order size allowed to warehouse . 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 and Y) from inventory control decisions (Q) and mean and variance for demand (D and V) 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: For fixed values of the Lagrangian multipliers, , , and , we minimize (21) over location variables, , and the assignment variables . For the given , , and vectors, the problem decouples to the following subproblem for each warehouse : We include a set of valid inequalities 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 and [19].

Each subproblem (22) may be decoupled for the fixed values of the Lagrangian multipliers for each iteration , , as follows:   denotes the benefit of facility and represents the contribution of opening facility to the objective function (12). This decomposition consists of solving to compute and then solving to calculate , based on the computed , 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: For fixed values of the Lagrangian multipliers, and , we want to minimize (25) over location variables, , and the assignment variables . For the given and vectors, the problem decouples to the following subproblems:  Each subproblem (26) may be decoupled for the fixed values of the Lagrangian multipliers for each iteration , , in the following subproblems for each warehouse :  This decomposition consists of solving to compute and then solving to calculate , based on the computed , as explained in Section 5.3.

5.3. Subproblem Solving

5.3.1. First Lagrangian Relaxation

For fixed values of the Lagrangian multipliers , which are associated with relaxing constraints (17), (18), and (13), respectively, we obtain an infeasible solution of the primal problem in each iteration of the algorithm. This solution generates a lower bound on the optimal value of the primal problem.

First, we solve to calculate the value of of subproblems (23), for which an exact procedure is found in Miranda [36]. Once is obtained, is solved based on the value of according to Algorithm 1 (see Appendix A).

5.3.2. Second Lagrangian Relaxation

For fixed values of the Lagrangian multipliers and , which are associated with relaxing constraints (17) and (18), respectively, we obtain an infeasible solution of the primal problem in each iteration 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 to calculate the value of of subproblems (26), which is identical to subproblem (23). Once is obtained, is solved based on the value of through the solver CPLEX.

5.4. Lagrangian Heuristic and Subgradient Optimization

At each iteration k 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 to N, based on the results and dual information of the subproblems . Namely, the complete heuristic is executed N 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 solution of the subproblems and the Lagrange multipliers () are known. For the warehouse selection, the optimal costs of subproblems are taken as initial values. Then, the best warehouses are chosen (see Algorithm 2 in Appendix A).