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. 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.
    5. 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).
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Veenstra, Marjolein & Roodbergen, Kees Jan & Coelho, Leandro C. & Zhu, Stuart X., 2018. "A simultaneous facility location and vehicle routing problem arising in health care logistics in the Netherlands," European Journal of Operational Research, Elsevier, vol. 268(2), pages 703-715.
    12. Ahmadi-Javid, Amir & Amiri, Elahe & Meskar, Mahla, 2018. "A Profit-Maximization Location-Routing-Pricing Problem: A Branch-and-Price Algorithm," European Journal of Operational Research, Elsevier, vol. 271(3), pages 866-881.
    13. M. Tadaros & A. Migdalas, 2022. "Bi- and multi-objective location routing problems: classification and literature review," Operational Research, Springer, vol. 22(5), pages 4641-4683, November.
    14. Çağrı Koç, 2019. "Analysis of vehicle emissions in location-routing problem," Flexible Services and Manufacturing Journal, Springer, vol. 31(1), pages 1-33, March.
    15. Menezes, Mozart B.C. & Ruiz-Hernández, Diego & Verter, Vedat, 2016. "A rough-cut approach for evaluating location-routing decisions via approximation algorithms," Transportation Research Part B: Methodological, Elsevier, vol. 87(C), pages 89-106.
    16. Zhang, Ying & Qi, Mingyao & Lin, Wei-Hua & Miao, Lixin, 2015. "A metaheuristic approach to the reliable location routing problem under disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 83(C), pages 90-110.
    17. Darvish, Maryam & Archetti, Claudia & Coelho, Leandro C. & Speranza, M. Grazia, 2019. "Flexible two-echelon location routing problem," European Journal of Operational Research, Elsevier, vol. 277(3), pages 1124-1136.
    18. Adria Soriano & Margaretha Gansterer & Richard F. Hartl, 2018. "The two-region multi-depot pickup and delivery problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 1077-1108, October.
    19. Brandstätter, Georg & Kahr, Michael & Leitner, Markus, 2017. "Determining optimal locations for charging stations of electric car-sharing systems under stochastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 17-35.
    20. Wolfinger, David & Gansterer, Margaretha & Doerner, Karl F. & Popper, Nikolas, 2023. "A Large Neighbourhood Search Metaheuristic for the Contagious Disease Testing Problem," European Journal of Operational Research, Elsevier, vol. 304(1), pages 169-182.

    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.