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]

Tien-Yu Lin, Bhaba R. Sarker, Chien-Jui Lin. An optimal setup cost reduction and lot size for economic production quantity model with imperfect quality and quantity discounts. Journal of Industrial & Management Optimization, 2021, 17 (1) : 467-484. doi: 10.3934/jimo.2020043
[2]

Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020158
[3]

Qiang Fu, Yanlong Zhang, Yushu Zhu, Ting Li. Network centralities, demographic disparities, and voluntary participation. Mathematical Foundations of Computing, 2020, 3 (4) : 249-262. doi: 10.3934/mfc.2020011
[4]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025
[5]

Sushil Kumar Dey, Bibhas C. Giri. Coordination of a sustainable reverse supply chain with revenue sharing contract. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020165
[6]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044
[7]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170
[8]

Guangbin CAI, Yang Zhao, Wanzhen Quan, Xiusheng Zhang. Design of LPV fault-tolerant controller for hypersonic vehicle based on state observer. Journal of Industrial & Management Optimization, 2021, 17 (1) : 447-465. doi: 10.3934/jimo.2019120
[9]

Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of a Sobolev type impulsive functional evolution system in Banach spaces. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020049
[10]

Jian Zhang, Tony T. Lee, Tong Ye, Liang Huang. An approximate mean queue length formula for queueing systems with varying service rate. Journal of Industrial & Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106
[11]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103
[12]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[13]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019
[14]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076
[15]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078
[16]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462
[17]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250
[18]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120
[19]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115
[20]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences