Solving a Distribution-Free Multi-Period Newsvendor Problem With Advance Purchase Discount via an Online Ordering Solution

Abstract

In this paper, we study a distribution-free multi-period newsvendor problem with advance purchase discount (APD). In addition to the regular-order placed at the beginning of each period, a decision-maker (DM) can also commit to an advance-order from the upstream supplier and receive discounts. The goal of the DM is to maximize total profits, and in this problem, the DM only has access to past demand data. To solve this problem, we apply an online method based on the theory of prediction and learning with expert advice to propose an explicit online ordering solution by using the fixed-stock policy as expert advice. With the properties of the gain function, we derive a theoretical result that guarantees, for any given advance-order quantity, the newsvendor’s cumulative gains achieved by the proposed online ordering solution converge to those from the best expert advice in hindsight for a sufficient large horizon. In addition, we extend the problem to the discrete case and obtain the corresponding explicit strategy and performance guarantee. Finally, numerical studies illustrate the effectiveness of the proposed solution, and the newsvendor’s total profits are comparable to the best expert advice. Sensitivity analysis also shows the robustness of the proposed solution.

Keywords

newsvendor advance purchase discount online learning weak aggregating algorithm

Introduction

Inventory management is one of the classical operations management problems which has attracted wide attention from industry and academia. A decision-maker (DM) needs to minimize the costs or maximize the profits by choosing an ordering quantity in the inventory problem. In real life, the sales of newspapers, electronic products, and blood product control are typical examples (Bravo-Moreno, 2019).

Since the classical newsvendor problem was pioneered by Arrow et al. (1951) and Morse et al. (1951), there has attracted considerable literature on this topic (Khouja, 1999; Pedroza-Gutiérrez & Hernández, 2020; Yan et al., 2011; J. Zhang et al., 2021). The classical newsvendor problem assumes the probability distribution of the demand is fully known. The optimal decision is known as a critical quantile of the inverse cumulative distribution of the demand. However, the reality is that DM often does not know the demand distribution in advance. Thus, some research assumes only the mean and standard deviation of the demand is known and uses the minimax approach, a common approach for modeling demand uncertainty in the literature, to study this problem. Scarf (1958) considers a distribution-free newsvendor problem, and show a $(s, S)$ -policy is optimal. Gallego and Moon (1993) give a new proof of the optimality of $(s, S)$ -policy proposed by Scarf, and extend the analysis to the recourse case. Moon and Choi (1995) allow customers to balk when inventory is low and relax the cumulative distribution function of the demand and merely assume that the first two moments of the distribution function are known. Alfares and Elmorra (2005) consider the shortage cost to the newsvendor problem. Khouja (2000) extends the single-period problem to the case where demand is price-dependent and multiple discounts with prices, and puts the corresponding algorithm to get the optimal order quantity and discount settings to finally achieve the purpose of selling excess inventory. Sarkar et al. (2018) develop a distribution-free newsvendor model with consignment policy and retailer’s loyalty reduction. When the family of demand distribution is known, the Bayesian update is also a common approach in the literature. Related studies include Azoury (1985) and Scarf (1959).

When there is no assumption on inherent demand distribution, and the DM only has access to the historical demands, many pieces of research propose data-driven approaches to this problem (Gallego & Moon, 1993; Huh & Rusmevichientong, 2009; Levina et al., 2010; Li et al., 2017). Levi et al. (2007, 2015) apply the sample average approximation (SAA) to the newsvendor model and multi-period inventory model. They use samples from the inherent demand to build empirical distribution and establish uniform bounds on the number of samples to guarantee the SAA is near-optimal. Also, with historical demand data, Bookbinder and Lordahl (1989) use the bootstrap method to ensure the inventory re-order levels by estimating the fractile of the inherent demand distribution. Huh et al. (2011) use the well-known Kaplan-Meier estimator from statistics to study a data-driven inventory control problem with censored demands. They prove that the proposed policies almost surely converge to the optimal solutions. Other studies include Ban and Rudin (2019), B. Chen et al. (2019), Gan (2019), and Huh and Rusmevichientong (2009). Following this stream of research, this paper investigates a distribution-free multi-period newsvendor problem with advance purchase discount. In such a case, there is no statistical assumption on the inherent demand, and the DM only has access to the past demand data and gains feedback. By using a new method of online prediction with expert advice from computer science, this study modifies the regular-order strategy with the gained feedback from different experts’ advice. In addition, the whole process does not need to solve the specific distribution of the potential demand function, which is also the main difference between this study and the above studies. Thus, this study enriches research on data-driven newsvendor problems.

Many studies have addressed the inventory problem with advance purchase discount and they mainly focus on sellers who provide end consumers within a supply chain. As Gan et al. (2019) summarize, there are many reasons for suppliers to do this, such as savings in operating costs (Gilbert & Ballou, 1999), soliciting information directly from the buyers or shaping competition in the downstream market. Gilbert and Ballou (1999) study a supply chain consisting of a steel distributor and some customers, and show that careful balancing of advance order time and price discounts can lead to lower costs for all channel members. Cachon (2004) studies a supply chain coordination problem involving advance purchase discounts, and he also considers the risk allocation of participants in the supply chain. Dong and Zhu (2007) consider the issue of inventory ownership in a supplier-retailer supply chain, and they find that Pareto improvements can be achieved when inventory ownership is transferred from the individual to the share, and sometimes vice versa. Chintapalli et al. (2017) find that when supplier’s production cost is lower for advance orders, an advance purchase discount contract alone does not achieve the supply chain coordination, but the ones with a pre-specified minimum order do. Cvsa and Gilbert (2002) and J. Y. Chen et al. (2017) show that advance purchase discount from the supplier can shape the downstream competition and benefit participants other than retailers in a supply chain with one supplier and two retailers. Cho and Tang (2013) find the retailer’s advance selling is better than other strategies, such as regular and a mix of advanced and regular strategies. Tang and Girotra (2017) use real data to study an advance purchase discount contract considering the retailer’s information acquisition cost and the wholesaler’s limited information about the cost, and they find that advance purchase discount contract can incentivize retailers to share demand information with dual-purchasing wholesalers. Ganet et al. (2019) extend the research of Scarf (1958) and introduce an advance purchase discount into Scarf’s model. They show that for any given advance order size, an advance-order dependent $(s, S)$ policy is optimal.

