The warehouse-retailer network design game

Gaidi Li; Jiating Shao; Dachuan Xu; Wen-Qing Xu

doi:10.3934/jimo.2015.11.291

Article Contents

2015, Volume 11, Issue 1: 291-305. Doi: 10.3934/jimo.2015.11.291

This issue Previous Article A survey on models and algorithms for discrete evacuation planning network problems Next Article A QP-free algorithm of quasi-strongly sub-feasible directions for inequality constrained optimization

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
3.
Department of Applied Mathematics, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing, 100124

Received: October 31, 2012

Revised: December 31, 2013

Published: December 2014

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90C59; Secondary: 90C10.

Citation:

Related Papers

Cited by

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.