nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

3. Fixed-Charge Facility Location Problems

verfasst von : Elena Fernández, Mercedes Landete

Erschienen in: Location Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Fixed-Charge Facility Location Problems are among core problems in Location Science. There is a finite set of users with demand of service and a finite set of potential locations for the facilities that will offer service to users. Two types of decisions must be made: Location decisions determine where to establish the facilities whereas allocation decisions dictate how to satisfy the users demand from the established facilities. Potential applications of various types arise in many different contexts. We provide an overview of the main elements that may intervene in the modeling and the solution process of Fixed-Charge Facility Location Problems, namely, modeling hypotheses and their implications, characteristics of formulations and their relation to other formulations, properties of the domains, and appropriate solution techniques.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel The p-Median Problem

Nächstes Kapitel p-Center Problems

Aardal K (1998) Reformulation of capacitated facility location problems: how redundant information can help. Ann Oper Res 82:289–308

Ahuja RK, Orlin JB, Pallottino S, Scaparra MP, Scutellà MG (2004) A multi-exchange heuristic for the single-source capacitated facility location problem. Manag Sci 50:749–760

Akinc U, Khumawala BM (1977) An efficient branch and bound algorithm for the capacitated warehouse location problem. Manag Sci 23:585–594

Albareda-Sambola, M, Fernández E, Hinojosa Y, Puerto J (2009a) The multi-period sequential coverage facility location problem. Comput Oper Res 36:1356–1375

Albareda-Sambola M, Fernández E, Laporte G (2009b) The capacity and distance constrained plant location problem. Comput Oper Res 36(2): 597–611

Albareda-Sambola M, Fernández E, Hinojosa Y, Puerto J (2010) The single period coverage facility location problem: lagrangean heuristic and column generation approaches. TOP 18:43–61

Albareda-Sambola M, Fernández E, Saldanha da Gama F (2011) The facility location problem with Bernoulli demands. Omega 39:335–345

Albareda-Sambola M, Fernández E, Nickel S (2012) Multiperiod location-routing with decoupled time scales. Eur J Oper Res 217:248–258

Albareda-Sambola M, Alonso-Ayuso A, Escudero LF, Fernández E, Pizarro C (2013) Fix-and-relax-coordination for a multi-period location-allocation problem under uncertainty. Comput Oper Res 40:2878–2892

Babayev DA (1974) Comments on a note of Frieze. Math Program 7:249–252

Baïou M, Barahona F (2009a) On the integrality of some facility location polytopes. SIAM J Discret Math 23:665–679

Baïou M, Barahona F (2009b) A polyhedral study of a two-level facility model. IBM Research Report RC24886 (W0910–176) October 28

Balcik B, Beamon M (2008) Facility location in humanitarian relief. Int J Logist Res Appl Leading J Supply Chain Manag 11:101–121

Balinski M (1966) On finding integer solutions to linear programs. In: Proceedings of IBM scientific symposium on combinatorial problems, IBM Data processing division, White Plains, New York

Barahona F, Chudak FA (2005) Near-optimal solutions to large-scale facility location problems. Discret Optim 2:35–50

Barceló J, Casanovas (1984) A heuristic algorithm for the capacitated plant location problem. Eur J Oper Res 15:212–226

Barceló J, Hallefjord Å, Fernández E, Jörnsten K (1990) Lagrangean relaxation and constraint generation procedures for capacitated plant location problems. OR Spektrum 12:79–88

Barceló J, Fernández, E, Jörnsten K (1991) Computational results from a new lagrangean relaxation algorithm for the capacitated plant location problem. Eur J Oper Res 53:38–45

Beasley JE (1988) An algorithm for solving large capacitated warehouse location problems. Eur J Oper Res 33:314–325

Beasley JE (1993) Lagrangean heuristics for location problems. Eur J Oper Res 65:383–399

Beltran-Royo C, Vial J-P, Alonso-Ayuso A (2012) Semi-lagrangian relaxation applied to the uncapacitated facility location problem. Comput Optim Appl 51:387–409

Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4:238–252

Bilde O, Krarup J (1977) Sharp lower bounds and efficient algorithms for the simple plant location problem. Ann Discret Math 1:79–97

Boland N, Domínguez-Marín P, Nickel S, Puerto J (2006) Exact procedures for solving the discrete ordered median problem. Comput Oper Res 33:3270–3300

Cánovas L, Landete M, Marín A (2000) New facets for the set packing polytope. Oper Res Lett 27:153–161

Cánovas L, Landete M, Marín A (2001) Extreme points of discrete location polyhedra. TOP 9:115–138