In this paper, we apply the Weak Aggregating Algorithm (WAA) to this distribution-free multi-period newsvendor problem. The Weak Aggregating Algorithm (WAA) is an online algorithm, first proposed by Kalnishkan and Vyugin (2008) and is improved from Vovk’s (2001) Aggregating Algorithm (AA). In current literature, some research has applied WAA to study the multi-period newsvendor problem. Levina et al. (2010) first apply the WAA method to the multi-period newsvendor problem and propose an online explicit ordering solution. In addition, they show a theoretical guarantee of cumulative profits. Y. Zhang et al. (2014) extend this problem to a non-stationary demand and propose a competitive ordering policy. Y. Zhang and Yang (2016) consider a two-product muti-period stationary newsvendor problem. Y. Zhang et al. (2019a) extend the two-product multi-period stationary newsvendor problem to a non-stationary case with budget constraints. They show that their policy is competitive with the best expert advice. Y. Zhang et al. (2019b) study a discrete newsvendor problem with order value-based free-shaping. Based on the return loss function, they obtain online ordering strategies and show the threshold of the order value-based free-shipping significantly affects the cumulative losses. Y. Zhang et al. (2020) extend the research of G. Zhang (2010) and learn a multi-period newsvendor problem with quantity discounts.

Different from the above research, we consider the impact of advance-order on the regular-order decision in the distribution-free multi-period newsvendor problem and find the optimal regular-order decision under different advance purchase contracts. Meanwhile, with the inspiration of the WAA, we first obtain the explicit online ordering solution for this problem. Then, we derive a theoretical guarantee which ensures that for any given advance-order quantity, our online ordering solution convergences to the best expert advice for a sufficient large horizon. The remainder of this paper is organized as follows. The Weak Aggregating Algorithm is introduced in Section 2. In Section 3.1, we formulate our online ordering solution and theoretical guarantee of its cumulative gains under the condition of continuous distribution. Based on Section 3.1, we continue to discuss the discrete distribution in Section 3.2. Numerical studies are carried out in Section 4. The paper concludes in Section 5.

Weak Aggregating Algorithm

The online ordering solution will be obtained by applying the Weak Aggregating Algorithm in this distribution-free multi-period newsvendor problem with advance purchase discount. The Weak Aggregating Algorithm (WAA) proposed by Kalnishkan and Vyugin (2008) is an online prediction and learning method with expert advice. It makes the decision based on advice from a pool of experts and aims to develop an algorithm to compete with a benchmark set of “experts” who can be free agents or strategies. Given a set of experts who give decisions at the beginning of each period, the DM makes ordering decisions by merging these decisions in a certain way, then meets the demand and gets the feedback. The WAA is similar to the Aggregating Algorithm proposed by Vovk (2001) but uses a learning rate parameter that is proportional to $\sqrt{n}$ .

In WAA, an initial weight distribution will be set on an expert set when the planning horizon starts. In each period, the weights will be recomputed and assigned to each expert according to the feedback from the previous period and the level of trust DM (newsvendor in this problem) has in each expert. We denote the experts set by $Θ$ and assume $Θ$ is a measurable space. The decisions made by the experts and the newsvendor are from a set $T$ . The demand set is denoted by $D$ . Gain function $π$ in each period is defined on $T \times D$ . In one period $n$ , given the newsvendor’s decision $y_{n} \in T$ and demand $d_{n} \in D$ , the newsvendor’s gain is $g_{n} = π (y_{n}, d_{n})$ . Given the expert $θ' s$ decision $y_{n}^{θ}$ , the gain is $g_{n} = π (y_{n}^{θ}, d_{n})$ . The cumulative gains for the newsvendor and the expert $θ$ in first $n$ period are $G_{n} = \sum_{i = 1}^{n} g_{i}$ and $G_{n}^{θ} = \sum_{i = 1}^{n} g_{i}^{θ}$ , respectively. We let $q (d θ)$ as the prior weights assigned to the experts. The weights are recomputed continuously in period $n$ and they are represented by a probability measure $p_{n} (d θ)$ . For more details about the WAA applied to the newsvendor problem, please refer to the following pseudo-code:

- Initialize the cumulative gains $G_{n}$ and $G_{n}^{θ}$ are 0, $θ \in Θ$ ;

- In each period $n = 1, 2, \dots$ ,

1. The experts’ weights are recomputed:

p_{n} (d θ) : = \frac{β_{n}^{G_{n - 1}^{θ}} q (d θ)}{\int_{Θ} β_{n}^{G_{n - 1}^{θ}} q (d θ)},

(1)

where $β_{n} : = \exp (\frac{1}{\sqrt{n}})$ , $θ \in Θ$ ;

2. Experts give the decisions $y_{n}^{θ}$ ;

3. The newsvendor make the decision

y_{n} : = \int_{Θ} y_{n}^{θ} p_{n} (d θ);

(2)

4. The demand $d_{n}$ arrives;

5. The cumulative gains are updated: $G_{n} : = G_{n - 1} + π (γ_{n}, ω_{n})$ , $G_{n}^{θ} : = G_{n - 1}^{θ} + π (γ_{n}^{θ}, ω_{n})$ ;

Analytic Results

In many industries, ordering in advance to get discounts is a widely-used method for suppliers and retailers. In this section, we incorporate the advance purchase order into the multi-period newsvendor problem and develop ordering solutions by the WAA framework, as mentioned above. Before the start of the planning horizon, a sourcing contract for advance order between the supplier and the retailer is confirmed, and a fixed size of advance orders will be shipped to the retailer for each period. We assume there is only one product is considered. Let $Z$ denotes the advance order size for each period, $c_{1}$ is unit cost for an advance order, $c_{2}$ $(c_{1} < c_{2})$ is unit cost for a regular order, selling price is $p$ $(p > c_{2})$ , $B$ is an upper bound on total ordering quantity from the supplier by the newsvendor. Throughout this paper, rigorous proofs are provided in the appendix.

Online Ordering Solution for the Continuous Case

Based on the assumption and notations above, given advance order size $Z$ , regular order quantity $y$ , and demand $d$ , the newsvendor’s gain in one period is

