# A Capacitated Location-Inventory Model with Demand Selection

Authors: Zhengyi Li; Jiangtao Hai
Journal: Journal of Advanced Transportation
 (2019)

---

## Abstract

In this paper, we consider an integrated supply chain network design problem, which incorporates inventory and pricing decisions into the capacitated facility location model. We assume that each warehouse has a capacity limitation that limits the average demand flowing through the warehouse and that the supplier can choose whether to satisfy each potential retailer’s demand. We formulate the problem as a nonlinear integer programming model and solve the model via a Lagrangian relaxation based approach. We develop an efficient algorithm to solve the subproblem that arises from the Lagrangian relaxation procedure. Finally, we conduct extensive computational experiments to test the performance of the algorithms proposed in this paper and provide the managerial insights based on the computational results.


---

## Body

## 1. Introduction

Network design is among the most important supply chain decisions, as their implications are significant and long lasting. Thus, in designing a supply chain distribution network, the supply chain drivers, such as facilities, transportation, inventory, and pricing, should be considered together to support the competitive strategy of a company and maximize the supply chain profits [1]. Traditionally, decisions associated with these drivers are made separately. In this paper, we study an integrated supply chain distribution network design problem, which incorporates inventory and pricing decisions into the capacitated facility location model. We consider that a supplier (company) owns the production facility and produces one type of product to serve a set of potential retailers, each facing an uncertain demand. The supplier replenishes the retailers via the warehouses that serve as intermediate facilities for the shipment of the product. The objective of the supplier is to determine how many warehouses to locate and where to locate them, which retailers to assign to each warehouse, when and how many to reorder and what level of the safety stock to maintain at warehouses, and how much the sale price of the product at each region associated with a particular warehouse to maximize the total profits, while ensuring that the capacity constraints for warehouses are not exceeded and maintaining a specific service level. The total profits for the supplier are equal to the total revenues subtracting the transportation cost, the working inventory and safety stock holding cost at the warehouses, and the locating and operating cost of the warehouses.In the supply chain distribution network design problems, most papers assume that all the demands should be served by the supplier, and then the objective is to minimize the system-wide costs. In practice, it is advisable that the supplier may lose some potential retailers to competitors in order to increase the profits because either the costs of serving those retailers can be very costly [2, 3] or the warehouses serving those retailers have capacity limitations, possibly both. Therefore, in this paper, we consider that the supplier can choose whether to satisfy each potential retailer’s demand and then explore the benefits that the supplier will achieve by conducting this market strategy. The supplier determines which retailers to serve via the pricing decisions. In the pricing decisions, each retailer holds a reserve price for the product, and if the per unit cost charged for a retailer by the supplier is higher than the retailer’s reserve price, the supplier will lose the retailer. The per unit cost charged for a retailer contains the wholesale price of the product and the per unit transportation cost from a specific warehouse to the retailer. Thus, it is important for the supplier to determine the wholesale price of the product at each region associated with a particular warehouse, which directly affects the supplier in terms of the level of profit achieved as well as the demand profile that the supplier attempts to serve.Furthermore, in this paper, we assume that each warehouse is subject to a capacity limitation, such as in the capacitated fixed charged facility location problem, which limits the average demand that flows through the warehouse. This situation might occur, for example, in contexts where the plant has a finite annual production capacity, or the warehouse has only a fixed number of square feet of storage space. The warehouse capacity constraints considered in this paper are different with those considered in Ozsen et al. [4], which limit the maximum possible inventory accumulation at the warehouses.In summary, the distribution network design problem studied in this paper has the following features. (i) Each warehouse has a capacity limitation that limits the average demand flowing through the warehouse; (ii) each retailer faces an uncertain demand; (iii) the supplier can choose which potential retailers to serve; (iv) the objective of the supplier is to maximize the total profits. The main contribution of this paper is that, in designing the supply chain distribution network, we consider these features simultaneously and introduce an algorithm to solve the problem effectively.The rest of this paper is organized as follows. In Section2, we provide a review of the literature. In Section 3, we present a nonlinear integer programming model for the capacitated distribution network design problem. In Section 4, we introduce a Lagrangian relaxation based approach to solve the capacitated distribution network design problem and an efficient algorithm to solve the subproblem that arises from the Lagrangian relaxation procedure. In Section 5, we present the computational results. Finally, we conclude our discussions in Section 6.


## 2. Literature Review

Recently, there is an extensive body of research on the supply chain network design, such as supply chain network design with multiechelon inventory [5, 6], multicommodity supply chain network design [7, 8], multisourcing supply chain network design [9–11], multiobjective supply chain network design [12, 13], reliable supply chain network design [14–16], closed-loop supply chain network design [17, 18], and green supply chain network design [19–22]. We refer the readers to Shen [23], Melo et al. [24], Farahani et al. [25], and Govindan et al. [26] for reviews of related research.In this paper, we only review literature on the location-inventory models that aim to minimize the sum of facility location costs, transportation costs, and inventory-related costs by choosing the optimal warehouse locations among given candidate sites to serve a set of retailers and at the same time determining the optimal inventory replenishment policies for the warehouses. Nozick and Turnquist [27] study a distribution network design problem, in which the inventory policy adopted at the distribution centers is an (s-1, s) continuous review policy, and the safety stock holding costs are approximated by a linear function of the number of distribution centers. They formulate the problem as a fixed-charge facility location model with inventory costs included in the fixed location cost as a constant. Shen et al. [28] study an uncapacitated location-inventory problem, in which the mean-to-variance ratio of the demand at each retailer is identical for all retailers, and the risk-pooling benefits are considered. They formulate the problem as a set-covering model and then make use of a column generation based approach to solve the set-covering model. Daskin et al. [29] formulate the same problem as a nonlinear integer programming model, and they develop a Lagrangian relaxation procedure to solve their model. Shu et al. [30] extend the works of Shen et al. [28] by proposing an effective algorithm for the pricing problem that arises from the column generation for all demand patterns. Sourirajan et al. [31] study a distribution network design problem that focuses on the trade-off between the safety stocks and the leading times at the DCs, in which they assume the leading time at a DC is directly related to the total demands assigned to the DC. They consider the facility location costs, the pipeline inventory costs between the production facility and the DCs, and the safety stock holding costs at the DCs, but they ignore the transportation costs between the DCs and the retailers in their model. They solve their model by a Lagrangian relaxation based algorithm. Berman et al. [32] study a coordinated location-inventory problem in which they consider a periodic review (R,S) inventory policy at distribution centers and two types of coordination for the distribution network system, i.e., partial coordination and full coordination. They show that the full coordination increases the location and inventory costs, but it is likely to reduce the overall costs of running the distribution system.The models we discuss above deal with the problems in which the facilities are uncapacitated. Miranda and Garrido [33] propose a distribution network design model by incorporating inventory decisions into the capacitated facility location model, which also captures the risk-pooling effects. They develop a heuristic algorithm based on Lagrangian relaxation for solving the model by decomposing the corresponding Lagrangian dual problem into three subproblems. Ozsen et al. [4] study a capacitated logistic network design problem with risk-pooling, in which they consider the capacity constraint on the maximum possible inventory accumulation at a given warehouse instead of the capacity constraint that limits the average quantity of products flowing through the warehouse. They formulate the capacitated logistic network design problem as a nonlinear integer programming model and solve it by a Lagrangian relaxation based algorithm. Ozsen et al. [9] study a similar problem such that they consider multisourcing retailers; i.e., each retailer can be supplied by two or more warehouses. Vidyarthi et al. [34] and Park et al. [35] study the multistage distribution network design problems that need to determine the number and locations of suppliers or plants. Vidyarthi et al. [34] assume that both DCs and suppliers have finite capacity, and Park et al. [35] assume that only DCs have finite capacity.However, the literature on supply chain distribution network design problems with integrating the pricing decisions is rather limited. Zhang [36] proposes a profit-maximizing location model, where a firm, facing a set of potential retailers, needs to determine where to locate its center warehouse and the price for its product. He assumes that each retailer holds a reserve price for the product and if the actual price charged by the firm is higher than the reserve price, then the retailer will be lost from the firm. But he ignores the inventory cost in his model. Shen [3] studies a location-inventory problem with integrating the pricing decisions. He considers that each warehouse has no capacity limitation and each retailer faces a deterministic demand. He formulates the problem as a set-packing model and then solves it via column generation. Shu et al. [37] propose a two-echelon location-inventory model with a profit-maximizing objective. They assume that both warehouses and retailers carry inventory, and the supplier is in charge of the warehouse-retailer inventory replenishment. They formulate the problem as a set-packing model and then introduce a column generation based approach for solving the set-packing model. Ahmadi-Javid and Hoseinpour [38] study a profit-maximization multicommodity supply chain network design problem. They assume that the customer demands are price-sensitive and formulate the problem as a mixed-integer nonlinear programming model for the uncapacitated and capacitated distribution centers, respectively. They use Lagrangian relaxation based algorithm to solve their model.In this paper, we present a capacitated location-inventory model by incorporating inventory and pricing decisions into the capacitated facility location model. The problem we studied in this paper is closely related to Miranda and Garrido [33], Shen [3], Ozsen et al. [4], Shu et al. [37], and Ahmadi-Javid and Hoseinpour [38]. Comparing with Shen [3] and Shu et al. [37], the feature of our paper is that we consider each warehouse has a capacity limitation, and each retailer faces an uncertain demand; comparing with Miranda and Garrido [33], the feature of our paper is that we integrate the pricing decisions into the supply chain network design; comparing with Ozsen et al. [4], the feature of our paper is that we consider different warehouse capacity constraints; comparing with Ahmadi-Javid and Hoseinpour [38], the feature of our paper is that we consider that the supplier can choose which retailers to serve, and each retailer faces an uncertain demand. We formulate this capacitated distribution network design problem as a nonlinear integer programming model and then introduce a Lagrangian relaxation based approach to solve this model. The subproblem that arises from the Lagrangian relaxation procedure is a nonlinear zero-one integer programming model, which maximizes a convex objective function subject to a single knapsack constraint. We also use the Lagrangian relaxation to solve the subproblem. Finally, we conduct the computational experiments to test the efficiency and effectiveness of the algorithms proposed in this paper.


## 3. Model Formulation

We consider a distribution network consisting of a production facility, a set of candidate warehouses, and a set of potential retailers, where the location of the production facility and the retailers is known, and the production rate of production facility is infinite. We assume that a supplier owns the production facility and produces one type of product, where we ignore the production cost. After production, the supplier transports the product to several warehouses for distribution. We also assume that the leading time from the production facility to each candidate warehouse is deterministic, and the demand at each retailer is uncorrelated across retailers, and that if the supplier chooses to serve a retailer, the supplier should satisfy all the demand of the retailer. In this paper, we consider single source strategy, which means a retailer is only served by one warehouse. The notations we used throughout the paper are defined as follows.Sets I: set of potential retailers; J: set of candidate warehouse locations;Inputs and Parameters u i: mean demand per year at retailer i, for each i∈I. We calculate ui using the formula ui=χui′, where ui′ is the mean demand per day at retailer i and χ is a constant used to convert daily demand into annual demand, e.g., χ=300; σ i: variance of daily demand at retailer i, for each i∈I; d 0 j: per unit transportation cost of delivering product from the supplier to warehouse j, for each j∈J; d i j: per unit transportation cost of delivering product from warehouse j to retailer i, for each i∈I; K j: fixed cost of placing an order from warehouse j to the supplier, for each j∈J; h j: per unit inventory holding cost rate at warehouse j per year, for each j∈J; L j: leading time in days for deliveries from the supplier to warehouse j, for each j∈J; α: the desired percentage of retailers orders satisfied; z α: standard normal deviate such that P(z≤zα)=α; v i: the reserve price of retailer i, for each i∈I; f j ( · ): the (annual) cost of locating and operating warehouse j, which is a concave and nondecreasing function of the annual demand flows through warehouse j, for each j∈J; C j: the capacity of warehouse j, for each j∈J;Decision Variables p j: per unit wholesale price of the product at the region served by warehouse j, for each j∈J; x j = 1, if we locate a warehouse at candidate location j, and 0 otherwise, for each j∈J; y i j = 1, if the demand at retailer i is served by warehouse j, and 0 otherwise, for each i∈I,j∈J.Letri(pj,dij) denote the per unit gross profits of serving retailer i using warehouse j for the supplier, and we define ri(pj,dij) in the following. We know that when the wholesale price plus the per unit transportation cost charged to a retailer is higher than the retailer’s reserve price, this retailer will turn to some other suppliers; i.e., the supplier will lose this retailer. Then we have [3, 36] (1)ripj,dij=pj+dij-d0j,pj+dij≤vi,0,pj+dij>vi.We know that when pj+dij≤vi, retailer i can be served by the supplier for the per unit cost retailer i has to pay lower than his reserve price, and thus the supplier can get revenues from serving retailer i; when pj+dij>vi, retailer i cannot be served by the supplier for the per unit cost, retailer i has to pay higher than his reserve price, and thus the supplier cannot get any revenue from retailer i. Therefore, the pricing decisions determine which retailers can be served by the supplier, which is important for maximizing the supplier’s profits.In this paper, we focus on Type I service level [39], i.e., probability of no stock out per order cycle, which is one of the most commonly used service levels in inventory management [40, 41], and for calculating the safety stocks at warehouses, we assume that the normal approximation for demands is appropriate [28]. Since retailer demands are independent and the normal approximation for demands is appropriate, the warehouse demands can be represented by the Normal distribution. Thus, for each warehouse j, the leading time demand at warehouse j is Normal distribution with mean Lj∑i∈Iui′yij and variance Lj∑i∈Iσi2yij, and then the safety stock required at warehouse j with the probability α of no stock out per order cycle is zαLj∑i∈Iσi2yij.Using the above notations, we formulate the capacitated distribution network design problem as follows:(2)P:max∑j∈J∑i∈Iripj,dijuiyij-2hjKj∑i∈Iuiyij-hjzαLj∑i∈Iσi2yij-fj∑i∈Iuiyijxj(3)s.t.∑j∈Jyij≤1,∀i∈I,(4)yij-xj≤0,∀i∈I,j∈J,(5)∑i∈Iuiyij≤Cj,∀j∈J,(6)yij∈0,1,∀i∈I,j∈J,(7)xj∈0,1,∀j∈J.The first term of the objective function (2) is the gross profits of serving retailers using warehouses; the second term describes the working inventory holding cost determined by the EOQ model with ordering cost Kj, per unit holding cost hj, and demand ∑i∈Iuiyij; the third term represents the safety stocks holding cost; the fourth term is the cost of locating and operating warehouses, which is associated with how many demands flow through the warehouses. Constraint (3) states that a retailer may not be assigned to any warehouse. Constraint (4) stipulates that retailers can be only assigned to opened warehouses. Constraint (5) stipulates that the total demands served by a warehouse cannot exceed the capacity limit of the warehouse. Lastly, constraints (6) and (7) are standard integrality constraints, and constraint (6) also requires that each retailer is assigned to exactly one warehouse.Note that the above model formulated is an extension of the classic capacitated facility location problem, which is already NP-hard, and furthermore the objective function (2) of the above model contains nonlinear cost terms as well. Thus any commercial solver cannot solve the above model effectively. In what follows, we develop a Lagrangian relaxation based approach to solve the above nonlinear integer programming model.


## 4. Solution Approach

Lagrangian relaxation method has been used successfully to solve many integer programming problems, such as facility location problems and supply chain network design problems [4, 9, 29, 34, 42, 43]. Fisher [44] gives an excellent discussion of the Lagrangian relaxation method for solving the integer programming problems. In this section, we develop a Lagrangian relaxation procedure to solve P. We first obtain the Lagrangian dual problem of P by relaxing the assignment constraint (3), and then, for fixed Lagrangian multipliers, the Lagrangian dual problem is a nonlinear zero-one integer programming model, which maximizes a convex objective function subject to a single knapsack constraint. We also use the Lagrangian relaxation method to solve the Lagrangian dual problem. We describe the details of the Lagrangian relaxation procedure as follows.


### 4.1. Obtaining an Upper Bound

We obtain the Lagrangian dual problem by relaxing the assignment constraint (3) and associating with a set of Lagrange multipliers, denoted by λi, as follows: (8)minλmaxx,y∑j∈J∑i∈Iripj,dijui-λiyij-∑j∈J2hjKj∑i∈Iuiyij-∑j∈JhjzαLj∑i∈Iσi2yij-∑j∈Jfj∑i∈Iuiyijxj+∑i∈Iλi(9)s.t.yij-xj≤0,∀i∈I,j∈J,∑i∈Iuiyij≤Cj,∀j∈J,yij∈0,1,∀i∈I,j∈J,xj∈0,1,∀i∈I,where λ=(λ1,λ2,…,λn), and λi≥0,i=1,2,…,n.Note that we solve the Lagrangian dual problem for fixed values of Lagrange multipliers,λi, to obtain an upper bound on optimal objective function value of the capacitated distribution network design problem. Clearly, we want to maximize the Lagrangian function (8) over decision variables, xj, yij, and pj, and to minimize the function over the Lagrange multipliers, λi. Minimizing the Lagrangian function (8) over the Lagrange multipliers, λi, can be done using subgradient optimization [44]. Therefore, we focus on solving the problem for fixed values of the Lagrange multipliers, λi.For fixed values of Lagrange multipliers,λi, we solve the following subproblem for each candidate warehouse j.(10)Pj:max∑i∈Iripj,dijui-λiyij-2hjKj∑i∈Iuiyij-hjzαLj∑i∈Iσi2yij-fj∑i∈Iuiyijs.t.∑i∈Iuiyij≤Cj,yi,j∈0,1.We note that Pj is a 0-1 integer programming problem with a nonlinear convex objective function and a single knapsack constraint. Let Oj be the optimal objective function value of Pj, and we easily know that ∑j:Oj>0,j∈JOj+∑i∈Iλi is an upper bound for the optimal objective function value of P. Since pj is a decision variable in the objective function of Pj, we first show how to solve Pj for a fixed pj, and then we show how to solve Pj when pj is a decision variable as well.


#### 4.1.1. Solution Approach forPj with a Fixed pj

For a fixedpj, we solve Pj by the Lagrangian relaxation method as well. By relaxing the capacity constraint (5), the Lagrangian dual problem of Pj is then formulated as follows:(11)minλ¯jmaxy∑i∈Iripj,dijui-λi-λ¯juiyij-2hjKj∑i∈Iuiyij-hjzαLj∑i∈Iσi2yij-fj∑i∈Iuiyij+λ¯jCj(12)s.t.yij∈0,1,where λ¯j is the Lagrange multiplier associated with the capacity constraint (5), and λ¯j≥0.For a fixed value of the Lagrange multiplierλ¯j, we want to maximize (11) over the assignment variables yij. Thus, for a fixed λ¯j, the Lagrangian relaxation dual problem of Pj reduces to the following problem:(13)Lλ¯j:max∑i∈Iripj,dijui-λi-λ¯juiyij-2hjKj∑i∈Iuiyij-hjzαLj∑i∈Iσi2yij-fj∑i∈Iuiyijs.t.yij∈0,1.LetO¯j be the optimal objective function value of Lλ¯j, and then O¯j+λ¯jCj is an upper bound for the optimal objective function value of Pj. Furthermore, we can rewrite Lλ¯j as a different but equivalent formulation as follows:(14)minS⊆Ifj∑i∈Sui+2hjKj∑i∈Sui+hjzαLj∑i∈Sσi2-∑i∈Sripj,dijui-λi-λ¯jui,where S is a subset of I.LetGj(∑i∈Sui)≡2hjKj∑i∈Sui+fj(∑i∈Sui) and ai(pj,dij)≡λi+λ¯jui-ri(pj,dij)ui. Then, Lλ¯j can be reformulated as(15)minS⊆I∑i∈Saipj,dij+Gj∑i∈Sui+hjzαLj∑i∈Sσi2.LetS¯j denote the optimal solution of (15), and we have the following observation.Lemma 1.
For eachi∈I, we have ai(pj,dij)<0 if i∈S¯j.Proof.
We prove it by contradiction. Suppose that there existsi∈S¯j such that ai(pj,dij)≥0. Then we let S^j=S¯j∖{i}, and note that the objective function value of (15) for S^j is less than that for S¯j, which contradicts the optimality of S¯j. We therefore establish that if i∈S¯j, then ai(pj,dij)<0.We defineIj-={i∈I∣ai(pj,dij)<0}. For a fixed pj, from Lemma (2), we know that when we solve Lλ¯j, we only focus on the retailers within the set Ij- instead of the set I. Then we let ai≡ai(pj,dij), bi≡ui, and ci≡σi2. As shown in Shu et al. [30], we know that the optimal solution of (15) is {i∣β(-bi/ci)+γ(-ci/ai)<1,i∈Ij-}, where both β and γ are arbitrary positive real numbers, i.e., β>0,γ>0.For a fixedpj, (15) can be solved in O(n2log⁡n) time [23, 30], where n is the number of retailers. In this paper, we solve (15) by a dual algorithm [23], and we depict the steps of the dual algorithm as follows.Step 1.
For each pair of (i, i′), i∈Ij-,i′∈Ij-, we solve the following linear equations: (16)β-biai+γ-ciai=1β-bi′ai′+γ-ci′ai′=1.
Let(βii′,γii′) denote the solution of (16), and we choose the solution if both βii′ and γii′ are positive.Step 2.
For the ease of exposition, we relabel theβii′ as βk so that βk≤βk+1, k=1,2,…,m and m≤I2, and we also denote β0=0, for k=0, and βm+1=+∞, for k=m+1.Step 3.
For eachk=0,1,…,m,
(a) LetΓi=(1-β′(-bi/ai))/(-ci/ai) for each i∈I-, where βk≤β′<βk+1, and we then sort the lines β(-bi/ai)+γ(-ci/ai)=1 in the nondecreasing value of Γi for all i∈Ij-.
(b) Letk1≤k2≤⋯≤k∣Ij-∣ denote the ordering of the lines when the value of Γi is obtained at β′. So, if Γkl≥0,l=1,2,…,Ij-, then {kl,kl+1,…,k∣Ij-∣},{kl+1,…,k∣Ij-∣},…,{k∣Ij-∣} are the feasible solutions of (15).Step 4.
From the feasible solutions of (15), we select the one with minimum objective function value of (15), and then this solution is the optimal solution of (15).Having solved the Lagrangian relaxation problemLλ¯j, we need to minimize the Lagrangian function (11) over the Lagrange multiplier λ¯j. We do so using a subgradient optimization procedure.We then show how to obtain a lower bound for the optimal objective function value ofPj, and it is sufficient to find a feasible solution for Pj. At each iteration of the Lagrangian procedure, we depict the details of the step for obtaining a feasible solution for Pj as follows:LetIj1={i∈Ij-∣yij=1} and Ij0={i∈Ij-∣yij=0}.Step 1.
If∑i∈Ij1uiyij≤Cj, then the current solution for the Lagrangian relaxation problem is feasible for Pj, and for a retailer i∈Ij0, we also let yij=1 for which the capacity constraint is satisfied and that increases the objective function value to the maximum based on the assignments made so far.Step 2.
If∑i∈Ij1uiyij≥Cj, for each i∈Ij1, we first let yij=0 for which yij=1 and that decreases the objective function value to the minimum based on the assignments made so far until the capacity constraint is satisfied. Secondly, we update the set Ij0, and then for a retailer i∈Ij0, we also let yij=1 for which the capacity constraint is satisfied and that increases the objective function value to the maximum based on the assignments made so far.Step 3.
Update the setIj1={i∈I∣yij=1}, and then Ij1 is a feasible solution of Pj.


#### 4.1.2. Solution Approach forPj When pj Is a Decision Variable

