Corridor location for the design of new transmission infrastructure is a complicated problem, made difficult by the need to simultaneously consider numerous competing factors. Additionally, if a public agency or utility cannot guarantee that virtually all alternative routes have been considered, the publics’ distrust will remain. As a result, the planning process often degenerates into a struggle between the applicant, regulatory authorities, concerned stakeholders, and the public. Thus, there is a critical need for improved and credible analytical approaches for determining virtually all alternative transmission corridor pathways and a system to display, measure, and compare any proposals (raised in good faith or otherwise) in real time in a public setting. One approach to address these issues is to solve a bi-objective shortest path (BSP) problem, which can be used to find the set of all paths that represent the optimal trade-off between two specified objectives. Finding the complete set of these solutions though represents an NP-Hard problem, making it computationally difficult. We will discuss a new heuristic to efficiently compute a tight upper bound solution set on the BSP, and explain how this can be used for a faster exact algorithm. We will also expand on how this method can be parallelized to take advantage of high performance computing resources.