# American Institute of Mathematical Sciences

January  2015, 11(1): 291-305. doi: 10.3934/jimo.2015.11.291

## The warehouse-retailer network design game

 1 Department of Applied Mathematics, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing 100124 2 Department of Applied Mathematics, Beijing University of Technology, Beijing 100124, China, China 3 Department of Applied Mathematics, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing, 100124

Received  November 2012 Revised  January 2014 Published  May 2014

In this paper, we consider the warehouse-retailer network design game based on the warehouse-retailer network design problem (WRND) proposed by Teo and Shu (2004). By carefully defining the generalized distance function, we present a cost-sharing method for the warehouse-retailer network design game. We show that the proposed cost-sharing scheme is cross-monotonic, competitive, and $3$-approximate cost recovery.
Citation: Gaidi Li, Jiating Shao, Dachuan Xu, Wen-Qing Xu. The warehouse-retailer network design game. Journal of Industrial and Management Optimization, 2015, 11 (1) : 291-305. doi: 10.3934/jimo.2015.11.291
##### References:
 [1] N. R. Devanur, M. Mihail and V. V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Proceedings of the 4th ACM conference on Electronic commerce, (2003), 108-114. doi: 10.1145/779928.779942. [2] L. Fleischer and S. Iwata, A push-relabel framework for submodular function minimization and applications to parametric optimization, Discrete Applied Mathematics, 131 (2003), 311-322. doi: 10.1016/S0166-218X(02)00458-4. [3] M. X. Goemans and M. Skutella, Cooperative facility location games, Journal of Algorithms, 50 (2004), 194-214. doi: 10.1016/S0196-6774(03)00098-1. [4] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1988. doi: 10.1007/978-3-642-97881-4. [5] N. Immorlica, M. Mahdian and V. Mirrokni, Limitations of cross-monotonic cost-sharing schemes, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, (2005), 602-611. [6] S. Iwata, L. Fleischer and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM, 48 (2001), 761-777. doi: 10.1145/502090.502096. [7] K. Jain and V. V. Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, (2001), 364-372. doi: 10.1145/380752.380825. [8] G. Li, Y. Li, J. Shu and D. Xu, A cross-monotonic cost-sharing scheme for the concave facility location game, Journal of Global Optimization, 56 (2013), 1325-1334. doi: 10.1007/s10898-012-9852-0. [9] Y. Li, J. Shu, X. Wang, N. Xiu, D. Xu and J. Zhang, Approximation algorithms for integrated distribution network design problem, INFORMS Journal on Computing, 25 (2013), 572-584. doi: 10.1287/ijoc.1120.0522. [10] W. Lim, J. Ou and C. Teo, Inventory cost effect of consolidating several one-warehouse multiretailer systems, Operations Research, 51 (2003), 668-672. doi: 10.1287/opre.51.4.668.16092. [11] H. Moulin and S. Shenker, Strategyproof sharing of submodular costs: Budget balance versus efficiency, Econom Theory, 18 (2001), 511-533. doi: 10.1007/PL00004200. [12] M. Pál and É. Tardos, Group strategyproof mechanisms via primal-dual algorithms, Proceedings of FOCS, (2003), 584-593. [13] R. Roundy, $98%$ Effective integer-ratio lot-sizing for one warehouse multi-retailer systems, Management science, 31 (1985), 1416-1430. doi: 10.1287/mnsc.31.11.1416. [14] A. Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory, Series B, 80 (2000), 346-355. doi: 10.1006/jctb.2000.1989. [15] J. Shu, An efficient greedy heuristic for warehouse-retailer network design optimization, Transportation Science, 44 (2010), 183-192. doi: 10.1287/trsc.1090.0302. [16] J. Shu, C. Teo and Z. Shen, Stochastic transportation-inventory network design problem, Operations Research, 53 (2005), 48-60. doi: 10.1287/opre.1040.0140. [17] C. Teo and J. Shu, Warehouse-retailer network design problem, Operations Research, 52 (2004), 396-408. doi: 10.1287/opre.1030.0096. [18] D. Xu and D. Du, The $k$-level facility location game, Operation Research Letter, 34 (2006), 421-426. doi: 10.1016/j.orl.2005.06.002. [19] J. Zhang, Cost allocation for joint replenishment models, Operations Research, 57 (2009), 146-156. doi: 10.1287/opre.1070.0491.