In this subsection, we discuss how to solvePj as well as decide the optimal sale price pj when the price pj charged to retailers is a decision variable. We let Sj∗ denote the optimal solution of Pj.LetIj={i∣dij<vi,i∈I}. Note that Ij is a set of potential retailers that can be served by warehouse j when the per unit sale price of the product is zero. To solve Pj and decide the optimal sale price pj, we first give the following theorem.Theorem 2.
Letpj∗ be the optimal price of Pj and pji=vi-dij,i∈Ij. When the optimal solution Sj∗ of Pj is a nonempty set, the optimal price pj∗ is in the set {pji,i∈Ij}.Proof.
For the notational convenience, we relabel the retailers in setIj as {1,2,…,Ij} so that pji+1≥pji,i=1,2,…,Ij.
Ifpj∗>pj∣Ij∣, pj∗+dij≥vi,∀i∈I. Then we have ri(pj∗,dij)ui-λi≤0,∀i∈I, and it is obvious that the optimal solution Sj∗ of Pj is an empty set. This is to say, no retailers can be served by warehouse j because of the high price, and at this time the optimal price has no practical significance. Thus we have 0<pj∗≤pj∣Ij∣.
Sincepj∗≤pj∣Ij∣, there exists an i0∈{1,2,…,Ij} such that pji0≥pj∗ and pji0=argminpji,i∈Ij(pji-pj∗). If pj∗=pji0, then pj∗∈{pji,i∈Ij}. If pj∗<pji0, then ri(pj∗,dij)ui-λi≤0,i∈{1,2,…,i0-1} and ri(pj∗,dij)ui-λi>0,i∈{i0,i0+1,…,Ij}, which implies that the optimal solution Sj∗⊆{i0,i0+1,…,Ij}. Notice that ri(pj∗,dij)<ri(pji0,dij),i∈{i0,i0+1,…,Ij}. Then, we have ri(pj∗,dij)-λi<ri(pji0,dij)-λi,i∈{i0,i0+1,…,Ij}, and we also have(17)∑i∈Sj∗ripj∗,dijui-λi-2hjKj∑i∈Sj∗ui-hjzαLj∑i∈Sj∗σi2-fj∑i∈Sj∗ui<∑i∈Sj∗ripji0,dijui-λi-2hjKj∑i∈Sj∗ui-hjzαLj∑i∈Sj∗σi2-fj∑i∈Sj∗ui.This would imply that pj∗ is not the optimal price of Pj and, therefore, a contradiction exists. We establish that pj∗∈{pji,i∈Ij}.Theorem2 shows that we can attain the optimal price pj∗ for Pj within the set {pji,i∈Ij}. Based on Theorem 2, we describe how to solve Pj when pj is a decision variable as follows:Step 1.
For eachi∈Ij, we first solve Pj at pj=pji by the algorithm proposed in Section 4.1.1.Step 2.
Then, we select the one with maximum objective value, and the corresponding solution and price are the optimal solution and price ofPj.


### 4.2. Obtaining a Lower Bound

In this subsection, we show how to obtain a feasible solution ofP, and, therefore, we obtain a lower bound on optimal objective function value for P. We depict the details of obtaining a feasible solution of P as follows. At each iteration of the Lagrangian procedure, we first fix the warehouse locations at those locations for which xj=1 in the current Lagrangian solution. Then we assign the retailers to the fixed warehouses in a two-step heuristic process.Step 1.
For retaileri, if ∑j∈Jyij≥1, then we assign retailer i to warehouse j for which yij=1 and that increases the profit to the maximum based on the assignments made so far.Step 2.
For retaileri, if ∑j∈Jyij=0, then we assign retailer i to warehouse j for which the capacity constraint is satisfied and that increases the total profit to the maximum based on the assignments made so far.


## 4.1. Obtaining an Upper Bound

We obtain the Lagrangian dual problem by relaxing the assignment constraint (3) and associating with a set of Lagrange multipliers, denoted by λi, as follows: (8)minλmaxx,y∑j∈J∑i∈Iripj,dijui-λiyij-∑j∈J2hjKj∑i∈Iuiyij-∑j∈JhjzαLj∑i∈Iσi2yij-∑j∈Jfj∑i∈Iuiyijxj+∑i∈Iλi(9)s.t.yij-xj≤0,∀i∈I,j∈J,∑i∈Iuiyij≤Cj,∀j∈J,yij∈0,1,∀i∈I,j∈J,xj∈0,1,∀i∈I,where λ=(λ1,λ2,…,λn), and λi≥0,i=1,2,…,n.Note that we solve the Lagrangian dual problem for fixed values of Lagrange multipliers,λi, to obtain an upper bound on optimal objective function value of the capacitated distribution network design problem. Clearly, we want to maximize the Lagrangian function (8) over decision variables, xj, yij, and pj, and to minimize the function over the Lagrange multipliers, λi. Minimizing the Lagrangian function (8) over the Lagrange multipliers, λi, can be done using subgradient optimization [44]. Therefore, we focus on solving the problem for fixed values of the Lagrange multipliers, λi.For fixed values of Lagrange multipliers,λi, we solve the following subproblem for each candidate warehouse j.(10)Pj:max∑i∈Iripj,dijui-λiyij-2hjKj∑i∈Iuiyij-hjzαLj∑i∈Iσi2yij-fj∑i∈Iuiyijs.t.∑i∈Iuiyij≤Cj,yi,j∈0,1.We note that Pj is a 0-1 integer programming problem with a nonlinear convex objective function and a single knapsack constraint. Let Oj be the optimal objective function value of Pj, and we easily know that ∑j:Oj>0,j∈JOj+∑i∈Iλi is an upper bound for the optimal objective function value of P. Since pj is a decision variable in the objective function of Pj, we first show how to solve Pj for a fixed pj, and then we show how to solve Pj when pj is a decision variable as well.


### 4.1.1. Solution Approach forPj with a Fixed pj

For a fixedpj, we solve Pj by the Lagrangian relaxation method as well. By relaxing the capacity constraint (5), the Lagrangian dual problem of Pj is then formulated as follows:(11)minλ¯jmaxy∑i∈Iripj,dijui-λi-λ¯juiyij-2hjKj∑i∈Iuiyij-hjzαLj∑i∈Iσi2yij-fj∑i∈Iuiyij+λ¯jCj(12)s.t.yij∈0,1,where λ¯j is the Lagrange multiplier associated with the capacity constraint (5), and λ¯j≥0.For a fixed value of the Lagrange multiplierλ¯j, we want to maximize (11) over the assignment variables yij. Thus, for a fixed λ¯j, the Lagrangian relaxation dual problem of Pj reduces to the following problem:(13)Lλ¯j:max∑i∈Iripj,dijui-λi-λ¯juiyij-2hjKj∑i∈Iuiyij-hjzαLj∑i∈Iσi2yij-fj∑i∈Iuiyijs.t.yij∈0,1.LetO¯j be the optimal objective function value of Lλ¯j, and then O¯j+λ¯jCj is an upper bound for the optimal objective function value of Pj. Furthermore, we can rewrite Lλ¯j as a different but equivalent formulation as follows:(14)minS⊆Ifj∑i∈Sui+2hjKj∑i∈Sui+hjzαLj∑i∈Sσi2-∑i∈Sripj,dijui-λi-λ¯jui,where S is a subset of I.LetGj(∑i∈Sui)≡2hjKj∑i∈Sui+fj(∑i∈Sui) and ai(pj,dij)≡λi+λ¯jui-ri(pj,dij)ui. Then, Lλ¯j can be reformulated as(15)minS⊆I∑i∈Saipj,dij+Gj∑i∈Sui+hjzαLj∑i∈Sσi2.LetS¯j denote the optimal solution of (15), and we have the following observation.Lemma 1.
For eachi∈I, we have ai(pj,dij)<0 if i∈S¯j.Proof.
We prove it by contradiction. Suppose that there existsi∈S¯j such that ai(pj,dij)≥0. Then we let S^j=S¯j∖{i}, and note that the objective function value of (15) for S^j is less than that for S¯j, which contradicts the optimality of S¯j. We therefore establish that if i∈S¯j, then ai(pj,dij)<0.We defineIj-={i∈I∣ai(pj,dij)<0}. For a fixed pj, from Lemma (2), we know that when we solve Lλ¯j, we only focus on the retailers within the set Ij- instead of the set I. Then we let ai≡ai(pj,dij), bi≡ui, and ci≡σi2. As shown in Shu et al. [30], we know that the optimal solution of (15) is {i∣β(-bi/ci)+γ(-ci/ai)<1,i∈Ij-}, where both β and γ are arbitrary positive real numbers, i.e., β>0,γ>0.For a fixedpj, (15) can be solved in O(n2log⁡n) time [23, 30], where n is the number of retailers. In this paper, we solve (15) by a dual algorithm [23], and we depict the steps of the dual algorithm as follows.Step 1.
For each pair of (i, i′), i∈Ij-,i′∈Ij-, we solve the following linear equations: (16)β-biai+γ-ciai=1β-bi′ai′+γ-ci′ai′=1.
Let(βii′,γii′) denote the solution of (16), and we choose the solution if both βii′ and γii′ are positive.Step 2.
For the ease of exposition, we relabel theβii′ as βk so that βk≤βk+1, k=1,2,…,m and m≤I2, and we also denote β0=0, for k=0, and βm+1=+∞, for k=m+1.Step 3.
For eachk=0,1,…,m,
(a) LetΓi=(1-β′(-bi/ai))/(-ci/ai) for each i∈I-, where βk≤β′<βk+1, and we then sort the lines β(-bi/ai)+γ(-ci/ai)=1 in the nondecreasing value of Γi for all i∈Ij-.
(b) Letk1≤k2≤⋯≤k∣Ij-∣ denote the ordering of the lines when the value of Γi is obtained at β′. So, if Γkl≥0,l=1,2,…,Ij-, then {kl,kl+1,…,k∣Ij-∣},{kl+1,…,k∣Ij-∣},…,{k∣Ij-∣} are the feasible solutions of (15).Step 4.
From the feasible solutions of (15), we select the one with minimum objective function value of (15), and then this solution is the optimal solution of (15).Having solved the Lagrangian relaxation problemLλ¯j, we need to minimize the Lagrangian function (11) over the Lagrange multiplier λ¯j. We do so using a subgradient optimization procedure.We then show how to obtain a lower bound for the optimal objective function value ofPj, and it is sufficient to find a feasible solution for Pj. At each iteration of the Lagrangian procedure, we depict the details of the step for obtaining a feasible solution for Pj as follows:LetIj1={i∈Ij-∣yij=1} and Ij0={i∈Ij-∣yij=0}.Step 1.
If∑i∈Ij1uiyij≤Cj, then the current solution for the Lagrangian relaxation problem is feasible for Pj, and for a retailer i∈Ij0, we also let yij=1 for which the capacity constraint is satisfied and that increases the objective function value to the maximum based on the assignments made so far.Step 2.
If∑i∈Ij1uiyij≥Cj, for each i∈Ij1, we first let yij=0 for which yij=1 and that decreases the objective function value to the minimum based on the assignments made so far until the capacity constraint is satisfied. Secondly, we update the set Ij0, and then for a retailer i∈Ij0, we also let yij=1 for which the capacity constraint is satisfied and that increases the objective function value to the maximum based on the assignments made so far.Step 3.
Update the setIj1={i∈I∣yij=1}, and then Ij1 is a feasible solution of Pj.


