IDEAS home Printed from https://ideas.repec.org/a/spr/telsys/v62y2016i1d10.1007_s11235-015-0067-9.html
   My bibliography  Save this article

Multi-commodity k-splittable survivable network design problems with relays

Author

Listed:
  • Ozgur Kabadurmus

    (Yasar University)

  • Alice E. Smith

    (Auburn University)

Abstract

The network design problem is a well known optimization problem with applications in telecommunication, infrastructure designs and military operations. This paper devises the first formulation and solution methodology for the multi-commodity k-splittable two-edge disjoint survivable network design problem with capacitated edges and relays. This problem realistically portrays telecommunications network design but has not been solved previously due to its computational difficulty. Edge capacity is considered as either a discrete or a continuous variable. An exact method and a practical heuristic method are presented, and computational results are discussed.

Suggested Citation

  • Ozgur Kabadurmus & Alice E. Smith, 2016. "Multi-commodity k-splittable survivable network design problems with relays," Telecommunication Systems: Modelling, Analysis, Design and Management, Springer, vol. 62(1), pages 123-133, May.
    • Handle: RePEc:spr:telsys:v:62:y:2016:i:1:d:10.1007_s11235-015-0067-9
    DOI: 10.1007/s11235-015-0067-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11235-015-0067-9
    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/s11235-015-0067-9?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. Konak, Abdullah, 2012. "Network design problem with relays: A genetic algorithm with a path-based crossover and a set covering formulation," European Journal of Operational Research, Elsevier, vol. 218(3), pages 829-837.
    2. Cabral, Edgar Alberto & Erkut, Erhan & Laporte, Gilbert & Patterson, Raymond A., 2007. "The network design problem with relays," European Journal of Operational Research, Elsevier, vol. 180(2), pages 834-844, July.
    3. Geir Dahl & Mechthild Stoer, 1998. "A Cutting Plane Algorithm for Multicommodity Survivable Network Design Problems," INFORMS Journal on Computing, INFORMS, vol. 10(1), pages 1-11, February.
    4. Ramirez-Marquez, José Emmanuel & Rocco S., Claudio M., 2009. "Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery," Reliability Engineering and System Safety, Elsevier, vol. 94(5), pages 913-921.
    5. Alysson Costa & Jean-François Cordeau & Bernard Gendron, 2009. "Benders, metric and cutset inequalities for multicommodity capacitated network design," Computational Optimization and Applications, Springer, vol. 42(3), pages 371-392, April.
    6. Garg, Manish & Smith, J. Cole, 2008. "Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios," Omega, Elsevier, vol. 36(6), pages 1057-1071, December.
    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. Khodakaram Salimifard & Sara Bigharaz, 2022. "The multicommodity network flow problem: state of the art classification, applications, and solution methods," Operational Research, Springer, vol. 22(1), pages 1-47, March.

    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. Yiyong Xiao & Abdullah Konak, 2017. "A variable neighborhood search for the network design problem with relays," Journal of Heuristics, Springer, vol. 23(2), pages 137-164, June.
    2. Liberatore, Federico & Scaparra, Maria P. & Daskin, Mark S., 2012. "Hedging against disruptions with ripple effects in location analysis," Omega, Elsevier, vol. 40(1), pages 21-30, January.
    3. Yıldız, Barış & Karaşan, Oya Ekin, 2015. "Regenerator Location Problem and survivable extensions: A hub covering location perspective," Transportation Research Part B: Methodological, Elsevier, vol. 71(C), pages 32-55.
    4. Kewcharoenwong, Panitan & Li, Qiaofeng & Üster, Halit, 2023. "Lagrangean relaxation algorithms for fixed-charge capacitated relay network design," Omega, Elsevier, vol. 121(C).
    5. Leitner, Markus & Ljubić, Ivana & Riedler, Martin & Ruthmair, Mario, 2020. "Exact approaches for the directed network design problem with relays," Omega, Elsevier, vol. 91(C).
    6. Markus Leitner & Ivana Ljubić & Martin Riedler & Mario Ruthmair, 2019. "Exact Approaches for Network Design Problems with Relays," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 171-192, February.
    7. Nigam, Ashutosh & Agarwal, Yogesh K., 2014. "Optimal relay node placement in delay constrained wireless sensor network design," European Journal of Operational Research, Elsevier, vol. 233(1), pages 220-233.
    8. Levitin, G. & Gertsbakh, I. & Shpungin, Y., 2013. "Evaluating the damage associated with intentional supply deprivation in multi-commodity network," Reliability Engineering and System Safety, Elsevier, vol. 119(C), pages 11-17.
    9. Siqian Shen & Mingdi You & Yintai Ma, 2017. "Single‐commodity stochastic network design under demand and topological uncertainties with insufficient data," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(2), pages 154-173, March.
    10. Hong Zheng & Xiaozheng He & Yongfu Li & Srinivas Peeta, 2017. "Traffic Equilibrium and Charging Facility Locations for Electric Vehicles," Networks and Spatial Economics, Springer, vol. 17(2), pages 435-457, June.
    11. Wang, Ning & Xiao, Yiyong & Tian, Tianzi & Yang, Jun, 2023. "The optimal 5G base station location of the wireless sensor network considering timely reliability," Reliability Engineering and System Safety, Elsevier, vol. 236(C).
    12. Agarwal, Y.K. & Aneja, Y.P. & Jayaswal, Sachin, 2022. "Directed fixed charge multicommodity network design: A cutting plane approach using polar duality," European Journal of Operational Research, Elsevier, vol. 299(1), pages 118-136.
    13. Sara Mattia, 2012. "Solving survivable two-layer network design problems by metric inequalities," Computational Optimization and Applications, Springer, vol. 51(2), pages 809-834, March.
    14. Halit Üster & Panitan Kewcharoenwong, 2011. "Strategic Design and Analysis of a Relay Network in Truckload Transportation," Transportation Science, INFORMS, vol. 45(4), pages 505-523, November.
    15. SteadieSeifi, M. & Dellaert, N.P. & Nuijten, W. & Van Woensel, T., 2017. "A metaheuristic for the multimodal network flow problem with product quality preservation and empty repositioning," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 321-344.
    16. Yogesh Agarwal, 2013. "Design of Survivable Networks Using Three- and Four-Partition Facets," Operations Research, INFORMS, vol. 61(1), pages 199-213, February.
    17. Yogesh K. Agarwal, 2002. "Design of Capacitated Multicommodity Networks with Multiple Facilities," Operations Research, INFORMS, vol. 50(2), pages 333-344, April.
    18. Chi Zhang & Jose Ramirez-Marquez, 2013. "Protecting critical infrastructures against intentional attacks: a two-stage game with incomplete information," IISE Transactions, Taylor & Francis Journals, vol. 45(3), pages 244-258.
    19. Garg, Manish & Smith, J. Cole, 2008. "Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios," Omega, Elsevier, vol. 36(6), pages 1057-1071, December.
    20. Li, Y.F. & Sansavini, G. & Zio, E., 2013. "Non-dominated sorting binary differential evolution for the multi-objective optimization of cascading failures protection in complex networks," Reliability Engineering and System Safety, Elsevier, vol. 111(C), pages 195-205.

    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:telsys:v:62:y:2016:i:1:d:10.1007_s11235-015-0067-9. 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.