IDEAS home Printed from https://ideas.repec.org/a/spr/cejnor/v19y2011i2p191-200.html
   My bibliography  Save this article

Online facility location with facility movements

Author

Listed:
  • Gabriella Divéki
  • Csanád Imreh

Abstract

In the online facility location problem demand points arrive one at a time and the goal is to decide where and when to open a facility. In this paper we consider a new version of the online facility location problem, where the algorithm is allowed to move the opened facilities in the metric space. We consider the uniform case where each facility has the same constant cost. We present an algorithm which is 2-competitive for the general case and we prove that it is 3/2-competitive if the metric space is the line. We also prove that no algorithm with smaller competitive ratio than $${(\sqrt{13}+1)/4\approx 1.1514}$$ exists. We also present an empirical analysis which shows that the algorithm gives very good results in the average case. Copyright Springer-Verlag 2011

Suggested Citation

  • Gabriella Divéki & Csanád Imreh, 2011. "Online facility location with facility movements," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 19(2), pages 191-200, June.
    • Handle: RePEc:spr:cejnor:v:19:y:2011:i:2:p:191-200
    DOI: 10.1007/s10100-010-0153-8
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10100-010-0153-8
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10100-010-0153-8?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

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

    References listed on IDEAS

    as
    1. Donald Erlenkotter, 1978. "A Dual-Based Procedure for Uncapacitated Facility Location," Operations Research, INFORMS, vol. 26(6), pages 992-1009, December.
    2. Christofides, N. & Beasley, J. E., 1982. "A tree search algorithm for the p-median problem," European Journal of Operational Research, Elsevier, vol. 10(2), pages 196-204, June.
    3. R. S. Garfinkel & A. W. Neebe & M. R. Rao, 1974. "An Algorithm for the M-Median Plant Location Problem," Transportation Science, INFORMS, vol. 8(3), pages 217-236, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Goldengorin, Boris, 2001. "Solving the simple plant location problem using a data correcting approach," Research Report 01A53, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    2. 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.
    3. Drexl, Andreas & Klose, Andreas, 2001. "Facility location models for distribution system design," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 546, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    4. Klose, Andreas & Drexl, Andreas, 2005. "Facility location models for distribution system design," European Journal of Operational Research, Elsevier, vol. 162(1), pages 4-29, April.
    5. Cruz, F. R. B. & Smith, J. MacGregor & Mateus, G. R., 1999. "Algorithms for a multi-level network optimization problem," European Journal of Operational Research, Elsevier, vol. 118(1), pages 164-180, October.
    6. Goldengorin, Boris & Ghosh, Diptesh & Sierksma, Gerard, 2001. "Branch and peg algorithms for the simple plant location problem," Research Report 01A14, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    7. Canovas, Lazaro & Garcia, Sergio & Marin, Alfredo, 2007. "Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique," European Journal of Operational Research, Elsevier, vol. 179(3), pages 990-1007, June.
    8. Abareshi, Maryam & Zaferanieh, Mehdi, 2019. "A bi-level capacitated P-median facility location problem with the most likely allocation solution," Transportation Research Part B: Methodological, Elsevier, vol. 123(C), pages 1-20.
    9. Syam, Siddhartha S. & Côté, Murray J., 2010. "A location-allocation model for service providers with application to not-for-profit health care organizations," Omega, Elsevier, vol. 38(3-4), pages 157-166, June.
    10. Ortiz-Astorquiza, Camilo & Contreras, Ivan & Laporte, Gilbert, 2018. "Multi-level facility location problems," European Journal of Operational Research, Elsevier, vol. 267(3), pages 791-805.
    11. Sundarraj, R. P., 2002. "An optimization approach to plan for reusable software components," European Journal of Operational Research, Elsevier, vol. 142(1), pages 128-137, October.
    12. Zvi Drezner & Jack Brimberg & Nenad Mladenović & Said Salhi, 2016. "New local searches for solving the multi-source Weber problem," Annals of Operations Research, Springer, vol. 246(1), pages 181-203, November.
    13. Harkness, Joseph & ReVelle, Charles, 2003. "Facility location with increasing production costs," European Journal of Operational Research, Elsevier, vol. 145(1), pages 1-13, February.
    14. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.
    15. Vaithyanathan, Shivakumar & Burke, Laura I. & Magent, Michael A., 1996. "Massively parallel analog tabu search using neural networks applied to simple plant location problems," European Journal of Operational Research, Elsevier, vol. 93(2), pages 317-330, September.
    16. Holmberg, Kaj & Ling, Jonas, 1997. "A Lagrangean heuristic for the facility location problem with staircase costs," European Journal of Operational Research, Elsevier, vol. 97(1), pages 63-74, February.
    17. C S Sung & W Yang, 2008. "An exact algorithm for a cross-docking supply chain network design problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(1), pages 119-136, January.
    18. Francisco Casas & Claudio E. Torres & Ignacio Araya, 2022. "A heuristic search based on diversity for solving combinatorial problems," Journal of Heuristics, Springer, vol. 28(3), pages 287-328, June.
    19. Klose, Andreas & Gortz, Simon, 2007. "A branch-and-price algorithm for the capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1109-1125, June.
    20. 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.

    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:spr:cejnor:v:19:y:2011:i:2:p:191-200. See general information about how to correct material in RePEc.

    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 bibliographic 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.