### 4.1.2. Solution Approach forPj When pj Is a Decision Variable

In this subsection, we discuss how to solvePj as well as decide the optimal sale price pj when the price pj charged to retailers is a decision variable. We let Sj∗ denote the optimal solution of Pj.LetIj={i∣dij<vi,i∈I}. Note that Ij is a set of potential retailers that can be served by warehouse j when the per unit sale price of the product is zero. To solve Pj and decide the optimal sale price pj, we first give the following theorem.Theorem 2.
Letpj∗ be the optimal price of Pj and pji=vi-dij,i∈Ij. When the optimal solution Sj∗ of Pj is a nonempty set, the optimal price pj∗ is in the set {pji,i∈Ij}.Proof.
For the notational convenience, we relabel the retailers in setIj as {1,2,…,Ij} so that pji+1≥pji,i=1,2,…,Ij.
Ifpj∗>pj∣Ij∣, pj∗+dij≥vi,∀i∈I. Then we have ri(pj∗,dij)ui-λi≤0,∀i∈I, and it is obvious that the optimal solution Sj∗ of Pj is an empty set. This is to say, no retailers can be served by warehouse j because of the high price, and at this time the optimal price has no practical significance. Thus we have 0<pj∗≤pj∣Ij∣.
Sincepj∗≤pj∣Ij∣, there exists an i0∈{1,2,…,Ij} such that pji0≥pj∗ and pji0=argminpji,i∈Ij(pji-pj∗). If pj∗=pji0, then pj∗∈{pji,i∈Ij}. If pj∗<pji0, then ri(pj∗,dij)ui-λi≤0,i∈{1,2,…,i0-1} and ri(pj∗,dij)ui-λi>0,i∈{i0,i0+1,…,Ij}, which implies that the optimal solution Sj∗⊆{i0,i0+1,…,Ij}. Notice that ri(pj∗,dij)<ri(pji0,dij),i∈{i0,i0+1,…,Ij}. Then, we have ri(pj∗,dij)-λi<ri(pji0,dij)-λi,i∈{i0,i0+1,…,Ij}, and we also have(17)∑i∈Sj∗ripj∗,dijui-λi-2hjKj∑i∈Sj∗ui-hjzαLj∑i∈Sj∗σi2-fj∑i∈Sj∗ui<∑i∈Sj∗ripji0,dijui-λi-2hjKj∑i∈Sj∗ui-hjzαLj∑i∈Sj∗σi2-fj∑i∈Sj∗ui.This would imply that pj∗ is not the optimal price of Pj and, therefore, a contradiction exists. We establish that pj∗∈{pji,i∈Ij}.Theorem2 shows that we can attain the optimal price pj∗ for Pj within the set {pji,i∈Ij}. Based on Theorem 2, we describe how to solve Pj when pj is a decision variable as follows:Step 1.
For eachi∈Ij, we first solve Pj at pj=pji by the algorithm proposed in Section 4.1.1.Step 2.
Then, we select the one with maximum objective value, and the corresponding solution and price are the optimal solution and price ofPj.


## 4.1.1. Solution Approach forPj with a Fixed pj

For a fixedpj, we solve Pj by the Lagrangian relaxation method as well. By relaxing the capacity constraint (5), the Lagrangian dual problem of Pj is then formulated as follows:(11)minλ¯jmaxy∑i∈Iripj,dijui-λi-λ¯juiyij-2hjKj∑i∈Iuiyij-hjzαLj∑i∈Iσi2yij-fj∑i∈Iuiyij+λ¯jCj(12)s.t.yij∈0,1,where λ¯j is the Lagrange multiplier associated with the capacity constraint (5), and λ¯j≥0.For a fixed value of the Lagrange multiplierλ¯j, we want to maximize (11) over the assignment variables yij. Thus, for a fixed λ¯j, the Lagrangian relaxation dual problem of Pj reduces to the following problem:(13)Lλ¯j:max∑i∈Iripj,dijui-λi-λ¯juiyij-2hjKj∑i∈Iuiyij-hjzαLj∑i∈Iσi2yij-fj∑i∈Iuiyijs.t.yij∈0,1.LetO¯j be the optimal objective function value of Lλ¯j, and then O¯j+λ¯jCj is an upper bound for the optimal objective function value of Pj. Furthermore, we can rewrite Lλ¯j as a different but equivalent formulation as follows:(14)minS⊆Ifj∑i∈Sui+2hjKj∑i∈Sui+hjzαLj∑i∈Sσi2-∑i∈Sripj,dijui-λi-λ¯jui,where S is a subset of I.LetGj(∑i∈Sui)≡2hjKj∑i∈Sui+fj(∑i∈Sui) and ai(pj,dij)≡λi+λ¯jui-ri(pj,dij)ui. Then, Lλ¯j can be reformulated as(15)minS⊆I∑i∈Saipj,dij+Gj∑i∈Sui+hjzαLj∑i∈Sσi2.LetS¯j denote the optimal solution of (15), and we have the following observation.Lemma 1.
For eachi∈I, we have ai(pj,dij)<0 if i∈S¯j.Proof.
We prove it by contradiction. Suppose that there existsi∈S¯j such that ai(pj,dij)≥0. Then we let S^j=S¯j∖{i}, and note that the objective function value of (15) for S^j is less than that for S¯j, which contradicts the optimality of S¯j. We therefore establish that if i∈S¯j, then ai(pj,dij)<0.We defineIj-={i∈I∣ai(pj,dij)<0}. For a fixed pj, from Lemma (2), we know that when we solve Lλ¯j, we only focus on the retailers within the set Ij- instead of the set I. Then we let ai≡ai(pj,dij), bi≡ui, and ci≡σi2. As shown in Shu et al. [30], we know that the optimal solution of (15) is {i∣β(-bi/ci)+γ(-ci/ai)<1,i∈Ij-}, where both β and γ are arbitrary positive real numbers, i.e., β>0,γ>0.For a fixedpj, (15) can be solved in O(n2log⁡n) time [23, 30], where n is the number of retailers. In this paper, we solve (15) by a dual algorithm [23], and we depict the steps of the dual algorithm as follows.Step 1.
For each pair of (i, i′), i∈Ij-,i′∈Ij-, we solve the following linear equations: (16)β-biai+γ-ciai=1β-bi′ai′+γ-ci′ai′=1.
Let(βii′,γii′) denote the solution of (16), and we choose the solution if both βii′ and γii′ are positive.Step 2.
For the ease of exposition, we relabel theβii′ as βk so that βk≤βk+1, k=1,2,…,m and m≤I2, and we also denote β0=0, for k=0, and βm+1=+∞, for k=m+1.Step 3.
For eachk=0,1,…,m,
(a) LetΓi=(1-β′(-bi/ai))/(-ci/ai) for each i∈I-, where βk≤β′<βk+1, and we then sort the lines β(-bi/ai)+γ(-ci/ai)=1 in the nondecreasing value of Γi for all i∈Ij-.
(b) Letk1≤k2≤⋯≤k∣Ij-∣ denote the ordering of the lines when the value of Γi is obtained at β′. So, if Γkl≥0,l=1,2,…,Ij-, then {kl,kl+1,…,k∣Ij-∣},{kl+1,…,k∣Ij-∣},…,{k∣Ij-∣} are the feasible solutions of (15).Step 4.
From the feasible solutions of (15), we select the one with minimum objective function value of (15), and then this solution is the optimal solution of (15).Having solved the Lagrangian relaxation problemLλ¯j, we need to minimize the Lagrangian function (11) over the Lagrange multiplier λ¯j. We do so using a subgradient optimization procedure.We then show how to obtain a lower bound for the optimal objective function value ofPj, and it is sufficient to find a feasible solution for Pj. At each iteration of the Lagrangian procedure, we depict the details of the step for obtaining a feasible solution for Pj as follows:LetIj1={i∈Ij-∣yij=1} and Ij0={i∈Ij-∣yij=0}.Step 1.
If∑i∈Ij1uiyij≤Cj, then the current solution for the Lagrangian relaxation problem is feasible for Pj, and for a retailer i∈Ij0, we also let yij=1 for which the capacity constraint is satisfied and that increases the objective function value to the maximum based on the assignments made so far.Step 2.
If∑i∈Ij1uiyij≥Cj, for each i∈Ij1, we first let yij=0 for which yij=1 and that decreases the objective function value to the minimum based on the assignments made so far until the capacity constraint is satisfied. Secondly, we update the set Ij0, and then for a retailer i∈Ij0, we also let yij=1 for which the capacity constraint is satisfied and that increases the objective function value to the maximum based on the assignments made so far.Step 3.
Update the setIj1={i∈I∣yij=1}, and then Ij1 is a feasible solution of Pj.


## 4.1.2. Solution Approach forPj When pj Is a Decision Variable

In this subsection, we discuss how to solvePj as well as decide the optimal sale price pj when the price pj charged to retailers is a decision variable. We let Sj∗ denote the optimal solution of Pj.LetIj={i∣dij<vi,i∈I}. Note that Ij is a set of potential retailers that can be served by warehouse j when the per unit sale price of the product is zero. To solve Pj and decide the optimal sale price pj, we first give the following theorem.Theorem 2.
Letpj∗ be the optimal price of Pj and pji=vi-dij,i∈Ij. When the optimal solution Sj∗ of Pj is a nonempty set, the optimal price pj∗ is in the set {pji,i∈Ij}.Proof.
For the notational convenience, we relabel the retailers in setIj as {1,2,…,Ij} so that pji+1≥pji,i=1,2,…,Ij.
Ifpj∗>pj∣Ij∣, pj∗+dij≥vi,∀i∈I. Then we have ri(pj∗,dij)ui-λi≤0,∀i∈I, and it is obvious that the optimal solution Sj∗ of Pj is an empty set. This is to say, no retailers can be served by warehouse j because of the high price, and at this time the optimal price has no practical significance. Thus we have 0<pj∗≤pj∣Ij∣.
Sincepj∗≤pj∣Ij∣, there exists an i0∈{1,2,…,Ij} such that pji0≥pj∗ and pji0=argminpji,i∈Ij(pji-pj∗). If pj∗=pji0, then pj∗∈{pji,i∈Ij}. If pj∗<pji0, then ri(pj∗,dij)ui-λi≤0,i∈{1,2,…,i0-1} and ri(pj∗,dij)ui-λi>0,i∈{i0,i0+1,…,Ij}, which implies that the optimal solution Sj∗⊆{i0,i0+1,…,Ij}. Notice that ri(pj∗,dij)<ri(pji0,dij),i∈{i0,i0+1,…,Ij}. Then, we have ri(pj∗,dij)-λi<ri(pji0,dij)-λi,i∈{i0,i0+1,…,Ij}, and we also have(17)∑i∈Sj∗ripj∗,dijui-λi-2hjKj∑i∈Sj∗ui-hjzαLj∑i∈Sj∗σi2-fj∑i∈Sj∗ui<∑i∈Sj∗ripji0,dijui-λi-2hjKj∑i∈Sj∗ui-hjzαLj∑i∈Sj∗σi2-fj∑i∈Sj∗ui.This would imply that pj∗ is not the optimal price of Pj and, therefore, a contradiction exists. We establish that pj∗∈{pji,i∈Ij}.Theorem2 shows that we can attain the optimal price pj∗ for Pj within the set {pji,i∈Ij}. Based on Theorem 2, we describe how to solve Pj when pj is a decision variable as follows:Step 1.
For eachi∈Ij, we first solve Pj at pj=pji by the algorithm proposed in Section 4.1.1.Step 2.
Then, we select the one with maximum objective value, and the corresponding solution and price are the optimal solution and price ofPj.


## 4.2. Obtaining a Lower Bound

In this subsection, we show how to obtain a feasible solution ofP, and, therefore, we obtain a lower bound on optimal objective function value for P. We depict the details of obtaining a feasible solution of P as follows. At each iteration of the Lagrangian procedure, we first fix the warehouse locations at those locations for which xj=1 in the current Lagrangian solution. Then we assign the retailers to the fixed warehouses in a two-step heuristic process.Step 1.
For retaileri, if ∑j∈Jyij≥1, then we assign retailer i to warehouse j for which yij=1 and that increases the profit to the maximum based on the assignments made so far.Step 2.
For retaileri, if ∑j∈Jyij=0, then we assign retailer i to warehouse j for which the capacity constraint is satisfied and that increases the total profit to the maximum based on the assignments made so far.


## 5. Computational Results

