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

New formulations for two location problems with interconnected facilities

Author

Listed:
  • Kuzbakov, Yerlan
  • Ljubić, Ivana

Abstract

This paper studies two location problems with interconnected facilities. In the first problem, all customers need to be served by open facilities, and in the second (covering) variant a penalty is imposed for customers that cannot receive the service. Compared to the standard facility location setting, an additional constraint is imposed asking that all open facilities are interconnected, i.e., all open facilities need to be within a given radius of each other. These problems combine classical facility location aspects with network design, and we exploit this link to derive new mixed integer programming models. The strength of these models is investigated both theoretically and empirically. An extensive computational study is conducted on a set of benchmark instances from the literature, in which branch-and-cut, Benders decomposition and compact models are assessed in terms of the runtime and the resulting gaps.

Suggested Citation

  • Kuzbakov, Yerlan & Ljubić, Ivana, 2024. "New formulations for two location problems with interconnected facilities," European Journal of Operational Research, Elsevier, vol. 314(1), pages 51-65.
  • Handle: RePEc:eee:ejores:v:314:y:2024:i:1:p:51-65
    DOI: 10.1016/j.ejor.2023.09.030
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221723007464
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2023.09.030?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. Matteo Fischetti & Ivana Ljubić & Markus Sinnl, 2017. "Redesigning Benders Decomposition for Large-Scale Facility Location," Management Science, INFORMS, vol. 63(7), pages 2146-2162, July.
    2. Elena Fernández & Mercedes Landete, 2015. "Fixed-Charge Facility Location Problems," Springer Books, in: Gilbert Laporte & Stefan Nickel & Francisco Saldanha da Gama (ed.), Location Science, edition 127, chapter 0, pages 47-77, Springer.
    3. Sourour Elloumi, 2010. "A tighter formulation of the p-median problem," Journal of Combinatorial Optimization, Springer, vol. 19(1), pages 69-83, January.
    4. Weninger, Dieter & Wolsey, Laurence A., 2023. "Benders-type branch-and-cut algorithms for capacitated facility location with single-sourcing," European Journal of Operational Research, Elsevier, vol. 310(1), pages 84-99.
    5. Leitner, Markus & Ljubić, Ivana & Salazar-González, Juan-José & Sinnl, Markus, 2017. "An algorithmic framework for the exact solution of tree-star problems," European Journal of Operational Research, Elsevier, vol. 261(1), pages 54-66.
    6. Andrew Romich & Guanghui Lan & J. Cole Smith, 2015. "A robust sensor covering and communication problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(7), pages 582-594, October.
    7. Duran-Mateluna, Cristian & Ales, Zacharie & Elloumi, Sourour, 2023. "An efficient benders decomposition for the p-median problem," European Journal of Operational Research, Elsevier, vol. 308(1), pages 84-96.
    8. Guang Xu & Jinhui Xu, 2009. "An improved approximation algorithm for uncapacitated facility location problem with penalties," Journal of Combinatorial Optimization, Springer, vol. 17(4), pages 424-436, May.
    9. Si Chen & Ivana Ljubić & S. Raghavan, 2015. "The Generalized Regenerator Location Problem," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 204-220, May.
    10. Mark S. Daskin & Kayse Lee Maass, 2015. "The p-Median Problem," Springer Books, in: Gilbert Laporte & Stefan Nickel & Francisco Saldanha da Gama (ed.), Location Science, edition 127, chapter 0, pages 21-45, Springer.
    11. Markus Leitner & Ivana Ljubić & Martin Luipersbeck & Markus Sinnl, 2018. "A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 402-420, May.
    12. Mladenovic, Nenad & Brimberg, Jack & Hansen, Pierre & Moreno-Perez, Jose A., 2007. "The p-median problem: A survey of metaheuristic approaches," European Journal of Operational Research, Elsevier, vol. 179(3), pages 927-939, June.
    13. Daniel Rehfeldt & Thorsten Koch, 2022. "On the Exact Solution of Prize-Collecting Steiner Tree Problems," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 872-889, March.
    14. Krarup, Jakob & Pruzan, Peter Mark, 1983. "The simple plant location problem: Survey and synthesis," European Journal of Operational Research, Elsevier, vol. 12(1), pages 36-57, January.
    15. M. Gisela Bardossy & S. Raghavan, 2010. "Dual-Based Local Search for the Connected Facility Location and Related Problems," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 584-602, November.
    16. Contreras, Ivan & Fernández, Elena & Marín, Alfredo, 2010. "The Tree of Hubs Location Problem," European Journal of Operational Research, Elsevier, vol. 202(2), pages 390-400, April.
    17. Cordeau, Jean-François & Furini, Fabio & Ljubić, Ivana, 2019. "Benders decomposition for very large scale partial set covering and maximal covering location problems," European Journal of Operational Research, Elsevier, vol. 275(3), pages 882-896.
    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. Duran-Mateluna, Cristian & Ales, Zacharie & Elloumi, Sourour, 2023. "An efficient benders decomposition for the p-median problem," European Journal of Operational Research, Elsevier, vol. 308(1), pages 84-96.
    2. Lin, Yun Hui & Wang, Yuan & Lee, Loo Hay & Chew, Ek Peng, 2022. "Omnichannel facility location and fulfillment optimization," Transportation Research Part B: Methodological, Elsevier, vol. 163(C), pages 187-209.
    3. Pedersen, Jaap & Weinand, Jann Michael & Syranidou, Chloi & Rehfeldt, Daniel, 2024. "An efficient solver for large-scale onshore wind farm siting including cable routing," European Journal of Operational Research, Elsevier, vol. 317(2), pages 616-630.
    4. Pablo Adasme & Ali Dehghan Firoozabadi, 2019. "Facility Location with Tree Topology and Radial Distance Constraints," Complexity, Hindawi, vol. 2019, pages 1-29, November.
    5. Mercedes Landete & Gilbert Laporte, 2019. "Facility location problems with user cooperation," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(1), pages 125-145, April.
    6. Christensen, Tue Rauff Lind & Klose, Andreas, 2021. "A fast exact method for the capacitated facility location problem with differentiable convex production costs," European Journal of Operational Research, Elsevier, vol. 292(3), pages 855-868.
    7. Chen, Liang & Chen, Sheng-Jie & Chen, Wei-Kun & Dai, Yu-Hong & Quan, Tao & Chen, Juan, 2023. "Efficient presolving methods for solving maximal covering and partial set covering location problems," European Journal of Operational Research, Elsevier, vol. 311(1), pages 73-87.
    8. Boris Goldengorin & Dmitry Krushinsky & Jannes Slomp, 2012. "Flexible PMP Approach for Large-Size Cell Formation," Operations Research, INFORMS, vol. 60(5), pages 1157-1166, October.
    9. Kahr, Michael, 2022. "Determining locations and layouts for parcel lockers to support supply chain viability at the last mile," Omega, Elsevier, vol. 113(C).
    10. Alcaraz, Javier & Landete, Mercedes & Monge, Juan F., 2012. "Design and analysis of hybrid metaheuristics for the Reliability p-Median Problem," European Journal of Operational Research, Elsevier, vol. 222(1), pages 54-64.
    11. Contreras, Ivan & Fernández, Elena, 2012. "General network design: A unified view of combined location and network design problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 680-697.
    12. Pelegrín, Mercedes, 2023. "New variants of the simple plant location problem and applications," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1094-1108.
    13. Sergio García & Martine Labbé & Alfredo Marín, 2011. "Solving Large p -Median Problems with a Radius Formulation," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 546-556, November.
    14. Ashley, Thomas & Carrizosa, Emilio & Fernández-Cara, Enrique, 2019. "Heliostat field cleaning scheduling for Solar Power Tower plants: A heuristic approach," Applied Energy, Elsevier, vol. 235(C), pages 653-660.
    15. Lin, Yun Hui & Tian, Qingyun, 2021. "Branch-and-cut approach based on generalized benders decomposition for facility location with limited choice rule," European Journal of Operational Research, Elsevier, vol. 293(1), pages 109-119.
    16. Antiopi Panteli & Basilis Boutsinas & Ioannis Giannikos, 2021. "On solving the multiple p-median problem based on biclustering," Operational Research, Springer, vol. 21(1), pages 775-799, March.
    17. Chandra Ade Irawan & Dylan Jones, 2019. "Formulation and solution of a two-stage capacitated facility location problem with multilevel capacities," Annals of Operations Research, Springer, vol. 272(1), pages 41-67, January.
    18. Pawel Kalczynski & Jack Brimberg & Zvi Drezner, 2022. "Less is more: discrete starting solutions in the planar p-median problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 34-59, April.
    19. 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.
    20. Alumur, Sibel A. & Yaman, Hande & Kara, Bahar Y., 2012. "Hierarchical multimodal hub location problem with time-definite deliveries," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(6), pages 1107-1120.

    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:314:y:2024:i:1:p:51-65. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.