{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T15:51:12Z","timestamp":1765295472062,"version":"build-2065373602"},"reference-count":39,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2024,3,31]],"date-time":"2024-03-31T00:00:00Z","timestamp":1711843200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2019-07199"],"award-info":[{"award-number":["RGPIN-2019-07199"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems"],"abstract":"<jats:p>Path redundancy is essential for safety and reliability in many real-world routing problems, such as the design of networks for power transmission, transportation, etc. These problems are typically posed to find the shortest path on a weighted graph. For the shortest path with path redundancy, particularly in the Disjoint Shortest 2-Path (DS2P) problem, two disjoint paths are desired such that the combined weight of the two paths is minimized while a minimum distance path separation is maintained. The conventional formulation of the above requires a large-scale mixed-integer programming (MIP) model. However, this approach is practically intractable due to the model\u2019s complexity and extremely long run-time. We demonstrate why DS2P is NP-complete and propose an efficient heuristic to find an approximate solution to the problem in a much shorter time frame. We demonstrate the approach on a realistic dataset for power transmission routing, integrating the computational methodology with a visualization interface using Google Maps. The resulting prototype software is freely available through GitHub and can be deployed on a cloud platform, such as Amazon AWS.<\/jats:p>","DOI":"10.3390\/systems12040117","type":"journal-article","created":{"date-parts":[[2024,3,31]],"date-time":"2024-03-31T13:28:00Z","timestamp":1711891680000},"page":"117","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Resilient Network Design: Disjoint Shortest Path Problem for Power Transmission Application"],"prefix":"10.3390","volume":"12","author":[{"given":"Amit","family":"Jha","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics, University of Calgary, Calgary, AB T2N 1N4, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haotian","family":"Song","sequence":"additional","affiliation":[{"name":"School of Management, Zhejiang University, Hangzhou 310058, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuriy","family":"Zinchenko","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, University of Calgary, Calgary, AB T2N 1N4, Canada"},{"name":"Gurobi Optimization, LLC, Beaverton, OR 97008-7105, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,3,31]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Ward, S., Gwyn, B., Antonova, G., Apostolov, A., Austin, T., Beaumont, P., Beresh, B., Bradt, D., Brunello, G., and Bui, D.-P. (April, January 29). Redundancy Considerations for Protective Relaying Systems. Proceedings of the 2010 63rd Annual Conference for Protective Relay Engineers, College Station, TX, USA.","DOI":"10.1109\/CPRE.2010.5469478"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A Note on Two Problems in Connexion with Graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1002\/atr.132","article-title":"Designing Robust Rapid Transit Networks with Alternative Routes","volume":"45","author":"Laporte","year":"2011","journal-title":"J. Adv. Transp."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Cheng, D., Gkountouna, O., Z\u00fcfle, A., Pfoser, D., and Wenk, C. (2019, January 5). Shortest-Path Diversification through Network Penalization: A Washington DC Area Case Study. Proceedings of the IWCTS\u201919: 12th ACM SIGSPATIAL International Workshop on Computational Transportation Science, Chicago, IL, USA.","DOI":"10.1145\/3357000.3366137"},{"key":"ref_5","first-page":"24","article-title":"Robust Routing Using Electrical Flows","volume":"9","author":"Sinop","year":"2023","journal-title":"ACM Trans. Spat. Algorithms Syst."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1012","DOI":"10.1287\/opre.43.6.1012","article-title":"Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements","volume":"43","author":"Monma","year":"1995","journal-title":"Oper. Res."},{"key":"ref_7","first-page":"697","article-title":"An Expert System for Transmission Line Route Selection","volume":"Volume 2","year":"1993","journal-title":"Proceedings of the International Power Engineering Conference"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"636","DOI":"10.1109\/TPWRS.2006.889112","article-title":"A New Optimal Routing Algorithm for Loss Minimization and Voltage Stability Improvement in Radial Power Systems","volume":"22","author":"Shin","year":"2007","journal-title":"IEEE Trans. Power Syst."},{"key":"ref_9","unstructured":"Donovan, J. (2023, December 01). A National Model for Sitting Transmission Lines. Electric Energy T&D Magazine. Available online: https:\/\/electricenergyonline.com\/energy\/magazine\/286\/article\/a-national-model-for-siting-transmission-lines.htm."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Billinton, R., and Allan, R.N. (1996). Reliability Evaluation of Power Systems, Springer.","DOI":"10.1007\/978-1-4899-1860-4"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Lisnianski, A., and Levitin, G. (2003). Multi-State System Reliability: Assessment, Optimization and Applications, World Scientific. Series on Quality, Reliability & Engineering Statistics.","DOI":"10.1142\/5221"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Quintana, E., and Inga, E. (2022). Optimal Reconfiguration of Electrical Distribution System Using Heuristic Methods with Geopositioning Constraints. Energies, 15.","DOI":"10.3390\/en15155317"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2103","DOI":"10.1007\/s00202-018-0688-6","article-title":"Solving Power Transmission Line Routing Problem Using Improved Genetic and Artificial Bee Colony Algorithms","volume":"100","author":"Eroglu","year":"2018","journal-title":"Electr. Eng."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"934","DOI":"10.1109\/TPWRD.2004.839724","article-title":"GIS Spatial Analysis Applied to Electric Line Routing Optimization","volume":"20","author":"Monteiro","year":"2005","journal-title":"Power Deliv. IEEE Trans."},{"key":"ref_15","unstructured":"Piveteau, N., Schito, J., Martin, R., and Weibel, R. (2018, January 7\u20139). A Novel Approach to the Routing Problem of Overhead Transmission Lines. Proceedings of the 38. Wissenschaftlich-Technische Jahrestagung der DGPF und PFGK18, Munich, Germany."},{"key":"ref_16","unstructured":"Tomlin, D.C. (1990). Geographic Information Systems and Cartographic Modeling, Esri Press."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1068\/a090727","article-title":"An Evaluation of Lattice Solutions to the Problem of Corridor Location","volume":"9","author":"Goodchild","year":"1977","journal-title":"Environ. Plan. A Econ. Space"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1061\/(ASCE)0733-947X(1985)111:2(114)","article-title":"Transmission Corridor Location Modeling","volume":"111","author":"Huber","year":"1985","journal-title":"J. Transp. Eng."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1111\/j.1467-9671.2012.01355.x","article-title":"Comparison of Different Strategies for Determining Raster-Based Least-Cost Paths with a Minimum Amount of Distortion","volume":"17","author":"Antikainen","year":"2013","journal-title":"Trans. GIS"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","article-title":"On a Routing Problem","volume":"16","author":"Bellman","year":"1958","journal-title":"Q. Appl. Math."},{"key":"ref_21","unstructured":"Ford, L.R. (1956). Network Flow Theory, RAND Corporation."},{"key":"ref_22","first-page":"596","article-title":"Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms","volume":"3","author":"Fredman","year":"1984","journal-title":"ACM"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","article-title":"Algorithm 97: Shortest Path","volume":"5","author":"Floyd","year":"1962","journal-title":"Commun. ACM"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/321105.321107","article-title":"A Theorem on Boolean Matrices","volume":"9","author":"Warshall","year":"1962","journal-title":"J. Assoc. Comput. Mach."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1090\/qam\/253822","article-title":"An Algorithm for Finding Shortest Routes from All Source Nodes to a Given Destination in General Networks","volume":"27","author":"Yen","year":"1970","journal-title":"Quart. Appl. Math"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1137\/S0097539795290477","article-title":"Finding the k Shortest Paths","volume":"28","author":"Eppstein","year":"1999","journal-title":"SIAM J. Comput."},{"key":"ref_27","first-page":"113","article-title":"The Disjoint Shortest Paths Problem","volume":"85","year":"1998","journal-title":"Discret. Appl. Math. J. Comb. Algorithms Inform. Comput. Sci."},{"key":"ref_28","first-page":"125","article-title":"Disjoint Paths in a Network","volume":"4","author":"Suurballe","year":"1974","journal-title":"Netw. Int. J."},{"key":"ref_29","unstructured":"Alvarado, A., and Mitchell, J. (2015). Wiley Encyclopedia of Electrical and Electronics Engineering, Wiley."},{"key":"ref_30","unstructured":"de Sousa, A., Santos, D., and Monteiro, P. (2017, January 8\u201310). Determination of the Minimum Cost Pair of D-Geodiverse Paths. Proceedings of the DRCN 2017\u2014Design of Reliable Communication Networks, 13th International Conference, Munich, Germany."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Almeida, J.P., Alvelos, F.P.E., Cerdeira, J.O., Moniz, S., and Requejo, C. (2022, January 6\u20138). Implementation of Geographic Diversity in Resilient Telecommunication Networks. Proceedings of the Operational Research, \u00c9vora, Portugal.","DOI":"10.1007\/978-3-031-46439-3"},{"key":"ref_32","unstructured":"Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. (1993). Network Flows: Theory, Algorithms, and Applications, Prentice Hall."},{"key":"ref_33","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Saito, N., and Nishizeki, T. (1981). Graph Theory and Algorithms: 17th Symposium of Research Institute of Electrical Communication, Tohoku University, Sendai, Japan, 24\u201325 October 1980, 1980 Proceedings, Springer.","DOI":"10.1007\/3-540-10704-5"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Shepard, D. (1968, January 27\u201329). A two-dimensional Interpolation Function for Irregularly-spaced Data. Proceedings of the 1968 23rd ACM National Conference, New York, NY, USA.","DOI":"10.1145\/800186.810616"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1292","DOI":"10.1016\/j.cageo.2010.03.012","article-title":"Accelerating POCS Interpolation of 3D Irregular Seismic Data with Graphics Processing Units","volume":"36","author":"Wang","year":"2010","journal-title":"Comput. Geosci."},{"key":"ref_37","unstructured":"Varady, T., and Martin, R. (2002). The Handbook of Computer-Aided Geometric Design, Elsevier."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/s10107-002-0347-5","article-title":"Solving Semidefinite-Quadratic-Linear Programs Using SDPT3","volume":"95","author":"Toh","year":"2003","journal-title":"Math. Program. Ser. B"},{"key":"ref_39","unstructured":"Jha, A. (2023, December 01). Disjoint_SPfinder. Available online: https:\/\/github.com\/jha-amit\/Disjoint_SPfinder."}],"container-title":["Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-8954\/12\/4\/117\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:21:47Z","timestamp":1760106107000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-8954\/12\/4\/117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,31]]},"references-count":39,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2024,4]]}},"alternative-id":["systems12040117"],"URL":"https:\/\/doi.org\/10.3390\/systems12040117","relation":{},"ISSN":["2079-8954"],"issn-type":[{"type":"electronic","value":"2079-8954"}],"subject":[],"published":{"date-parts":[[2024,3,31]]}}}