Cánovas L, Landete M, Marín A (2002) On the facets of the simple plant location problem. Discret Appl Math 124:27–53

Cánovas L, Landete M, Marín A (2003) Facet obtaining procedures for set packing problems. SIAM J Discret Math 16:127–155

Chen X, Chen Z, Zang W (2012) Total dual integrality in some facility location problems. SIAM J Discret Math 26:1022–1030

Cho DC, Johnson EL, Padberg MW, Rao MR (1983a) On the uncapacitated plant location problem I: valid inequalities and facets. Math Oper Res 8:579–589

Cho DC, Padberg MW, Rao MR (1983b) On the uncapacitated plant location problem II: facets and lifting theorems. Math Oper Res 8:590–612

Christofides N, Beasley JE (1983) Extensions to a lagrangean relaxation approach for the capacitated warehouse location problem. Eur J Oper Res 12:19–28

Chudak FA, Shmoys DB (1999) Improved approximation algorithms for a capacitated facility location problem. In: Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms, pp 875–886

Contreras I, Fernández E (2014) Hub location as the minimization of a supermodular set function. Oper Res 62:557–570

Contreras I, Fernández E, Reinelt G (2012) The center facility location/network design problem with budget constraint. Omega 40:847–860

Cornuéjols GP, Thizy JM (1982) Some facets of the simple plant location polytope. Math Program 23:50–74

Cornuéjols GP, Fisher M, Nemhauser GL (1977) On the uncapacitated location problem. Ann Discret Math 1:163–177

Cornuéjols GP, Nemhauser GL, Wolsey LA (1990) The uncapacitated facility location problem. In: Mirchandani PB, Francis RL (eds) Discrete location theory. Wiley-Interscience, New York

Cornuéjols GP, Sridharan R, Thizy JM (1991) A comparison of heuristics and relaxations for the capacitated plant location problem. Eur J Oper Res 50:280–297

Correia I, Gouveia LE, Saldanha da Gama F (2010) Discretized formulations for capacitated location problems with modular distribution costs. Eur J Oper Res 204:237–244

Cortinhal MJ, Captivo ME (2003) Genetic algorithms for the single source capacitated plant location problem. In: Resende MGC, Pinho de Sousa J, Viana A (eds) Metaheuristics: computer decision-making. Kluwer Academic Publishers, Boston, pp 187–216

Daskin MS, Coullard CR, Shen ZM (2002) An inventory-location model: formulation, solution algorithm and computational results. Ann Oper Res 110:83–106

Davis PS, Ray TL (1969) Branch and bound algorithm for the capacitated facilities location problem. Nav Res Logist Q 16:331–343

Delmaire H, Díaz JA, Fernández E, Ortega M (1999b) Comparing new heuristics for the pure integer capacitated plant location problem. Investig Oper 8:217–242

Delmaire H, Díaz JA, Fernández E, Ortega M (1999a) Reactive GRASP and tabu search based heuristics for the single source capacitated plant location problem. Inform Syst Oper Res (INFOR) 37:194–225

Díaz JA, Fernández E (2002) A branch and price algorithm for the single source capacitated plant location problem. J Oper Res Soc 53:728–748

Drezner Z, Hamacher HW (eds) (2002) Facility location: applications and theory. Springer, New York

Efroymson MA, Ray TL (1966) A branch and bound algorithm for plant location. Oper Res 14:361–368

Elloumi S, Labbé M, Pochet Y (2004) A new formulation and resolution method for the p-center problem. INFORMS J Comput 16:84–94

Ellwein LB, Gray P (1971) Solving fixed charge location-allocation problems with capacity and configuration constraints. AIIE T 3:290–299

Erkenkotter D (1978) A dual-based procedure for uncapacitated facility location. Oper Res 26:992–1009

Escudero LF, Landete M, Marín A (2009) A branch-and-cut algorithm for the winner determination problem. Decis Support Syst 46:649–659

Fernández E, Puerto J (2003) Multiobjective solution of the uncapacitated plant location problem. Eur J Oper Res 145:509–529

Filho VJMF, Galvão RD (1998) A tabu search heuristic for the concentrator location problem. Locat Sci 6:189–209

Fisher ML, Nemhauser GL, Wolsey LA (1978) An analysis of approximations for maximizing submodular set functions -II. Math Program Stud 8:73–87

Fisher ML, Jaikumar R, Van Wassenhove LN (1986) A multiplier adjustment method for the generalized assignment problem. Manag Sci 32:1095–1103

Frieze AM (1974) A cost function property for plant location problems. Math Program 7:245–248

Gao Y (2012) Uncertain models for single facility location problems on networks. Appl Math Model 36:2592–2599

Garey MR, Johnson DS (1979) Computers and intractabiliy: a guide to the theory of NP-completeness. Freeman, San Francisco

Gendron B, Semet F (2009) Formulations and relaxations for a multi-echelon capacitated location-distribution problem. Comput Oper Res 36:1335–1355

Geoffrion AM, McBride R (1978) Lagrangean relaxation applied to capacitated facility location problems. AIIE T 10:40–47

Ghiani G, Guerriero F, Musmanno R (2002) The capacitated plant location problem with multiple facilities in the same site. Comput Oper Res 29:1903–1912

Ghiani G, Laganà, Manni E, Triki C (2012) Capacitated location of collection sites in an urban waste management system. Waste Manag 32:1291–1296

Goldengorin B, Ghosh D, Sierksma G (2004) Branch and peg algorithms for the simple plant location problem. Comput Oper Res 31:241–255

Gourdin É, Klopfenstein O (2008) Multi-period capacitated location with modular equipments. Comput Oper Res 35:661–682

Gouveia LE, Saldanha da Gama F (2006) On the capacitated concentrator location problem: a reformulation by discretization. Comput Oper Res 33:1242–1258

Guignard M (1980) Fractional vertices, cuts and facets of the simple plant location problem. Math Program Stud 12:150–162

Guignard, M (1988) A Lagrangean dual ascent algorithm for simple plant location problems. Eur J Oper Res 35:193–200

Guignard M, Kim S (1983) A strong Lagrangean relaxation for capacitated plant location problems. Working Paper 56, Decision Sciences Department, The Wharton School, University of Pennsylvania

Guignard M, Opaswongkarn K (1990) Lagrangean dual ascent algorithms for computing bounds in capacitated location problems. Eur J Oper Res 46:73–83

Guignard M, Spielberg K (1977) Algorithms for exploiting the structure of the simple plant location problem. Ann Discret Math 1:247–271

Hamacher HW, Labbé M, Nickel S, Sonneborn T (2004) Adapting polyhedral properties from facility to hub location problems. Discret Appl Math 145:104–116

Hindi KS, Pieńkosz K (1999) Efficient solution of large scale, single-source, capacitated plant location problem. J Oper Res Soc 50:268–274

Holmberg K, Rönnqvist M, Yuan D (1999) An exact algorithm for the capacitated facility location problems with single sourcing. Eur J Oper Res 113:554–559

Jacobsen SK (1983) Heuristics for the capacitated plant location model. Eur J Oper Res 12:253–261

Janacek J, Buzna L (2008) An acceleration of Erlenkotter-Körkel’s algorithms for the uncapacitated facility location problem. Ann Oper Res 164:97–109

Jiaa H, Ordoñez F, Dessouky M (2007) A modeling framework for facility location of medical services for large-scale emergencies. IIE T 39:41–55

Khumawala BM (1972) An efficient branch and bound algorithm for the warehouse location problem. Manag Sci 18:718–731

Klincewicz JG, Luss H (1986) A Lagrangean relaxation heuristic for the capacitated facility location with single-source constraints. J Oper Res Soc 37:495–500

Klose A, Drexl A (2005) Facility location models for distribution system design. Eur J Oper Res 162:4–29

Klose A, Görtz S (2007) A branch-and-price algorithm for the capacitated facility location problem. Eur J Oper Res 179:1109–1125

Körkel M (1989) On the exact solution of large-scale simple plant location problems. Eur J Oper Res 39:157–173

Krarup J, Pruzan PM (1983) The simple plant location problem: survey and synthesis. Eur J Oper Res 12:36–81

Kuehn AA, Hamburger MJ (1963) A heuristic program for locating warehouses. Manag Sci 9:645–666

Labbé M, Peeters D, Thisse JF (1995) Location on networks. In: Ball MO, Magnanti TL, Monma CL, Nemhauser GL (eds) Network routing, handbooks in operations research and management science, vol 8. North-Holland, Amsterdam, pp 551–624

Letchford AN, Miller SJ (2012) Fast bounding procedures for large instances of the simple plant location problem. Comput Oper Res 39:985–990

Letchford AN, Miller SJ (2014) An aggressive reduction scheme for the simple plant location problem. Eur J Oper Res 234:674–682

Leung J, Magnanti TL (1989) Valid inequalities and facets of the capacitated plant location problem. Math Program 44:271–291

Lin CKY (2009) Stochastic single-source capacitated facility location model with service level requirements. Int J Prod Econ 117:439–451

Louveaux FV, Peeters D (1992) A dual-based procedure for stochastic facility location. Oper Res 40:564–573

