A stochastic programming approach for transportation network protection.

摘要

Finding effective strategies of allocating limited mitigation resources to critical infrastructure system components for protection, response, and recovery is among the central tasks of disaster mitigation and management. This dissertation tackles the pre-disaster network protection problem, a specific instance of the above general resource allocation problem, of determining which network components should be protected (e.g. retrofitted or strengthened) before disasters given resource constraints. The most prominent feature of this problem is decision making under uncertainty since disasters are not realized yet and hence uncertain at the time of making protection decisions. A popular method for dealing with uncertainty in the practice of disaster mitigation is scenario analysis. System cost is evaluated under each disaster scenario and scenario dependent policies may be generated. One then can aggregate these scenario dependent policies into an implementable policy or simply take the policy from the most likely scenario. This scenario analysis approach has little possibility to ensure an optimal policy in the sense of optimizing mathematically well defined system measures (e.g. expected loss from disasters).;This dissertation develops a rigorous approach based on stochastic programming and network optimization with the capability of capturing system component interdependency and explicitly incorporating uncertainty. We study two variants of the network protection problem with different assumptions of network flows. Firstly assuming network flows are completely controllable to achieve system optimum (SO), we formulate the problem as a two-stage risk averse stochastic program with nonlinear recourse and binary variables in the first stage, which seeks a balance between minimizing expected system cost and reducing system cost variation. An efficient algorithm is designed via extending the well-known L-shaped method. Numerical experiment results demonstrate the superiority of the stochastic programming approach to the engineering method. Secondly assuming network flows are in the user equilibrium (UE) condition, we formulate the problem as a stochastic mathematical program with complementarity constraints (SMPCC), which is hard to solve due to its non-convexity and non-smoothness. The Progressive Hedging (PH) method is employed to solve the SMPCC, which iterates between the process of solving scenario (perturbed) subproblems and aggregating scenario solutions into an implementable policy. Each scenario subproblem, a mathematical program with complementarity constraints (MPCC), is solved via a relaxation approach.