Skip to main content

Advertisement

SpringerLink
Log in

GASUB: finding global optima to discrete location problems by a genetic-like algorithm

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

In many discrete location problems, a given number s of facility locations must be selected from a set of m potential locations, so as to optimize a predetermined fitness function. Most of such problems can be formulated as integer linear optimization problems, but the standard optimizers only are able to find one global optimum. We propose a new genetic-like algorithm, GASUB, which is able to find a predetermined number of global optima, if they exist, for a variety of discrete location problems. In this paper, a performance evaluation of GASUB in terms of its effectiveness (for finding optimal solutions) and efficiency (computational cost) is carried out. GASUB is also compared to MSH, a multi-start substitution method widely used for location problems. Computational experiments with three types of discrete location problems show that GASUB obtains better solutions than MSH. Furthermore, the proposed algorithm finds global optima in all tested problems, which is shown by solving those problems by Xpress-MP, an integer linear programing optimizer (21). Results from testing GASUB with a set of known test problems are also provided.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Francis R.L., Lowe T.J., Tamir A. (2002) Demand point aggregation for location models. In: Drezner Z., Hamacher H. (eds) Facility Location: Application and Theory. Springer, Berlin, pp. 207–232

    Google Scholar 

  2. Eiselt H.A., Laporte G., Thisse J.F. (1993) Competitive location models: a framework and bibliography. Transport. Sci. 27, 44–54

    Google Scholar 

  3. Hamacher H.W., Nickel S. (1998) Classification of location models. Location Sci. 13, 229–242

    Article  Google Scholar 

  4. ReVelle C.S., Eiselt H.A. (2005) Location analysis: a synthesis and survey. EJOR 165(1):1–19

    Article  Google Scholar 

  5. Daskin M.S. (1995) Network and Discrete location: Models, Algorithms and Applications. Wiley, New York

    Google Scholar 

  6. Mirchandani P.B. (1990) The p-median problem and generalizations. In: Mirchandani P.B. Francis R.L. (eds) Discrete Location Theory. Wiley-Interscience, New York, pp. 55–117

    Google Scholar 

  7. Serra D., ReVelle C. (1995) Competitive location in discrete space. In: Drezner Z. (eds) Facility Location: A Survey of Applications and Methods. Springer, Berlin, pp. 367–386

    Google Scholar 

  8. García M.D., Fernández P., Pelegrín B. (2004) On price competition in location-price models with spatially separated markets. TOP 12(2):351–374

    Article  Google Scholar 

  9. Lederer P.J., Hurter A.P. (1986) Competition of firms: discriminatory pricing and location. Econometrica, 54(3):623–640

    Article  Google Scholar 

  10. Lederer P.J., Thisse J.F. (1990) Competitive location on networks under delivered pricing. Opera. Res. Lett. 9(91):147–153

    Article  Google Scholar 

  11. Dorta-González P., Santos-Peñate D.R., Suárez Vega R. (2005) Spatial competition in networks with discriminatory pricing. Pap. Regi. Sci. 84(2):271–280

    Article  Google Scholar 

  12. Fernández, P., Pelegrín, B., García, M.D., Peeters, P.: A discrete long-term location-price problem under the assumption of discriminatory pricing: Formulations and parametric analysis. Eur. J. Opera. Rese. 2006. DOI 10.1016/j.ejor.2005.03.075

  13. Berman O., Krass D. (2002) Locating multiple competitive facilities: spatial interaction models with variable expenditures. Ann. Oper. Res. 11, 197–225

    Article  Google Scholar 

  14. Suárez-Vega R., Santos-Peñate D.R., Dorta-González P. (2004) Discretization and resolution of the (r | X p )-medianoid problem involving quality criteria. TOP 12, 111–134

    Article  Google Scholar 

  15. Ortigosa P.M., García I., Jelasity M. (2001) Reliability and performance of UEGO, a clustering-based global optimizer. Jo. Global Optim. 19(3):265–289

    Article  Google Scholar 

  16. Cornuejols G., Fisher M.L., Nemhauser G.L. (1997) Locations of bank accounts to optimize float: an analytical study of exact and approximate algorithms. Manage. Sci. 23, 789–810

    Article  Google Scholar 

  17. Hakimi S.L. (1983) On locating new facilities in a competitive environment. Eur. J. Oper. Res. 12, 29–35

    Article  Google Scholar 

  18. Colomé R., Serra D. (2001) Consumer choice and optimal location models : Formulations and heuristics. Pap. Reg. Sci. 80, 439–464

    Article  Google Scholar 

  19. Moreno J.A., Roda García J.L., Marcos J.M., Moreno-Vega M. (1994) A parallel genetic algorithm for the discrete p-median problem. Studies Location. Analy. 7, 131–141

    Google Scholar 

  20. Rosing K.E., Revelle C. (1997) Heuristic concentration: two stage solution construction. Eur. J. Oper. Res. 97, 75–86

    Article  Google Scholar 

  21. Xpress-MP. Dash optimization, 2004

  22. Pelegrín, B., Fernández, P., Redondo, J.L., García, I., Ortigosa, P.M.: Solving a competitive facility location problem by stochastic algorithms. In: Proceedings of the Tenth International Symposium on Locational Decisions, ISOLDE X, pp 217–218. Sevilla, Spain (2005)

  23. Alp O., Drezner Z., Erkut E. (2003) An efficient genetic algorithm for the p-median problem. Ann. Oper. Res. 122(1):21–42

    Article  Google Scholar 

  24. Beasley J.E. (1990) Or-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11):1069–1072

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Statistics and Operational Research, University of Murcia, Murcia, Spain

    Blas Pelegrín & Pascual Fernández

  2. Department of Computer Architecture and Electronics, University of Almería, Almeria, Spain

    Juani L. Redondo, Inmaculada García & Pilar M. Ortigosa

Authors
  1. Blas Pelegrín
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Juani L. Redondo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pascual Fernández
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Inmaculada García
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Pilar M. Ortigosa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Blas Pelegrín.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pelegrín, B., Redondo, J.L., Fernández, P. et al. GASUB: finding global optima to discrete location problems by a genetic-like algorithm. J Glob Optim 38, 249–264 (2007). https://doi.org/10.1007/s10898-006-9076-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-006-9076-2

Keywords

Search

Navigation