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

Improved algorithms for joint optimization of facility locations and network connections

Author

Listed:
  • Lai, Xiaofan
  • Xu, Zhou

Abstract

This paper studies a k-median Steiner forest problem that jointly optimizes the opening of at most k facility locations and their connections to the client locations, so that each client is connected by a path to an open facility, with the total connection cost minimized. The problem has wide applications in the telecommunication and transportation industries, but is strongly NP-hard. In the literature, only a 2-approximation algorithm is known, it being based on a Lagrangian relaxation of the problem and using a sophisticated primal-dual schema. In this study, we have developed an improved approximation algorithm using a simple transformation from an optimal solution of a minimum spanning tree problem. Compared with the existing 2-approximation algorithm, our new algorithm not only achieves a better approximation ratio that is easier to be proved, but also guarantees to produce solutions of equal or better quality—up to 50 percent improvement in some cases. In addition, for two non-trivial special cases, where either every location contains a client, or all the locations are in a tree-shaped network, we have developed, for the first time in the literature, new algorithms that can solve the problem to optimality in polynomial time.

Suggested Citation

  • Lai, Xiaofan & Xu, Zhou, 2016. "Improved algorithms for joint optimization of facility locations and network connections," European Journal of Operational Research, Elsevier, vol. 250(3), pages 745-753.
    • Handle: RePEc:eee:ejores:v:250:y:2016:i:3:p:745-753
    DOI: 10.1016/j.ejor.2015.10.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715009108
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.10.003?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. Rathinam, Sivakumar & Sengupta, Raja, 2007. "3/2-Approximation Algorithm for a Generalized, Multiple Depot, Hamiltonina Path Problem," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt06p2815q, Institute of Transportation Studies, UC Berkeley.
    2. Chhajed, Dilip & Lowe, Timothy J., 1992. "An O(nm) algorithm for a special case of the multimedian location problem on a tree," European Journal of Operational Research, Elsevier, vol. 63(2), pages 222-230, December.
    3. Xu, Liang & Xu, Zhou & Xu, Dongsheng, 2013. "Exact and approximation algorithms for the min–max k-traveling salesmen problem on a tree," European Journal of Operational Research, Elsevier, vol. 227(2), pages 284-292.
    4. R. Ravi & Amitabh Sinha, 2006. "Approximation Algorithms for Problems Combining Facility Location and Network Design," Operations Research, INFORMS, vol. 54(1), pages 73-81, February.
    5. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    6. Éric Gourdin & Martine Labbé & Gilbert Laporte, 2000. "The Uncapacitated Facility Location Problem with Client Matching," Operations Research, INFORMS, vol. 48(5), pages 671-685, October.
    7. 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.
    8. Aardal, Karen & van den Berg, Pieter L. & Gijswijt, Dion & Li, Shanfei, 2015. "Approximation algorithms for hard capacitated k-facility location problems," European Journal of Operational Research, Elsevier, vol. 242(2), pages 358-368.
    9. Prodhon, Caroline & Prins, Christian, 2014. "A survey of recent research on location-routing problems," European Journal of Operational Research, Elsevier, vol. 238(1), pages 1-17.
    10. Tetsuo Asano & Naoki Katoh & Kazuhiro Kawashima, 2001. "A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree," Journal of Combinatorial Optimization, Springer, vol. 5(2), pages 213-231, June.
    11. Marek Karpinski & Alexander Zelikovsky, 1997. "New Approximation Algorithms for the Steiner Tree Problems," Journal of Combinatorial Optimization, Springer, vol. 1(1), pages 47-65, March.
    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. Carrasco Heine, Oscar F. & Demleitner, Antonia & Matuschke, Jannik, 2023. "Bifactor approximation for location routing with vehicle and facility capacities," European Journal of Operational Research, Elsevier, vol. 304(2), pages 429-442.
    2. Liwei Zeng & Sunil Chopra & Karen Smilowitz, 2019. "The Covering Path Problem on a Grid," Transportation Science, INFORMS, vol. 53(6), pages 1656-1672, November.
    3. Sahar Validi & Arijit Bhattacharya & P. J. Byrne, 2020. "Sustainable distribution system design: a two-phase DoE-guided meta-heuristic solution approach for a three-echelon bi-objective AHP-integrated location-routing model," Annals of Operations Research, Springer, vol. 290(1), pages 191-222, July.
    4. Zhu, Stuart X. & Ursavas, Evrim, 2018. "Design and analysis of a satellite network with direct delivery in the pharmaceutical industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 190-207.
    5. Capelle, Thomas & Cortés, Cristián E. & Gendreau, Michel & Rey, Pablo A. & Rousseau, Louis-Martin, 2019. "A column generation approach for location-routing problems with pickup and delivery," European Journal of Operational Research, Elsevier, vol. 272(1), pages 121-131.
    6. Tricoire, Fabien & Parragh, Sophie N., 2017. "Investing in logistics facilities today to reduce routing emissions tomorrow," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 56-67.
    7. Alvarez, Jose A. Lopez & Buijs, Paul & Deluster, Rogier & Coelho, Leandro C. & Ursavas, Evrim, 2020. "Strategic and operational decision-making in expanding supply chains for LNG as a fuel," Omega, Elsevier, vol. 97(C).
    8. Gläser, Sina, 2022. "A waste collection problem with service type option," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1216-1230.
    9. Danışment Vural & Robert F. Dell & Erkan Kose, 2021. "Locating unmanned aircraft systems for multiple missions under different weather conditions," Operational Research, Springer, vol. 21(1), pages 725-744, March.
    10. Michiel A. J. uit het Broek & Albert H. Schrotenboer & Bolor Jargalsaikhan & Kees Jan Roodbergen & Leandro C. Coelho, 2021. "Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm," Operations Research, INFORMS, vol. 69(2), pages 380-409, March.
    11. Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2020. "Integrating first-mile pickup and last-mile delivery on shared vehicle routes for efficient urban e-commerce distribution," Transportation Research Part B: Methodological, Elsevier, vol. 131(C), pages 26-62.
    12. Jaller, Miguel & Pahwa, Anmol, 2023. "Coping with the Rise of E-commerce Generated Home Deliveries through Innovative Last-mile Technologies and Strategies," Institute of Transportation Studies, Working Paper Series qt5t76x0kh, Institute of Transportation Studies, UC Davis.
    13. Zajac, Sandra & Huber, Sandra, 2021. "Objectives and methods in multi-objective routing problems: a survey and classification scheme," European Journal of Operational Research, Elsevier, vol. 290(1), pages 1-25.
    14. Andrés Martínez-Reyes & Carlos L. Quintero-Araújo & Elyn L. Solano-Charris, 2021. "Supplying Personal Protective Equipment to Intensive Care Units during the COVID-19 Outbreak in Colombia. A Simheuristic Approach Based on the Location-Routing Problem," Sustainability, MDPI, vol. 13(14), pages 1-16, July.
    15. Keliang Chang & Hong Zhou & Guijing Chen & Huiqin Chen, 2017. "Multiobjective Location Routing Problem considering Uncertain Data after Disasters," Discrete Dynamics in Nature and Society, Hindawi, vol. 2017, pages 1-7, March.
    16. Tran, Trung Hieu & Nagy, Gábor & Nguyen, Thu Ba T. & Wassan, Niaz A., 2018. "An efficient heuristic algorithm for the alternative-fuel station location problem," European Journal of Operational Research, Elsevier, vol. 269(1), pages 159-170.
    17. Younes Rahmani & Wahiba Ramdane Cherif-Khettaf & Ammar Oulamara, 2016. "The two-echelon multi-products location-routing problem with pickup and delivery: formulation and heuristic approaches," International Journal of Production Research, Taylor & Francis Journals, vol. 54(4), pages 999-1019, February.
    18. Côté, J.F. & Guastaroba, G. & Speranza, M.G., 2017. "The value of integrating loading and routing," European Journal of Operational Research, Elsevier, vol. 257(1), pages 89-105.
    19. Janjevic, Milena & Merchán, Daniel & Winkenbach, Matthias, 2021. "Designing multi-tier, multi-service-level, and multi-modal last-mile distribution networks for omni-channel operations," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1059-1077.
    20. Ben Mohamed, Imen & Klibi, Walid & Sadykov, Ruslan & Şen, Halil & Vanderbeck, François, 2023. "The two-echelon stochastic multi-period capacitated location-routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 645-667.

    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:250:y:2016:i:3:p:745-753. 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.