Hierarchical Approach for Survivable Network Design

A central design challenge facing network planners is how to select a cost-effective network configuration that can provide uninterrupted service despite edge failures. In this paper, we study the Survivable Network Design (SND) problem, a core model underlying the design of such resilient networks that incorporates complex cost and connectivity trade-offs. Given an undirected graph with specified edge costs and (integer) connectivity requirements between pairs of nodes, the SND problem seeks the minimum cost set of edges that interconnects each node pair with at least as many edge-disjoint paths as the connectivity requirement of the nodes. We develop a hierarchical approach for solving the problem that integrates ideas from decomposition, tabu search, randomization, and optimization. The approach decomposes the SND problem into two subproblems, Backbone design and Access design, and uses an iterative multi-stage method for solving the SND problem in a hierarchical fashion. Since both subproblems are NP-hard, we develop effective optimization-based tabu search strategies that balance intensification and diversification to identify near-optimal solutions. To initiate this method, we develop two heuristic procedures that can yield good starting points. We test the combined approach on large-scale SND instances, and empirically assess the quality of the solutions vis-à-vis optimal values or lower bounds. On average, our hierarchical solution approach generates solutions within 2.7% of optimality even for very large problems (that cannot be solved using exact methods), and our results demonstrate that the performance of the method is robust for a variety of problems with different size and connectivity characteristics.

Transport of Hydraulic Fracturing Water and Wastes in the Susquehanna River Basin, Pennsylvania

The development of the Marcellus Shale gas play in Pennsylvania and the northeastern United States has resulted in significant amounts of water and wastes transported by truck over roadways. This study used geographic information systems (GIS) to quantify truck travel distances via both the preferred routes (minimum distance while also favoring higher-order roads) as well as, where available, the likely actual distances for freshwater and waste transport between pertinent locations (e. g., gas wells, treatment facilities, freshwater sources). Results show that truck travel distances in the Susquehanna River Basin are greater than those used in prior life-cycle assessments of tight shale gas. When compared to likely actual transport distances, if policies were instituted to constrain truck travel to the closest destination and higher-order roads, transport mileage reductions of 40-80% could be realized. Using reasonable assumptions of current practices, greenhouse gas (GHG) emissions associated with water and waste hauling were calculated to be 70-157 MT CO2 eq per gas well. Furthermore, empty so-called backhaul trips, such as to freshwater withdrawal sites or returning from deep well injection sites, were found to increase emissions by an additional 30%, underscoring the importance of including return trips in the analysis. The results should inform future life-cycle assessments of tight shale gases in managed watersheds and help local and regional governments plan for impacts of transportation on local infrastructure. (C) 2013 American Society of Civil Engineers.