# Optimal Utilization of Ports’ Free-of-Charge Times in One Distribution Center and Multiple Ports Inventory Systems

Authors: Zhengyi Li
Journal: Complexity
 (2019)

---

## Abstract

In this paper, we consider a distribution system consisting of one distribution center (DC), a set of ports, and a set of retailers, in which the product is distributed to the retailers from the DC through the ports by the water transport, and study inventory management for the distribution system with considering the effect of the free storage periods provided by the ports. Inventory management for the distribution system is to determine the order intervals of the DC and the retailers while minimizing the inventory ordering and holding costs. Focusing on stationary and integer-ratio policies, we formulate this inventory management problem as an optimization problem with a convex objective function and a set of integer-ratio constraints and presentO(Nlog⁡N) time algorithm to solve the relaxed problem (relaxing the integer-ratio constraints) to optimality, where N is the number of the retailers. We prove that the relaxed problem provides a lower bound on average cost for all the feasible policies (containing dynamic policies) for this inventory management problem. By using the optimal solution of the relaxed problem, we build a stationary integer-ratio policy (a power-of-two policy) for this inventory management problem and prove that the power-of-two policy can approximate the optimal inventory policy to 83% accuracy.


---

## Body

## 1. Introduction

With the growth of international trade and regional economic, from January 2017 to June 2018, the word seaborne trade increased by 4%, and total volumes reached 10.7 billion tons [1]. In China, from January 2018 to August 2018, the cargo volumes of the domestic water transport reached 4.48 billion tons and increased by 3.3% over the same period last year (http://xxgk.mot.gov.cn/jigou/zhghs/201809/t20180914_3087694.html (in Chinese)). The above data shows that more and more firms distribute their product by the water transport. Thus, in this paper, we consider a distribution system consisting of one distribution center (DC), a set of retailers, and a set of ports, in which the product is distributed to the retailers from the DC through the ports by the water transport, and study inventory management for the distribution system.In practice, when the cargo arrives at the port, the port normally allows the cargo (in-transit inventory) to stay in the ports for free for a certain time period [2, 3]. For example, the free storage times at the major container ports are from 3 to 9 days in Europe, from 3 to 5 days in Asia, and about 10 days in Egypt (http://www.cma-cgm.com/ebusiness/tariffs/demurrage-detention). To take advantage of these free storage periods, the distributors should take into account the free storage periods to better coordinate their DC-retailer inventory replenishment activities to minimize the two-echelon inventory costs. Therefore, we study inventory management for the distribution system with considering the free storage periods and explore the impact of the free storage periods provided by the ports on the inventory policies for the distribution system.Inventory management for the distribution system with one DC multiretailer or the one warehouse multiretailer (OWMR) system has been extensively studied, and we refer the readers to Roundy [4], Muckstadt and Roundy [5], Levi et al. [6], and Chu and Shen [7] for the related research. The research associated with the free storage period in the framework of supply chain is few. Dekker et al. [8] and Pourakbar et al. [9] consider a floating stock distribution strategy in the intermodal transport for the fast moving customer goods supply chain, in which the stocks are deployed at the intermodal terminals in advance of customer demands within the free storage period provided by the terminals. They analyze four different distribution strategies on a conceptual model and a container shipping scheduling problem and show that the floating stock strategy may lead to lower storage costs and a shorter ordering lead time. Furthermore, they use a real case study to support their findings. van Asperen and Dekker [10] discuss application of the floating stock in the evaluation of port-of-entry choices. Additionally, the research on the storage pricing for the container terminals also considers the effect of the free storage period provided by the terminals or ports, in which the pricing schedules associated with the free storage period are always assumed [2, 3, 11, 12].In this paper, we study the inventory problem for the one DC multiretailer distribution system with considering the effect of the free storage periods provided by the ports. The objective is to determine the order intervals of the DC and the retailers while minimizing the inventory ordering and holding costs. We focus on stationary and integer-ratio policies and formulate this problem as a nonlinear optimization problem. We first solve a relaxed problem of the nonlinear optimization problem and prove that the optimal solution of the relaxed problem provides a lower bound for all the feasible policies (stationary and dynamic policies) for this inventory problem. Then we build a stationary integer-ratio policy (a power-of-two policy) based on the optimal solution of the relaxed problem and also discuss the gap between the power-of-two policy and the optimal policy for this inventory problem. Note that some results of this paper were presented in the 2017 2nd International Conference on Mechanical Control and Automation [13].The remainder of this paper is organized as follows. We formulate the inventory management problem and give the solution approach for the optimization problem in Section2. In Section 3, we prove that the optimal solution of the relaxed problem provides a lower bound on average cost for all feasible policies for the inventory problem, and, in Section 4, we build a power-of-two policy for the inventory problem. We give a numerical example in Section 5 and conclude this paper in Section 6.


## 2. Model Formulation and Solution Approach

We consider a distribution system with one DC, a set of ports, and a set of retailers, which is shown in Figure1. The factory/supplier supplies one kind of product, and the DC orders from the single factory/supplier and replenishes the retailers through the ports by the water transport. For the distribution system based on ports, we make the following assumptions:(i)
The distribution system is a centralized system. That is to say, the decisions for inventory replenishment for the DC and the retailers are made centrally.(ii)
The demand at each retailer is deterministic.(iii)
There are no limits on the capacities of the factory/supplier and the DC.(iv)
In the inventory replenishment, no shortages are allowed.(v)
The leading times for replenishing inventories for the DC and the retailers are deterministic. Without loss of generality, we assume that the leading times are zero. Note that the model we formulated in this paper can be extended to the case that the leading times are not zero easily [4, 5].(vi)
We only consider the free storage periods provided by the ports associated with the retailers and ignore the free storage period provided by the port associated with the DC. That is to say, we only consider the free storage periods for the inbound cargo [2, 3, 11, 12].Figure 1
A distribution system with one DC, a set of ports, and a set of retailers.In the inventory management, the inventory policies contain stationary policies and dynamic policies. The stationary policies mean that the order intervals and the order quantities do not change over time, and the dynamic policies mean that the order intervals and the order quantities change over time. Inventory management for this distribution system is to determine the optimal inventory policies (the optimal order intervals) for the DC and the retailers while minimizing the long-run average system-wide inventory ordering and holding costs over an infinite time horizon, which we callthe primal problem. It is known that the optimal inventory policy for the primal problem is unknown [4, 14]. The optimal inventory policy for the primal problem might be very complicated, and we even do not know the optimal inventory policy is stationary or dynamic. Thus, we focus on stationary and integer-ratio inventory policies for the primal problem, and the reason is that stationary integer-ratio inventory policies are more practical in production planning and scheduling [5].For this distribution system, the integer-ratio policies mean that, for each retailer, the ratio of the order interval at the DC to that at the retailer or the ratio of the order interval at the retailer to that at the DC is an integer [4, 5, 15]. For example, suppose that there is a distribution system with two retailers, and the demand rate at each retailer is 1. Let the order intervals at the DC, the 1st retailer, and the 2nd retailer be 1, 1/2, and 2, respectively. We know that this policy satisfies the integer-ratio constraint and is an integer-ratio policy. Under this integer-ratio policy, the optimal order quantities at the DC and the retailers are shown in Table 1.Table 1
The order intervals and quantities in the example.
Facility DC 1st retailer 2nd retailer Order interval 1 1/2 2 Order quantity 3,1,3,1,⋯ 1/2 2From Table1, we see that the order quantities at the 1st retailer and 2nd retailer are stationary, but the order quantity at the DC is not stationary. Thus this policy is not a stationary integer-ratio policy for this simple distribution system. In this paper, we study the stationary integer-ratio policies for the one DC and multiple ports distribution system and use the stationary integer-ratio policies (power-of-two policies) to approximate the optimal policy for the distribution system as well.In order to formulate this inventory management problem, we first introduce the following notation:(i)
R: the set of retailers, where R={1,2,⋯,N}(ii)
K0: the fixed ordering cost at the DC(iii)
h0: the inventory holding cost rate at the DC(iv)
Ki: the fixed ordering cost at the retailer i,i∈R(v)
hi: the inventory holding cost rate at the retailer i,i∈R(vi)
λi: the constant demand rate at the retailer i,i∈R(vii)
ti: the free storage period provided by the port associated with retailer i,i∈RNote that, for ease of exposition, we assumeh0≤hi,∀i∈R; i.e., the holding cost rate at warehouse is no more than those at retailers, which is practically reasonable [5, 15].LetT={T0,T1,⋯,TN} be a feasible stationary integer-ratio inventory policy for this distribution system, where T0 is the order interval at the DC and Ti is that at retailer i,i∈R. Let C(T) denote the average system-wide inventory holding and ordering cost under policy T and ci(T0,Ti) denote the average inventory holding and ordering cost for retailer i under T0 and Ti, i∈R. Then we have (1)CT=K0T0+∑i∈RciT0,Ti,where K0/T0 is average ordering cost at the DC.Next we show how to calculateci(T0,Ti),i∈R. For each i∈R, we consider two cases:(i)
T0≥Ti. In this case, we know that the order frequency at the DC is less than that at retailer i. That is to say, retailer i should order at least once from the DC before the DC places an order next time from the factory, and the DC needs to hold inventory to serve the demand at retailer i [4, 5, 16]. For example, the demand rate at retailer i is 1, the order interval at retailer i is 1, and the order interval at the DC is 2. Within the order interval at the DC, retailer i places order twice. Obviously, the DC needs to hold 1 inventory to serve retailer i before he places an order next time. Then we have (2)ciT0,Ti=KiTi+12λihiTi-ti+Ti-ti+Ti+12λih0T0-Ti,where Ki/Ti is the average ordering cost at retailer i, 1/2λihiTi-ti+Ti-ti+/Ti is the average holding cost at retailer i, in which we consider the holding cost is zero within the free storage period ti, and 1/2λih0(T0-Ti) is the average holding cost at the DC for serving demand at retailer i.(ii)
T0<Ti. In this case, we know that the order frequency at the DC is higher than that at retailer i. That is to say, retailer i will not order again from the DC before the DC places an order next time from the factory, and the DC does not need to hold any inventory to serve the demand at retailer i [4, 5, 16]. For example, the demand rate at retailer i is 1, the order interval at retailer i is 2, and the order interval at the DC is 1. When retailer i places an order from the DC, the DC also places an order from the factory. Obviously, there is not any inventory to be carried at the DC to serve retailer i. Then we have (3)ciT0,Ti=KiTi+12λihiTi-ti+Ti-ti+Ti.Based on the above analysis, we formulate ci(T0,Ti),i∈R, as follows: (4)ciT0,Ti=KiTi+12λihiTi-ti+Ti-ti+Ti+12λih0max⁡T0,Ti-Ti).Focusing on stationary integer-ratio policies, we formulate inventory management for the distribution system based on ports as the following optimization problem:(5)Q:minK0T0+∑i∈RKiTi+12∑i∈RλihiTi-ti+Ti-ti+Ti+12∑i∈Rλih0max⁡T0,Ti-Ti(6)s.t.T0Ti,orTiT0∈Z+,i=1,…,N,(7)Ti>0,i=0,1,…,N,where the first term of the objective function of the model Q is the average ordering cost at the DC, the second term is average ordering cost at the retailers, the third term is the average holding cost at the retailers, and the last term is average holding cost at the DC. Constraints (6) are the integer-ratio restrictions, and constraints (7) describe that the order intervals for the DC and the retailers are positive. Note that, for each retailer i∈R, the holding cost within the free storage period ti is zero, and we conclude that the optimal order interval for retailer i is greater than ti. Thus, we have the following lemma.Lemma 1.
LetTi∗, i=1,⋯,N, denote the optimal order intervals for the retailers. Then Ti∗≥ti,∀i=1,⋯,N.Proof.
We prove it by contradiction. LetT0 denote the order interval for the DC, and suppose that there exists i∈R such that Ti∗=ti′<ti. Then we have the following: (i)
Ifti′<ti≤T0, max(T0,ti′)-ti′=T0-ti′≥T0-ti=max(T0,ti)-ti.(ii)
Ifti′≤T0<ti, max(T0,ti′)-ti′=T0-ti′≥max(T0,ti)-ti=0.(iii)
IfT0<ti′<ti, maxT0,ti′-ti′=max⁡(T0,ti)-ti=0.
It follows directly that(8)Kiti′+12∑i∈Rλih0max⁡T0,ti′-ti′>Kiti+12∑i∈Rλih0max⁡T0,ti-ti.Since the cost associated with all the other retailers is unchanged, Ti∗=ti gives another solution which is better than the one with Ti∗=ti′<ti.By Lemma1, Q can be rewritten as (9)Q:minK0T0+∑i∈RKiTi+12∑i∈RλihiTi-ti2Ti+12∑i∈Rλih0max⁡T0,Ti-Tis.t.6,7.Obviously, it is very hard for us to directly solve the modelQ for the integer-ratio constraints (6). Thus, we first relax the integer-ratio constraints (6) and solve the corresponding relaxed problem. Then we build stationary integer-ratio policies for the primal problem using the optimal solution of the relaxed problem. By relaxing the integer-ratio constraints (6), we obtain the following relaxed problem: (10)minTi>0,i∈R∪0⁡K0T0+∑i∈RKiTi+12∑i∈RλihiTi-ti2Ti+12∑i∈Rλih0max⁡T0,Ti-Ti.Note that the relaxed problem (10) is a convex optimization problem. Next we show how to solve the relaxed problem (10). We first give the following theorem.Theorem 2.
LetT0∗ and Ti∗ denote the optimal solution to (10), i∈R, and we have (1)
Ti∗>T0∗ if and only if Ti∗=λihiti2+2Ki/λihi, and this set of retailers is denoted by G.(2)
Ti∗<T0∗ if and only if Ti∗=λihiti2+2Ki/λi(hi-h0), and this set of retailers is denoted by L.(3)
Ti∗=T0∗ if and only if λihiti2+2Ki/λihi<Ti∗=T0∗<λihiti2+2Ki/λi(hi-h0), and this set of retailers is denoted by E.Proof.
Letgi(Ti)=Ki/Ti+1/2λihi(Ti-ti)2/Ti, and li(Ti)=Ki/Ti+1/2λihi(Ti-ti)2/Ti+1/2λih0(T0-Ti), i∈R, and we have g′′(Ti)>0 for Ti>0, and li′′(Ti)>0 for Ti>0, i∈R. Thus, gi(Ti) and li(Ti) are both strictly convex function, i∈R.
(1)⇒: Suppose that T0∗<Ti∗, and we have Ti∗∈arg⁡minTi>0gi(Ti). Since gi(Ti) is a strictly convex function, we know that Ti∗ is the unique minimizer of gi(Ti) over Ti>0 [17], and then (11)gi′Ti∗=-KiTi∗2+12λihi1-ti2Ti∗2=0⇒Ti∗=λihiti2+2Kiλihi≥ti.
Therefore, ifT0∗<Ti∗, we always have Ti∗=λihiti2+2Ki/λihi>T0∗.
⇐ : Suppose that Ti∗=λihiti2+2Ki/λihi. We next show that Ti∗>T0∗. If Ti∗≤T0∗, then we have li(Ti)≤li(Ti∗) for Ti∗=λihiti2+2Ki/λihi<Ti≤λihiti2+2Ki/λi(hi-h0). This implies that any value of Ti satisfying λihiti2+2Ki/λihi<Ti≤λihiti2+2Ki/λi(hi-h0) can give a better objective function value and contradicts the optimality of Ti∗.
Therefore, ifTi∗=λihiti2+2Ki/λihi, we always have Ti∗>T0∗.
(2)⇒: Suppose that T0∗>Ti∗, and we have Ti∗∈arg⁡minTi>0li(Ti). Since li(Ti) is a strictly convex function, we know that Ti∗ is the unique minimizer of li(Ti) over Ti>0 [17], and then (12)fi′Ti∗=-KiTi∗2+12λihi1-ti2Ti∗2-12λih0=0⇒Ti∗=λihiti2+2Kiλihi-h0≥ti.
Therefore, ifTi∗<T0∗, we always have Ti∗=λihiti2+2Ki/λi(hi-h0)<T0∗.
⇐ : Suppose that Ti∗=λihiti2+2Ki/λi(hi-h0). We next show that Ti∗<T0∗. If Ti∗≥T0∗, then we have gi(Ti)≤gi(Ti∗) for Ti∗=λihiti2+2Ki/λihi<Ti≤λihiti2+2Ki/λi(hi-h0). This implies that any value of Ti satisfying λihiti2+2Ki/λihi<Ti≤λihiti2+2Ki/λi(hi-h0) can give a better objective function value and hence contradicts the optimality of Ti∗.
Therefore, ifTi∗=λihiti2+2Ki/λi(hi-h0), we always have Ti∗<T0∗.
(3) According to (1) and (2), we can easily establish thatT0∗=Ti∗ if and only if λihiti2+2Ki/λihi<T0∗=Ti∗<λihiti2+2Ki/λi(hi-h0).From Theorem2, we know that no matter how much ti is, ∀i, the optimal distribution strategy, will always force the inventories to stay at each port associated with retailer i for some time longer than ti. Based on Theorem 2 and by using of the ideal of Roundy [4], we introduce the following algorithm to solve the relaxed problem (10) to optimality. For any retailer i∈R, let us define (13)TiG=λihiti2+2KiλihiandTiL=λihiti2+2Kiλihi-h0.We depict the details of the algorithm as follows.Step 1.
LetZ∗=+∞. Partition the real line by TiG, TiL for all i∈R. Note that TiG≤TiL for any i.Step 2.
SupposeT0∗ falls in a particular interval, say [a,b] (choosing the intervals from left to right). We can use Theorem 2 to determine the sets G, E, and L, depending on whether TiG, TiL fall to the left or right of the interval [a,b].
More specifically,i∈G and Ti=TiG if a≤b≤TiG, i∈E if TiG≤a≤b≤TiL, i∈L, and Ti=TiL if TiL≤a≤b.
After determining the retailers in the setsG and L, we need to solve the following problem to find optimal value of T0(14)K0T0+∑i∈EKiT0+12∑i∈EλihiT0-ti2T0+12∑i∈Lλih0T0.
According to the first-order condition, we have(15)-K0T02-∑i∈EKiT02+12∑i∈Eλihi1-ti2T0∗2+12∑i∈Lλih0=0,
and hence(16)-2K0-2∑i∈EKi+∑i∈EλihiT02-∑i∈Eλihiti2+∑i∈Lλih0T02=0T¯0=2K0+2∑i∈EKi+∑i∈Eλihiti2∑i∈Eλihi+∑i∈Lλih0.
IfT0¯∈[a,b], then set T0=Ti=T0¯ for any i∈E, calculate the value of the cost Z using (6), and let Z∗:=Z if Z∗>Z. Note that, for any i∈E, we have T0=Ti≥ti as ti≤TiG≤a. Otherwise, move to the next interval (i.e., our guess that T0∗ is in [a,b] is wrong).Step 3.
Go to Step2 till it reaches the last interval. The value of T0,Ti corresponding to Z∗ is the optimal reorder interval of the warehouse and retailer i, respectively.
We get at most2N+1 intervals along the line in Step 1. Note that as long as T0∗ falls within any interval, we have enough information to determine for all i∈R, whether i∈G,E,L. We also note that, by construction of the intervals, none of the values in TiG, TiL,∀i∈R, will fall in the interval (a,b). Hence G∪E∪L=R. Step 1 requires a sorting operation for O(N) values, which requires O(Nlog⁡N) comparisons. The number of operations in Steps 2 and 3 can be performed in O(N) operations, which is dominated by the number of operations in Step 1. Thus we have the following.Theorem 3.
The computational complexity of the algorithm to solve the relaxed problem (10) is O(Nlog⁡N), where N is the number of the retailers.


## 3. Lower Bound Theorem

Obviously the optimal solution of the relaxed problem (10) provides a lower bound for Q (a lower bound for the stationary integer policies), but not for the primal problem (the optimal inventory policy for the primal problem may be dynamic). Thus we want to know whether the optimal solution of the relaxed problem of Q also provides a lower bound for the primal problem.In this section, we give a Theorem4, which is primarily designed to demonstrate that the optimal solution of the relaxed problem of Q also provides a lower bound for the primal problem. That is to say, the stationary policy obtained by the optimal solution of the relaxed problem of Q provides a lower bound for all the feasible stationary and dynamic policies for the primal problem.Theorem 4 (lower bound theorem).
LetZ∗ be the optimal objective function value of the relaxed problem (10). Then Z∗ is a lower bound on the average cost for any feasible inventory policy (possibly dynamic) for the primal problem.Proof.
We prove Theorem4 using the similar spirits of Roundy [4]. Let T∗=(T0∗,T1∗,T2∗⋯,TN∗) denote the optimal solution to (10) and Z∗ be the corresponding optimal objective value for (10), where T∗ can be obtained by the algorithm proposed in Section 2. Note that T∗ is the optimal relaxed order intervals for the DC and retailers. From Theorem 2, we see that the retailers naturally fall into three groups G={i:T0∗<TiG=Ti∗}, E={i:TiG≤T0∗=Ti∗≤TiL}, and L={i:Ti∗=TiL<T0∗}, where TiG=λihiti2+2Ki/λihi and TiL=λihiti2+2Ki/λi(hi-h0),∀i∈R.
For each policyT={T0,T1,T2,⋯,Tn}, we say that the policy Tpreserves the order of T∗ if Ti≥T whenever i∈G, Ti=T whenever i∈E, and Ti≤T whenever i∈L. For each order-preserving policy T, (10) can be rewritten as (17)minT0≥ti,∀i∈E,Ti≥ti,∀i∈Ec⁡K¯0T0+12λ0H¯0T0+∑i∈EcK¯iTi+12λiHiTi-Mwhere Ec≡G∪L, K¯0≡K0+∑i∈E‍(Ki+1/2λihiti2), λ0≡∑i∈E∪L‍λi, H¯0≡1/λ0(∑i∈E‍λihi+∑i∈L‍λih0), K¯i≡Ki+1/2λihiti2, Hi≡hi for all i∈G, Hi≡(hi-h0) for all i∈L, and M≡∑i∈R‍λihiti. From the definitions of T∗ and Z∗ and the formulation of (17), we observe that the minimum relaxed average cost Z∗ is (18)Z∗=M¯0+∑i∈EcMi-M,where M¯0≡(2K¯0λ0H¯0)1/2, and Mi≡(2K¯iλiHi)1/2 for all i∈Ec.
For each retaileri∈E, we define Hi=2(Ki+1/2λihiti2)/λ0T0∗2, and, for the warehouse, we define H0=2K0/λ0T0∗2. We also define λ¯i,i∈R, as follows: (19)λ¯i=λi,i∈E,λ0,i∈Ec.Then we have(1)
H¯0=∑i∈E∪0‍Hi;(2)
λ0H0=∑i∈R‍(λihi-λ¯iHi);(3)
λi(hi-h0)≤λ¯iHi≤λihi,∀i∈R.
We prove (1), (2), and (3) as follows. From the definitions ofHi,∀i∈R, we have (20)H¯0=2K¯0λ0T∗2=2K0+2∑i∈EKi+1/2λihiti2λ0T∗2=2K0λ0T∗2+∑i∈E2Ki+1/2λihiti2λ0T∗2=∑i∈E∪0Hi,and (21)λ0H0=λ0H¯0-∑i∈Eλ0Hi=∑i∈Eλihi+∑i∈Lλih0-∑i∈Eλ0Hi=∑i∈Eλihi-λ0Hi+∑i∈Lλih0=∑i∈Eλihi-λ0Hi+∑i∈Ecλihi-λiHi=∑i∈Rλihi-λi¯Hi.
For eachi∈R, if i∈G, then Hi=hi and λ¯i=λi, and we have λi(hi-h0)<λ¯iHi=λihi; if i∈L, then Hi=hi-h0 and λ¯i=λi, and we have λi(hi-h0)=λ¯iHi<λihi; if i∈E, then λ¯i=λ0 and Hi=2(Ki+1/2λihiti2)/λ0T0∗2, and since TiG≤T0∗=Ti∗≤TiL, we have λi(hi-h0)≤λ¯iHi≤λihi. Therefore, we complete the proof for (1), (2), and (3).
SinceT0∗2=2K¯0/λ0H¯0=2K0/λ0H0=2(Ki+1/2λihiti2)/λ0Hi,∀i∈E, we also have (22)M¯0=2K¯0λ0H¯01/2=2K¯0T0∗=2K0T0∗+∑i∈E2Ki+1/2λihiti2T0∗=2K0λ0H01/2+∑i∈E2Ki+12λihiti2λ0Hi=∑i∈E∪0Mi,where M0 is the minimum value of K0/x+1/2λ0H0x and Mi is the minimum value of (Ki+1/2λihiti2)/x+1/2λ0Hix for all x≥ti,i∈E. Then we can rewrite (18) as(23)Z∗=∑i∈R∪0Mi-M,where M0 is the minimum value of K0/x+1/2λ0H0x for all x≥ti∀i∈E and Mi is the minimum value of (Ki+1/2λihiti2)/x+1/2λ¯iHix for all x≥ti,i∈R.
We are ready to proveZ∗ is a lower bound on average cost of all the feasible inventory policies for the primal problem. Let T′={T0′,T1′,T2′,⋯,TN′} be an arbitrary inventory policy over the infinite horizon for the primal problem and Z(t′) be the average cost incurred in the interval [0,t′) by the policy. For the feasible policy T′, if there are some order intervals Ti′<ti,i∈R, we can find a better feasible policy by letting Ti′=ti. From Lemma 1, we note that the cost for the new feasible policy is less than T′. Thus, for the policy T′, without loss of generality, we assume that Ti′≥ti,∀i∈R. It suffices to show that Z∗≤Z(t′), for every t′>0, and we also assume t′ is large enough for the problem.
Letmi be the number of orders placed by the retailer i in [0,t′], Iit be the inventory at retailer i at time t, and Ii0t be the inventory at the DC destined for retailer i,i∈R. We note that Iit is zero if t is in the initial time interval [0,ti] in each order interval for each retailer i∈R. Thus, the total holding cost for the policy T′ in the interval [0,t′] is (24)∑i∈R∫0t′hiIit+h0Ii0tdt.We next show that (25)∑i∈R∫0t′hiIit+h0Ii0tdt≥∑i∈R∫0t′HiIit+λihiλ¯i-HiIi0tdt.
In order to prove (25), for each i∈R, we should prove hiIit+h0Ii0t≥HiIit+(λihi/λ¯i-Hi)Ii0t. There are three cases to consider.
Case 1 ( i ∈ G ). We have Hi=hi and λ¯i=λi, and thus hiIit+h0Ii0t≥HiIit+(λihi/λ¯i-Hi)Ii0t.
Case 2 ( i ∈ L ). We have Hi=hi-h0 and λ¯i=λi, and thus hiIit+h0Ii0t≥HiIit+(λihi/λ¯i-Hi)Ii0t.
Case 3 ( i ∈ E ). We have λi(hi-h0)≤λ¯iHi≤λihi and λ¯i=λ0, and then Hi/hi≤λi/λ¯i≤1 and Hi-λihi/λ0+h0≥Hi-λihi/λ0+λih0/λ0≥0. Since hiIit+h0Ii0t-HiIit-(λihi/λ¯i-Hi)Ii0t=(hi-Hi)Iit+(Hi-λihi/λ0+h0)Ii0t≥0, then hiIit+h0Ii0t≥HiIit+(λihi/λ¯i-Hi)Ii0t.
LetI0t=1/H0∑i∈R‍(λihi/λ¯i-Hi)Ii0t be the average inventory at the DC at time t, and then we have (26)∑i∈R∫0t′hiIit+h0Ii0tdt≥∑i∈R∫0t′HiIit+λihiλ¯i-HiIi0tdt=∑i∈R∫0t′HiIitdt+∫0t′H0I0tdt.Note that the ith term in the sum of the first term on the right hand of (26) can be thought of the total holding cost incurred in the interval [0,t′] in asingle-item lot-size problem in which mi orders are placed in [0,t′], the demand rate per unit time is λ¯i, the per unit inventory holding cost per unit time is Hi, the setup cost is Ki, and the free inventory storage time is ti in each order interval, and the second term on the right hand of (26) can be thought of the total holding cost incurred in [0,t′] in asingle-item lot-size problem in which m0 orders are placed in [0,t′], the demand rate per unit time is λ0, the per unit inventory holding cost per unit time is H0, and the setup cost is K0. For the ith term in the sum of the first term on the right hand of (26), the inventory policy with minimum cost for this problem is every t′/mi(t′/mi≥ti) unit time orders λ¯it′/mi units, and the resulting total holding cost is miλ¯iHi(t′/mi-ti)2/2. For the second term on the right hand of (26), the inventory policy with minimum cost for this problem is every t′/m0 unit time orders λ0t′/m0 units, and the resulting total holding cost is m0λ0H0(t′/m0)2/2. Thus we have (27)ZT′,t′t′≥∑i∈RKimi+∫0t′HiIitdt+K0m0+∫0t′H0I0tdt≥∑i∈RKimi+miλ¯iHit′/mi-ti22+K0m0+m0λ0H0t′/m022.In what follows, we prove (28)1t′∑i∈RKimi+miλ¯iHit′/mi-ti22+1t′K0m0+m0λ0H0t′/m022≥Z∗.There are three cases to consider.
Case 1 ( i ∈ G ). Then Hi=hi and λ¯i=λi, and we have (29)1t′Kimi+miλ¯iHit′/mi-ti22=Kimit′+λ¯iHit′2mi+miλihiti22t′-λihiti.
Case 2 ( i ∈ L ). Then Hi=hi-h0 and λ¯i=λi, and we have (30)1t′Kimi+miλ¯iHit′/mi-ti22=Kimit′+λ¯iHit′2mi+miλihiti22t′-λihiti+λih0ti1-miti2t′≥Kimit′+λ¯iHit′2mi+miλihiti22t′-λihiti.
Case 3 ( i ∈ E ). Then λi(hi-h0)≤λ¯iHi≤λihi and λ¯i=λ0, and we have (31)1t′Kimi+miλ¯iHit′/mi-ti22=Kimit′+λ¯iHit′2mi+miλ¯iHiti22t′-λ¯iHitit′=Kimit′+λ¯iHit′2mi+miλihiti22t′-λihiti+t′tiλihi-λ¯iHi+12miti2λ¯iHi-λihi=Kimit′+λ¯iHit′2mi+miλihiti22t′-λihiti+λihiti-λ¯iHitit′-12miti≥Kimit′+λ¯iHit′2mi+miλihiti22t′-λihiti.Thus we have(32)1t′∑i∈RKimi+miλ¯iHit′/mi-ti22≥∑i∈RmiKi+1/2λihiti2t′+12λ¯iHit′mi-λihiti,and then(33)ZT′,t′≥1t′∑i∈RKimi+miλ¯iHit′/mi-ti22+K0m0t′+12λ0H0t′m0≥∑i∈RmiKi+1/2λihiti2t′+12λ¯iHit′mi+K0m0t′+12λ0H0t′m0-∑i∈Rλihiti≥Z∗.


