Article Contents
Article Contents

# Distribution-free solutions to the extended multi-period newsboy problem

• * Corresponding author: Xingyu Yang
• This paper concerns the distribution-free, multi-period newsboy problem in which the newsboy has to decide the order quantity of the newspaper in the subsequent period without knowing the distribution of the demand. The Weak Aggregating Algorithm (WAA) developed in learning and prediction with expert advices makes decision only based on historical information and provides theoretical guarantee for the decision-making method. Based on the advantage of WAA and stationary expert advices, this paper continues providing distribution-free methods for the extended multi-period newsboy problems in which the shortage cost and the integral order quantities are considered. In particular, we provide an alternative proof for the theoretical result which guarantees the cumulative gain our proposed method achieves is as large as that of the best stationary expert advice. Numerical examples are provided to illustrate the effectiveness of our proposed methods.

Mathematics Subject Classification: Primary: 90B05, 68W27; Secondary: 68W40.

 Citation:

• Figure 1.  The gain function for Levina et al.'s multi-period newsboy problem with salvage. The slope of the graph is $p-c$ to the left of $y=d$ and $s-c$ to the right of $y=d$

Figure 2.  Comparison of daily cumulative gain without shortage cost

Figure 3.  Comparison of daily cumulative gain with shortage cost

Figure 4.  Comparison between daily cumulative gain of DAS and ANS for trial 1

Figure 5.  Comparison between daily cumulative gain of DAS and ANS for trial 2

Table 1.  Cumulative gains of DAS and experts without/with shortage cost

 $N$ 100 200 300 400 DAS 3864/3721 6843/6211 9978/8928 12672/11339 $\theta=1$ 1520/-1966 3040/-3218 4560/-4568 6080/-5582 $\theta=2$ 2635/325 5093/1089 7678/1952 10187/3033 $\theta=3$ 3497/2223 6489/4375 9531/6507 12396/8700 $\theta=4$ 3955/3493 6923/6167 10068/9018 12733/11459 $\theta=5$ 3780/3780 6269/6269 8936/8936 10995/10995 Ratios 0.977/0.984 0.988/0.986 0.991/0.990 0.995/0.989

Table 2.  AVEs and STDs of Ratios of cumulative gains of DAS and best expert without/with shortage cost

 TN 10 20 30 40 AVE 0.9861/0.9917 0.9821/0.9904 0.9802/0.9905 0.9800/0.9910 STD 0.0152/0.0041 0.0135/0.0035 0.0147/0.0037 0.0148/0.0034

Table 3.  Comparison between cumulative gains of DAS and ANS without shortage cost

 trial 1 2 3 4 5 6 7 8 9 10 DAS 235 110 164 185 153 227 158 188 196 150 ANS 241 106 159 180 151 211 153 183 192 147
•  [1] S. Al-Binali, A risk-reward framework for the competitive analysis of financial games, Algorithmica, 25 (1999), 99-115.  doi: 10.1007/PL00009285. [2] H. K. Alfares and H. H. Elmorra, The distribution-free newsboy problem: extension to the shortage penalty case, International Journal of Production Economics, 93-94 (2005), 465-477.  doi: 10.1016/j.ijpe.2004.06.043. [3] O. Besbes and A. Muharremoglu, On implications of demand censoring in the newsvendor problem, Management Science, 59 (2013), 1407-1424. [4] A. Burnetas and C. Smith, Adaptive ordering and pricing for perishable products, Operations Research, 48 (2000), 436-443.  doi: 10.1287/opre.48.3.436.12437. [5] N. Cesa-Bianchi and G. Lugosi, Prediction, Learning, and Games, Cambridge University Press, Cambridge, 2006. doi: 10.1017/CBO9780511546921. [6] L. L. Ding, X. M. Liu and Y. F. Xu, Competitive risk management for online Bahncard problem, Journal of Industrial and Management Optimization, 6 (2010), 1-14.  doi: 10.3934/jimo.2010.6.1. [7] G. Gallego and I. Moon, The distribution free newsboy problem: review and extensions, Journal of the Operational Research Society, 44 (1993), 825-834.  doi: 10.2307/2583894. [8] W. T. Huh, R. Levi, P. Rusmevichientong and J. B. Orlin, Adaptive data-driven inventory control with censored demand based on Kaplan-Meier estimator, Operations Research, 59 (2011), 929-941.  doi: 10.1287/opre.1100.0906. [9] W. T. Huh and P. Rusmevichientong, A non-parametric asymptotic analysis of inventory planning with censored demand, Mathematics of Operations Research, 34 (2009), 103-123.  doi: 10.1287/moor.1080.0355. [10] Y. Kalnishkan and M. V. Vyugin, The weak aggregating algorithm and weak mixability, Journal of Computer and System Sciences, 74 (2008), 1228-1244.  doi: 10.1016/j.jcss.2007.08.003. [11] M. Keisuke, The multi-period newsboy problem, European Journal of Operational Research, 171 (2006), 170-188.  doi: 10.1016/j.ejor.2004.08.030. [12] S. Kunnumkal and H. Topaloglu, Using stochastic approximation methods to compute optimal base-stock levels in inventory inventory control problems, Operations Research, 56 (2008), 646-664.  doi: 10.1287/opre.1070.0477. [13] S. Kunnumkal and H. Topaloglu, A stochastic approximation method for the single-leg revenue management problem with discrete demand distributions, Mathematical Methods of Operations Research, 70 (2009), 477-504.  doi: 10.1007/s00186-008-0278-x. [14] T. Levina, Y. Levin, J. McGill, M. Nediak and V. Vovk, Weak aggregating algorithm for the distribution-free perishable inventory problem, Operations Research Letters, 38 (2010), 516-521.  doi: 10.1016/j.orl.2010.09.006. [15] X. Lu, J. Song and K. Zhu, Analysis of perishable-inventory systems with censored demand data, Operations Research, 56 (2008), 1034-1038.  doi: 10.1287/opre.1080.0553. [16] I. Moon and S. Choi, Distribution free newsboy problem with balking, Journal of the Operational Research Society, 46 (1995), 537-542. [17] I. Moon and S. Choi, Distribution free procedures for make-to-order (MTO), make-in-advance (MIA), and composite policies, International Journal of Production Economics, 48 (1997), 21-28.  doi: 10.1016/S0925-5273(96)00026-6. [18] I. Moon and E. A. Silver, The multi-item newsvendor problem with a budget constraint and fixed ordering costs, Journal of the Operational Research Society, 51 (2000), 602-608. [19] G. R. Murray and E. A. Silver, A Bayesian analysis of the style goods inventory problem, Management Science, 12 (1996), 785-797.  doi: 10.1287/mnsc.12.11.785. [20] H. Scarf, A min-max solution of an inventory problem, in: K. Arrow, S. Karlin, H. Scarf (Eds.), Studies in The Mathematical Theory of Inventory and Production, Stanford University Press, California, (1958), 201–209. [21] H. Scarf, Bayes solution of the statistical inventory problem, Annals of Mathematical Statistics, 30 (1959), 490-508.  doi: 10.1214/aoms/1177706264. [22] G. L. Vairaktarakis, Robust multi-item newsboy models with abudget constraint, International Journal of Production Economics, 66 (2000), 213-226. [23] Y. Zhang, V. Vovk and W. G Zhang, Probability-free solutions to the non-stationary newsvendor problem, Annals of Operation Research, 223 (2014), 433-449.  doi: 10.1007/s10479-014-1620-8.

Figures(5)

Tables(3)