×

Lower and upper bounds for a two-stage capacitated facility location problem with handling costs. (English) Zbl 1304.90124

Summary: We study in this paper multi-product facility location problem in a two-stage supply chain in which plants have production limitation, potential depots have limited storage capacity and customer demands must be satisfied by plants via depots. In the paper, handling cost for batch process in depots is considered in a realistic way by a set of capacitated handling modules. Each module can be regards as alliance of equipment and manpower. The problem is to locate depots, choose appropriate handling modules and to determine the product flows from the plants, opened depots to customers with the objective to minimize total location, handling and transportation costs. For the problem, we developed a hybrid method. The initial lower and upper bounds are provided by applying a Lagrangean based on local search heuristic. Then a weighted Dantzig-Wolfe decomposition and path-relinking combined method are proposed to improve obtained bounds. Numerical experiments on 350 randomly generated instances demonstrate our method can provide high quality solution with gaps below 2%.

MSC:

90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming

Software:

CPLEX; Tabu search
Full Text: DOI

References:

[1] Ahuja, R. K.; Orlin, J. B.; Pallottino, S.; Scaparra, M. P.; Scutellà, M. G., A multi-exchange heuristic for the single-source capacitated facility location problem, Management Science, 50, 6, 749-760 (2004) · Zbl 1232.90257
[2] Brandeau, M. L.; Chiu, S. S., An overview of representative problems in location research, Management Science, 35, 6, 645-674 (1989) · Zbl 0669.90040
[3] Contreras, I. A.; Díaz, J. A., Scatter search for the single source capacitated facility location problem, Annals of Operations Research, 157, 1, 73-89 (2008) · Zbl 1153.90481
[4] Cornuejols, G.; Sridharan, R.; Thizy, J. M., A comparison of heuristics and relaxations for the capacitated plant location problem, European Journal of Operational Research, 50, 3, 280-297 (1991) · Zbl 0734.90046
[5] Crainic, T. G.; Gendron, B.; Hernu, G., A slope scaling/Lagrangean perturbation heuristic with long-term memory for multicommodity capacitated fixed-charge network design, Journal of Heuristics, 10, 5, 525-545 (2004) · Zbl 1062.90009
[6] Dias, J.; Captivo, M. E.; Clímaco, J., Efficient primal-dual heuristic for a dynamic location problem, Computers and Operations Research, 34, 6, 1800-1823 (2007) · Zbl 1159.90439
[7] Elhedhli, S.; Gzara, F., Integrated design of supply chain networks with three echelons, multiple commodities and technology selection, IIE Transactions, 40, 1, 31-44 (2008)
[8] Gendron, B.; Potvin, J. Y.; Soriano, P., A tabu search with slope scaling for the multicommodity capacitated location problem with balancing requirements, Annals of Operations Research, 122, 1-4, 193-217 (2003) · Zbl 1039.90026
[9] Glover, F.; Laguna, M., Tabu search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers London · Zbl 0930.90083
[11] Jayaraman, V.; Pirkul, H., Planning and coordination of production and distribution facilities for multiple commodities, European Journal of Operational Research, 133, 2, 394-408 (2001) · Zbl 1001.90026
[12] Keskin, B. B.; Üster, H., A scatter search-based heuristic to locate capacitated transshipment points, Computers and Operations Research, 34, 10, 3112-3125 (2007) · Zbl 1185.90134
[13] Keskin, B. B.; Üster, H., Meta-heuristic approaches with memory and evolution for a multi-product production/distribution system design problem, European Journal of Operational Research, 182, 2, 663-682 (2007) · Zbl 1121.90022
[14] Kim, D.; Pardalos, P. M., Dynamic slope scaling and trust interval techniques for solving concave piecewise linear network flow problems, Networks, 35, 3, 216-222 (2000) · Zbl 0963.90011
[15] Klose, A., An LP-based heuristic for two-stage capacitated facility location problems, Journal of the Operational Research Society, 50, 2, 157-166 (1999) · Zbl 1054.90590
[16] Klose, A., A Lagrangean relax-and-cut approach for the two-stage capacitated facility location problem, European Journal of Operational Research, 126, 2, 185-198 (2000)
[17] Klose, A.; Görtz, S., A branch-and-price algorithm for the capacitated facility location problem, European Journal of Operational Research, 179, 3, 1109-1125 (2007) · Zbl 1163.90607
[18] Li, J.; Chu, F.; Prins, C., Lower and upper bounds for a capacitated plant location problem with multicommodity flow, Computers and Operations Research, 36, 11, 3019-3030 (2009) · Zbl 1162.90495
[19] Lin, C. K.Y., Stochastic single-source capacitated facility location model with service level requirements, International Journal of Production Economics, 117, 2, 439-451 (2009)
[20] Li, J.; Ren, C.; Dong, J.; He, M.; Wang, Q.; Chen, F., A Lagrangean-based heuristic for a two-stage facility location problem with handling costs, Service Operations, Logistics, and Informatics (SOLI), 319-324 (2011)
[21] Martí, R.; Pelegrín, B., Applying Lagrangian relaxation to the resolution of two-stage location problems, Annals of Operations Research, 86, 0, 179-198 (1999) · Zbl 0921.90104
[22] Melo, M. T.; Nickel, S.; Saldanha da Gama, F., Dynamic multi-commodity capacitated facility location: A mathematical modeling framework for strategic supply chain planning, Computers and Operations Research, 33, 1, 181-208 (2006) · Zbl 1077.90006
[23] Newton, H. N.; Barnhart, C.; Vance, P. H., Constructing railroad blocking plans to minimize handling costs, Transportation Science, 32, 4, 330-345 (1998) · Zbl 0987.90510
[24] Pirkul, H.; Jayaraman, V., Production, transportation and distribution planning in a multi-commodity tri-echelon system, Transportation Science, 30, 4, 291-302 (1996) · Zbl 0879.90129
[25] Pirkul, H.; Jayaraman, V., A multi-commodity, multi-plant, capacitated facility location problem: Formulation and efficient heuristic solution, Computers and Operations Research, 25, 10, 869-878 (1998) · Zbl 1042.90580
[26] Şahin, G.; Süral, H., A review of hierarchical facility location models, Computers and Operations Research, 34, 8, 2310-2331 (2007) · Zbl 1144.90440
[27] Tragantalerngsak, S.; Holt, J.; Rönnqvist, M., Lagrangian heuristics for the two-echelon, single-source, capacitated facility location problem, European Journal of Operational Research, 102, 3, 611-625 (1997) · Zbl 0951.90561
[28] Wang, Q.; Batta, R.; Rump, C. M., Algorithms for a facility location problem with stochastic customer demand and immobile servers, Annals of Operations Research, 111, 1-4, 17-34 (2002) · Zbl 1013.90023
[29] Wentges, P., Weighted Dantzig-Wolfe decomposition for linear mixed-integer programming, International Transactions in Operational Research, 4, 2, 151-162 (1997) · Zbl 0886.90107
[30] Zhu, Z.; Chu, F.; Sun, L., The capacitated plant location problem with customers and suppliers matching, Transportation Research Part E, 46, 3, 469-480 (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.