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$
-
Previous Article
A class of descent four–term extension of the Dai–Liao conjugate gradient method based on the scaled memoryless BFGS update
- JIMO Home
- This Issue
-
Next Article
Parametric solutions to the regulator-conjugate matrix equations
April
2017, 13(2): 633-647.
doi: 10.3934/jimo.2016037
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 |
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:
Multi-period newsboy problem,
shortage cost,
integral order quantity,
distribution-free solution,
weak aggregating algorithm.
Mathematics Subject Classification:
Primary: 90B05, 68W27; Secondary: 68W40.
Citation:
Yong Zhang, Xingyu Yang, Baixun Li. Distribution-free solutions to the extended multi-period newsboy problem. Journal of Industrial and Management Optimization,
2017, 13
(2)
: 633-647.
doi: 10.3934/jimo.2016037
![]()
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. |
show all references
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. |
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
| 100 | 200 | 300 | 400 | |
| DAS | 3864/3721 | 6843/6211 | 9978/8928 | 12672/11339 |
| 1520/-1966 | 3040/-3218 | 4560/-4568 | 6080/-5582 | |
| 2635/325 | 5093/1089 | 7678/1952 | 10187/3033 | |
| 3497/2223 | 6489/4375 | 9531/6507 | 12396/8700 | |
| 3955/3493 | 6923/6167 | 10068/9018 | 12733/11459 | |
| 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 |
| 100 | 200 | 300 | 400 | |
| DAS | 3864/3721 | 6843/6211 | 9978/8928 | 12672/11339 |
| 1520/-1966 | 3040/-3218 | 4560/-4568 | 6080/-5582 | |
| 2635/325 | 5093/1089 | 7678/1952 | 10187/3033 | |
| 3497/2223 | 6489/4375 | 9531/6507 | 12396/8700 | |
| 3955/3493 | 6923/6167 | 10068/9018 | 12733/11459 | |
| 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 |
| 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 |
| 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] |
Zongwei Chen. An online-decision algorithm for the multi-period bank clearing problem. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2783-2803. doi: 10.3934/jimo.2021091 |
| [2] |
I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929 |
| [3] |
Zhiping Chen, Jia Liu, Gang Li. Time consistent policy of multi-period mean-variance problem in stochastic markets. Journal of Industrial and Management Optimization, 2016, 12 (1) : 229-249. doi: 10.3934/jimo.2016.12.229 |
| [4] |
Lin Jiang, Song Wang. Robust multi-period and multi-objective portfolio selection. Journal of Industrial and Management Optimization, 2021, 17 (2) : 695-709. doi: 10.3934/jimo.2019130 |
| [5] |
Lihua Bian, Zhongfei Li, Haixiang Yao. Time-consistent strategy for a multi-period mean-variance asset-liability management problem with stochastic interest rate. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1383-1410. doi: 10.3934/jimo.2020026 |
| [6] |
Hongguang Ma, Xiang Li. Multi-period hazardous waste collection planning with consideration of risk stability. Journal of Industrial and Management Optimization, 2021, 17 (1) : 393-408. doi: 10.3934/jimo.2019117 |
| [7] |
Lin Jiang, Changzhi Wu, Song Wang. Distributionally robust multi-period portfolio selection subject to bankruptcy constraints. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021218 |
| [8] |
Christina Burt, Louis Caccetta, Leon Fouché, Palitha Welgama. An MILP approach to multi-location, multi-period equipment selection for surface mining with case studies. Journal of Industrial and Management Optimization, 2016, 12 (2) : 403-430. doi: 10.3934/jimo.2016.12.403 |
| [9] |
Majid Khalilzadeh, Hossein Neghabi, Ramin Ahadi. An application of approximate dynamic programming in multi-period multi-product advertising budgeting. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021202 |
| [10] |
Lan Yi, Zhongfei Li, Duan Li. Multi-period portfolio selection for asset-liability management with uncertain investment horizon. Journal of Industrial and Management Optimization, 2008, 4 (3) : 535-552. doi: 10.3934/jimo.2008.4.535 |
| [11] |
Zhen Wang, Sanyang Liu. Multi-period mean-variance portfolio selection with fixed and proportional transaction costs. Journal of Industrial and Management Optimization, 2013, 9 (3) : 643-657. doi: 10.3934/jimo.2013.9.643 |
| [12] |
Ning Zhang. A symmetric Gauss-Seidel based method for a class of multi-period mean-variance portfolio selection problems. Journal of Industrial and Management Optimization, 2020, 16 (2) : 991-1008. doi: 10.3934/jimo.2018189 |
| [13] |
Hideaki Takagi. Extension of Littlewood's rule to the multi-period static revenue management model with standby customers. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2181-2202. doi: 10.3934/jimo.2020064 |
| [14] |
Chuangwei Lin, Li Zeng, Huiling Wu. Multi-period portfolio optimization in a defined contribution pension plan during the decumulation phase. Journal of Industrial and Management Optimization, 2019, 15 (1) : 401-427. doi: 10.3934/jimo.2018059 |
| [15] |
Yan Zhou, Chi Kin Chan, Kar Hung Wong. The impacts of retailers' regret aversion on a random multi-period supply chain network. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2651-2675. doi: 10.3934/jimo.2021086 |
| [16] |
Toyohiko Aiki. On the existence of a weak solution to a free boundary problem for a model of a shape memory alloy spring. Discrete and Continuous Dynamical Systems - S, 2012, 5 (1) : 1-13. doi: 10.3934/dcdss.2012.5.1 |
| [17] |
Zhenhua Guo, Zilai Li. Global existence of weak solution to the free boundary problem for compressible Navier-Stokes. Kinetic and Related Models, 2016, 9 (1) : 75-103. doi: 10.3934/krm.2016.9.75 |
| [18] |
Fatemeh Kangi, Seyed Hamid Reza Pasandideh, Esmaeil Mehdizadeh, Hamed Soleimani. The optimization of a multi-period multi-product closed-loop supply chain network with cross-docking delivery strategy. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021118 |
| [19] |
Xianping Wu, Xun Li, Zhongfei Li. A mean-field formulation for multi-period asset-liability mean-variance portfolio selection with probability constraints. Journal of Industrial and Management Optimization, 2018, 14 (1) : 249-265. doi: 10.3934/jimo.2017045 |
| [20] |
Huiling Wu, Xiuguo Wang, Yuanyuan Liu, Li Zeng. Multi-period optimal investment choice post-retirement with inter-temporal restrictions in a defined contribution pension plan. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2857-2890. doi: 10.3934/jimo.2019084 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]