Capacity planning and management for mesh survivable networks under demand uncertainty

This thesis presents a set of optimization-based strategies to assist network planners and operations support engineers in planning and managing the capacities of mesh-based survivable transport networks in the face of demand uncertainty. While there have been many works on network design, consideration of demand uncertainty into network design models has remained one of the least explored areas. The extent of uncertainty in planning problems in general has been already classified by others as follows: Level I: A Clear-Enough Future, Level II: Alternative Futures, Level III: A Range of Futures and IV: True Ambiguity. We have followed this schema and propose a set of new optimization models for the three levels where uncertainties are more pronounced: (1) For Level II: A two-part, stochastic programming-based optimization model is developed for incorporating demand uncertainty and network survivability into a single capacity-planning formulation. While almost all published studies on the design of survivable networks are based on a specific demand forecast (i.e. Level I) and optimize capacity cost for a single target planning view, the two-part formulation explicitly incorporates a set of plausible demand scenarios and optimizes both present and future long-term capacity investment. We also extend the two-part formulation to capture the modularity and economy-of-scale effects and show significant capacity cost savings of the new models over traditional single-forecast design methods. (2) For Level III: A framework, based on the concepts of Pattern Forecast Accuracy (PFA) and Servability, is designed for assessing the robustness of the ability of various survivable networks to cope with uncertainty in the demand forecast. This framework serves as an evaluation tool for network operators to effectively identify robust survivable network designs from any given sets of cost-optimal designs. (3) For Level IV: We develop two operational strategies, namely, max-profit demand loading and re-optimization strategies, for managing as-built capacities of any mesh survivable transport networks. The value of the demand loading formulation is to help service providers to identify and route a set of demands that could generate the maximum profit, taking the provisioning cost and service revenue into consideration. Multiple quality-of-protection (multi-QoP) service classes (i.e. protected, unprotected and preemptible classes) are also considered in the demand loading formulation. As another valuable tool for network operators, re-optimization strategy is used to improve a network's ability to carry future traffic, through rearranging solely the existing spare capacities or with the latitude of also rearranging in-service paths.; With the fact that the expenditure on transport capacity is in the order of millions and even billions of dollars, the potential capital savings from these optimization models can be substantial.