In this section, we summarize our computational experience with the algorithms outlined in the above section. We conduct two sets of experiments as follows. The first set of experiments is designed to solvePj that arises from the Lagrangian relaxation procedure, and the second set of experiments is designed to solve P. We solve Pj via the algorithm proposed in Section 4.1 and solve P by the Lagrangian relaxation procedure. All the algorithms are coded in C++. We conduct all the experiments on a PC with a dual-core CPU of 2.27 GHz and 4G RAM running the Windows 7 operating system. We randomly generate the potential retailer locations and the candidate warehouse locations on the plane [0,1000]×[0,1000], and we denote the point (0,0) as the supplier or plant. Without loss of generality, we let χ=300.All the parameters for the problem instances are generated as follows. For each retaileri, we randomly generate the daily mean demand ui′ in [50,100], the variance of daily demand σi in [10,50], and the reserve price vi in [10,50]. The fixed ordering cost Kj is set to 1000, the per unit holding cost rate hj is set to 5, the lead time Lj is set to 10, and the standard normal deviate zα is set to 1.96 corresponding to a 97.5% service level. Table 1 summarizes the values for the parameters.Table 1
Parameters for problem instances.
Parameter ui′ σ i v i K j h j Lj z α χ  Value [ 50 ,  100 ] [ 10 ,  50 ] [ 10 ,  50 ] 1000 5 10 1.96 300LetD be the total potential retailer demands, i.e., D=∑i∈Iui. In the first experiment, we fix a potential warehouse, say j, and solve the corresponding subproblem Pj. We denote the capacity of the fixed warehouse j as 0.5D, 0.7D, and 0.9D, respectively, which allows for the test problem instances with small capacity, medium capacity, and large capacity relative to the total potential retailer demands. In the second experiment, for each candidate warehouse j, we randomly generate the capacity limit Cj in [0.3D,0.5D], [0.5D,0.7D], and [0.7D,D], respectively, which allows for the test problem instances with small capacity, medium capacity, and large capacity relative to the total potential retailer demands. We let the locating and operating cost for warehouse j be 1000×Dj, where Dj is the total demands that flow through warehouse j, j∈J.Lett0j be the Euclidean distance between the supplier and warehouse j and tij be the Euclidean distance between warehouse j and retailer i. Then, we define the per unit transportation cost from the supplier to warehouse j, d0j, and the per unit transportation cost from warehouse j to retailer i, dij, in the following: (18)d0j=2,if0<t0j≤100,4,if100<t0j≤300,6,if300<t0j≤600,8,if600<t0j≤1000,10,if1000<t0j≤1500,dij=3,if0<tij≤100,6,if100<tij≤300,9,if300<tij≤600,12,if600<tij≤1000,15,if1000<tij≤1500,Note that the above transportation cost structures reflect different quantity discount schemes [3] and also display the economics of scale.For all problem instances, the parameters for the Lagrangian relaxation procedure are shown in Table2, where θ is the stepsize. In practice, the stopping criterion that the subgradient is zero for the Lagrangian procedure is rarely met, and then we terminate the Lagrangian procedure based on the maximum number of iterations allowed, or the minimum value of θ, whichever occurs first.Table 2
Parameters for Lagrangian procedures.
Parameter Value Maximum number of iterations 500 Minimumθ value allowed 0.00001 Number of no progress iterations before halvingθ 5 Initialθ value 2 Initial Lagrange multipliers 0


### 5.1. The Computational Results forPj

In this subsection, we report the computational results forPj and explore how the capacity limit of warehouse j affect the computational results for Pj. Note that when we solve Pj, without loss of generality, we let λj=0.For each size of problem, we randomly generate 20 problem instances, and the number of the problem instances tested in this computational experiment is20×5×3 = 300. We solve all the problem instances and report the average and worst-case results. Table 3 gives the performance of the algorithm for solving Pj with small capacity, medium capacity, and large capacity. The row titled “# Retailers” represents the number of retailers in the test problem instances; the rows titled “SC”, “MC”, and “LC” represent small capacity problem instances, medium capacity problem instances, and large capacity problem instance, respectively. The row titled “CPU Time(s)” represents the CPU time taken by the algorithm for solving Pj, where “Ave” represents the average CPU time and “Max” represents the maximum CPU time. The row titled “Gap(%)” represents the gap between the upper bound and lower bound obtained in Section 4.1, where Gap(%) = 100 × (upper bound - lower bound)/lower bound, “Ave” represents the average gap, and “Max” represents the maximum gap. From Table 3, we observe that the algorithm proposed in Section 4.1 can quickly solve Pj for medium size problem instances, and the CPU time taken by the algorithm for solving Pj decreases as the capacity constraint of the warehouse becomes loose. We also observe that for all the problem instances, the average gap is 0.47% and the maximum gap is no more than 6%, and furthermore, for most of problem instances with medium and large capacity, we can obtain the optimal solution of Pj via the algorithm proposed in Section 4.1. Then we conclude that the algorithm proposed in Section 4.1 for solving the subproblem Pj is very efficient.Table 3
Performance of the algorithm for solvingPj.
# Retailers 10 30 50 80 100 SC CPU Time(s) Ave 0.057 4.594 41.886 288.915 844.497 Max 0.109 7.753 55.364 343.967 1105.920 Gap(%) Ave 0.00 0.41 1.12 0.32 0.06 Max 0.00 2.17 5.87 2.57 0.67  MC CPU Time(s) Ave 0.043 4.017 33.824 217.616 726.392 Max 0.109 6.957 54.241 310.329 950.070 Gap(%) Ave 0.00 0.00 0.00 0.00 0.00 Max 0.00 0.00 0.00 0.00 0.00  LC CPU Time(s) Ave 0.014 1.903 9.626 99.271 309.888 Max 0.046 3.853 46.909 370.034 648.387 Gap(%) Ave 0.00 0.00 0.00 0.00 0.00 Max 0.00 0.00 0.00 0.00 0.00


### 5.2. The Computational Results forP

In this subsection, we report the computational results of the second set of experiments and explore how the capacity limits of the warehouses affect the computational results forP.Tables4–6 give the computational results for P with small capacity, medium capacity, and large capacity, respectively. The columns titled “#WHs” and “#Ret” represent the number of warehouses and the number of potential retailers in the test problem instances, respectively; the columns titled “#WHs Opened”, “#Ret Served”, “CPU(s)”, and “Gap(%)” represent the number of warehouses opened, the number of the retailers served by the opened warehouses, the number of CPU seconds taken by the Lagrangian procedure, and the percentage gap between upper bound and lower bound solutions, where Gap (%) = 100 × (Upper Bound - Lower Bound)/Lower Bound; the column titled “Δ(%)” in Tables 5 and 6 represents the percentage gap between the flexible model (with the constraints ∑j∈Jyij≤1, ∀i∈I) and the corresponding serve-all model (with the constraints ∑j∈Jyij=1, ∀i∈I), where Δ(%) = 100 ×(Z1-Z2)/Z2, Z1 is the best objective value of the flexible model we obtained, and Z2 is the best objective value of the corresponding serve-all model we obtained. We solve the serve-all model via the Lagrangian relaxation algorithm as well. Note that the serve-all model means that all the potential retailers must be served by the opened warehouses, which requires that ∑j∈JCj≥D, i.e., the problem instances with medium and large capacity constraints.Table 4
The computational results forP with small capacity.
Input Output #WHs #Ret #WHs Open #Ret Served CPU (s) Gap (%) 5 5 2 2 18.43 1.86 5 10 3 4 185.63 5.22 10 10 5 5 410.08 3.75 10 20 6 9 2764.90 2.46 20 30 10 14 6535.57 6.33 20 40 13 20 19059.60 2.12Table 5
The computational results forP with medium capacity.
Input Output #WHs #Ret #WHs Open #Ret Served CPU(s) Gap(%) Δ (%) 5 5 2 4 10.67 2.57 6.60 5 10 3 8 106.71 4.88 9.81 10 10 3 8 313.42 2.69 7.61 10 20 4 17 1929.37 1.91 10.26 20 30 7 23 3374.58 7.16 12.56 20 40 9 33 8425.08 3.80 14.70Table 6
The computational results forP with large capacity.
Input Output #WHs #Ret #WHs Open #Ret Served CPU(s) Gap (%) Δ (%) 5 5 2 4 10.67 2.57 6.60 5 10 3 8 76.71 4.88 9.81 10 10 3 9 258.44 1.66 6.03 10 20 4 17 829.37 1.91 10.26 20 30 7 26 2667.79 5.99 11.05 20 40 9 33 4231.18 3.80 14.70In Tables4–6, we observe that the average gap is 3.64% and the largest gap is no more than 8%, which shows that the algorithm proposed in this paper for solving P is practical and efficient. As shown in Tables 5 and 6, the percentage of extra profits gained from the flexible model is 10% on average, and the largest percentage of extra profits gained from the flexible model is 14.7%, which shows that the flexible model is more profitable than the serve-all model. From Tables 5 and 6, we also obtain that the percentage of extra profits gained from the flexible model decreases with increasing of the capacities of the warehouses and increases with increasing of the number of potential retailers. These results show that the flexible model proposed in this paper can gain more profits when the problem instances are large-scale and when the capacities of the warehouses are small relative to the retailer’s demands. Based on the above analyses, we conclude that the demand selection strategy is more profitable for the supplier in practice.


