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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Kewcharoenwong, Panitan & Li, Qiaofeng & Üster, Halit, 2023. "Lagrangean relaxation algorithms for fixed-charge capacitated relay network design," Omega, Elsevier, vol. 121(C).
    9. 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).
    10. Leitner, Markus & Ljubić, Ivana & Riedler, Martin & Ruthmair, Mario, 2020. "Exact approaches for the directed network design problem with relays," Omega, Elsevier, vol. 91(C).
    11. 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.
    12. Yeh, Wei-Chang, 2020. "A new method for verifying d-MC candidates," Reliability Engineering and System Safety, Elsevier, vol. 204(C).
    13. Zhang, Yue & Feng, Qiang & Fan, Dongming & Ren, Yi & Sun, Bo & Yang, Dezhen & Wang, Zili, 2023. "Optimization of maritime support network with relays under uncertainty: A novel matheuristics method," Reliability Engineering and System Safety, Elsevier, vol. 232(C).
    14. James F. Campbell & Morton E. O'Kelly, 2012. "Twenty-Five Years of Hub Location Research," Transportation Science, INFORMS, vol. 46(2), pages 153-169, May.
    15. 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.
    16. 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.
    17. 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.
    18. Zhu, Huaxing & Zhang, Chi, 2019. "Expanding a complex networked system for enhancing its reliability evaluated by a new efficient approach," Reliability Engineering and System Safety, Elsevier, vol. 188(C), pages 205-220.
    19. 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.
    20. Ramirez-Marquez, Jose E. & Rocco S, Claudio M. & Levitin, Gregory, 2009. "Optimal protection of general source–sink networks via evolutionary techniques," Reliability Engineering and System Safety, Elsevier, vol. 94(10), pages 1676-1684.

    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.