IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v150y2003i1p150-162.html
   My bibliography  Save this article

Neighborhood search heuristics for the uncapacitated facility location problem

Author

Listed:
  • Ghosh, Diptesh

Abstract

The uncapacitated facility location problem is one of choosing sites among a set of candidates in which facilities can be located, so that the demands of a given set of clients are satisfied at minimum costs. Applications of neighborhood search methods to this problem have not been reported in the literature. In this paper we first describe and compare several neighborhood structures used by local search to solve this problem. We then describe neighborhood search heuristics based on tabu search and complete local search with memory to solve large instances of the uncapacitated facility location problem. Our computational experiments show that on medium sized problem instances, both these heuristics return solutions with costs within 0.075% of the optimal with execution times that are often several orders of magnitude less than those required by exact algorithms. On large sized instances, the heuristics generate low cost solutions quite fast, and terminate with solutions whose costs are within 0.0345% of each other.
(This abstract was borrowed from another version of this item.)

Suggested Citation

  • Ghosh, Diptesh, 2003. "Neighborhood search heuristics for the uncapacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 150(1), pages 150-162, October.
  • Handle: RePEc:eee:ejores:v:150:y:2003:i:1:p:150-162
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(02)00504-0
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to look for a different version below or search for a different version of it.

    Other versions of this item:

    References listed on IDEAS

    as
    1. K.S. Al‐Sultan & M.A. Al‐Fawzan, 1999. "A tabu search approach to the uncapacitated facility location problem," Annals of Operations Research, Springer, vol. 86(0), pages 91-103, January.
    2. Labbe, M & Louveaux, F, 1997. "Annotated Bibliography on Location Problems," Papers 183, Notre-Dame de la Paix, Sciences Economiques et Sociales.
    3. Tuzun, Dilek & Burke, Laura I., 1999. "A two-phase tabu search approach to the location routing problem," European Journal of Operational Research, Elsevier, vol. 116(1), pages 87-99, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Resende, Mauricio G.C. & Werneck, Renato F., 2006. "A hybrid multistart heuristic for the uncapacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 174(1), pages 54-68, October.
    2. Aras, Necati & Aksen, Deniz, 2008. "Locating collection centers for distance- and incentive-dependent returns," International Journal of Production Economics, Elsevier, vol. 111(2), pages 316-333, February.
    3. repec:eee:ejores:v:269:y:2018:i:3:p:824-833 is not listed on IDEAS
    4. Marta Sofia R. Monteiro & Dalila B. M. M. Fontes & Fernando A. C. C. Fontes, 2009. "Restructuring Facility Networks under Economy of Scales," FEP Working Papers 324, Universidade do Porto, Faculdade de Economia do Porto.
    5. Minghe Sun & Zhen-Yu Chen & Zhi-Ping Fan, 2014. "A Multi-task Multi-kernel Transfer Learning Method for Customer Response Modeling in Social Media," Working Papers 0161mss, College of Business, University of Texas at San Antonio.
    6. Fathali Firoozi, 2008. "Boundary Distributions in Testing Inequality Hypotheses," Working Papers 0046, College of Business, University of Texas at San Antonio.
    7. Mina Husseinzadeh Kashan & Ali Husseinzadeh Kashan & Nasim Nahavandi, 2013. "A novel differential evolution algorithm for binary optimization," Computational Optimization and Applications, Springer, vol. 55(2), pages 481-513, June.
    8. Kurt Jörnsten & Andreas Klose, 2016. "An improved Lagrangian relaxation and dual ascent approach to facility location problems," Computational Management Science, Springer, vol. 13(3), pages 317-348, July.
    9. Melo, M.T. & Nickel, S. & Saldanha-da-Gama, F., 2012. "A tabu search heuristic for redesigning a multi-echelon supply chain network over a planning horizon," International Journal of Production Economics, Elsevier, vol. 136(1), pages 218-230.
    10. Robert Aboolian & Tingting Cui & Zuo-Jun Max Shen, 2013. "An Efficient Approach for Solving Reliable Facility Location Models," INFORMS Journal on Computing, INFORMS, vol. 25(4), pages 720-729, November.
    11. Letchford, Adam N. & Miller, Sebastian J., 2014. "An aggressive reduction scheme for the simple plant location problem," European Journal of Operational Research, Elsevier, vol. 234(3), pages 674-682.
    12. Pierre Hansen & Jack Brimberg & Dragan Urošević & Nenad Mladenović, 2007. "Primal-Dual Variable Neighborhood Search for the Simple Plant-Location Problem," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 552-564, November.
    13. repec:pal:jorsoc:v:68:y:2017:i:10:d:10.1057_s41274-016-0155-6 is not listed on IDEAS
    14. repec:pal:jorsoc:v:59:y:2008:i:3:d:10.1057_palgrave.jors.2602349 is not listed on IDEAS
    15. Arostegui, Marvin Jr. & Kadipasaoglu, Sukran N. & Khumawala, Basheer M., 2006. "An empirical comparison of Tabu Search, Simulated Annealing, and Genetic Algorithms for facilities location problems," International Journal of Production Economics, Elsevier, vol. 103(2), pages 742-754, October.
    16. Jaroslav Janáček & Ľuboš Buzna, 2008. "An acceleration of Erlenkotter-Körkel’s algorithms for the uncapacitated facility location problem," Annals of Operations Research, Springer, vol. 164(1), pages 97-109, November.
    17. Dohn, Anders & Christensen, Soren Gram & Rousoe, David Magid, 2007. "The p/q-active uncapacitated facility location problem: Investigation of the solution space and an LP-fitting heuristic," European Journal of Operational Research, Elsevier, vol. 180(2), pages 532-546, July.
    18. Dupont, Lionel, 2008. "Branch and bound algorithm for a facility location problem with concave site dependent costs," International Journal of Production Economics, Elsevier, vol. 112(1), pages 245-254, March.
    19. Jesús Muñuzuri & Pablo Cortés & Rafael Grosso & Luis Onieva, 2016. "Teaching Heuristic Methods to Industrial Engineers: A Problem-Based Experience," INFORMS Transactions on Education, INFORMS, vol. 16(2), pages 60-67, January.
    20. van der Gaast, J.P. & Rietveld, C.A. & Gabor, A.F. & Zhang, Y., 2011. "A Local Search Algorithm for Clustering in Software as a Service Networks," ERIM Report Series Research in Management ERS-2011-004-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    21. C. Beltran-Royo & J.-P. Vial & A. Alonso-Ayuso, 2012. "Semi-Lagrangian relaxation applied to the uncapacitated facility location problem," Computational Optimization and Applications, Springer, vol. 51(1), pages 387-409, January.
    22. Cordeau, Jean-François & Laporte, Gilbert & Pasin, Federico, 2008. "An iterated local search heuristic for the logistics network design problem with single assignment," International Journal of Production Economics, Elsevier, vol. 113(2), pages 626-640, June.
    23. Minghe Sun, 2008. "A Tabu Search Heuristic Procedure for the Capacitated Facility Location Problem," Working Papers 0050, College of Business, University of Texas at San Antonio.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:150:y:2003:i:1:p:150-162. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu). General contact details of provider: http://www.elsevier.com/locate/eor .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.