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

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy