IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i23p3812-d1535100.html
   My bibliography  Save this article

Uncertainty Modeling and Stability Assessment of Minimum Spanning Trees in Network Design

Author

Listed:
  • Ahmad Hosseini

    (Centre for Information Technologies and Applied Mathematics, School of Engineering and Management, University of Nova Gorica, 5000 Nova Gorica, Slovenia)

Abstract

The Minimum Spanning Tree (MST) problem in networks focuses on finding efficient routes, with applications in transportation, logistics, telecommunications, and more. However, catastrophes can make these networks uncertain, requiring robust computational models for decision-making. This paper introduces an uncertainty theory-based model to analyze the stability of MSTs in uncertain networks. By incorporating reliability and risk variables, we assess the robustness of uncertain MSTs (UMSTs) and address the challenge of computing link tolerances, which define the range within which network links can vary without compromising MST optimality. This study proposes computational formulations to systematically calculate these tolerances, offering a more efficient alternative to traditional re-optimization methods.

Suggested Citation

  • Ahmad Hosseini, 2024. "Uncertainty Modeling and Stability Assessment of Minimum Spanning Trees in Network Design," Mathematics, MDPI, vol. 12(23), pages 1-17, December.
    • Handle: RePEc:gam:jmathe:v:12:y:2024:i:23:p:3812-:d:1535100
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/23/3812/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/12/23/3812/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Zhu, Zhenran & Zhang, Anming & Zhang, Yahua, 2018. "Connectivity of intercity passenger transportation in China: A multi-modal and network approach," Journal of Transport Geography, Elsevier, vol. 71(C), pages 263-276.
    2. Zhongfeng Qin & Yuan Gao, 2017. "Uncapacitated $$p$$ p -hub location problem with fixed costs and uncertain flows," Journal of Intelligent Manufacturing, Springer, vol. 28(3), pages 705-716, March.
    3. Shuang Wang & Dong Yang & Jing Lu, 2018. "A connectivity reliability-cost approach for path selection in the maritime transportation of China’s crude oil imports," Maritime Policy & Management, Taylor & Francis Journals, vol. 45(5), pages 567-584, July.
    4. Xing, Tao & Zhou, Xuesong, 2011. "Finding the most reliable path with and without link travel time correlation: A Lagrangian substitution based approach," Transportation Research Part B: Methodological, Elsevier, vol. 45(10), pages 1660-1679.
    5. Zhou, Yaoming & Wang, Junwei & Sheu, Jiuh-Biing, 2019. "On connectivity of post-earthquake road networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 123(C), pages 1-16.
    6. Clark, Stephen & Watling, David, 2005. "Modelling network travel time reliability under stochastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 39(2), pages 119-140, February.
    7. Jing Wang & Jianming Zhu & Haoxiong Yang, 2013. "Reliable Path Selection Problem in Uncertain Traffic Network after Natural Disaster," Mathematical Problems in Engineering, Hindawi, vol. 2013, pages 1-5, May.
    8. Li, Jian & Dueñas-Osorio, Leonardo & Chen, Changkun & Shi, Congling, 2016. "Connectivity reliability and topological controllability of infrastructure networks: A comparative assessment," Reliability Engineering and System Safety, Elsevier, vol. 156(C), pages 24-33.
    9. Psaltoglou, Artemis & Calle, Eusebi, 2018. "Enhanced connectivity index – A new measure for identifying critical points in urban public transportation networks," International Journal of Critical Infrastructure Protection, Elsevier, vol. 21(C), pages 22-32.
    10. Muriel-Villegas, Juan E. & Alvarez-Uribe, Karla C. & Patiño-Rodríguez, Carmen E. & Villegas, Juan G., 2016. "Analysis of transportation networks subject to natural hazards – Insights from a Colombian case," Reliability Engineering and System Safety, Elsevier, vol. 152(C), pages 151-165.
    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. Zhou, Yaoming & Wang, Junwei & Sheu, Jiuh-Biing, 2019. "On connectivity of post-earthquake road networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 123(C), pages 1-16.
    2. Shen, Liang & Shao, Hu & Wu, Ting & Fainman, Emily Zhu & Lam, William H.K., 2020. "Finding the reliable shortest path with correlated link travel times in signalized traffic networks under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 144(C).
    3. Yamada, Takashi, 2022. "Generalizing the probability of reaching a destination in case of route blockage," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 607(C).
    4. Cancela, Héctor & Guerberoff, Gustavo & Robledo, Franco & Romero, Pablo, 2021. "Analysis and reliability of separable systems," Operations Research Perspectives, Elsevier, vol. 8(C).
    5. Prakash, A. Arun & Seshadri, Ravi & Srinivasan, Karthik K., 2018. "A consistent reliability-based user-equilibrium problem with risk-averse users and endogenous travel time correlations: Formulation and solution algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 114(C), pages 171-198.
    6. Pennetti, Cody A. & Fontaine, Michael D. & Jun, Jungwook & Lambert, James H., 2020. "Evaluating capacity of transportation operations with highway travel time reliability," Reliability Engineering and System Safety, Elsevier, vol. 204(C).
    7. Ahmad Hosseini & Mir Saman Pishvaee, 2022. "Capacity reliability under uncertainty in transportation networks: an optimization framework and stability assessment methodology," Fuzzy Optimization and Decision Making, Springer, vol. 21(3), pages 479-512, September.
    8. Zhaoqi Zang & Xiangdong Xu & Kai Qu & Ruiya Chen & Anthony Chen, 2022. "Travel time reliability in transportation networks: A review of methodological developments," Papers 2206.12696, arXiv.org, revised Jul 2022.
    9. Zhang, Yifan & Ng, S. Thomas, 2021. "A hypothesis-driven framework for resilience analysis of public transport network under compound failure scenarios," International Journal of Critical Infrastructure Protection, Elsevier, vol. 35(C).
    10. Hoang, Nam H. & Vu, Hai L. & Lo, Hong K., 2018. "An informed user equilibrium dynamic traffic assignment problem in a multiple origin-destination stochastic network," Transportation Research Part B: Methodological, Elsevier, vol. 115(C), pages 207-230.
    11. Lu, Mengyuan & Perez, Edgar Jimenez & Mason, Keith & He, Yin, 2024. "Fractal assessment analysis of China's air-HSR network integration," Journal of Transport Geography, Elsevier, vol. 114(C).
    12. Tu, Huizhao & Li, Hao & van Lint, Hans & van Zuylen, Henk, 2012. "Modeling travel time reliability of freeways using risk assessment techniques," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(10), pages 1528-1540.
    13. Jenelius, Erik & Mattsson, Lars-Göran, 2012. "Road network vulnerability analysis of area-covering disruptions: A grid-based approach with case study," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(5), pages 746-760.
    14. Li, Siping & Zhou, Yaoming & Kundu, Tanmoy & Zhang, Fangni, 2021. "Impact of entry restriction policies on international air transport connectivity during COVID-19 pandemic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    15. Yu Li & Ji Zheng & Fei Li & Xueting Jin & Chen Xu, 2017. "Assessment of municipal infrastructure development and its critical influencing factors in urban China: A FA and STIRPAT approach," PLOS ONE, Public Library of Science, vol. 12(8), pages 1-14, August.
    16. Brightnes Risimati & Trynos Gumbo & James Chakwizira, 2021. "Spatial Integration of Non-Motorized Transport and Urban Public Transport Infrastructure: A Case of Johannesburg," Sustainability, MDPI, vol. 13(20), pages 1-17, October.
    17. Monfared, M.A.S. & Rezazadeh, Masoumeh & Alipour, Zohreh, 2022. "Road networks reliability estimations and optimizations: A Bi-directional bottom-up, top-down approach," Reliability Engineering and System Safety, Elsevier, vol. 222(C).
    18. Zhang, Yanzi & Diabat, Ali & Zhang, Zhi-Hai, 2021. "Reliable closed-loop supply chain design problem under facility-type-dependent probabilistic disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 146(C), pages 180-209.
    19. Li, Siping & Zhou, Yaoming & Kundu, Tanmoy & Sheu, Jiuh-Biing, 2021. "Spatiotemporal variation of the worldwide air transportation network induced by COVID-19 pandemic in 2020," Transport Policy, Elsevier, vol. 111(C), pages 168-184.
    20. Clavijo-Buritica, Nicolás & Triana-Sanchez, Laura & Escobar, John Willmer, 2023. "A hybrid modeling approach for resilient agri-supply network design in emerging countries: Colombian coffee supply chain," Socio-Economic Planning Sciences, Elsevier, vol. 85(C).

    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:gam:jmathe:v:12:y:2024:i:23:p:3812-:d:1535100. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.