show all references

##### References:
 [1] N. R. Devanur, M. Mihail and V. V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Proceedings of the 4th ACM conference on Electronic commerce, (2003), 108-114. doi: 10.1145/779928.779942. [2] L. Fleischer and S. Iwata, A push-relabel framework for submodular function minimization and applications to parametric optimization, Discrete Applied Mathematics, 131 (2003), 311-322. doi: 10.1016/S0166-218X(02)00458-4. [3] M. X. Goemans and M. Skutella, Cooperative facility location games, Journal of Algorithms, 50 (2004), 194-214. doi: 10.1016/S0196-6774(03)00098-1. [4] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1988. doi: 10.1007/978-3-642-97881-4. [5] N. Immorlica, M. Mahdian and V. Mirrokni, Limitations of cross-monotonic cost-sharing schemes, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, (2005), 602-611. [6] S. Iwata, L. Fleischer and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM, 48 (2001), 761-777. doi: 10.1145/502090.502096. [7] K. Jain and V. V. Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, (2001), 364-372. doi: 10.1145/380752.380825. [8] G. Li, Y. Li, J. Shu and D. Xu, A cross-monotonic cost-sharing scheme for the concave facility location game, Journal of Global Optimization, 56 (2013), 1325-1334. doi: 10.1007/s10898-012-9852-0. [9] Y. Li, J. Shu, X. Wang, N. Xiu, D. Xu and J. Zhang, Approximation algorithms for integrated distribution network design problem, INFORMS Journal on Computing, 25 (2013), 572-584. doi: 10.1287/ijoc.1120.0522. [10] W. Lim, J. Ou and C. Teo, Inventory cost effect of consolidating several one-warehouse multiretailer systems, Operations Research, 51 (2003), 668-672. doi: 10.1287/opre.51.4.668.16092. [11] H. Moulin and S. Shenker, Strategyproof sharing of submodular costs: Budget balance versus efficiency, Econom Theory, 18 (2001), 511-533. doi: 10.1007/PL00004200. [12] M. Pál and É. Tardos, Group strategyproof mechanisms via primal-dual algorithms, Proceedings of FOCS, (2003), 584-593. [13] R. Roundy, $98%$ Effective integer-ratio lot-sizing for one warehouse multi-retailer systems, Management science, 31 (1985), 1416-1430. doi: 10.1287/mnsc.31.11.1416. [14] A. Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory, Series B, 80 (2000), 346-355. doi: 10.1006/jctb.2000.1989. [15] J. Shu, An efficient greedy heuristic for warehouse-retailer network design optimization, Transportation Science, 44 (2010), 183-192. doi: 10.1287/trsc.1090.0302. [16] J. Shu, C. Teo and Z. Shen, Stochastic transportation-inventory network design problem, Operations Research, 53 (2005), 48-60. doi: 10.1287/opre.1040.0140. [17] C. Teo and J. Shu, Warehouse-retailer network design problem, Operations Research, 52 (2004), 396-408. doi: 10.1287/opre.1030.0096. [18] D. Xu and D. Du, The $k$-level facility location game, Operation Research Letter, 34 (2006), 421-426. doi: 10.1016/j.orl.2005.06.002. [19] J. Zhang, Cost allocation for joint replenishment models, Operations Research, 57 (2009), 146-156. doi: 10.1287/opre.1070.0491.
 [1] Xue-Yan Wu, Zhi-Ping Fan, Bing-Bing Cao. Cost-sharing strategy for carbon emission reduction and sales effort: A nash game with government subsidy. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1999-2027. doi: 10.3934/jimo.2019040 [2] Wei Xu, Liying Yu, Gui-Hua Lin, Zhi Guo Feng. Optimal switching signal design with a cost on switching action. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2531-2549. doi: 10.3934/jimo.2019068 [3] Adriana Navarro-Ramos, William Olvera-Lopez. A solution for discrete cost sharing problems with non rival consumption. Journal of Dynamics and Games, 2018, 5 (1) : 31-39. doi: 10.3934/jdg.2018004 [4] Xiaohu Qian, Min Huang, Wai-Ki Ching, Loo Hay Lee, Xingwei Wang. Mechanism design in project procurement auctions with cost uncertainty and failure risk. Journal of Industrial and Management Optimization, 2019, 15 (1) : 131-157. doi: 10.3934/jimo.2018036 [5] Xiaomei Li, Renjing Liu, Zhongquan Hu, Jiamin Dong. Information sharing in two-tier supply chains considering cost reduction effort and information leakage. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021200 [6] 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 [7] Cheng-Ta Yeh, Yi-Kuei Lin. Component allocation cost minimization for a multistate computer network subject to a reliability threshold using tabu search. Journal of Industrial and Management Optimization, 2016, 12 (1) : 141-167. doi: 10.3934/jimo.2016.12.141 [8] Cheng-Dar Liou. Note on "Cost analysis of the M/M/R machine repair problem with second optional repair: Newton-Quasi method". Journal of Industrial and Management Optimization, 2012, 8 (3) : 727-732. doi: 10.3934/jimo.2012.8.727 [9] Gang Qian, Deren Han, Hongjin He. Congestion control with pricing in the absence of demand and cost functions: An improved trial and error method. Journal of Industrial and Management Optimization, 2010, 6 (1) : 103-121. doi: 10.3934/jimo.2010.6.103 [10] Kuo-Hsiung Wang, Chuen-Wen Liao, Tseng-Chang Yen. Cost analysis of the M/M/R machine repair problem with second optional repair: Newton-Quasi method. Journal of Industrial and Management Optimization, 2010, 6 (1) : 197-207. doi: 10.3934/jimo.2010.6.197 [11] R. Enkhbat , N. Tungalag, A. S. Strekalovsky. Pseudoconvexity properties of average cost functions. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 233-236. doi: 10.3934/naco.2015.5.233 [12] Giuseppe Buttazzo, Serena Guarino Lo Bianco, Fabrizio Oliviero. Optimal location problems with routing cost. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1301-1317. doi: 10.3934/dcds.2014.34.1301 [13] Yassine El Gantouh, Said Hadd, Abdelaziz Rhandi. Approximate controllability of network systems. Evolution Equations and Control Theory, 2021, 10 (4) : 749-766. doi: 10.3934/eect.2020091 [14] Piernicola Bettiol, Nathalie Khalil. Necessary optimality conditions for average cost minimization problems. Discrete and Continuous Dynamical Systems - B, 2019, 24 (5) : 2093-2124. doi: 10.3934/dcdsb.2019086 [15] Lars Grüne, Marleen Stieler. Multiobjective model predictive control for stabilizing cost criteria. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 3905-3928. doi: 10.3934/dcdsb.2018336 [16] Tai Chiu Edwin Cheng, Bertrand Miao-Tsong Lin, Hsiao-Lan Huang. Talent hold cost minimization in film production. Journal of Industrial and Management Optimization, 2017, 13 (1) : 223-235. doi: 10.3934/jimo.2016013 [17] Xiaoli Yang, Jin Liang, Bei Hu. Minimization of carbon abatement cost: Modeling, analysis and simulation. Discrete and Continuous Dynamical Systems - B, 2017, 22 (7) : 2939-2969. doi: 10.3934/dcdsb.2017158 [18] Fan Sha, Deren Han, Weijun Zhong. Bounds on price of anarchy on linear cost functions. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1165-1173. doi: 10.3934/jimo.2015.11.1165 [19] Ş. İlker Birbil, Kerem Bülbül, J. B. G. Frenk, H. M. Mulder. On EOQ cost models with arbitrary purchase and transportation costs. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1211-1245. doi: 10.3934/jimo.2015.11.1211 [20] Onur Şimşek, O. Erhun Kundakcioglu. Cost of fairness in agent scheduling for contact centers. Journal of Industrial and Management Optimization, 2022, 18 (2) : 873-896. doi: 10.3934/jimo.2021001

2021 Impact Factor: 1.411