Browsing by Author "Jha, Amit"

Now showing 1 - 1 of 1
  • Thumbnail Image
    ItemOpen Access
    WEB-ENABLED SOFTWARE PLATFORM FOR IDENTIFICATION OF MINIMUM-COST POWER TRANSMISSION LINES WITH REDUNDANCY CONSTRAINTS
    (2022-09) Jha, Amit; Zinchenko, Yuriy; Greenberg, Matthew; Ware, Antony
    Path 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.