## 5.1. The Computational Results forPj

In this subsection, we report the computational results forPj and explore how the capacity limit of warehouse j affect the computational results for Pj. Note that when we solve Pj, without loss of generality, we let λj=0.For each size of problem, we randomly generate 20 problem instances, and the number of the problem instances tested in this computational experiment is20×5×3 = 300. We solve all the problem instances and report the average and worst-case results. Table 3 gives the performance of the algorithm for solving Pj with small capacity, medium capacity, and large capacity. The row titled “# Retailers” represents the number of retailers in the test problem instances; the rows titled “SC”, “MC”, and “LC” represent small capacity problem instances, medium capacity problem instances, and large capacity problem instance, respectively. The row titled “CPU Time(s)” represents the CPU time taken by the algorithm for solving Pj, where “Ave” represents the average CPU time and “Max” represents the maximum CPU time. The row titled “Gap(%)” represents the gap between the upper bound and lower bound obtained in Section 4.1, where Gap(%) = 100 × (upper bound - lower bound)/lower bound, “Ave” represents the average gap, and “Max” represents the maximum gap. From Table 3, we observe that the algorithm proposed in Section 4.1 can quickly solve Pj for medium size problem instances, and the CPU time taken by the algorithm for solving Pj decreases as the capacity constraint of the warehouse becomes loose. We also observe that for all the problem instances, the average gap is 0.47% and the maximum gap is no more than 6%, and furthermore, for most of problem instances with medium and large capacity, we can obtain the optimal solution of Pj via the algorithm proposed in Section 4.1. Then we conclude that the algorithm proposed in Section 4.1 for solving the subproblem Pj is very efficient.Table 3
Performance of the algorithm for solvingPj.
# Retailers 10 30 50 80 100 SC CPU Time(s) Ave 0.057 4.594 41.886 288.915 844.497 Max 0.109 7.753 55.364 343.967 1105.920 Gap(%) Ave 0.00 0.41 1.12 0.32 0.06 Max 0.00 2.17 5.87 2.57 0.67  MC CPU Time(s) Ave 0.043 4.017 33.824 217.616 726.392 Max 0.109 6.957 54.241 310.329 950.070 Gap(%) Ave 0.00 0.00 0.00 0.00 0.00 Max 0.00 0.00 0.00 0.00 0.00  LC CPU Time(s) Ave 0.014 1.903 9.626 99.271 309.888 Max 0.046 3.853 46.909 370.034 648.387 Gap(%) Ave 0.00 0.00 0.00 0.00 0.00 Max 0.00 0.00 0.00 0.00 0.00


## 5.2. The Computational Results forP

In this subsection, we report the computational results of the second set of experiments and explore how the capacity limits of the warehouses affect the computational results forP.Tables4–6 give the computational results for P with small capacity, medium capacity, and large capacity, respectively. The columns titled “#WHs” and “#Ret” represent the number of warehouses and the number of potential retailers in the test problem instances, respectively; the columns titled “#WHs Opened”, “#Ret Served”, “CPU(s)”, and “Gap(%)” represent the number of warehouses opened, the number of the retailers served by the opened warehouses, the number of CPU seconds taken by the Lagrangian procedure, and the percentage gap between upper bound and lower bound solutions, where Gap (%) = 100 × (Upper Bound - Lower Bound)/Lower Bound; the column titled “Δ(%)” in Tables 5 and 6 represents the percentage gap between the flexible model (with the constraints ∑j∈Jyij≤1, ∀i∈I) and the corresponding serve-all model (with the constraints ∑j∈Jyij=1, ∀i∈I), where Δ(%) = 100 ×(Z1-Z2)/Z2, Z1 is the best objective value of the flexible model we obtained, and Z2 is the best objective value of the corresponding serve-all model we obtained. We solve the serve-all model via the Lagrangian relaxation algorithm as well. Note that the serve-all model means that all the potential retailers must be served by the opened warehouses, which requires that ∑j∈JCj≥D, i.e., the problem instances with medium and large capacity constraints.Table 4
The computational results forP with small capacity.
Input Output #WHs #Ret #WHs Open #Ret Served CPU (s) Gap (%) 5 5 2 2 18.43 1.86 5 10 3 4 185.63 5.22 10 10 5 5 410.08 3.75 10 20 6 9 2764.90 2.46 20 30 10 14 6535.57 6.33 20 40 13 20 19059.60 2.12Table 5
The computational results forP with medium capacity.
Input Output #WHs #Ret #WHs Open #Ret Served CPU(s) Gap(%) Δ (%) 5 5 2 4 10.67 2.57 6.60 5 10 3 8 106.71 4.88 9.81 10 10 3 8 313.42 2.69 7.61 10 20 4 17 1929.37 1.91 10.26 20 30 7 23 3374.58 7.16 12.56 20 40 9 33 8425.08 3.80 14.70Table 6
The computational results forP with large capacity.
Input Output #WHs #Ret #WHs Open #Ret Served CPU(s) Gap (%) Δ (%) 5 5 2 4 10.67 2.57 6.60 5 10 3 8 76.71 4.88 9.81 10 10 3 9 258.44 1.66 6.03 10 20 4 17 829.37 1.91 10.26 20 30 7 26 2667.79 5.99 11.05 20 40 9 33 4231.18 3.80 14.70In Tables4–6, we observe that the average gap is 3.64% and the largest gap is no more than 8%, which shows that the algorithm proposed in this paper for solving P is practical and efficient. As shown in Tables 5 and 6, the percentage of extra profits gained from the flexible model is 10% on average, and the largest percentage of extra profits gained from the flexible model is 14.7%, which shows that the flexible model is more profitable than the serve-all model. From Tables 5 and 6, we also obtain that the percentage of extra profits gained from the flexible model decreases with increasing of the capacities of the warehouses and increases with increasing of the number of potential retailers. These results show that the flexible model proposed in this paper can gain more profits when the problem instances are large-scale and when the capacities of the warehouses are small relative to the retailer’s demands. Based on the above analyses, we conclude that the demand selection strategy is more profitable for the supplier in practice.


## 6. Conclusions

In this paper, we study a supply chain distribution network design problem in which each warehouse has a capacity limitation that limits the average demand flowing through the warehouse and each retailer faces an uncertain demand. We consider that the supplier can choose whether to satisfy each potential retailer’s demand for the warehouse capacity limitation, or the high cost of serving the retailer, and the supplier determines which retailers to serve via the pricing decisions. The one contribution of this paper to the literature is that in designing the supply chain distribution network, we consider warehouses have capacity limits, retailers face uncertain demands, and the supplier has flexibility in determining which retailers to serve simultaneously. We formulate this problem as a nonlinear integer programming model and solve the nonlinear integer programming model via a Lagrangian relaxation based approach. The subproblem that arises from the Lagrangian relaxation procedure is a 0-1 integer programming problem, which maximizes a nonlinear convex objective function subject to a single knapsack constraint. The other contribution of this paper to the literature is that we introduce an efficient algorithm to solve the subproblem. Finally, we conduct two sets of computational experiments to test the efficiency of the algorithms proposed in this paper. From the computational experiments, we obtain the following results:(1) the algorithm proposed in this paper for solving the subproblem Pj is efficient, and, in most cases, the algorithm can solve the Pj to optimality; (2) the Lagrangian relaxation based algorithm proposed in this paper for solving the master problem P is efficient, where the average gap is 3.64%, and the largest gap is no more than 8%; (3) the flexible model is more profitable than the serve-all model, which means the demand selection strategy is more profitable for the supplier; (4) when the problem instances are large-scale, and when the capacities of the warehouses are tight, the demand selection strategy can make more profits for the supplier.The problem studied in this paper can be extended in many ways. First, in this paper, we consider the capacity of each warehouse is exogenous; i.e., the capacity of each warehouse is regarded as a fixed input, and, in practice, we want to determine the best capacity level to install at each warehouse. Thus, an extension of the problem studied in this paper is to allow the capacity of each warehouse to be a decision variable [45, 46]. Second, we only deal with medium size problem instances, and, in the future, we want to explore how to design the efficient approximation algorithms for the problem [6, 47–50].



---

*Source: 2143042-2019-01-23.xml*