Magnanti TL, Wong RT (1990) Decomposition methods for facility location problems. In: Mirchandani PB, Francis RL (eds) Discrete location theory. Wiley-Interscience, New York

Manne AS (1964) Plant location under economies-of-scale – decentralization and computations. Manag Sci 11:213–235

Marín A (2011) The discrete facility location problem with balanced allocation of customers. Eur J Oper Res 210:27–38

Melkote S, Daskin MS (2001) Capacitated facility location/network design problems. Eur J Oper Res 129:481–495

Melo T, Nickel S, Saldanha da Gama F (2009) Facility location and supply chain management: a review. Eur J Oper Res 196:401–412

Mladenović N, Brimberg J, Hansen P (2006) A note on duality gap in the simple plant location problem. Eur J Oper Res 174:11–22

Myung YS, Tcha DW (1996) Feasible region reduction cuts for the simple plant location problem. J Oper Res Soc Jpn 39:614–622

Nagy G, Salhi S (2007) Location-routing: issues, models and methods. Eur J Oper Res 177:649–672

Nauss RM (1978) An improved algorithm for the capacitated facility location problem. J Oper Res Soc 29:1195–1201

Neebe AW, Rao MR (1983) An algorithm for the fixed-charge assigning users to sources problem. J Oper Res Soc 34:1107–1113

Nemhauser GL, Wolsey LA (1981) Maximizing submodular functions: formulations and analysis of algorithms. Ann Discret Math 11:279–301

Nemhauser GL, Wolsey LA (1988) Integer and combinatorial optimization. Wiley, New York

Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions I. Math Program 14:265–294

Owen SH, Daskin MS (1998) Strategic facility location: a review. Eur J Oper Res 111:423–447

Pirkul H (1987) Efficient algorithms for the capacitated concentrator location problems. Comput Oper Res 14:197–208

ReVelle CS, Laporte G (1996) The plant location problem: new models and research prospects. Oper Res 44:864–874

Sá G (1969) Branch and bound and approximate solutions to the capacitated plant-location problem. Oper Res 17:1005–1016

Sankaran JK (2007) On solving large instances of the capacitated facility location problem. Eur J Oper Res 178:663–676

Sharma RRK, Berry V (2007) Developing new formulations and relaxations of single stage capacitated warehouse location problem (SSCWLP): empirical investigation for assessing relative strengths and computational effort. Eur J Oper Res 177:803–812

Shetty B (1990) Approximate solutions to large scale capacitated facility location problems. Appl Math Comput 39:159–175

Shmoys DB, Tardos E, Aardal K (1997) Approximation algorithms for facility location problems. In: Proceedings of the 29th annual ACM symposium on theory of computing (STOC). ACM Press, New York, pp 265–274

Singh KN (2008) The uncapacitated facility location problem: some applications in scheduling and routing. Int J Oper Res 5:36–43

Spielberg K (1969a) Plant location with generalized search origin. Manag Sci 16:165–178

Spielberg K (1969b) Algorithms for the simple plant location problem with some side conditions. Oper Res 17:85–111

Sridharan R (1993) A lagrangian heuristic for the capacitated plant location problem with single source constraints. Eur J Oper Res 66:305–312

Sridharan R (1995) The capacitated plant location problem. Eur J Oper Res 87:203–213

Stollsteimer JF (1963) A working model for plant numbers and locations. J Farm Econ 45:631–645

Van Roy TJ (1986) A cross decomposition algorithm for capacitated facility location. Oper Res 34:145–163

Verter V (2011) Uncapacitated and capacitated facility location problems. In: Eiselt HA, Marianov V (eds) Principles of location science. Springer, New York, pp 25–37

Wentges P (1996) Accelerating Benders decomposition for the capacitated facility location problem. Math Method Oper Res 44:267–290

Wu LY, Zhang XS, Zhang JL (2006) Capacitated facility location problem with general setup cost. Comput Oper Res 33:1226–1241

Zanjirani Farahani R, SteadieSeifi M, Asgari N (2010) Multiple criteria facility location problems: a survey. Appl Math Model 34:1689–1709

Zhen Y, Chu F, Chen H (2012) A cut-and-solve based algorithm for the single-source capacitated facility location problem. Eur J Oper Res 221:521–532

Titel: Fixed-Charge Facility Location Problems
verfasst von: Elena Fernández
Mercedes Landete
Verlag: Springer International Publishing
Buch: Location Science
Print ISBN: 978-3-319-13110-8

Electronic ISBN: 978-3-319-13111-5

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-13111-5_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner