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.

Identifying Resiliency Performance Measures for Megaregional Planning Case Study of the Transportation Corridor Between Boston, Massachusetts, and Washington, DC

Transportation corridors in megaregions present a unique challenge for planners because of the high concentration of development, complex interjurisdictional issues, and history of independent development of core urban centers. The concept of resilience, as applied to megaregions, can be used to understand better the performance of these corridors. Resiliency is the ability to recover from or adjust easily to change. Resiliency performance measures can be expanded on for application to megaregions throughout the United States. When applied to transportation corridors in megaregions and represented by performance measures such as redundancy, continuity, connectivity, and travel time reliability, the concept of resiliency captures the spatial and temporal relationships between the attributes of a corridor, a network, and neighboring facilities over time at the regional and local levels. This paper focuses on the development of performance measurements for evaluating corridor resiliency as well as a plan for implementing analysis methods at the jurisdictional level. The transportation corridor between Boston, Massachusetts, and Washington, D.C., is used as a case study to represent the applicability of these measures to megaregions throughout the country.