g = π (Z, y, d) = p \cdot \min {(Z + y), d} - c_{1} Z - c_{2} y

(3)

To obtain an explicit ordering decision $y$ , we apply the WAA to stationary experts who keep the regular order quantity at the same value throughout the planning horizon to construct the ordering solution. Let $d_{(1)}, \dots, d_{(n - 1)}$ be the order statistics demand for the first $n - 1$ periods, $d_{(t)} \in [0, B]$ for $t = 1, \dots, n - 1$ . Considering the advance order $Z$ , we let ${\tilde{d}}_{(k)} = max {d_{(k)} - Z, 0}$ for $k = 1, \dots, n - 1$ and set ${\tilde{d}}_{(0)} = 0$ and ${\tilde{d}}_{(n)} = \bar{B}$ $(\bar{B} = B - Z)$ . The expert $θ = y \in [0, \bar{B}]$ stays the same value throughout the planning horizon $N$ . For the convenience of presenting formulas, we let

e_{k}^{n} = n^{- \frac{1}{2}} / (p (n - k - 1) - c_{2} (n - 1)), k = 1, \dots, n - 1,

(4)

by applying the WAA to stationary expert advice with advance purchase discount, the online ordering solution for regular order in period $n$ is

\begin{matrix} y_{n} = \\ \frac{\sum_{k = i - 1}^{n - 1} \exp {n^{- \frac{1}{2}} [p (\sum_{t = 1}^{k} d_{(t)} + Z (n - k - 1)) - c_{1} (n - 1) Z]} Λ_{k}^{n}}{\sum_{k = i - 1}^{n - 1} \exp {n^{- \frac{1}{2}} [p (\sum_{t = 1}^{k} d_{(t)} + Z (n - k - 1)) - c_{1} (n - 1) Z]} {\tilde{Λ}}_{k}^{n}} \end{matrix}

(5)

where

\begin{matrix} Λ_{k}^{n} = \\ (\begin{matrix} \begin{matrix} \frac{1}{2} ({\tilde{d}}_{(k + 1)}^{2} - {\tilde{d}}_{(k)}^{2}) & for p (n - k - 1) = c_{2} (n - 1) \\ e_{k}^{n} {[\exp (\frac{y}{e_{k}^{n}}) (y - e_{k}^{n})]}_{\tilde{d} (k)}^{\tilde{d} (k + 1)} & for p (n - k - 1) \neq c_{2} (n - 1), \end{matrix} \end{matrix} \end{matrix}

(6)

{\tilde{Λ}}_{k}^{n} = (\begin{matrix} \begin{matrix} {\tilde{d}}_{(k + 1)} - {\tilde{d}}_{(k)} & for p (n - k - 1) = c_{2} (n - 1) \\ e_{k}^{n} {[\exp (\frac{y}{e_{k}^{n}})]}_{\tilde{d} (k)}^{\tilde{d} (k + 1)} & for p (n - k - 1) \neq c_{2} (n - 1) . \end{matrix} \end{matrix}

(7)

Proof. With the advance purchase discount factor and the procedure of the WAA, the order quantity in period $n$ can be written as follows:

y_{n} = \int_{Θ} y_{n}^{θ} p_{n} (d θ) = \frac{\int_{0}^{\bar{B}} y β_{n}^{G_{n - 1}^{θ}} q (d θ)}{\int_{0}^{\bar{B}} β_{n}^{G_{n - 1}^{θ}} q (d θ)} = \frac{\int_{0}^{\bar{B}} y β_{n}^{G_{n - 1}^{θ}} q (dy)}{\int_{0}^{\bar{B}} β_{n}^{G_{n - 1}^{θ}} q (dy)} .

Based on the order statistics demand, we have

\begin{matrix} \int_{0}^{\bar{B}} y β_{n}^{G_{n - 1}^{θ}} q (dy) \\ = \int_{0}^{\bar{B}} y β_{n}^{G_{n - 1}^{θ}} dy = \int_{0}^{\bar{B}} y \exp (G_{n - 1}^{y} / \sqrt{n}) dy \\ = \sum_{k = 0}^{n - 1} \int_{{\tilde{d}}_{(k)}}^{{\tilde{d}}_{(k + 1)}} y \exp (G_{n - 1}^{y} / \sqrt{n}) dy \\ = \sum_{k = 0}^{n - 1} \int_{{\tilde{d}}_{(k)}}^{{\tilde{d}}_{(k + 1)}} y \exp {n^{- \frac{1}{2}} \sum_{t = 1}^{n - 1} [p min ((Z + y), d_{(t)}) - c_{1} Z - c_{2} y]} dy \\ = \sum_{k = 0}^{n - 1} \int_{{\tilde{d}}_{(k)}}^{{\tilde{d}}_{(k + 1)}} y \exp {n^{- \frac{1}{2}} [p (\sum_{t = 1}^{k} d_{(t)} + (n - k - 1) (Z + y)) \\ - (n - 1) (c_{1} Z + c_{2} y)]} dy \\ = \sum_{k = 0}^{n - 1} \exp {n^{- \frac{1}{2}} [p (\sum_{t = 1}^{k} d_{(t)} + Z (n - k - 1)) - c_{1} (n - 1) Z]} \\ \int_{{\tilde{d}}_{(k)}}^{{\tilde{d}}_{(k + 1)}} y \exp {\frac{y}{e_{k}^{n}}} dy \\ = \sum_{k = 0}^{n - 1} \exp {n^{- \frac{1}{2}} [p (\sum_{t = 1}^{k} d_{(t)} + Z (n - k - 1)) - c_{1} (n - 1) Z]} Λ_{k}^{n} . \end{matrix}

Similarly,

\begin{matrix} \int_{0}^{\bar{B}} β_{n}^{G_{n - 1}^{θ}} q (dy) = \sum_{k = 0}^{n - 1} \exp {n^{- \frac{1}{2}} [p (\sum_{t = 1}^{k} d_{(t)} + Z (n - k - 1)) \\ - c_{1} (n - 1) Z]} {\tilde{Λ}}_{k}^{n} . \end{matrix}

Hence, we get the explicit online ordering solution $y_{n}$ .□

Base on the following lemma from Levina et al. (2010), the theoretical guarantee for ordering solution (5) is obtained.

Lemma 3.1. Let $π \in [- L, 0]$ . The WAA guarantees that, for all $N$ ,

G_{N} \geq (\ln \int_{Θ} e^{G_{N} / \sqrt{N}} - L^{2}) \sqrt{N} .

(8)

Theorem 3.2. The online solution (5) for the multi-period newsvendor problem with advance purchase discount guarantees that, for all N,

G_{N} \geq \begin{matrix} max \\ y \in [0, \bar{B}] \end{matrix} G_{N}^{y} - \sqrt{N} (p^{2} (\bar{B} + Z)^{2} + \bar{B} p + \ln \sqrt{N}) .

(9)

We can see that the average performance of newsvendor utilizing the WAA is at most an order of $\ln (N) / \sqrt{N}$ worse than any of the experts in $Θ$ in this theory. Let $s (s < c_{1})$ and $u$ be the unit salvage value and shortage cost. When further considering the shortage cost and salvage value, the ordering solution and theoretical guarantee can be obtained by replacing $p$ by $p + u - s$ and $c$ by $c - s$ in equations $(5)$ and $(9)$ .

Online Ordering Solution for the Discrete Case

The online ordering solution and theoretical guarantee obtained by the above cases have an assumption that the product is infinitely divisible, that is, the demand and the total orders (regular ordering quantity plus advance ordering quantity) in one period can be any values in [0, B]. This section considers a more realistic situation where the total ordering quantity and demand in one period are discrete integers in [0,B].

Same as $§ 3.1$ , first we let $d_{(1)}, \dots, d_{(n - 1)}$ be the order statistics demand for the first $n - 1$ periods, $d_{(t)} \in [0, B]$ for $t = 1, \dots, n - 1$ . Considering the advance order $Z$ , we let ${\tilde{d}}_{(t)} = max {d_{(t)} - Z, 0}$ for $t = 1, \dots, n - 1$ and set ${\tilde{d}}_{(0)} = 0$ and ${\tilde{d}}_{(n)} = \bar{B}$ . Suppose that ${\tilde{d}}_{(k + 1)} = {\tilde{d}}_{(k)} + m_{k}$ , $k = 0, \dots, n - 1$ , where $m_{k}$ are integers. For the convenience of presenting formulas, we let

\begin{matrix} f (x) = \\ \frac{(1 + {\tilde{d}}_{(k)}) + \exp (x (1 + {\tilde{d}}_{(k)})) - {\tilde{d}}_{(k + 1)} \exp (x (1 + {\tilde{d}}_{(k + 1)}))}{1 - \exp (x)} \\ + \frac{\exp (x (2 + {\tilde{d}}_{(k)})) (1 - \exp (x (m_{k} - 1)))}{{(1 - \exp (x))}^{2}} \end{matrix}

(10)

and

g (x) = \frac{\exp (x (1 + {\tilde{d}}_{(k)})) (1 - \exp (x (m_{k}))}{1 - \exp (x)} .

(11)

When there is no salvage value and shortage cost, the online ordering solution can be presented as function (12) according to the procedure of WAA with stationary expert advice. Based on the lemma 3.3 in Levina et al. (2010), theoretical guarantee can be obtained in Theorem 3.4.

With the advance purchase discount factor, the regular ordering quantity for discrete multi-period newsvendor problem in period n is given as follows:

\begin{matrix} y_{n} = \\ \frac{\sum_{k = i - 1}^{n - 1} \exp {n^{- \frac{1}{2}} [p (\sum_{t = 1}^{k} d_{(t)} + Z (n - k - 1)) - c_{1} (n - 1) Z]} Φ_{k}^{n}}{1 + \sum_{k = i - 1}^{n - 1} \exp {n^{- \frac{1}{2}} [p (\sum_{t = 1}^{k} d_{(t)} + Z (n - k - 1)) - c_{1} (n - 1) Z]} {\tilde{Φ}}_{k}^{n}}, \end{matrix}

(12)

where

Φ_{k}^{n} = {\begin{matrix} \begin{matrix} \frac{m_{k} ({\tilde{d}}_{(k)} + {\tilde{d}}_{(k + 1)} + 1)}{2} & for p (n - k - 1) = c_{2} (n - 1) \\ f \frac{p (n - k - 1) - c_{2} (n - 1)}{n^{- 1 / 2}} & for p (n - k - 1) \neq c_{2} (n - 1) . \end{matrix} \end{matrix}

(13)

Φ_{k}^{n} = {\begin{matrix} \begin{matrix} m_{k} & for p (n - k - 1) = c_{2} (n - 1) \\ g \frac{p (n - k - 1) - c_{2} (n - 1)}{n^{- \frac{1}{2}}} & for p (n - k - 1) \neq c_{2} (n - 1) . \end{matrix} \end{matrix}

(14)

Proof. According to the decision-making process of the WAA, the regular order quantity is

y_{n} = \frac{\sum_{y = 0}^{\bar{B}} y \exp (n^{- 1 / 2} G_{n - 1}^{y}) / (\bar{B} + 1)}{\sum_{y = 0}^{\bar{B}} \exp (n^{- 1 / 2} G_{n - 1}^{y}) / (\bar{B} + 1)} = \frac{\sum_{y = 0}^{\bar{B}} y \exp (n^{- 1 / 2} G_{n - 1}^{y})}{\sum_{y = 0}^{\bar{B}} \exp (n^{- 1 / 2} G_{n - 1}^{y})}

where

\begin{matrix} \sum_{y = 0}^{\bar{B}} y \exp (n^{- 1 / 2} G_{n - 1}^{y}) \\ = \sum_{y = {\tilde{d}}_{(0)} + 1}^{{\tilde{d}}_{(1)}} y \exp (n^{- 1 / 2} G_{n - 1}^{y}) + \dots + \sum_{y = {\tilde{d}}_{(n - 1)} + 1}^{{\tilde{d}}_{(n)}} y \exp (n^{- 1 / 2} G_{n - 1}^{y}) \\ = \sum_{k = i - 1}^{n - 1} \sum_{y = {\tilde{d}}_{(k)} + 1}^{{\tilde{d}}_{(k + 1)}} y \exp {n^{- 1 / 2} [p (\sum_{t = 0}^{k} d_{(t)} + Z (n - k - 1)) - c_{1} (n - 1) Z \\ + (p (n - k - 1) - c_{2} (n - 1)) y]} \\ = \sum_{k = i - 1}^{n - 1} \exp (n^{- 1 / 2} [p (\sum_{t = 0}^{k} d_{(t)} + Z (n - k - 1)) - c_{1} (n - 1) Z \\ \sum_{y = {\tilde{d}}_{(k)} + 1}^{{\tilde{d}}_{(k + 1)}} y \exp {n^{- 1 / 2} y [p (n - k - 1) - c_{2} (n - 1)]} \\ = \sum_{k = i - 1}^{n - 1} \exp {n^{- 1 / 2} [p (\sum_{t = 1}^{k} d_{(t)} + Z (n - k - 1)) - c_{1} (n - 1) Z]} Φ_{k}^{n}, \end{matrix}

similarly,

\begin{matrix} \sum_{y = 0}^{\bar{B}} y \exp (n^{- 1 / 2} G_{n - 1}^{y}) \\ = 1 + \sum_{k = i - 1}^{n - 1} \exp (n^{- 1 / 2} [p (\sum_{t = 0}^{k} d_{(t)} + Z (n - k - 1)) - c_{1} (n - 1) Z \\ \sum_{y = {\tilde{d}}_{(k)} + 1}^{{\tilde{d}}_{(k + 1)}} \exp {n^{- 1 / 2} y [p (n - k - 1) - c_{2} (n - 1)]} \\ = 1 + \sum_{k = i - 1}^{n - 1} \exp {n^{- 1 / 2} [p (\sum_{t = 1}^{k} d_{(t)} + Z (n - k - 1)) - c_{1} (n - 1) Z]} {\tilde{Φ}}_{k}^{n}, \end{matrix}

□

Lemma 3.3. Let $π \in [- L, 0]$ and the prior $q$ be discrete. The WAA guarantees that, for all $N$ and $θ \in Θ$ ,

G_{N} \geq G_{N}^{θ} + (\ln q ({θ}) - L^{2}) \sqrt{N}

(15)

Theorem 3.4. The online solution $(12)$ for the discrete multi-period newsvendor problem with advance purchase discount guarantees that, for all N,

G_{N} \geq \begin{matrix} max \\ y \in {0, \bar{B}} \end{matrix} G_{N}^{y} - \sqrt{N} (p^{2} (\bar{B} + Z)^{2} + \ln (1 + \bar{B})) .

(16)

The proof of Theorem 3.4 can be easily obtained by Lemma 3.3.

Numerical Studies

In this section, we carry out numerical studies to illustrate the competitive performance of our proposed online ordering solution. In our setting, we set $B = 21$ , $p = 2$ , $c_{1} = 0.8$ , $c_{2} = 1$ , $u = 0.2$ , $s = 0.2$ , and $N = {30, 60, 90, 120, 150, 180}$ . The stationary demand in our study means the demand in each period is a random number in $[0, B]$ . We consider two different demand distributions: uniform and normal. The uniform distribution is on the interval $[0, B]$ ; The normal distribution has a mean of 10 and a standard deviation of ${2, 4, 6, 8}$ . For the convenience of programming and simplicity, we consider a discrete multi-period newsvendor problem in which we truncate each distribution to interval $[0, B]$ and only take integers. For the convenience of presenting, the performance of online ordering solution and the benchmark best expert solution without shortage cost and salvage cost are referred to as the $POS$ and $BPOS$ . Similarly, the performances with shortage cost and salvage value are referred as $POSC$ and $BPOSC$ . In Section 4.1, we first find the optimal advance purchase size with (without) shortage cost and salvage value. In order to show the performance of online solution $POS$ and $POSC$ , in Section 4.2 we compare them with the best expert advice. In Section 4.3, we perform a sensitivity analysis on different demand parameters and compare the corresponding $POS$ and $POSC$ with the $BPOS$ and $BPOSC$ .

Finding the Optimal Z

In this section, we consider two demand distributions mentioned above and the situation with (without) shortage cost and salvage value. Figures 1 to 4 show the cumulative gains under different advance order sizes and planning horizon $N$ for two demand distributions, respectively. From the figures, we find that there is indeed an optimal advance order size and cumulative gain function $G_{N}$ is approximately convex in $Z$ . And as $N$ increases, $G_{N}$ approaches the cumulative gains recommended by the best expert advice determined in hindsight, a more detailed comparison in section 4.2.

Figure 1.

Graphs of $G_{N}$ for the uniform demand distribution. The optimal advance ordering quantity is 12. For the left graph, $N = 30$ ; for the right graph, $N = 180$ .

Figure 2.

Graphs of $G_{N}$ for the uniform demand distribution and considering salvage value and shortage cost. The optimal advance ordering quantity is 14. For the left graph, $N = 30$ ; for the right graph, $N = 180$ .

Figure 3.

Graphs of $G_{N}$ for the normal demand distribution. The optimal advance ordering quantity is 10. For the left graph, $N = 30$ ; for the right graph, $N = 180$ .

Figure 4.

Graphs of $G_{N}$ for the normal demand distribution and considering salvage value and shortage cost. The optimal advance ordering quantity is 10. For the left graph, $N = 30$ ; for the right graph, $N = 180$ .

Competitive Performance of POS and POSC Versus BPOS and BPOSC

To clearly show the performance of $POS$ , $POSC$ , $BPOS$ , and $BPOSC$ , we generate cumulative gains by taking the average of 100 times per trial. The results are presented in Tables 1 and 2, where $Ratio = POS / BPOS \times 100 %$ . From the tables, we can see that almost all the average $Ratios$ further show $POS$ and $POSC$ are competitive when the benchmark is the best fixed-stock policy under the different advance order sizes. Figure 5 shows the effect of planning horizon length $N$ on the performance of $POS$ and $POSC$ where $Z = 0$ , from the figure we can see the $Ratio$ s increase with $N$ , which confirms the theoretical guarantee derived above that when $N$ is large enough, the performance of $POS$ and $POSC$ can be as good as the best expert advice. Figures 6 and 7 show the changes in regular order quantity and demand over time, we can see that when the shortage cost and salvage value are considered, $POSC$ ’s order quantity is higher than $POS$ ’s order quantity.

Table 1.

Results for Uniform Distriubtion Where Advance Order Size is 0, 4, 8, and 12 and $N = 30$ .

Trial	$Z = 0$			$Z = 4$			$Z = 8$			$Z = 12$
Trial	POSC	BPOSC	Ratio	POSC	BPOSC	Ratio	POSC	BPOSC	Ratio	POSC	BPOSC	Ratio
1	130.76	143.0	91.44	162.5	172.14	94.4	189.36	195.18	97.02	192.95	197.56	97.67
2	138.76	151.66	91.49	158.86	166.76	95.26	195.38	201.84	96.8	209.27	213.98	97.8
3	132.83	143.68	92.45	153.99	163.86	93.98	190.56	196.96	96.75	207.41	211.88	97.89
4	130.5	141.5	92.23	160.94	169.32	95.05	189.66	195.68	96.92	200.14	204.6	97.82
5	134.0	145.0	92.41	160.12	170.5	93.91	193.87	200.18	96.85	197.47	201.8	97.85
6	128.88	138.6	92.99	165.81	176.12	94.15	191.24	196.5	97.32	196.7	200.86	97.93
7	128.83	140.5	91.69	164.1	174.16	94.22	190.35	196.08	97.08	205.52	210.28	97.74
8	128.18	139.12	92.14	151.02	161.52	93.5	189.58	196.84	96.31	217.49	222.06	97.94
9	132.45	142.84	92.73	165.83	175.04	94.74	189.06	194.8	97.05	196.25	200.62	97.82
10	132.35	144.82	91.39	160.02	169.22	94.56	192.98	198.74	97.1	201.8	206.3	97.82
11	132.15	142.12	92.98	161.38	172.08	93.78	192.58	198.92	96.81	205.45	209.84	97.91
12	136.86	147.54	92.96	155.72	166.08	93.76	194.66	201.16	96.77	229.81	233.53	97.83

Table 2.

Results for Uniform Distriubtion With Shortage Cost and Salvage Value Where Advance Order Size is 0, 4, 9, and 14 and $N = 30$ .

Trial	$Z = 0$			$Z = 4$			$Z = 9$			$Z = 14$
Trial	POSC	BPOSC	Ratio	POSC	BPOSC	Ratio	POSC	BPOSC	Ratio	POSC	BPOSC	Ratio
1	133.29	145.06	91.89	168.86	179.11	94.28	205.75	210.99	97.52	224.17	227.54	98.52
2	138.33	150.24	92.07	173.18	182.75	94.76	201.11	204.94	98.13	223.08	226.55	98.47
3	139.56	150.87	92.5	168.01	177.6	94.6	203.82	207.39	98.28	216.08	219.8	98.31
4	144.83	155.42	93.19	172.19	180.96	95.15	205.66	211.14	97.4	221.78	225.48	98.36
5	142.23	153.9	92.42	174.37	184.75	94.38	207.31	213.56	97.07	219.22	222.88	98.36
6	140.19	150.33	93.25	169.64	180.98	93.73	204.34	209.84	97.38	228.21	232.12	98.32
7	138.28	149.8	92.31	164.47	174.97	94.0	204.27	208.03	98.19	224.75	228.45	98.38
8	136.75	148.74	91.94	174.06	183.25	94.98	211.05	215.68	97.85	216.31	220.05	98.3
9	133.8	146.17	91.54	170.83	179.23	95.31	201.55	207.27	97.24	231.6	235.47	98.36
10	139.21	150.9	92.25	166.99	177.53	94.06	202.37	208.23	97.19	233.34	237.0	98.46
11	139.0	150.83	92.16	165.81	177.02	93.67	204.37	209.82	97.4	224.75	228.44	98.38
12	132.62	145.0	91.46	172.79	183.21	94.31	202.41	207.5	97.55	229.81	233.53	98.41

Figure 5.

Ratios with $N$ when $Z = 0$ , $N = {30, 60, 90, 120, 150}$ .

Figure 6.

Regular order quntity changes over time where $Z = 0$ and demand satifies a uniform distribution.

Figure 7.

Regular order quntity changes over time where $Z = 0$ and demand satifies a uniform distribution.

Sensitivity Analysis

In this subsection, we perform a sensitivity analysis on the demand distribution first, and then on the ratio of $u / s$ . For a given advance order size $Z$ , cumulative gains change over time under different parameters are shown in Figures 8 and 9. From the figures, we can see that as the volatility of demand increases, the cumulative gains decrease, which is consistent with intuitive perception, because the increase in uncertainty will increase the difficulty of forecasting, and from Table 3, we can see the optimal fixed-stock policy also show similar results, and our $POS$ $(POSC)$ needs more time to be as good as the optimal fixed-stock policy.

Figure 8.

Changes in cumulative gains over time under normal demand distribution where SD (standard deviation) in {2, 4, 6, 8} and $Z = 0$ .

Figure 9.

Under normal distribution, the Cumulative gains of shortage cost and salvage value are considered where SD (standard deviation) in {2, 4, 6, 8} and $Z = 0$ .

Table 3.

Cumulative Gains and Ratio Under Different Demand Distribution Where $Z = 0$ .

Demand	N(10,2)	N(10,4)	N(10,6)	N(10,8)
POS	233	183.2	139.69	109.35
BPOS	236.15	189.76	149.32	121.46
Ratio	98.67	96.54	93.55	90.03
POSC	234.25	184.9	141.96	113.54
BPOSC	239.38	192.28	152.44	125.91
Ratio	97.86	96.16	93.13	90.18

Next, we test how cumulative gains are affected by different ratios of $u$ and $s$ , the demand distribution is normal distribution. We let $Z = {0, 10}$ and $u / s = {0, 0.5, 1, 1.5}$ , demand distribution is consistent with the initial setting. From Figures 10 and 11, we can see that under normal demand distributions and different advance order sizes, our $POSC$ ’s cumulative gains all increase with the ratio of $u / s$ . Because from function 3, it’s easy to see that the gain function $g$ increase with $u$ . From Table 4, we find the cumulative gains of the best fixed-stock policies $BPOSC$ s all decrease with the ratio of $u / s$ . Because for the best fixed-stock policy, due to the increase in the cost of shortage, the dynamic order quantity shows better demand satisfaction and cost reduction.

Figure 10.

Changes in cumulative gains over time under different ratios of $u / s$ and $Z = 0$ .

Figure 11.

Changes in cumulative gains over time under different ratios of $u / s$ and $Z = 10$ .

Table 4.

Cumulative Gains Under Different Ratios of $u / s$ and $Z = {0, 5, 10}, N = 30$ .

Z	u/s	0	0.5	1	1.5
0	POSC	228.13	231.3	233.55	236.51
	BPOSC	242.67	241.06	238.45	236.72
	Ratio	94.01	95.95	97.95	99.91
5	POSC	255.33	259.33	262.09	266.29
	BPOSC	271.62	270.78	268.43	267.59
	Ratio	94	95.77	97.64	99.51
10	POSC	282.83	287.88	292.45	296.36
	BPOSC	302.47	301.23	299.55	297.06
	Ratio	93.51	95.57	97.63	99.76

Conclusions

In this paper, we study a distribution-free multi-period newsvendor problem with advance purchase discount, which widely exists in real life. We design an explicit online ordering solution for this problem using the weak aggregating algorithm from computer science. Taking the best fixed-stock policy determined in hindsight as the benchmark, we prove that the proposed online solution can theoretically guarantee that the cumulative gains are competitive to the benchmark. More importantly, the results obtained in this study can provide a reference for industrial managers who need to order perishables continuously for a long time when the demand distribution is unknown. Finally, it is interesting to expand this problem to the multi-product case and integrate some other practical factors into the problem in future research.

Footnotes

Appendix

Proof of Theorem 3.2. Under the setting above, $Θ = [0, \bar{B}]$ where $\bar{B} = B - Z$ is finite. The online ordering solution 5 is obtained by the WAA to stationary experts where $y_{n}^{θ} = y \in [0, \bar{B}]$ stays the same value throughout all of the planning days, decision set $T$ is in $[0, \bar{B}]$ and demand set $D$ is in $[0, B]$ . According to gain function (3), the largest profit in one period comes from when the advance ordering quantity plus the regular ordering quantity equals demand $B$ , which is $(Z + \bar{B}) p - c_{1} Z - c_{2} \bar{B}$ ; and the worst gain comes from when the advance ordering quantity plus the regular ordering quantity equals $B$ but the demand is 0, which is equal to $- c_{1} Z - c_{2} \bar{B}$ . Thus the gain function satisfies

- c_{1} Z - c_{2} \bar{B} \leq π (Z, y, d) \leq (Z + \bar{B}) p - c_{1} Z - c_{2} \bar{B} .

Without loss of generality, we let $π (Z, y, d) : = π (Z, y, d) - [(Z + \bar{B}) p - c_{1} Z - c_{2} \bar{B}]$ and get

- p (Z + \bar{B}) \leq π (Z, y, d) \leq 0

Defining $L : = - p (Z + \bar{B})$ , and put this problem into the framework of Lemma 3.1. Let $δ : = max (p - c_{2}, c_{2}) \leq p$ be the least upper bound of the absolute value of the slope of the gain function as a function of $y$ . According to Levina et al. (2010), we can bound of the integral $\ln \int_{Θ} e^{G_{N}^{θ} / \sqrt{N}} qd (θ)$ in ((8)) from below by replacing the interval of intehration $[0, \bar{B}]$ by the $\bar{B} / \sqrt{N}$ neighborhood of some given initial stock $y \in [0, \bar{B}]$ . The volume of this neighborhood $y$ is an interval of length at least $\bar{B} / \sqrt{N}$ (its length is exactly $\bar{B} / \sqrt{N}$ if $y$ is one of the end-points of $Θ$ ). Simultaneously, bounding the integral in this way is reasonable because the best performing values of $y$ will asymptotically have much higher weights than the poorly performing ones. Lastly, most of weights will concentrate in the neighborhood of the best values. Thus, on this neighborhood, $G_{N}^{θ} \geq G_{n}^{y} - N \bar{B} δ / \sqrt{N}$ , we have

\begin{matrix} \ln \int_{Θ} \overset{G_{N}^{θ} / \sqrt{N}}{\exp} qd (θ) = \ln \int_{0}^{\bar{B}} \exp (G_{N}^{θ} / \sqrt{N}) qd (θ) \\ \geq \ln {\frac{\bar{B}}{\sqrt{N}} \exp [(G_{N}^{y} - N \bar{B} δ / \sqrt{N}) / \sqrt{N}]} \\ \geq G_{N}^{y} / \sqrt{N} - \bar{B} δ - \ln (\sqrt{N}) . \end{matrix}

Subsituting to the Lemma 3.1 and equation (8), we get

\begin{matrix} G_{N} \geq \sqrt{N} (G_{N}^{y} / \sqrt{N} - \bar{B} δ - \ln \sqrt{N} - L^{2}) = \\ G_{N}^{y} - \sqrt{N} (\bar{B} δ + L^{2} + \ln \sqrt{N}) \geq G_{N}^{y} - \sqrt{N} (p^{2} {(\bar{B} + Z)}^{2} \\ + \bar{B} p + \ln \sqrt{N}) \end{matrix}

where the second inequality is obtained by replacing $δ$ with $p$ and $L$ with $- p (Z + \bar{B})$ .□

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by youth project of humanities and social science research program of Chongqing Education Commission of China(23SKGH266).

ORCID iDs

Rui Wang

Chuanjin Zhu

References

Alfares

H. K.

Elmorra

H. H.

(2005). The distribution-free newsboy problem: Extensions to the shortage penalty case. International Journal of Production Economics, 93–94, 465–477.

Arrow

K. J.

Harris

Marschak

(1951). Optimal inventory policy. Econometrica: Journal of the Econometric Society, 19(3), 250–272.

Azoury

K. S.

(1985). Bayes solution to dynamic inventory models under unknown demand distribution. Management Science, 31(9), 1150–1160.

Ban

G.-Y.

Rudin

(2019). The big data newsvendor: Practical insights from machine learning. Operations Research, 67(1), 90–108.

Bookbinder

J. H.

Lordahl

A. E.

(1989). Estimation of inventory re-prder levels using the bootstrap statistical procedure. IIE Research, 67(1), 90–108.

Bravo-Moreno

(2019). Deconstructing Single Mothers by Choice: Transcending Blood, Genes, and the Biological Nuclear Family? SAGE Open, 9(4), 2158244019898258.

Cachon

G. P.

(2004). The allocation of inventory risk in a supply chain: Push, pull, and advance-purchase discount contracts. Management Science, 50(2), 222–238.

Chen

Chao

Ahn

H.-S.

(2019). Coordinating pricing and inventory replenishment with nonparametric demand learning. Operations Research, 67(4), 1035–1052.

Chen

J. Y.

Dada

Q. J.

(2017). Flexible procurement contracts for competing retailers. European Journal of Operational Research, 259(1), 130–142.

10.

Chintapalli

Disney

S. M.

Tang

C. S.

(2017). Coordinating supply chains via advance order discounts, minimum order quantities, and delegations. Production and Operations Management. 26(12), 2175–2186.

11.

Cho

S.-H.

Tang

C. S.

(2013). Advance selling in a supply chain under uncertain supply and demand.Manufacturing & Service Operations Management, 15(2), 305–319.

12.

Cvsa

Gilbert

S. M.

(2002). Strategic commitment versus postponement in a two-tier supply chain. European Journal of Operational Research, 141(3), 526–543.

13.

Dong

Zhu

(2007). Two-wholesale-price contracts: Push, pull, and advance-purchase discount contracts. Anufacturing & Service Operations Management, 9(3), 311.

14.

Gallego

Moon

(1993). The distribution free newsboy problem: Review and extensions. Journal of the Operational Research Society, 44(8), 825–834.

15.

Gan

(2019). Solving a newsvendor problem driven by environmental and individual-level data. SSRN 3446796.

16.

Gan

Sethi

S. P.

(2019). Simultaneous optimization of contingent and advance purchase orders with fixed ordering costs. Omega, 89, 227–241.

17.

Gilbert

S. M.

Ballou

R. H.

(1999). Supply chain benefits from advanced customer commitments. Journal of Operations Management, 18(1), 61–73.

18.

Huh

W. T.

Levi

Rusmevichientong

Orlin

J. B.

(2011). Adaptive data-driven inventory control with censored demand based on kaplan-meier estimator. Operations Research, 59(4), 929–941.

19.

Huh

W. T.

Rusmevichientong

(2009). A nonparametric asymptotic analysis of inventory planning with censored demand. Mathematics of Operation Research, 34(1), 103–123.

20.

Kalnishkan

Vyugin

M. V.

(2008). The weak aggregating algorithm and weak mixability. Journal of Computer and System Sciences, 74(8), 1228–1244.

21.

Khouja

M. J.

(1999). The single-period (news-vendor) problem: literature review and suggestions for future research. Omega, 27(5), 537–553.

22.

Khouja

M. J.

(2000). Optimal ordering, discounting, and pricing in the single-period problem. International Journal of Production Economics, 65(2), 201–216.

23.

Levi

Perakis

Uichanco

(2015). The data-driven newsvendor problem: New bounds and insights. Operations Research, 63(6), 1294–1306.

24.

Levi

Roundy

R. O.

Shmoys

D. B.

(2007). Provably near-optimal sampling-based policies for stochastic inventory control models. Mathematics of Operations Research, 32(4), 821–839.

25.

Levina

Levin

Mcgill

Nediak

Vovk

(2010). Weak aggregating algorithm for the distribution-free perishable inventory problem. Operations Research Letters, 38(6), 516–521.

26.

Yang

Zhang

(2017). Distribution-free solutions to the extended multi-period newsboy problem. Journal of Industrial & Management Optimization, 13(2), 37–37.

27.

Moon

Choi

(1995). The distribution free newsboy problem with balking. Journal of the Operational Research Society, 46(4), 537–542.

28.

Morse

P. M.

Kimball

G. E.

Blackett

(1951). Methods of operations research. Physics Today, 4(11): 18–20.

29.

Pedroza-Gutiérrez

Hernández

J. M.

(2020). Social Networks and Supply Chain Management in Fish Trade. Sage Open, 10(2), 2158244020931815.

30.

Sarkar

Zhang

Majumder

Sarkar

Won Seo

(2018). A distribution free newsvendor model with consignment policy and retailer’s royalty reduction. International Journal of Production Research, 56(15), 5025–5044.

31.

Scarf

Arrow

Karlin

(1958). A min-max solution of an inventory problem. Studies in the Mathematical Theory of Inventory and Production, 10, 201–209.

32.

Scarf

(1959). Bayes solutions of the statistical inventory problem. The Annals of Mathematical Statistics, 30(2), 490–508.

33.

Tang

Girotra

(2017). Using advance purchase discount contracts under uncertain information acquisition cost. Production and Operations Management, 26(8), 1553–1567.

34.

Vovk

(2001). Competitive on-line statistics. International Statistical Review, 69(2), 213–248.

35.

Yan

Wang

Vakharia

A. J.

Chen

Seref

(2011). The newsvendor problem: Review and directions for future research. European Journal of Operational Research, 213(2), 361–374.

36.

Zhang

(2010). The multi-product newsboy problem with supplier quantity discounts and a budget constraint. European Journal of Operational Research, 206(2), 350–360.

37.

Zhang

Kuo

Y. H.

Chen

(2021). Coordinating supply chain financing for e-commerce companies through a loan contract. SAGE Open, 11(4), 21582440211065455.

38.

Zhang

Vovk

Zhang

(2014). Probability-free solutions to the non-stationary newsvendor problem. Annals of Operations Research, 223(1), 433–449.

39.

Zhang

Yang

(2016). Online ordering policies for a two-product, multi-period stationary newsvendor problem. Computers & Operations Research, 74, 143–151.

40.

Zhang

Yang

Zhang

Chen

(2020). Online ordering rules for the multi-period newsvendor problem with quantity discounts. Annals of Operations Research, 288(1), 495–524.

41.

Zhang

Yang

(2019a). A two-product, multi-period nonstationary newsvendor problem with budget constraint. Soft Computing, 23(12), 4277–4287.

42.

Zhang

Zhong

Liu

Huang

(2019b). Online ordering strategy for the discrete newsvendor problem with order value-based free-shipping. Journal of Industrial & Management Optimization, 15(4), 16–17.