## 4. Power-of-Two Policies

In this section, we make use of the optimal solution of the relaxed problem (10) to build a stationary integer-ratio, i.e., a power-of-two policy, for the model Q. The power-of-two policy is a power-of-two multiple of the base planning period, which is an easy-to-use policy in practice. Muckstadt and Roundy [5] and Muckstadt and Sapra [15] discuss the advantages of the power-of-two policy in detail, especially on the inventory management and production planning and scheduling.LetT∗={T0∗,T1∗,⋯,TN∗} be the optimal solution for the relaxed problem (10) and TL be the base planning period, such as a day or a week. We use T∗ to build a power-of-two policy, denoted by T¯={T¯0,T¯1,⋯,T¯N}, in the following: For each i∈R,(i)
ifi∈Ec, let T¯i=2liTL, where li is a positive integer, such that 1/2Ti∗≤2liTL≤2Ti∗;(ii)
ifi∈E∪{0}, let T¯i=2liTL, where li is a positive integer, such that 1/2T0∗≤2liTL≤2T0∗.Obviously,T¯={T¯0,T¯1,⋯,T¯N} is a feasible stationary integer-ratio policy for the model Q. Next we explore the gap between the power-of-two policy T¯ and the optimal solution of the model Q.In practice, the fixed cost in the water transport is relatively high [18, 19], and then for each retailer i∈R, we assume that ti≤2Ki/λihi, which means the free storage period ti is less than the optimal ordering interval for the EOQ model with the fixed ordering cost Ki, the holding cost rate hi, and the demand rate λi. With this assumption, we give the following lemma.Lemma 5.
LetT∗=(T0∗,T1∗,T2∗⋯,TN∗) be the optimal solution of the relaxed problem (10) and Z∗ be the corresponding optimal objective function value. For each retailer i∈R, if ti≤2Ki/λihi, then we have (1)
Ti∗≥2ti;(2)
Z∗≥(2-1)M, where M≡∑i∈R‍λihiti.Proof.
(1) For eachi∈R, if ti≤2Ki/λihi, we consider the following three cases.
Case  1.If i∈G, then (34)Ti∗=λihiti2+2Kiλihi=ti2+2Kiλihi≥2ti.
Case  2.If i∈L, then (35)Ti∗=λihiti2+2Kiλihi-h0>λihiti2+2Kiλihi≥2ti.
Case  3.If i∈E, then (36)Ti∗≥λihiti2+2Kiλihi≥2ti.Thus, for each i∈R, if ti≤2Ki/λihi, we have Ti∗≥2ti.
(2) SinceT∗=(T0∗,T1∗,T2∗⋯,Tn∗) is optimal for the relaxed problem (10), then (37)Z∗=K0T0∗+∑i∈RKiTi∗+12∑i∈RλihiTi∗-tiTi∗+12∑i∈Gλih0T0∗-Ti∗=K0T0∗+12∑i∈Gλih0T0∗-Ti∗+∑i∈RKi+1/2λihiti2Ti∗+12∑i∈RλihiTi∗+∑i∈Rλihiti>∑i∈RKi+1/2λihiti2Ti∗+12∑i∈RλihiTi∗+∑i∈Rλihiti.
Since(Ki+1/2λihiti2)/Ti∗=1/2∑i∈R‍λihiTi∗,i∈R, and Ti∗≥2ti, then (38)Z∗>∑i∈RKi+1/2λihiti2Ti∗+12∑i∈RλihiTi∗+∑i∈Rλihiti=∑i∈RλihiTi∗-∑i∈Rλihiti≥2-1∑i∈Rλihiti=2-1M.Based on Lemma5, we show that the power-of-two policy T¯={T¯0,T¯1,⋯,T¯N} we build above can approximate the optimal inventory policy of the primal problem to 83% accuracy. We give the following theorem.Theorem 6.
LetC∗ denote the optimal objective value of the primal problem, Z∗ denote the optimal objective value of the relaxed problem (10), and Z(T¯) denote the objective value of the model Q under the power-of-two policy T¯. For each retailer i∈R, if ti≤2Ki/λihi, we have Z∗≤C∗≤Z(T¯)≤1.20Z∗≤1.20C∗; i.e., Z(T¯) approximates C∗ to 83% accuracy.Proof.
Obviously, we haveZ∗≤C∗≤Z(T¯). In order to prove Theorem 6, we only need to prove Z(T¯)≤1.20Z∗. Let T∗=(T0∗,T1∗,T2∗⋯,TN∗) be the optimal solution of the relaxed problem (10). By (17), we have(39)ZT¯=K¯0T¯0+12λ0H¯0T¯0+∑i∈EcK¯iT¯i+12λiHiT¯i-M.
SinceK¯0/T0∗=1/2λ0H¯0T0∗=M¯0/2 and K¯i/Ti∗=1/2λiHiTi∗=Mi/2,i∈Ec, we can rewrite Z(T¯) as (40)ZT¯=M¯02T0∗T¯0+T¯0T0∗+∑i∈EcMi2Ti∗T¯i+T¯iTi∗-M.
Note that1/2Ti∗≤T¯i≤2Ti∗,i∈Ec, and 1/2T0∗≤T¯i≤2T0∗,i∈E∪0, and then we have(41)ZT¯=M¯02T0∗T¯0+T¯0T0∗+∑i∈EcMi2Ti∗T¯i+T¯iTi∗-M≤M¯022+12+∑i∈EcMi22+12-M=122+12M¯0+∑i∈EcMi-M+122+12M-M=122+12Z∗+3-2222M.From Lemma 5, we know that, for each i∈R, if ti≤2Ki/λihi, then we have Z∗≥(2-1)M. Since Z∗≥(2-1)M, we have(42)ZT¯≤122+12Z∗+3-2222M≤122+12Z∗+3-222212-1Z∗≈1.20Z∗.
Finally, we have(43)Z∗≤C∗≤ZT¯≤1.20Z∗≤1.20C∗.


## 5. Numerical Example

In this section, we give a numerical example to show how to calculateci(T0,Ti), i∈R, how to solve the relaxed problem (10), and how to build the power-of-two policy via the optimal solution of the relaxed problem (10). We suppose that there is a distribution system consisting of one DC, ten ports, and ten retailers. For the DC, we set the fixed ordering cost, K0, as 500 and set the holding cost rate per unit per year, h0, as 10. For the ports, we randomly generate the free time period, ti, in [1,20], and the values for ti are shown in Table 2.Table 2
The values forti.
Parameters t 1 t2 t3 t4 t5 t6 t7 t8 t9 t10 Day 3 11 4 18 6 6 12 15 13 10 Year 3/365 11/365 4/365 18/365 6/365 6/365 12/365 15/365 13/365 10/365For the retailers, we randomly generate the fixed ordering cost,Ki, in [100,1000], the inventory holding cost rate per unit per year, hi, in (10,30], and the demand rate per year, λi, in [100,1500], and those values are shown in Table 3.Table 3
The values forKi, hi, and λi.
Parameters K 1 K2 K3 K4 K5 K6 K7 K8 K9 K10 Values 254 859 595 371 363 301 415 871 160 550  Parameters h 1 h2 h3 h4 h5 h6 h7 h8 h9 h10 Values 30 22 30 26 13 23 14 16 24 19  Parameters λ 1 λ2 λ3 λ4 λ5 λ6 λ7 λ8 λ9 λ10 Values 603 592 284 310 925 1264 423 1032 1186 525LetT0 be the order interval at the DC and Ti be the order at the retailer i, i∈R. We first calculate ci(T0,Ti) as follows: (44)c1T0,T1=254T1+12×603×30×T1-32T1+12×603×10×max⁡T0,T1-T1,c2T0,T2=859T2+12×592×22×T2-112T2+12×592×10×max⁡T0,T2-T2,c3T0,T3=595T3+12×284×30×T3-42T3+12×284×10×max⁡T0,T3-T3,c4T0,T4=371T4+12×310×26×T4-182T4+12×310×10×max⁡T0,T4-T4,c5T0,T5=363T5+12×925×13×T5-62T5+12×925×10×max⁡T0,T5-T5,c6T0,T6=301T6+12×1264×23×T6-62T6+12×1264×10×max⁡T0,T6-T6,c7T0,T7=415T7+12×423×14×T7-122T7+12×423×10×max⁡T0,T7-T7,c8T0,T8=871T8+12×1032×16×T8-152T8+12×1032×10×max⁡T0,T8-T8,c9T0,T9=160T9+12×1186×24×T9-132T9+12×1186×10×max⁡T0,T9-T9,c10T0,T10=550T10+12×525×19×T10-102T10+12×525×10×max⁡T0,T10-T10.By the aboveci(T0,Ti), i∈R, we get the following relaxed problem (10): (45)minTi>0,i∈R∪0⁡500T0+254T1+859T2+595T3+371T4+363T5+301T6+415T7+871T8+160T9+550T10+9045T1-32T1+6512T2-112T2+4260T3-42T3+4030T4-182T4+12025T5-622T5+14536T6-62T6+2961T7-122T7+8256T8-152T8+14232T9-132T9+9975T10-1022T10+3015max⁡T0,T1+2960max⁡T0,T2+1420max⁡T0,T3+1550max⁡T0,T4+4625max⁡T0,T5+6320max⁡T0,T6+2115max⁡T0,T7+5160max⁡T0,T8+5930max⁡T0,T9+2625max⁡T0,T10-3015T1+2960T2+1420T3+1550T4+4625T5+6320T6+2115T7+5160T8+5930T9+2625T10.We solve the above relaxed problem (10) by the algorithm proposed in Section 2 and obtain the optimal Ti, i∈R∪{0}, in Table 4.Table 4
The optimal solution for the relaxed problem.
Order interval T 0 ∗ T 1 ∗ T2∗ T3∗ T4∗ T5∗ T6∗ T7∗ T8∗ T9∗ T 10 ∗ Year 0.189 0.189 0.364 0.374 0.307 0.246 0.189 0.376 0.327 0.146 0.333 Day 69.16 69.16 133.02 136.47 112.20 89.89 69.16 137.17 119.50 53.45 121.62Note that the optimal order quantity at each facility (the DC and the retailers) equals the optimal order interval multiplied by the demand rate. By the method proposed in Section4, we build a power-of-two policy for the primal problem via the optimal solution for the relaxed problem (10) as shown in Table 5.Table 5
A power-of-two policy for the primal problem.
Order interval T ¯ 0 T ¯ 1 T¯2 T¯3 T¯4 T¯5 T¯6 T¯7 T¯8 T¯9 T ¯ 10 Year 0.25 0.25 0.5 0.5 0.25 0.25 0.25 0.5 0.25 0.125 0.25 Day 91.25 91.25 182.5 182.5 91.25 91.25 91.25 182.5 91.25 45.625 91.25In this example, the optimal objective function value for the relaxed problem is 34073.143, and the objective function value for the primal problem under the power-of-two policy is 35391.838. Then we know that the gap between the power-of-two policy built in above and the optimal policy for the primal problem is 3.87% (100×35391.838-34073.143/34073.143). Thus we conclude that the power-of-two policies may perform much better in practice.Additionally, in this example, we also solve the inventory management problem without considering the effect of the free time periods provided by the ports and comparing the objective function values for the primal problem with and without considering the effect of the free time periods; we obtain that the system-wide cost for this distribution system reduces 9.16% by making use of the free time periods provided by the ports. That is to say, making use of the free time periods provided by the ports can significantly reduce the system-wide cost for the distribution systems that distribute their product by the water transport.


## 6. Conclusions

In this paper, we study inventory management for the distribution system consisting with one DC, a set of ports, and a set of retailers. The DC orders the product from a single factory/supplier and replenishes the retailers through the ports by the water transport. Since the ports always allow the cargo arriving in the ports to stay for free for a period of time, which we call the free storage period, we study inventory management for this distribution system with integrating the impact of the free storage periods provided by the ports. Focusing on stationary and integer-ratio policies, we formulate this inventory management problem as a nonlinear optimization model with a convex objective function and a set of integer-ratio constraints. We first solve the relaxed problem by relaxing the integer-ratio constraints inO(Nlog⁡N) time and then build a stationary integer-ratio policy (a power-of-two policy) for this inventory management problem by using the optimal solution of the relaxed problem. More importantly, we prove that the optimal solution of the relaxed problem provides a lower bound on the average cost of any feasible policies (possibly dynamic policies) for this inventory management problem and that the power-of-two policy we build can approximate the optimal inventory policy for this inventory management problem to 83% accuracy. Finally, we give an example to show how to apply the models and algorithms proposed in this paper in practice, and we also obtain some management insights from the example.



---

*Source: 4510586-2019-02-28.xml*