带次模特性的仓库选址问题研究
|
摘要
本文研究了一系列具有次模特性的仓库选址问题,包括：带次模运营费用的仓库选址问题,带次模惩罚费用的仓库选址问题,以及带次模运营费用和次模惩罚费用的仓库选址问题.我们分别对这三类问题设计近似算法.对于每一个本文研究的问题,我们的近似算法都具有目前最好的近似比.
在第一章,我们介绍了本文将用到的相关知识,研究的内容,背景以及我们的研究结果.
在第二章,我们研究了两类带次模运营费用的仓库选址问题,即：仓库零售商网络设计(WRND)问题和随机运输库存网络设计(STIND)问题.这两个问题都可以看做是经典的组合优化问题——无容量限制的设施选址(UFL)问题的推广.在UFL问题的基础上,WRND问题和STIND问题难度的增加主要在于引入一个新的费用——库存费用：其中WRND问题引入了仓库-零售商互相影响的两层库存费用,STIND问题引入了安全库存费用.我们为这两个问题设计了常数近似比的近似算法,可以用于解决大规模问题.
在第三章,我们研究了带次模惩罚费用的仓库选址(WLPSP)司题以及它的特殊情况带线性惩罚的仓库选址问题(WLPLP)我们先给出了关于WLPSP司题的2.044-近似算法,并把这个近似算法推广成一个算法框架用以解决一系列的带次模惩罚问题.具体的来说,我们给出的算法框架,可以把一个不带次模惩罚问题基于舍入技巧的α-近似算法改造成带次模惩罚问题的(1-e-1/α)-近似算法.另外,我们通过探索WLPSP问题和WLPLP司题的特殊结构,我们进一步给出WLPSP问题的一个改进算法,将近似比改进到2；进一步给出WLPLP问题的一个改进算法,将近似比改进到1.5148.
在第四章,我们继续研究WLPSP问题,我们通过组合已有的原始对偶算法和我们的贪婪增广算法,给出一个新的组合近似算法.这个算法是目前组合算法中近似比最好的算法,将目前原始对偶算法的近似比3改进到了2.375.并且如果不考虑第三章我们给出的算法,我们给出的组合算法实际上改进了已有最好的近似比2.488.
第五章,我们提出并研究了带次模惩罚费用的仓库零售商网络设计(WRNDSP)问题.在这个问题中我们允许以支付惩罚费用为代价不为一部分零售商提供服务.我们假设这个惩罚费用是一个关于被拒绝提供服务的零售商集合的不减次模函数.我们给出了关于这个问题的一个3-近似原始对偶算法.
The thesis investigates a series of warehouse location problems with submodular-ity, including warehouse location problem with submodular operation cost, warehouse location problem with submodular penalty cost and warehouse location problem with submodular operation cost and penalty cost. We disign approximation algorithms for those problems respectively and the approximation ratios of our algorithms for all the problems we studied are the best so far.
In Chapter1, we introduce some related basic knowledge, specific issues, relative backgrounds of the research and our results.
In Chapter2, we study two warehouse location problems with submodular oper-ation cost, namely, the warehouse-retailer network design (WRND) problem and the stochastic transportation-inventory network design (STIND) problem. These two prob-lems generalize the classical uncapacitated facility location problem by incorporating, respectively, the warehouse-retailer echelon inventory cost and the warehouse cycle in-ventory together with the safety stock costs. Our main contribution is to obtain two3-approximation algorithms for the WRND and the STIND, which are capable of solv-ing large-scale instances of these problems efficiently.
In Chapter3, we study warehouse location problem with submodular penalties (WLPSP) and introduce a general algorithmic framework that leverages existing approximation re-sults for the traditional models to obtain corresponding results for their counterpart mod-els with submodular penalties. More specifically, any rounding-based a-approximation for the traditional model can be leveraged to a (1-e-1/α)-approximation algorithm for the counterpart model with submodular penalties. With exploiting the special prop-erties, for WLPSP we can improve the approximation ratio from2.044to2, and for the more special case——warehouse location problem with linear penalties (WLPLP), we present a1.5148-approximation algorithm, which offer the currently best approximation ratios, respectively.
In Chapter4, we continued to study WLPSP and offer the a combinatorial approxi-mation algorithm with currently best approximation ratio2.375, which improves not only the previous best combinatorial ratio3, but also the previous best non-combinatorial ra-tio2.488. We achieve this improved ratio by combining the primal-dual scheme with the greedy augmentation technique.
In Chapter5, we propose and study the warehoues-retailer network design problem with submodular penalties (WRNDSP). In this problem, we might not choose to serve some retailers at the cost of paying a penalty cost which is assumed to be a non-decreasing nonnegative submodular function. We propose a primal-dual approximation algorithm with a performance factor of3for this problem.
在第一章,我们介绍了本文将用到的相关知识,研究的内容,背景以及我们的研究结果.
在第二章,我们研究了两类带次模运营费用的仓库选址问题,即：仓库零售商网络设计(WRND)问题和随机运输库存网络设计(STIND)问题.这两个问题都可以看做是经典的组合优化问题——无容量限制的设施选址(UFL)问题的推广.在UFL问题的基础上,WRND问题和STIND问题难度的增加主要在于引入一个新的费用——库存费用：其中WRND问题引入了仓库-零售商互相影响的两层库存费用,STIND问题引入了安全库存费用.我们为这两个问题设计了常数近似比的近似算法,可以用于解决大规模问题.
在第三章,我们研究了带次模惩罚费用的仓库选址(WLPSP)司题以及它的特殊情况带线性惩罚的仓库选址问题(WLPLP)我们先给出了关于WLPSP司题的2.044-近似算法,并把这个近似算法推广成一个算法框架用以解决一系列的带次模惩罚问题.具体的来说,我们给出的算法框架,可以把一个不带次模惩罚问题基于舍入技巧的α-近似算法改造成带次模惩罚问题的(1-e-1/α)-近似算法.另外,我们通过探索WLPSP问题和WLPLP司题的特殊结构,我们进一步给出WLPSP问题的一个改进算法,将近似比改进到2；进一步给出WLPLP问题的一个改进算法,将近似比改进到1.5148.
在第四章,我们继续研究WLPSP问题,我们通过组合已有的原始对偶算法和我们的贪婪增广算法,给出一个新的组合近似算法.这个算法是目前组合算法中近似比最好的算法,将目前原始对偶算法的近似比3改进到了2.375.并且如果不考虑第三章我们给出的算法,我们给出的组合算法实际上改进了已有最好的近似比2.488.
第五章,我们提出并研究了带次模惩罚费用的仓库零售商网络设计(WRNDSP)问题.在这个问题中我们允许以支付惩罚费用为代价不为一部分零售商提供服务.我们假设这个惩罚费用是一个关于被拒绝提供服务的零售商集合的不减次模函数.我们给出了关于这个问题的一个3-近似原始对偶算法.
The thesis investigates a series of warehouse location problems with submodular-ity, including warehouse location problem with submodular operation cost, warehouse location problem with submodular penalty cost and warehouse location problem with submodular operation cost and penalty cost. We disign approximation algorithms for those problems respectively and the approximation ratios of our algorithms for all the problems we studied are the best so far.
In Chapter1, we introduce some related basic knowledge, specific issues, relative backgrounds of the research and our results.
In Chapter2, we study two warehouse location problems with submodular oper-ation cost, namely, the warehouse-retailer network design (WRND) problem and the stochastic transportation-inventory network design (STIND) problem. These two prob-lems generalize the classical uncapacitated facility location problem by incorporating, respectively, the warehouse-retailer echelon inventory cost and the warehouse cycle in-ventory together with the safety stock costs. Our main contribution is to obtain two3-approximation algorithms for the WRND and the STIND, which are capable of solv-ing large-scale instances of these problems efficiently.
In Chapter3, we study warehouse location problem with submodular penalties (WLPSP) and introduce a general algorithmic framework that leverages existing approximation re-sults for the traditional models to obtain corresponding results for their counterpart mod-els with submodular penalties. More specifically, any rounding-based a-approximation for the traditional model can be leveraged to a (1-e-1/α)-approximation algorithm for the counterpart model with submodular penalties. With exploiting the special prop-erties, for WLPSP we can improve the approximation ratio from2.044to2, and for the more special case——warehouse location problem with linear penalties (WLPLP), we present a1.5148-approximation algorithm, which offer the currently best approximation ratios, respectively.
In Chapter4, we continued to study WLPSP and offer the a combinatorial approxi-mation algorithm with currently best approximation ratio2.375, which improves not only the previous best combinatorial ratio3, but also the previous best non-combinatorial ra-tio2.488. We achieve this improved ratio by combining the primal-dual scheme with the greedy augmentation technique.
In Chapter5, we propose and study the warehoues-retailer network design problem with submodular penalties (WRNDSP). In this problem, we might not choose to serve some retailers at the cost of paying a penalty cost which is assumed to be a non-decreasing nonnegative submodular function. We propose a primal-dual approximation algorithm with a performance factor of3for this problem.
引文
[1]A. Ageev, Y.Ye and J. Zhang. Improved combinatorial approximation algorithms for the k-level facility location problem. SIAM Journal on Discrete Mathmatics.2004.18(1):207-217
[2]S. Anily and M. Haviv. The cost allocation problem for the first order interaction joint replenishment model. Operations Research.2007.55(2):292-302
[3]M. L. Balinksi. On finding integer solutions to linear programs. Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems.1966. IBM,225-248
[4]J. Byrka and K. Aardal. An optimal bifactor approximation algorithm for the metric unca-pacitated facility location problem. SIAM Journal on Computing.2010.39(6),2212-2231
[5]M. Charikar and S. Guha. Improved combinatorial algorithms for the facility location and k-median problems. Proceedings of the 40th Annual Symposium on Foundations of Computer Science.1999.378-388
[6]M. Charikar, S. Khuller, D. M. Mount and G. Naraasimban. Algorithms for facility location problems with outliers. Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms.2001.642-651
[7]M. Charikar and S. Guha. Improved combinatorial algorithms for facility location and k-median problems. Proceedings of the 40th Annual IEEE Symposium on Foundations of Com-puter Science.1999.378-388
[8]C. Chekuri and A. Ene. Submodular cost allocation problem and applications. Proceedings of the 38th International Colloquim Conference on Automata.2011.354-366
[9]X. Chen and B. Chen. Approximation algorithms for soft-capacitated facility location in capacitated network design. Algorithmica.2007.53(3):263-297
[10]F. A. Chudak and K. Nagano. Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovasz extension and non-smooth convex optimization. Proceedings of the Eighteenth Annual ACM-SIAM symposium on Discrete Algorithms.2007. 79-88
[11]F. A. Chudak and D. B. Shmoys. Improved approximation algorithms for the uncapacitated facility location problem. SIAM Journal on Computing.2004.33(1):1-25
[12]M. S. Daskin, C. R. Coullard, and Z. J. Max Shen. An inventory-location model:formu-lation, solution algorithm and computational results. Annals of Operations Research.2002. 110:83-106
[13]N. Devanur, M. Mihail and V. V. Vazirani. Strateproof cost-sharing Mechenisms for set cover and facility location games. Proceedings of the 4th ACM Conference on Electronic commerce.2003.108-114
[14]D. Du, R. Lu and D. Xu. A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica.2012.63(1):191-200
[15]D. Du, X. Wang and D. Xu. An approximation algorithm for the k-level capacitated facility location problem. Journal of Combinatorial Optimization.2010.20(4):361-368
[16]S. Fujishige. Submodular functions and optimization. Second Edition. Annals of Discrete Mathematics. Elsevier.2005
[17]J. Geunes, R. Levi, H. E. Romeijn and D. B. Shmoys. Approximation algorithms for supply chain planning and logistics problems with market choice. Mathematical Programming.2011. 130(1):85-106
[18]M. X. Goemans and M. Skutella. Cooperative facility location game. Journal of algorithms. 2004.50(2):194-214
[19]D. Granot. A generalized linear production model:A unifying model. Mathematical Pro-gramming.1986.34(2):212-222
[20]S. Guha and S. Khuller. Greedy strikes back:Improved facilitylocation algorithms. Journal of Algorithms.31,228-248, (1999).
[21]L. A. Guardiola, A. Meca and J. Puerto. Production-inventory games:a new class of to-tally balanced combinatorial optimization games. Technical Report,2005. Universitas Miguel Hernandes
[22]M. T. Hajiaghayi, M. Mahdian, and V. S. Mirrokni. The facility location problem with general cost Functions. Networks.2003.42:42-47
[23]B. Hartman, M. Dror and M. Shsked. Cores of inventory centralization costs with varying cost parameters. Game and Economic Behavior.2000.31(1):26-49
[24]B. C. Hartman and M, Dror. Cost allocation in continuous review inventory models. Naval Research Logistics Quarterly.1996.43(4):549-561
[25]A. Hayrapetyan, C. Swamy, E. Tardos. Network design for information networks. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms.2005.933-942
[26]T. Ichiishi. Supermodularity:applications to convex games and the greedy for LP. Journal of Economic Theory.1981.25(2):283-286
[27]P. Jackson, W. Maxwell and J. Muckstadt. The joint replenishment problem with a powers-of-two restriction. IIE Transactions.1985.17(1):25-32
[28]K. Jain, M. Mahdian, M., E. Markakis, A. Saberi, V. V. Vazirani. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. Journal of the ACM.2003. 50(6):795-824
[29]K. Jain and V. V. Vazirani. Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM.2001.48(2):274-296
[30]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.
[31]A. A. Kuehn and M. J. Hamburger. A heuristic program for locating warehouses. Manage-ment Science.1963.9(4):643-666
[32]M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. Journal of Algorithms.2000.37(1):146-188
[33]S. Li. A 1.488-Approximation algorithm for the uncapacitated facility location problem. Pro-ceedings of the 38th International Conference on Automata, Languages and Programming. 2011.77-88
[34]黎煜,无容量约束选址与软容量约束选址博弈.硕士学位论文.北京工业大学,2010
[35]W. S. Lim, J. H. On, and C. P. Teo. Inventory cost effect of consolidating several one-warehouse multiretailer systems. Operations Research.2003.51(4):668-672
[36]M. Mahdian. Facility location and the analysis of algorithms through factor-revealing pro-grams. Ph. D. thesis, MIT, Cambridge.2004
[37]M. Mahdian, Y. Ye and J. Zhang. Approxiamtion alogrithms formetric facility location prblems. SIAM Journal on Computing.2006.36(2):411-432
[38]A. S. Manne. Plant location undereconomies-of-scale-decentralization and computation. Management Science.1964.11:213-235
[39]A. S. Many. Programming of dynamic lot sizes. Management Science.1958 4:115-135
[40]A. Meca, J. Timmer, I. Gatcia-Jurado and P. Borm. Inventory games. Eourpean Jouranl of Operational Research.2004.156(1):127-139
[41]M. T. Melo, S. Nickel and F. Saldanha-da-Gama. Facility location and supply chain man-agement-a review. European Journal of Operational Research.2009.196(2):401-412
[42]A. Muller and M. Scarsini. The newsvendor game has a non-emptycore. Games and Eco-nomic Behavior.2002.38(1):118-126
[43]G. Owen. On the core of linear production games. Mathematical Programming.1957.9(1): 358-370
[44]U. Ozen, J. Fransoo, H. W. Norde and M. Slikker. Cooperation between multiple newsven-dors with warehouses. Manufacturing and Service Operations Management.2008.10(2): 331-324
[45]M. Pal and E. Tardos. Group strategyproof mechanisms via primal-dual algorithms. Pro-ceedings of the 44th Annual Symposium on Foundations of Computer Science.2003.584-593
[46]Y. Pochet and L. A. Wolsey. Lot-size models with backlogging:strong reformulations and cutting planes. Mathematical Programming.1988.40(1-3):317-335
[47]L. Qi, Z. J. Max Shen and L. V. Snyder. The effect of supply disruptions on supply chain design decisions. Transportation Science.2010.44(2):274-289
[48]任鸣鸣.供应链系统节点设施选址研究.博士学位论文.华中科技大学.2008
[49]R. O. Roundy.98% effective integer ratio lot-sizing for one warehouse multi-retailer systems. Mamagement Science.1985.31(11):1416-1430
[50]D. Samet and E. Zemel. On the core and dual set of linear programming games. Mathematical of Operations Research.1984.9(2):309-316
[51]L. S. Shapley. On balanced sets and cores. Naval Research Logistics.1967.14(4):453-460
[52]Z. J. Max Shen. Integrated supply chain design models:a survey and future research direc-tions. Journal of Industrial and Management Optimization.2007.3(1):1-27
[53]Z. J. Max Shen, C. Coullard, and M. S. Daskin. A Joint Location-Inventory Model. Trans-portation Science.2003.37(1):40-55
[54]D. B. Shmoys and C. Swamy. An approximation scheme for stochastic linear programming and its application to stochastic integer programs. Journal of the ACM.2006.53(6):978-1012
[55]D. B. Shmoys, E. Tardos, and K. I. Aardal. Approximation algorithms for facility location problems. Proceedings of the Twenty-ninth Annual A CM Symposium on Theory of Comput-ing.1997.265-274
[56]J. Shu. An efficient greedy heuristic for warehouse-retailer network design optimization. Transportation Science.2010.44(2):183-192
[57]J. Shu, C. P. Teo and Z. J. Max Shen. Stochastic transportation-inventory network design problem. Operations Research.2005.53(1):48-60
[58]M. Slikker, J. Fransoo and M. Wouters. Coopertation between multiple newsvendors with transsipments. European Journal of Operational Research,2005.167(2):370-380
[59]L. V. Snyder and M. S. Daskin. Reliability models for facility location:the expected Failure cost case. Transportation Science.2005.39(3):400-416
[60]J. F. Stollsteimer. A working model for plant numbers andlocations. Journal of Farm Eco-nomics.1963.45(3):631-645
[61]M. Sviridenko. An improved approximation algorithm for the metric uncapacitated facility location problem. Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization.2002.240-257
[62]Z. Svitkina and E. Tardos. Facility location with hierarchical facility costs. Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm.2006.153-161.
[63]C. P. Teo, J. H. Ou, and M. Goh. Impact on inventory costs with consolidation of distribution centers. HE Transactions.2001.33:99-110
[64]C. P. Teo and J. Shu. Warehouse-retailer network design problem. Operations Research. 2004:52(3):396-408
[65]M. Thorup. Quick and good facility location. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms.2003.178-185
[66]J. Vondrak. Optimal approximation for the submodular welfare problem in the value oracle model. Proceedings of the Forty Annual ACM Symposium on Theory of Computing.2008. 67-74
[67]D. Xu and D. Du. The k-level facility location game. Operations Research Letters.2006 34(4),421-426
[68]G. Xu and J. Xu. An LP rounding algorithm for approximating uncapacitated facility location problem with penalties. Information Processing Letters.2005.94(3):119-123
[69]G. Xu and J. Xu. An improved approximation algorithm for uncapacitated facility location problem with penalties. Journal of Combinatorial Optimization.2009.17(4):424-436
[70]Y. Ye and J. Zhang. An approximation algorithm for the dynamic facility location problem. Combinatorial Optimization in Communication Networks.2006.18:623-637
[71]J. Zhang. Approximating the two-level facility location problem via a quasi-greedy approach. Mathematical Programming.2006.108(1):159-176
[72]J. Zhang, B. Chen and Y. Ye. A multiexchange local search algorithm for the capacitated facility location problem. Mathematics of Operations Research.30(2):389-403
[2]S. Anily and M. Haviv. The cost allocation problem for the first order interaction joint replenishment model. Operations Research.2007.55(2):292-302
[3]M. L. Balinksi. On finding integer solutions to linear programs. Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems.1966. IBM,225-248
[4]J. Byrka and K. Aardal. An optimal bifactor approximation algorithm for the metric unca-pacitated facility location problem. SIAM Journal on Computing.2010.39(6),2212-2231
[5]M. Charikar and S. Guha. Improved combinatorial algorithms for the facility location and k-median problems. Proceedings of the 40th Annual Symposium on Foundations of Computer Science.1999.378-388
[6]M. Charikar, S. Khuller, D. M. Mount and G. Naraasimban. Algorithms for facility location problems with outliers. Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms.2001.642-651
[7]M. Charikar and S. Guha. Improved combinatorial algorithms for facility location and k-median problems. Proceedings of the 40th Annual IEEE Symposium on Foundations of Com-puter Science.1999.378-388
[8]C. Chekuri and A. Ene. Submodular cost allocation problem and applications. Proceedings of the 38th International Colloquim Conference on Automata.2011.354-366
[9]X. Chen and B. Chen. Approximation algorithms for soft-capacitated facility location in capacitated network design. Algorithmica.2007.53(3):263-297
[10]F. A. Chudak and K. Nagano. Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovasz extension and non-smooth convex optimization. Proceedings of the Eighteenth Annual ACM-SIAM symposium on Discrete Algorithms.2007. 79-88
[11]F. A. Chudak and D. B. Shmoys. Improved approximation algorithms for the uncapacitated facility location problem. SIAM Journal on Computing.2004.33(1):1-25
[12]M. S. Daskin, C. R. Coullard, and Z. J. Max Shen. An inventory-location model:formu-lation, solution algorithm and computational results. Annals of Operations Research.2002. 110:83-106
[13]N. Devanur, M. Mihail and V. V. Vazirani. Strateproof cost-sharing Mechenisms for set cover and facility location games. Proceedings of the 4th ACM Conference on Electronic commerce.2003.108-114
[14]D. Du, R. Lu and D. Xu. A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica.2012.63(1):191-200
[15]D. Du, X. Wang and D. Xu. An approximation algorithm for the k-level capacitated facility location problem. Journal of Combinatorial Optimization.2010.20(4):361-368
[16]S. Fujishige. Submodular functions and optimization. Second Edition. Annals of Discrete Mathematics. Elsevier.2005
[17]J. Geunes, R. Levi, H. E. Romeijn and D. B. Shmoys. Approximation algorithms for supply chain planning and logistics problems with market choice. Mathematical Programming.2011. 130(1):85-106
[18]M. X. Goemans and M. Skutella. Cooperative facility location game. Journal of algorithms. 2004.50(2):194-214
[19]D. Granot. A generalized linear production model:A unifying model. Mathematical Pro-gramming.1986.34(2):212-222
[20]S. Guha and S. Khuller. Greedy strikes back:Improved facilitylocation algorithms. Journal of Algorithms.31,228-248, (1999).
[21]L. A. Guardiola, A. Meca and J. Puerto. Production-inventory games:a new class of to-tally balanced combinatorial optimization games. Technical Report,2005. Universitas Miguel Hernandes
[22]M. T. Hajiaghayi, M. Mahdian, and V. S. Mirrokni. The facility location problem with general cost Functions. Networks.2003.42:42-47
[23]B. Hartman, M. Dror and M. Shsked. Cores of inventory centralization costs with varying cost parameters. Game and Economic Behavior.2000.31(1):26-49
[24]B. C. Hartman and M, Dror. Cost allocation in continuous review inventory models. Naval Research Logistics Quarterly.1996.43(4):549-561
[25]A. Hayrapetyan, C. Swamy, E. Tardos. Network design for information networks. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms.2005.933-942
[26]T. Ichiishi. Supermodularity:applications to convex games and the greedy for LP. Journal of Economic Theory.1981.25(2):283-286
[27]P. Jackson, W. Maxwell and J. Muckstadt. The joint replenishment problem with a powers-of-two restriction. IIE Transactions.1985.17(1):25-32
[28]K. Jain, M. Mahdian, M., E. Markakis, A. Saberi, V. V. Vazirani. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. Journal of the ACM.2003. 50(6):795-824
[29]K. Jain and V. V. Vazirani. Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM.2001.48(2):274-296
[30]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.
[31]A. A. Kuehn and M. J. Hamburger. A heuristic program for locating warehouses. Manage-ment Science.1963.9(4):643-666
[32]M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. Journal of Algorithms.2000.37(1):146-188
[33]S. Li. A 1.488-Approximation algorithm for the uncapacitated facility location problem. Pro-ceedings of the 38th International Conference on Automata, Languages and Programming. 2011.77-88
[34]黎煜,无容量约束选址与软容量约束选址博弈.硕士学位论文.北京工业大学,2010
[35]W. S. Lim, J. H. On, and C. P. Teo. Inventory cost effect of consolidating several one-warehouse multiretailer systems. Operations Research.2003.51(4):668-672
[36]M. Mahdian. Facility location and the analysis of algorithms through factor-revealing pro-grams. Ph. D. thesis, MIT, Cambridge.2004
[37]M. Mahdian, Y. Ye and J. Zhang. Approxiamtion alogrithms formetric facility location prblems. SIAM Journal on Computing.2006.36(2):411-432
[38]A. S. Manne. Plant location undereconomies-of-scale-decentralization and computation. Management Science.1964.11:213-235
[39]A. S. Many. Programming of dynamic lot sizes. Management Science.1958 4:115-135
[40]A. Meca, J. Timmer, I. Gatcia-Jurado and P. Borm. Inventory games. Eourpean Jouranl of Operational Research.2004.156(1):127-139
[41]M. T. Melo, S. Nickel and F. Saldanha-da-Gama. Facility location and supply chain man-agement-a review. European Journal of Operational Research.2009.196(2):401-412
[42]A. Muller and M. Scarsini. The newsvendor game has a non-emptycore. Games and Eco-nomic Behavior.2002.38(1):118-126
[43]G. Owen. On the core of linear production games. Mathematical Programming.1957.9(1): 358-370
[44]U. Ozen, J. Fransoo, H. W. Norde and M. Slikker. Cooperation between multiple newsven-dors with warehouses. Manufacturing and Service Operations Management.2008.10(2): 331-324
[45]M. Pal and E. Tardos. Group strategyproof mechanisms via primal-dual algorithms. Pro-ceedings of the 44th Annual Symposium on Foundations of Computer Science.2003.584-593
[46]Y. Pochet and L. A. Wolsey. Lot-size models with backlogging:strong reformulations and cutting planes. Mathematical Programming.1988.40(1-3):317-335
[47]L. Qi, Z. J. Max Shen and L. V. Snyder. The effect of supply disruptions on supply chain design decisions. Transportation Science.2010.44(2):274-289
[48]任鸣鸣.供应链系统节点设施选址研究.博士学位论文.华中科技大学.2008
[49]R. O. Roundy.98% effective integer ratio lot-sizing for one warehouse multi-retailer systems. Mamagement Science.1985.31(11):1416-1430
[50]D. Samet and E. Zemel. On the core and dual set of linear programming games. Mathematical of Operations Research.1984.9(2):309-316
[51]L. S. Shapley. On balanced sets and cores. Naval Research Logistics.1967.14(4):453-460
[52]Z. J. Max Shen. Integrated supply chain design models:a survey and future research direc-tions. Journal of Industrial and Management Optimization.2007.3(1):1-27
[53]Z. J. Max Shen, C. Coullard, and M. S. Daskin. A Joint Location-Inventory Model. Trans-portation Science.2003.37(1):40-55
[54]D. B. Shmoys and C. Swamy. An approximation scheme for stochastic linear programming and its application to stochastic integer programs. Journal of the ACM.2006.53(6):978-1012
[55]D. B. Shmoys, E. Tardos, and K. I. Aardal. Approximation algorithms for facility location problems. Proceedings of the Twenty-ninth Annual A CM Symposium on Theory of Comput-ing.1997.265-274
[56]J. Shu. An efficient greedy heuristic for warehouse-retailer network design optimization. Transportation Science.2010.44(2):183-192
[57]J. Shu, C. P. Teo and Z. J. Max Shen. Stochastic transportation-inventory network design problem. Operations Research.2005.53(1):48-60
[58]M. Slikker, J. Fransoo and M. Wouters. Coopertation between multiple newsvendors with transsipments. European Journal of Operational Research,2005.167(2):370-380
[59]L. V. Snyder and M. S. Daskin. Reliability models for facility location:the expected Failure cost case. Transportation Science.2005.39(3):400-416
[60]J. F. Stollsteimer. A working model for plant numbers andlocations. Journal of Farm Eco-nomics.1963.45(3):631-645
[61]M. Sviridenko. An improved approximation algorithm for the metric uncapacitated facility location problem. Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization.2002.240-257
[62]Z. Svitkina and E. Tardos. Facility location with hierarchical facility costs. Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm.2006.153-161.
[63]C. P. Teo, J. H. Ou, and M. Goh. Impact on inventory costs with consolidation of distribution centers. HE Transactions.2001.33:99-110
[64]C. P. Teo and J. Shu. Warehouse-retailer network design problem. Operations Research. 2004:52(3):396-408
[65]M. Thorup. Quick and good facility location. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms.2003.178-185
[66]J. Vondrak. Optimal approximation for the submodular welfare problem in the value oracle model. Proceedings of the Forty Annual ACM Symposium on Theory of Computing.2008. 67-74
[67]D. Xu and D. Du. The k-level facility location game. Operations Research Letters.2006 34(4),421-426
[68]G. Xu and J. Xu. An LP rounding algorithm for approximating uncapacitated facility location problem with penalties. Information Processing Letters.2005.94(3):119-123
[69]G. Xu and J. Xu. An improved approximation algorithm for uncapacitated facility location problem with penalties. Journal of Combinatorial Optimization.2009.17(4):424-436
[70]Y. Ye and J. Zhang. An approximation algorithm for the dynamic facility location problem. Combinatorial Optimization in Communication Networks.2006.18:623-637
[71]J. Zhang. Approximating the two-level facility location problem via a quasi-greedy approach. Mathematical Programming.2006.108(1):159-176
[72]J. Zhang, B. Chen and Y. Ye. A multiexchange local search algorithm for the capacitated facility location problem. Mathematics of Operations Research.30(2):389-403