American Institute of Mathematical Sciences

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

The warehouse-retailer network design game

Gaidi Li 1, , Jiating Shao 2, , Dachuan Xu 3, and  Wen-Qing Xu 2,

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.
Keywords: approximate cost recovery., cost-sharing method, Warehouse-retailer network design.
Mathematics Subject Classification: Primary: 90C59; Secondary: 90C1.
Citation: Gaidi Li, Jiating Shao, Dachuan Xu, Wen-Qing Xu. The warehouse-retailer network design game. Journal of Industrial & 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.  doi: 10.1145/779928.779942.  Google Scholar

[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.  doi: 10.1016/S0166-218X(02)00458-4.  Google Scholar

[3]

M. X. Goemans and M. Skutella, Cooperative facility location games,, Journal of Algorithms, 50 (2004), 194.  doi: 10.1016/S0196-6774(03)00098-1.  Google Scholar

[4]

M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization,, Springer-Verlag, (1988).  doi: 10.1007/978-3-642-97881-4.  Google Scholar

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

[6]

S. Iwata, L. Fleischer and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions,, Journal of the ACM, 48 (2001), 761.  doi: 10.1145/502090.502096.  Google Scholar

[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.  doi: 10.1145/380752.380825.  Google Scholar

[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.  doi: 10.1007/s10898-012-9852-0.  Google Scholar

[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.  doi: 10.1287/ijoc.1120.0522.  Google Scholar

[10]

W. Lim, J. Ou and C. Teo, Inventory cost effect of consolidating several one-warehouse multiretailer systems,, Operations Research, 51 (2003), 668.  doi: 10.1287/opre.51.4.668.16092.  Google Scholar

[11]

H. Moulin and S. Shenker, Strategyproof sharing of submodular costs: Budget balance versus efficiency,, Econom Theory, 18 (2001), 511.  doi: 10.1007/PL00004200.  Google Scholar

[12]

M. Pál and É. Tardos, Group strategyproof mechanisms via primal-dual algorithms,, Proceedings of FOCS, (2003), 584.   Google Scholar

[13]

R. Roundy, $98%$ Effective integer-ratio lot-sizing for one warehouse multi-retailer systems,, Management science, 31 (1985), 1416.  doi: 10.1287/mnsc.31.11.1416.  Google Scholar

[14]

A. Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time,, Journal of Combinatorial Theory, 80 (2000), 346.  doi: 10.1006/jctb.2000.1989.  Google Scholar

[15]

J. Shu, An efficient greedy heuristic for warehouse-retailer network design optimization,, Transportation Science, 44 (2010), 183.  doi: 10.1287/trsc.1090.0302.  Google Scholar

[16]

J. Shu, C. Teo and Z. Shen, Stochastic transportation-inventory network design problem,, Operations Research, 53 (2005), 48.  doi: 10.1287/opre.1040.0140.  Google Scholar

[17]

C. Teo and J. Shu, Warehouse-retailer network design problem,, Operations Research, 52 (2004), 396.  doi: 10.1287/opre.1030.0096.  Google Scholar

[18]

D. Xu and D. Du, The $k$-level facility location game,, Operation Research Letter, 34 (2006), 421.  doi: 10.1016/j.orl.2005.06.002.  Google Scholar

[19]

J. Zhang, Cost allocation for joint replenishment models,, Operations Research, 57 (2009), 146.  doi: 10.1287/opre.1070.0491.  Google Scholar

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.  doi: 10.1145/779928.779942.  Google Scholar

[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.  doi: 10.1016/S0166-218X(02)00458-4.  Google Scholar

[3]

M. X. Goemans and M. Skutella, Cooperative facility location games,, Journal of Algorithms, 50 (2004), 194.  doi: 10.1016/S0196-6774(03)00098-1.  Google Scholar

[4]

M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization,, Springer-Verlag, (1988).  doi: 10.1007/978-3-642-97881-4.  Google Scholar

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

[6]

S. Iwata, L. Fleischer and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions,, Journal of the ACM, 48 (2001), 761.  doi: 10.1145/502090.502096.  Google Scholar

[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.  doi: 10.1145/380752.380825.  Google Scholar

[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.  doi: 10.1007/s10898-012-9852-0.  Google Scholar

[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.  doi: 10.1287/ijoc.1120.0522.  Google Scholar

[10]

W. Lim, J. Ou and C. Teo, Inventory cost effect of consolidating several one-warehouse multiretailer systems,, Operations Research, 51 (2003), 668.  doi: 10.1287/opre.51.4.668.16092.  Google Scholar

[11]

H. Moulin and S. Shenker, Strategyproof sharing of submodular costs: Budget balance versus efficiency,, Econom Theory, 18 (2001), 511.  doi: 10.1007/PL00004200.  Google Scholar

[12]

M. Pál and É. Tardos, Group strategyproof mechanisms via primal-dual algorithms,, Proceedings of FOCS, (2003), 584.   Google Scholar

[13]

R. Roundy, $98%$ Effective integer-ratio lot-sizing for one warehouse multi-retailer systems,, Management science, 31 (1985), 1416.  doi: 10.1287/mnsc.31.11.1416.  Google Scholar

[14]

A. Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time,, Journal of Combinatorial Theory, 80 (2000), 346.  doi: 10.1006/jctb.2000.1989.  Google Scholar

[15]

J. Shu, An efficient greedy heuristic for warehouse-retailer network design optimization,, Transportation Science, 44 (2010), 183.  doi: 10.1287/trsc.1090.0302.  Google Scholar

[16]

J. Shu, C. Teo and Z. Shen, Stochastic transportation-inventory network design problem,, Operations Research, 53 (2005), 48.  doi: 10.1287/opre.1040.0140.  Google Scholar

[17]

C. Teo and J. Shu, Warehouse-retailer network design problem,, Operations Research, 52 (2004), 396.  doi: 10.1287/opre.1030.0096.  Google Scholar

[18]

D. Xu and D. Du, The $k$-level facility location game,, Operation Research Letter, 34 (2006), 421.  doi: 10.1016/j.orl.2005.06.002.  Google Scholar

[19]

J. Zhang, Cost allocation for joint replenishment models,, Operations Research, 57 (2009), 146.  doi: 10.1287/opre.1070.0491.  Google Scholar

[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 & 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 & 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 & 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 & Management Optimization, 2019, 15 (1) : 131-157. doi: 10.3934/jimo.2018036
[5]

I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929
[6]

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 & Management Optimization, 2016, 12 (1) : 141-167. doi: 10.3934/jimo.2016.12.141
[7]

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 & Management Optimization, 2012, 8 (3) : 727-732. doi: 10.3934/jimo.2012.8.727
[8]

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 & Management Optimization, 2010, 6 (1) : 103-121. doi: 10.3934/jimo.2010.6.103
[9]

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 & Management Optimization, 2010, 6 (1) : 197-207. doi: 10.3934/jimo.2010.6.197
[10]

R. Enkhbat , N. Tungalag, A. S. Strekalovsky. Pseudoconvexity properties of average cost functions. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 233-236. doi: 10.3934/naco.2015.5.233
[11]

Giuseppe Buttazzo, Serena Guarino Lo Bianco, Fabrizio Oliviero. Optimal location problems with routing cost. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1301-1317. doi: 10.3934/dcds.2014.34.1301
[12]

Piernicola Bettiol, Nathalie Khalil. Necessary optimality conditions for average cost minimization problems. Discrete & Continuous Dynamical Systems - B, 2019, 24 (5) : 2093-2124. doi: 10.3934/dcdsb.2019086
[13]

Lars Grüne, Marleen Stieler. Multiobjective model predictive control for stabilizing cost criteria. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 3905-3928. doi: 10.3934/dcdsb.2018336
[14]

Tai Chiu Edwin Cheng, Bertrand Miao-Tsong Lin, Hsiao-Lan Huang. Talent hold cost minimization in film production. Journal of Industrial & Management Optimization, 2017, 13 (1) : 223-235. doi: 10.3934/jimo.2016013
[15]

Xiaoli Yang, Jin Liang, Bei Hu. Minimization of carbon abatement cost: Modeling, analysis and simulation. Discrete & Continuous Dynamical Systems - B, 2017, 22 (7) : 2939-2969. doi: 10.3934/dcdsb.2017158
[16]

Fan Sha, Deren Han, Weijun Zhong. Bounds on price of anarchy on linear cost functions. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1165-1173. doi: 10.3934/jimo.2015.11.1165
[17]

Ş. İ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 & Management Optimization, 2015, 11 (4) : 1211-1245. doi: 10.3934/jimo.2015.11.1211
[18]

Weidong Bao, Wenhua Xiao, Haoran Ji, Chao Chen, Xiaomin Zhu, Jianhong Wu. Towards big data processing in clouds: An online cost-minimization approach. Big Data & Information Analytics, 2016, 1 (1) : 15-29. doi: 10.3934/bdia.2016.1.15
[19]

Yujing Wang, Changjun Yu, Kok Lay Teo. A new computational strategy for optimal control problem with a cost on changing control. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 339-364. doi: 10.3934/naco.2016016
[20]

Brahim El Asri, Sehail Mazid. Stochastic impulse control Problem with state and time dependent cost functions. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020022

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (45)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences