Zinchenko, YuriyJha, Amit2022-09-282022-09-282022-09Jha, A. (2022). Web-enabled software platform for identification of minimum-cost power transmission lines with redundancy constraints (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.http://hdl.handle.net/1880/115320https://dx.doi.org/10.11575/PRISM/40326Path redundancy is essential for safety and reliability in many real-world routing problems, such as the design of networks for power transmission or oil transportation. These problems typically involve finding the shortest path on a weighted graph. Instead, in the shortest path with constrained path redundancy, two disjoint shortest paths are desired, such that the combined weight of the two paths is minimized and a minimum physical path separation is maintained. Finding two disjoint shortest paths subject to constraints on a graph is generally an NP-hard problem. Conventionally, the task of planning for a redundant transmission line requires a large-scale graph and a mixed integer programming (MIP) formulation of the problem. However, due to the the large model dimension MIP is practically intractable. To overcome the intractability, a new 3D embedding scheme has been proposed by [18], which allows avoiding many common pitfalls of available heuristic approaches, while maintaining a modest computation time requirement. To enable this scheme, we developed a software package containing (1) an optimized implementation of a 3D embedding scheme and algorithms which uses it for the identification of disjoint shortest paths with separation constraint on a graph, and (2) a graphical user interface that allows user inputs as well as visualization of the solution on Google Maps. We deployed this software on cloud.engUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.Disjoint two shortest pathsBezier surface InterpolationPower transmission line routingWeb-applicationEducation--Mathematicsmaster thesis