IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v70y2018i1d10.1007_s10898-017-0566-1.html
   My bibliography  Save this article

Approximation algorithms for the robust/soft-capacitated 2-level facility location problems

Author

Listed:
  • Chenchen Wu

    (Tianjin University of Technology)

  • Dachuan Xu

    (Beijing University of Technology)

  • Dongmei Zhang

    (Shandong Jianzhu University)

  • Peng Zhang

    (Shandong University)

Abstract

In this work, we consider the robust/soft-capacitated 2-level facility location problems. For the robust version, we propose a primal-dual based $$(3+\epsilon )$$ ( 3 + ϵ ) -approximation algorithm via construction of an adapted instance which explores some open facilities in the optimal solution. For the soft-capacitated version, we propose a $$ (4+ 1/ (e-1) +\epsilon )$$ ( 4 + 1 / ( e - 1 ) + ϵ ) -approximation algorithm via construction of the associated uncapacitated version whose connection cost is re-defined appropriately.

Suggested Citation

  • Chenchen Wu & Dachuan Xu & Dongmei Zhang & Peng Zhang, 2018. "Approximation algorithms for the robust/soft-capacitated 2-level facility location problems," Journal of Global Optimization, Springer, vol. 70(1), pages 207-222, January.
    • Handle: RePEc:spr:jglopt:v:70:y:2018:i:1:d:10.1007_s10898-017-0566-1
    DOI: 10.1007/s10898-017-0566-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-017-0566-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-017-0566-1?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. Tcha, Dong-wan & Lee, Bum-il, 1984. "A branch-and-bound algorithm for the multi-level uncapacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 18(1), pages 35-43, October.
    2. Fengmin Wang & Dachuan Xu & Chenchen Wu, 2016. "Combinatorial approximation algorithms for the robust facility location problem with penalties," Journal of Global Optimization, Springer, vol. 64(3), pages 483-496, March.
    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. Wang, Mengyue & Huang, Hongxuan, 2019. "The design of a flexible capital-constrained global supply chain by integrating operational and financial strategies," Omega, Elsevier, vol. 88(C), pages 40-62.
    2. Xiao Zhao & Xuhui Xia & Lei Wang & Guodong Yu, 2018. "Risk-Averse Facility Location for Green Closed-Loop Supply Chain Networks Design under Uncertainty," Sustainability, MDPI, vol. 10(11), pages 1-17, November.

    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. 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.
    2. Schnepper, Teresa & Klamroth, Kathrin & Stiglmayr, Michael & Puerto, Justo, 2019. "Exact algorithms for handling outliers in center location problems on networks using k-max functions," European Journal of Operational Research, Elsevier, vol. 273(2), pages 441-451.
    3. Holzapfel, Andreas & Potoczki, Tobias & Kuhn, Heinrich, 2023. "Designing the breadth and depth of distribution networks in the retail trade," International Journal of Production Economics, Elsevier, vol. 257(C).
    4. Melachrinoudis, Emanuel & Min, Hokey, 2000. "The dynamic relocation and phase-out of a hybrid, two-echelon plant/warehousing facility: A multiple objective approach," European Journal of Operational Research, Elsevier, vol. 123(1), pages 1-15, May.
    5. Li‐Lian Gao & E. Powell Robinson, 1992. "A dual‐based optimization procedure for the two‐echelon uncapacitated facility location problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(2), pages 191-212, March.
    6. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2017. "Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 767-779, November.
    7. 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.
    8. Fleischmann, Mortiz & Krikke, Hans Ronald & Dekker, Rommert & Flapper, Simme Douwe P., 2000. "A characterisation of logistics networks for product recovery," Omega, Elsevier, vol. 28(6), pages 653-666, December.
    9. Tragantalerngsak, Suda & Holt, John & Ronnqvist, Mikael, 2000. "An exact method for the two-echelon, single-source, capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 123(3), pages 473-489, June.
    10. Addis, Bernardetta & Carello, Giuliana & Ceselli, Alberto, 2013. "Combining very large scale and ILP based neighborhoods for a two-level location problem," European Journal of Operational Research, Elsevier, vol. 231(3), pages 535-546.
    11. Hinojosa, Y. & Puerto, J. & Fernandez, F. R., 2000. "A multiperiod two-echelon multicommodity capacitated plant location problem," European Journal of Operational Research, Elsevier, vol. 123(2), pages 271-291, June.
    12. Tragantalerngsak, Suda & Holt, John & Ronnqvist, Mikael, 1997. "Lagrangian heuristics for the two-echelon, single-source, capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 102(3), pages 611-625, November.
    13. Keskin, Burcu B. & Uster, Halit, 2007. "Meta-heuristic approaches with memory and evolution for a multi-product production/distribution system design problem," European Journal of Operational Research, Elsevier, vol. 182(2), pages 663-682, October.
    14. 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.
    15. Barros, A. I. & Dekker, R. & Scholten, V., 1998. "A two-level network for recycling sand: A case study," European Journal of Operational Research, Elsevier, vol. 110(2), pages 199-214, October.
    16. Ortiz-Astorquiza, Camilo & Contreras, Ivan & Laporte, Gilbert, 2015. "Multi-level facility location as the maximization of a submodular set function," European Journal of Operational Research, Elsevier, vol. 247(3), pages 1013-1016.
    17. Klose, Andreas, 2000. "A Lagrangean relax-and-cut approach for the two-stage capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 126(2), pages 408-421, October.
    18. Bloemhof-Ruwaard, Jacqueline M. & Salomon, Marc & Van Wassenhove, Luk N., 1996. "The capacitated distribution and waste disposal problem," European Journal of Operational Research, Elsevier, vol. 88(3), pages 490-503, February.
    19. Barros, Lilian & Riley, Michael, 2001. "A combinatorial approach to level of repair analysis," European Journal of Operational Research, Elsevier, vol. 129(2), pages 242-251, March.
    20. Dasci, Abdullah & Verter, Vedat, 2001. "A continuous model for production-distribution system design," European Journal of Operational Research, Elsevier, vol. 129(2), pages 287-298, March.

    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:jglopt:v:70:y:2018:i:1:d:10.1007_s10898-017-0566-1. 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.