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

Yong Zhang; Xingyu Yang; Baixun Li

doi:10.3934/jimo.2016037

Article Contents

2017, Volume 13, Issue 2: 633-647. Doi: 10.3934/jimo.2016037

This issue Previous Article Parametric solutions to the regulator-conjugate matrix equations Next Article A class of descent four–term extension of the Dai–Liao conjugate gradient method based on the scaled memoryless BFGS update

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

1.
School of Management, Guangdong University of Technology, Guangzhou 510520, China
2.
School of Business Administration, Guangdong University of Finance & Economics, Guangzhou 510320, China

* Corresponding author: Xingyu Yang
* Corresponding author: Xingyu Yang

Received: February 28, 2015

Revised: November 30, 2015

Published: August 2017

Abstract Full Text(HTML) Figure(5) / Table(3) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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$

Download: Full-size image PowerPoint slide

Figure 2. Comparison of daily cumulative gain without shortage cost

Download: Full-size image PowerPoint slide

Figure 3. Comparison of daily cumulative gain with shortage cost

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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.