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 & 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]

Sabyasachi Dey, Tapabrata Roy, Santanu Sarkar. Revisiting design principles of Salsa and ChaCha. Advances in Mathematics of Communications, 2019, 13 (4) : 689-704. doi: 10.3934/amc.2019041

[2]

Juliang Zhang, Jian Chen. Information sharing in a make-to-stock supply chain. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1169-1189. doi: 10.3934/jimo.2014.10.1169

[3]

Ziteng Wang, Shu-Cherng Fang, Wenxun Xing. On constraint qualifications: Motivation, design and inter-relations. Journal of Industrial & Management Optimization, 2013, 9 (4) : 983-1001. doi: 10.3934/jimo.2013.9.983

[4]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367

[5]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[6]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[7]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006

[8]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[9]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018

[10]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002

[11]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263

[12]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149

[13]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83

[14]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[15]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]